莫队算法二（树上莫队cot2，Haruna’s Breakfast）
包永新
例一：不带修改
| Time Limit: 1207MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
Description
You are given a tree with N nodes. The tree nodes are numbered from 1 to N. Each node has an integer weight.
We will ask you to perform the following operation:
- u v : ask for how many different integers that represent the weight of nodes there are on the path from u to v.
Input
In the first line there are two integers N and M. (N <= 40000, M <= 100000)
In the second line there are N integers. The i-th integer denotes the weight of the i-th node.
In the next N-1 lines, each line contains two integers u v, which describes an edge (u, v).
In the next M lines, each line contains two integers u v, which means an operation asking for how many different integers that represent the weight of nodes there are on the path from u to v.
Output
For each operation, print its result.
Example
Input: 8 2 105 2 9 3 8 5 7 7 1 2 1 3 1 4 3 5 3 6 3 7 4 8 2 5 7 8
Output: 4 4
题目链接：http://acm.hust.edu.cn/vjudge/problem/27636
学习参考博客：http://blog.csdn.net/kuribohg/article/details/41458639
理解：我们要在树上使用莫队算法，首先需要将树上的装换成普通的序列，这里我们用到了dfs序。用in和out表示遍历是的时间顺序。然后把这个当作下标排序，分块。在处理转移问题是我们用inv来表示当前访问节点是否在当前区间里，然后根据上面的博客原理异或即可。处理lca的问题我们用倍增法求lca。
注意：w的权重需要离散化，lst存的是dfs序对应的节点（数组为N的两倍）。
AC：
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<string.h>
#include<cstring>
#include<vector>
#include<queue>
#include<stdio.h>
using namespace std;
#define ll long long int
const int N=40008,M=100008;
int w[N],hd[N],to[N],dep[N],in[N],out[N],lst[N<<1],ans[M],pre[18][N],inv[N],v[N];
int num,uin,tot,n,m,res;
struct ss
{
int id,v;
bool operator < (const ss &a)const
{
return v<a.v;
}
}ww[N];
struct G
{
int v,next;
}mp[N<<1];
struct query
{
int l,r,id,anc;
bool operator <(const query &a) const
{
if(l/uin==a.l/uin) return r<a.r;
else return l/uin<a.l/uin;
}
}q[M];//查询
void add(int u,int v)//建树
{
mp[++tot].next=hd[u];
mp[tot].v=v;
hd[u]=tot;
}
void dfs(int now,int h)//求dfs序，顺便保存公共祖先
{
dep[now]=h;
in[now]=++num;
lst[num]=now;
for(int k=hd[now];k;k=mp[k].next)
{
if(!dep[mp[k].v])
{
dfs(mp[k].v,h+1);
pre[0][mp[k].v]=now;
}
}
out[now]=++num;
lst[num]=now;
}
void lca_init()//pre[i][j]表示j节点的第2^(i)个父亲
{
for (int i=1;i<=16;i++)
for (int j=1;j<=n;j++)
pre[i][j]=pre[i-1][pre[i-1][j]];
}
int lca(int u,int v)//倍增法求lca
{
int d;
if(dep[u]<dep[v]) swap(u,v);
d=dep[u]-dep[v];
for(int i=16;i>=0;i--)
{
if(d&(1<<i)) u=pre[i][u];
}//是u，v的深度相同
if(u==v) return u;
for(int i=16;i>=0;i--)
{
if(pre[i][u]!=pre[i][v])
{
u=pre[i][u],v=pre[i][v];
}
}
return pre[0][u];
}
void solve(int i)//转移状态
{
if(inv[lst[i]])
{
v[w[lst[i]]]--;
if(!v[w[lst[i]]]) res--;
inv[lst[i]]=0;
}
else
{
if(!v[w[lst[i]]]) res++;
v[w[lst[i]]]++;
inv[lst[i]]=1;
}
}
int main()
{
int x,y;
//freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
{
scanf("%d",&ww[i].v);
ww[i].id=i+1;
}
sort(ww,ww+n);
int tmp=0;
w[ww[0].id]=0;
for(int i=1;i<n;i++)
{
if(ww[i].v>ww[i-1].v) tmp++;
w[ww[i].id]=tmp;
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1,1);
pre[0][1]=1;
lca_init();
for(int i=0;i<m;i++)
{
scanf("%d%d",&x,&y);
q[i].id=i;
if(x==y) q[i].anc=-1;
else
{
q[i].anc=lca(x,y);
if(q[i].anc!=x&&q[i].anc!=y)
{
q[i].l=min(out[x],out[y]);
q[i].r=max(in[x],in[y]);
}
else
{
q[i].l=min(in[x],in[y]);
q[i].r=max(in[x],in[y]);
}
}
}
uin=(int)sqrt(m*1.0);
sort(q,q+m);
int l,r;
l=1; r=0;
for(int i=0;i<m;i++)
{
if(q[i].anc==-1)
{
ans[q[i].id]=1;
continue;
}
while(l<q[i].l)
{
solve(l);
l++;
}
while(l>q[i].l)
{
l--;
solve(l);
}
while(r>q[i].r)
{
solve(r);
r--;
}
while(r<q[i].r)
{
r++;
solve(r);
}
if(lst[q[i].l]==q[i].anc||lst[q[i].r]==q[i].anc)
{
ans[q[i].id]=res;
}
else
{
solve(in[q[i].anc]);
ans[q[i].id]=res;
solve(in[q[i].anc]);
}
}
for(int i=0;i<m ;i++)
{
printf("%d\n",ans[i]);
}
}例二：带修改
| Time Limit: 10000MS | Memory Limit: 131072KB | 64bit IO Format: %lld & %llu |
Description
Haruna每天都会给提督做早餐！ 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵
树上，每个结点都有一样食材，Shimakaze要考验一下她。
每个食材都有一个美味度，Shimakaze会进行两种操作：
1、修改某个结点的食材的美味度。
2、对于某条链，询问这条链的美味度集合中，最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。
Input
第一行包括两个整数n，m，代表树上的结点数(标号为1~n)和操作数。
第二行包括n个整数a1...an，代表每个结点的食材初始的美味度。
接下来n-1行，每行包括两个整数u，v，代表树上的一条边。
接下来m 行，每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u，v 为端点的链的mex值。
Output
对于每次询问，输出该链的mex值。
Sample Input
10 10 1 0 1 0 2 4 4 0 1 0 1 2 2 3 2 4 2 5 1 6 6 7 2 8 3 9 9 10 0 7 14 1 6 6 0 4 9 1 2 2 1 1 8 1 8 3 0 10 9 1 3 5 0 10 0 0 7 7
Sample Output
0 1 2 2 3
Hint
1<=n<=5*10^4
1<=m<=5*10^4
0<=ai<=10^9
解法：对于对点的权值存在修改，然后我们排序的时候增加一维，操作时间。对于询问区间时，我们可以先把点的权值转移到t的状态然后再跑一次普通的树上莫队。
注意：由于题目要求的是mex，我们只需要记录出现的权值即可。mex肯定在（0~n）之间，所以对于出现过大于n的权重我们可以跳过即可。ps：之前没发现这个，用map映射被一个lg卡到崩溃。。。。。。。
AC：
#include<iostream>
#include<string>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
using namespace std;
#define LL long long
#define INF 0x3f7f7f7f3f7f7f7f
const int maxn=100008;
const int K=16;
int hd[maxn],lst[maxn<<1],in[maxn],out[maxn],pre[20][maxn],dep[maxn],num,tot,unit,res;
int cc[maxn],uu[maxn],to[maxn],last[maxn],c[maxn],inv[maxn],vis[maxn],ans[maxn];
int v[maxn];
int n,m;
int mex()
{
for(int i=0;;i++)
{
if(!v[i]) return i;
}
}
struct query
{
int l,r,anc,id,ti;
bool operator < (const query &b) const
{
if(l/unit==b.l/unit)
{
return r==b.r? ti<b.ti:r<b.r;
}
else return l/unit<b.l/unit;
}
}q[maxn];
struct G
{
int next,v;
}mp[maxn<<1];
void add(int u,int v)
{
mp[++tot].v=v;
mp[tot].next=hd[u];
hd[u]=tot;
}
void dfs(int now,int h)
{
dep[now]=h;
in[now]=++num;
lst[num]=now;
for(int k=hd[now];k;k=mp[k].next)
{
if(!dep[mp[k].v])
{
dfs(mp[k].v,h+1);
pre[0][mp[k].v]=now;
}
}
out[now]=++num;
lst[num]=now;
}
void lca_init()
{
for(int i=1;i<=K;i++)
{
for(int j=1;j<=n;j++)
{
pre[i][j]=pre[i-1][pre[i-1][j]];
}
}
}
int lca(int u,int v)
{
if(dep[u]<dep[v]) swap(u,v);
int d=dep[u]-dep[v];
for(int i=K;i>=0;i--)
{
if(d&(1<<i))
{
u=pre[i][u];
}
}
if(u==v) return u;
for(int i=K;i>=0;i--)
{
if(pre[i][u]^pre[i][v])
{
u=pre[i][u];
v=pre[i][v];
}
}
return pre[0][u];
}
void solve(int i)//莫队转移
{
if (inv[lst[i]])
{
inv[lst[i]]=0;
if(c[lst[i]]>n) return ;
v[c[lst[i]]]--;
}
else
{
inv[lst[i]]=1;
if(c[lst[i]]>n) return ;
v[c[lst[i]]]++;
}
}
void chage(int t)//转移时间状态
{
if(vis[t])
{
vis[t]=0;
if(inv[uu[t]]&&c[uu[t]]<n)
{
v[c[uu[t]]]--;
}
c[uu[t]]=last[t];
if(inv[uu[t]]&&c[uu[t]]<n)
{
v[c[uu[t]]]++;
}
}
else
{
vis[t]=1;
if(inv[uu[t]]&&c[uu[t]]<n)
{
v[c[uu[t]]]--;
}
c[uu[t]]=to[t];
if(inv[uu[t]]&&c[uu[t]]<n)
{
v[c[uu[t]]]++;
}
}
}
struct FastIO
{
static const int S = 1310720;
int wpos;
char wbuf[S];
FastIO() : wpos(0) {}
inline int xchar()
{
static char buf[S];
static int len = 0, pos = 0;
if(pos == len)
pos = 0, len = fread(buf, 1, S, stdin);
if(pos == len) return -1;
return buf[pos ++];
}
inline int xuint()
{
int c = xchar(), x = 0;
while(c <= 32)
{
c = xchar();
}
for(; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
return x;
}
inline void wchar(int x)
{
if(wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
wbuf[wpos ++] = x;
}
inline void wint(int x)
{
if(x < 0) wchar('-'), x = -x;
char s[24];
int n = 0;
while(x || !n) s[n ++] = '0' + x % 10, x /= 10;
while(n--) wchar(s[n]);
}
~FastIO()
{
if(wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
}
} io;//输入外挂
int main()
{
//freopen("in.txt","r",stdin);
n=io.xuint();
m=io.xuint();
int u,v,len1,pos1,time;
len1=time=0;
for(int i=1;i<=n;i++)
{
c[i]=io.xuint();
cc[i]=c[i];
}
for(int i=1;i<n;i++)
{
u=io.xuint();
v=io.xuint();
add(u,v);
add(v,u);
}
pre[0][1]=1;
dfs(1,1);
lca_init();
unit=(int)sqrt(num*1.0);
for(int i=0;i<m;i++)
{
pos1=io.xuint();
u=io.xuint();
v=io.xuint();
if(pos1==1)
{
q[len1].anc=lca(u,v);
q[len1].ti=time;
q[len1].id=len1;
q[len1].anc=lca(u,v);
if (q[len1].anc!=u&&q[len1].anc!=v)
{
q[len1].l=min(out[u],out[v]);
q[len1].r=max(in[u],in[v]);
}
else
{
q[len1].l=min(in[u],in[v]);
q[len1].r=max(in[u],in[v]);
}
len1++;
}
else
{
uu[++time]=u;
to[time]=v;
last[time]=cc[u];
cc[u]=v;
}
}
sort(q,q+len1);
int l=1,r=0,t=0;
for(int i=0;i<len1;i++)
{
while(t<q[i].ti) chage(t+1),t++;
while(t>q[i].ti)chage(t),t--;
for (;l<q[i].l;l++) solve(l);
for (;q[i].l<l;l--) solve(l-1);
for (;r<q[i].r;r++) solve(r+1);
for (;q[i].r<r;r--) solve(r);
if (lst[q[i].l]==q[i].anc||lst[q[i].r]==q[i].anc)
ans[q[i].id]=mex();
else
{
solve(in[q[i].anc]);
ans[q[i].id]=mex();
solve(in[q[i].anc]);
}
}
for(int i=0;i<len1;i++)
{
io.wint(ans[i]);
io.wchar('\n');
}
}
类似资料：