https://cn.vjudge.net/problem/SPOJ-COT2

这个是树上莫队模版啊。。

树上莫队有两种，第一种就是括号序莫队

设节点i在括号序中首次出现位置为pl[i]

那么路径(i,j)上的节点，相当于括号序中pl[i]到pl[j]中所有只出现1次的节点，可能还要加上i,j,lca(i,j)

更精确的描述：https://blog.csdn.net/xianhaoming/article/details/52201761

这样很容易用序列莫队+lca(i,j),i,j的特判解决

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pi;

 int n,m;

 int a[];

 vector<int> e[];

 struct Q

 {

     int x,y,n;

 }q[];

 int sz=;

 int d[],pl[],bl[];

 bool vis[];

 int ans[],num[],an;

 int t1[];

 int anc[][],dep[],l2n=;

 map<int,int> ma;

 void dfs(int u,int fa)

 {

     int i;

     d[++d[]]=u;pl[u]=d[];

     anc[u][]=fa;

     dep[u]=dep[fa]+;

     for(i=;i<=l2n;i++)

         anc[u][i]=anc[anc[u][i-]][i-];

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

     d[++d[]]=u;

 }

 int lca(int x,int y)

 {

     int t,i;

     if(dep[x]<dep[y]){t=x;x=y;y=t;}

     for(t=dep[x]-dep[y],i=;t>;t>>=,i++)

         if(t&)    x=anc[x][i];

     if(x==y)    return x;

     for(i=l2n;i>=;i--)

         if(anc[x][i]!=anc[y][i])

         {

             x=anc[x][i];

             y=anc[y][i];

         }

     return anc[x][];

 }

 bool operator<(const Q &a,const Q &b)

 {

     return bl[a.x]==bl[b.x]?a.y<b.y:a.x<b.x;

 }

 void change(int u)

 {

     if(vis[u])

     {

         num[a[u]]--;

         if(num[a[u]]==)    an--;

         vis[u]=;

     }

     else

     {

         if(num[a[u]]==)    an++;

         num[a[u]]++;

         vis[u]=;

     }

 }

 int main()

 {

     int i,u,v;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;i++)    scanf("%d",&a[i]),t1[++t1[]]=a[i];

     sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;

     for(i=;i<=t1[];i++)    ma[t1[i]]=i;

     for(i=;i<=n;i++)    a[i]=ma[a[i]];

     //for(i=1;i<=n;i++)    printf("a%d %d\n",i,a[i]);

     for(i=;i<n;i++)

     {

         scanf("%d%d",&u,&v);

         e[u].pb(v);e[v].pb(u);

     }

     dfs(,);

     for(i=;i<=m;i++)

     {

         scanf("%d%d",&q[i].x,&q[i].y);

         q[i].x=pl[q[i].x];q[i].y=pl[q[i].y];

         if(q[i].x>q[i].y)    swap(q[i].x,q[i].y);

         q[i].n=i;

     }

     //putchar('a');

     //for(i=1;i<=d[0];i++)    printf("%d ",d[i]);

     //puts("");

     for(i=;i<=d[];i++)    bl[i]=(i-)/sz;

     sort(q+,q+m+);

     int l=,r=;

     for(i=;i<=m;i++)

     {

         while(l>q[i].x)    change(d[--l]);

         while(r<q[i].y)    change(d[++r]);

         while(l<q[i].x)    change(d[l++]);

         while(r>q[i].y)    change(d[r--]);

         bool fl1=vis[d[q[i].x]],fl2=vis[d[q[i].y]];

         int ll=lca(d[q[i].x],d[q[i].y]);

         bool fl3=vis[ll];

         //printf("b%d %d %d %d %d %d\n",q[i].x,q[i].y,ll,fl1,fl2,fl3);

         if(!fl1)    change(d[q[i].x]);

         if(!fl2)    change(d[q[i].y]);

         if(!fl3)    change(ll);

         ans[q[i].n]=an;

         if(!fl1)    change(d[q[i].x]);

         if(!fl2)    change(d[q[i].y]);

         if(!fl3)    change(ll);

     }

     for(i=;i<=m;i++)    printf("%d\n",ans[i]);

     return ;

 }

还有一种是树分块后直接做莫队

树分块的方法很多，按我自己的理解，此时可行的分块方法要求块内部任意两点间距离不超过根号级别，且各个块按照“块树”的dfs序排列（由这个顺序得到块编号）（不确定）

这样子的话，将所有询问以左端点的块编号为第一关键字，右端点的块编号为第二关键字，排序所有询问，

每一次转移的时候，两个端点都变了，但是可以当成一个端点一个端点的变；从(u,v1)的答案变到(u,v2)的答案，就是除了以u为根时lca(v1,v2)以外，对(v1,v2)的路径上所有点的“是否在当前答案中”属性取反（划掉的东西我不会证也不想维护）

根据一些证明，只要首先丢掉每个询问的两个端点的lca（处理这个询问时临时加上就行了），那么从(u,v1)变到(u,v2)，只要对(v1,v2)路径上所有点(除了lca)的“是否在当前答案中”属性取反就行了

证明：https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html

树分块方法：

（对于方法：如果某个节点父亲所在的块加上自己所在的块大小没超过K(指定的最大块大小)，那么将这两个块合并（一般K就取sqrt(n)）

能保证块大小，不能保证块数。。。

听说菊花图能卡掉。。。然而想了很久，也没想出来什么样的菊花图能卡掉这个方法的树上莫队

算了，还是不用了）

1.王室联邦分块

https://www.lydsy.com/JudgeOnline/problem.php?id=1086

做法：https://www.cnblogs.com/shenben/p/6368457.html

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,sz;

 vector<int> e[];

 int st[],tp,rt[],cnt,bl[];

 void dfs(int u,int fa)

 {

     int i,ltp=tp;

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

         {

             dfs(e[u][i],u);

             if(tp-ltp>=sz)

             {

                 rt[++cnt]=u;

                 while(tp!=ltp)    bl[st[tp--]]=cnt;

             }

         }

     st[++tp]=u;

 }

 int main()

 {

     int i,a,b;

     scanf("%d%d",&n,&sz);

     for(i=;i<n;i++)

     {

         scanf("%d%d",&a,&b);

         e[a].pb(b);e[b].pb(a);

     }

     dfs(,);

     while(tp)    bl[st[tp--]]=cnt;

     printf("%d\n",cnt);

     for(i=;i<=n;i++)    printf("%d ",bl[i]);

     puts("");

     for(i=;i<=cnt;i++)    printf("%d ",rt[i]);

     return ;

 }
 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 #include<cmath>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,sz,m;

 vector<int> e[];

 int st[],tp,rt[],cnt,bl[];

 int dd[];

 struct Q

 {

     int x,y,n;

 }q[];

 void dfs(int u,int fa)

 {

     int i,ltp=tp;

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

         {

             dfs(e[u][i],u);

             if(tp-ltp>=sz)

             {

                 rt[++cnt]=u;

                 while(tp!=ltp)    bl[st[tp--]]=cnt;

             }

         }

     st[++tp]=u;

 }

 bool operator<(const Q &a,const Q &b)

 {

     return bl[a.x]==bl[b.x]?bl[a.y]<bl[b.y]:bl[a.x]<bl[b.x];

 }

 int num[],an;

 bool vis[];

 void change(int u)

 {

     if(vis[u])

     {

         num[dd[u]]--;

         if(num[dd[u]]==)    an--;

         vis[u]=;

     }

     else

     {

         if(num[dd[u]]==)    an++;

         num[dd[u]]++;

         vis[u]=;

     }

 }

 namespace LCA

 {

 int anc[][],dep[],l2n=;

 void dfs(int u,int fa)

 {

     int i;

     anc[u][]=fa;

     dep[u]=dep[fa]+;

     for(i=;i<=l2n;i++)

         anc[u][i]=anc[anc[u][i-]][i-];

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

 }

 int lca(int x,int y)

 {

     int t,i;

     if(dep[x]<dep[y]){t=x;x=y;y=t;}

     for(t=dep[x]-dep[y],i=;t>;t>>=,i++)

         if(t&)    x=anc[x][i];

     if(x==y)    return x;

     for(i=l2n;i>=;i--)

         if(anc[x][i]!=anc[y][i])

         {

             x=anc[x][i];

             y=anc[y][i];

         }

     return anc[x][];

 }

 void work(int x,int y)

 {

     if(dep[x]<dep[y])    swap(x,y);

     while(dep[x]>dep[y])

     {

         change(x);

         x=anc[x][];

     }

     while(x!=y)

     {

         change(x);change(y);

         x=anc[x][];y=anc[y][];

     }

 }

 }

 using LCA::work;

 using LCA::lca;

 int t1[];

 map<int,int> ma;

 int ans[];

 int main()

 {

     int i,a,b,l;

     scanf("%d%d",&n,&m);sz=sqrt(n+0.5);

     if(m==)    return ;

     for(i=;i<=n;i++)    scanf("%d",&dd[i]),t1[++t1[]]=dd[i];

     sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;

     for(i=;i<=t1[];i++)    ma[t1[i]]=i;

     for(i=;i<=n;i++)    dd[i]=ma[dd[i]];

     for(i=;i<n;i++)

     {

         scanf("%d%d",&a,&b);

         e[a].pb(b);e[b].pb(a);

     }

     dfs(,);LCA::dfs(,);

     while(tp)    bl[st[tp--]]=cnt;

     for(i=;i<=m;i++)

     {

         scanf("%d%d",&q[i].x,&q[i].y);

         q[i].n=i;

     }

     sort(q+,q+m+);

     work(q[].x,q[].y);

     l=lca(q[].x,q[].y);

     change(l);

     ans[q[].n]=an;

     change(l);

     for(i=;i<=m;i++)

     {

         work(q[i].x,q[i-].x);

         work(q[i].y,q[i-].y);

         l=lca(q[i].x,q[i].y);

         change(l);

         ans[q[i].n]=an;

         change(l);

     }

     for(i=;i<=m;i++)    printf("%d\n",ans[i]);

     return ;

 }

https://www.lydsy.com/JudgeOnline/problem.php?id=2589

加强版啊。。强制在线啊

更麻烦了，不能用莫队了

不过做过强制在线区间众数，还是有一点类似的

随便搞一个根节点（比如1），分块

处理一些东西：

fa[i]表示i的父亲

rt[i]表示i块的“块顶”

bl[i]表示i节点所属块

an1[i][j]：rt[i],rt[j]间答案（除lca(rt[i],rt[j])）

d[i][j]：rt[i]到树根的路径中权值为j的有多少个

vv[i][j]：j是否在rt[i]到根的路径上

对于询问(a,b)，

设ra=rt[bl[a]],rb=rt[bl[b]]

先得到ra,rb路径上的答案（除lca(ra,rb)）（这个答案已经预处理出来了）

然后假装你得到了两个数组tt和vis，其中tt[i]表示ra到rb的路径上（除lca），权值i出现的次数；vis[i]表示i是否在ra到rb的路径上（除lca）

（你当然没有得到这两个数组，但是设l=lca(ra,rb)，那么预处理一些东西后，这两个数组的任一个元素都可以O(1)得到）

（每一次询问时，先求出gt[i]为l到rt[bl[l]]的路径上（含l，不含rt[bl[l]]）权值i出现的次数）

（那么tt[i]=d[bl[a]][i]+d[bl[b]][i]-2*d[bl[l]][i]-2*gt[i],vis[i]=vv[bl[a]][i]^vv[bl[b]][i]）

按照莫队的方法转移就行了，最后把lca临时加上

（显然不能直接修改，要另开空数组记录修改，得到答案后把修改还原）

听说这种类型的分块（记录两块间答案的）也可以通过调整块大小支持带修复杂度n^(5/3)？以后再说

理想很美好，现实很...

我卡常失败了，本地(破机子)一个点10秒，随便找个别的机子一个点4-5秒，测了一下运算次数，大概有30亿，跟暴力差不多。。。不知道是不是写错了；在"别的机子"上，强制在线莫队大概7秒，所以应该还好吧...

调了一个下午啊，以后再说吧

试验中可能有效的卡常：

1.修改时把修改的用另一个数组记录下来，后面根据记下的信息还原（直接置0），而不是反着做一遍，还原时可以用指针

2.261行之前把bl[a],bl[b],bl[l]用单独的变量先取出来，后面直接使用

3.261行乘号改左移；快读快写

失败代码：

错误记录：

1.分块的时候要注意，最后剩下的一部分，要么加入最后一块，额外使得rt[cnt]=1，要么另开一块，使得rt[cnt]=1；跟前面不一样

2.各种dd[x],x,bl[x]不分，代码中打了注释的就是错误记录

3.一开始没考虑(以上说明中)gt的贡献

 #pragma GCC optimize(3)

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 #include<cmath>

 //#include<cassert>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,sz,m;

 vector<int> e[];

 int rt[],cnt,bl[];

 namespace GBLOCK

 {

 int st[],tp;

 void dfs(int u,int fa)

 {

     int i,ltp=tp;

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

         {

             dfs(e[u][i],u);

             if(tp-ltp>=sz)

             {

                 rt[++cnt]=u;

                 while(tp!=ltp)    bl[st[tp--]]=cnt;

             }

         }

     st[++tp]=u;

 }

 void work()

 {

     dfs(,);

     //assert(rt[cnt]==1);

     ++cnt;rt[cnt]=;

     while(tp)    bl[st[tp--]]=cnt;

 }

 }

 int dd[];

 namespace LCA

 {

 int anc[][],dep[],l2n=;

 void dfs(int u,int fa)

 {

     int i;

     anc[u][]=fa;

     dep[u]=dep[fa]+;

     for(i=;i<=l2n;i++)

         anc[u][i]=anc[anc[u][i-]][i-];

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

 }

 int lca(int x,int y)

 {

     int t,i;

     if(dep[x]<dep[y]){t=x;x=y;y=t;}

     for(t=dep[x]-dep[y],i=;t>;t>>=,i++)

         if(t&)    x=anc[x][i];

     if(x==y)    return x;

     for(i=l2n;i>=;i--)

         if(anc[x][i]!=anc[y][i])

         {

             x=anc[x][i];

             y=anc[y][i];

         }

     return anc[x][];

 }

 }

 int an1[][];

 int d[][];

 bool vv[][];

 int tt[];

 bool vis[];

 int an;

 void Change(int x)

 {

     if(!vis[x])

     {//printf("1a%d\n",x);

         tt[dd[x]]++;

         if(tt[dd[x]]==)    an++;

     }

     else

     {//printf("1b%d\n",x);

         tt[dd[x]]--;

         if(tt[dd[x]]==)    an--;

     }

     vis[x]^=;

 }

 using LCA::lca;

 using LCA::anc;

 using LCA::dep;

 #define CLR(x) memset(x,0,sizeof(x))

 namespace PRE

 {

 vector<int> rts[];

 int s;

 void dfs1(int u,int fa)

 {

     int i;

     tt[dd[u]]++;vis[u]=;

     for(i=;i<rts[u].size();i++)

     {

         memcpy(d[rts[u][i]],tt,sizeof(tt));

         memcpy(vv[rts[u][i]],vis,sizeof(vis));

     }

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs1(e[u][i],u);

     tt[dd[u]]--;vis[u]=;

 }

 void dfs2(int u,int fa)

 {

     int i;

     Change(u);

     int l=lca(rt[s],u);

     Change(l);

     for(i=;i<rts[u].size();i++)

         an1[s][rts[u][i]]=an;

     Change(l);

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs2(e[u][i],u);

     Change(u);

 }

 void work()

 {

     int i;

     for(i=;i<=cnt;i++)    rts[rt[i]].pb(i);

     dfs1(,);

     for(i=;i<=cnt;i++)

     {

         s=i;

         dfs2(rt[s],);

     }

 }

 }

 int t1[];

 map<int,int> ma;

 int main()

 {

     //freopen("/tmp/2589/3.in","r",stdin);

     //freopen("/tmp/2589/3.ans","w",stdout);

     //auto ff=fopen("/tmp/2589/1.in","r");

     //auto ff=fopen("t1.txt","r");

     //#define scanf(...) fscanf(ff,__VA_ARGS__)

     int i,a,b,l,x,y,ra,rb,lans=;

     scanf("%d%d",&n,&m);sz=;//

     for(i=;i<=n;i++)    scanf("%d",&dd[i]),t1[++t1[]]=dd[i];

     sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;

     for(i=;i<=t1[];i++)    ma[t1[i]]=i;

     for(i=;i<=n;i++)    dd[i]=ma[dd[i]];

     for(i=;i<n;i++)

     {

         scanf("%d%d",&a,&b);

         e[a].pb(b);e[b].pb(a);

     }

     GBLOCK::work();LCA::dfs(,);

     PRE::work();

     //#undef scanf

 /*

     #undef scanf

     putchar('a');

     for(i=1;i<=n;i++)    printf("%d ",bl[i]);

     puts("");

     //scanf("%d",new int);

     puts("b");

     for(i=1;i<=cnt;i++)

     {

         for(int j=1;j<=cnt;j++)

         {

             printf("%d ",an1[i][j]);

         }

         puts("");

     }

     //scanf("%d",new int);

     putchar('c');

     for(i=1;i<=cnt;i++)    printf("%d ",rt[i]);

     puts("");

     //scanf("%d",new int);

     putchar('d');

     for(i=1;i<=n;i++)    printf("%d ",tt[i]);

     puts("");

     putchar('e');

     for(i=1;i<=n;i++)    printf("%d ",vis[i]);

     puts("");

     putchar('f');

     for(i=1;i<=cnt;i++)

     {

         for(int j=1;j<=n;j++)

         {

             printf("%d$%d ",vv[i][j],d[i][j]);

         }

         puts("");

     }

 */

 /*

 {

     int x=187,y=rt[bl[187]];

     if(dep[x]<dep[y])    swap(x,y);

     while(dep[x]>dep[y])

     {

         printf("n%d\n",x);

         x=anc[x][0];

     }

     //assert(x==y);

     while(x!=y){

     printf("ttt%d %d %d %d\n",x,y,dep[x],dep[y]);

     x=anc[x][0];y=anc[y][0];

     }

     printf("ttt%d %d %d %d\n",x,y,dep[x],dep[y]);

 }

 */

     for(i=;i<=m;i++)

     {

         scanf("%d%d",&a,&b);a^=lans;

         if(bl[a]==bl[b])

         {

             an=;

             x=a;y=b;

             if(dep[x]<dep[y])    swap(x,y);

             while(dep[x]>dep[y])

             {

                 Change(x);

                 x=anc[x][];

             }

             while(x!=y)

             {

                 Change(x);Change(y);

                 x=anc[x][];y=anc[y][];

             }

             Change(x);

             lans=an;

             Change(x);

             //printf("c%d %d\n",a,b);

             x=a;y=b;

             if(dep[x]<dep[y])    swap(x,y);

             while(dep[x]>dep[y])

             {

                 Change(x);

                 x=anc[x][];

             }

             while(x!=y)

             {

                 Change(x);Change(y);

                 x=anc[x][];y=anc[y][];

             }

         }

         else

         {

             ra=rt[bl[a]];rb=rt[bl[b]];

             l=lca(ra,rb);

             #define GD(i) (tt[i]+d[bl[a]][i]+d[bl[b]][i]-2*d[bl[l]][i])//

             #define GV(i) (vis[i]^vv[bl[a]][i]^vv[bl[b]][i])

             an=an1[bl[a]][bl[b]];//

             //

             x=l;

             while(x!=rt[bl[l]])

             {

                 //printf("d%d\n",x);

                 tt[dd[x]]-=;

                 //if(GD(dd[x])==0)    an--;

                 //vis[x]^=1;

                 x=anc[x][];

             }

             //

             x=a;y=ra;

             //printf("1s%d\n",GV(5));

             while(dep[x]>dep[y])

             {

                 //printf("tt%d %d %d %d %d %d %d %d\n",x,y,an,GD(dd[x]),tt[dd[x]],d[1][dd[x]],d[2][dd[x]],d[2][dd[x]]);

                 if(!GV(x))//if(!GV(dd[x]))//

                 {

                     tt[dd[x]]++;

                     if(GD(dd[x])==)    an++;

                     //putchar('_');

                     //printf("$%d$",GD(dd[x]));

                 }

                 else

                 {

                     tt[dd[x]]--;

                     if(GD(dd[x])==)    an--;

                     //putchar('-');

                 }

                 vis[x]^=;//vis[dd[x]]^=1;

                 //printf("t%d %d %d %d %d %d %d %d %d\n",ra,rb,l,a,b,bl[a],bl[b],x,an);

                 x=anc[x][];

             }

             //不需要x!=y的，因为x一定是rt[bl[x]]的子树中节点

             //assert(x==y);

             //if(x!=y)    printf("!!%d %d\n",x,y);

             x=b;y=rb;

             while(dep[x]>dep[y])

             {

                 if(!GV(x))//if(!GV(dd[x]))//

                 {

                     tt[dd[x]]++;

                     if(GD(dd[x])==)    an++;

                     //putchar('_');

                 }

                 else

                 {

                     tt[dd[x]]--;

                     if(GD(dd[x])==)    an--;

                     //putchar('-');

                 }

                 vis[x]^=;//vis[dd[x]]^=1;

                 //printf("p%d %d %d %d %d %d %d %d %d\n",ra,rb,l,a,b,bl[a],bl[b],x,an);

                 x=anc[x][];

             }

             x=lca(a,b);

             //printf("g%d\n",x);

             if(!GV(x))//if(!GV(dd[x]))//

             {

                 tt[dd[x]]++;

                 if(GD(dd[x])==)    an++;

                 //putchar('_');

             }

             else

             {

                 tt[dd[x]]--;

                 if(GD(dd[x])==)    an--;

                 //putchar('-');

             }

             vis[x]^=;//vis[dd[x]]^=1;

             lans=an;

             if(!GV(x))//if(!GV(dd[x]))//

             {

                 tt[dd[x]]++;

             }

             else

             {

                 tt[dd[x]]--;

             }

             vis[x]^=;//vis[dd[x]]^=1;

             x=a;y=ra;

             while(dep[x]>dep[y])

             {

                 if(!GV(x))//if(!GV(dd[x]))//

                 {

                     tt[dd[x]]++;

                 }

                 else

                 {

                     tt[dd[x]]--;

                 }

                 vis[x]^=;//vis[dd[x]]^=1;

                 x=anc[x][];

             }

             //assert(x==y);

             //if(x!=y)    printf("!!%d %d\n",x,y);

             x=b;y=rb;

             while(dep[x]>dep[y])

             {

                 if(!GV(x))//if(!GV(dd[x]))//

                 {

                     tt[dd[x]]++;

                 }

                 else

                 {

                     tt[dd[x]]--;

                 }

                 vis[x]^=;//vis[dd[x]]^=1;

                 x=anc[x][];

             }

             //

             x=l;

             while(x!=rt[bl[l]])

             {

                 tt[dd[x]]+=;

                 //vis[x]^=1;

                 x=anc[x][];

             }

             //

             #undef G

         }

         printf("%d\n",lans);

         //for(int i=1;i<=n;i++)    assert(tt[i]==0);

         //for(int i=1;i<=n;i++)    assert(vis[i]==0);

     }

     return ;

 }

可以发现这种分块方法好像可以搬到括号序上。。。

要能够对于一个k,O(1)求区间内有多少个数，仅出现一次，且“对应数”等于k

并不能直接搬！因为不能前缀和了

。。。并不能研究出来怎么搞（除非多一个log），又一次失败了

失败代码2：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 const int N=;

 const int ss=;

 int n,m,a1[N+];

 int t1[N+];

 map<int,int> ma;

 vector<int> e[N+];

 namespace LCA

 {

 int anc[N+][],dep[N+],l2n=;

 void dfs(int u,int fa)

 {

     int i;

     anc[u][]=fa;

     dep[u]=dep[fa]+;

     for(i=;i<=l2n;i++)

         anc[u][i]=anc[anc[u][i-]][i-];

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

 }

 int lca(int a1,int y)

 {

     int t,i;

     if(dep[a1]<dep[y]){t=a1;a1=y;y=t;}

     for(t=dep[a1]-dep[y],i=;t>;t>>=,i++)

         if(t&)    a1=anc[a1][i];

     if(a1==y)    return a1;

     for(i=l2n;i>=;i--)

         if(anc[a1][i]!=anc[y][i])

         {

             a1=anc[a1][i];

             y=anc[y][i];

         }

     return anc[a1][];

 }

 }

 using LCA::lca;

 int pl[N+],dd[*N+];

 void dfs(int u,int fa)

 {

     int i;

     dd[++dd[]]=u;pl[u]=dd[];

     for(i=;i<e[u].size();i++)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

     dd[++dd[]]=u;

 }

 bool vis[N+];int num[N+];

 int an,sz,sz1;

 int bl[*N+];

 int st[ss+],ed[ss+];

 int d[ss+][N+];//d[i][j]:i块(含)之前j出现次数

 bool vv[ss+][N+];

 int an1[ss+][ss+];//an1[i][j]:i块到j块(均含)间答案

 void change(int u)

 {

     if(vis[u])

     {

         num[a1[u]]--;

         if(num[a1[u]]==)    an--;

     }

     else

     {

         if(num[a1[u]]==)    an++;

         num[a1[u]]++;

     }

     vis[u]^=;

 }

 int h1[N+],tp1;

 int main()

 {

     int i,j,k,x,y,a,b,aa,bb,l,lans=;

     scanf("%d%d",&n,&m);sz=;

     for(i=;i<=n;i++)    scanf("%d",&a1[i]),t1[++t1[]]=a1[i];

     sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;

     for(i=;i<=t1[];i++)    ma[t1[i]]=i;

     for(i=;i<=n;i++)    a1[i]=ma[a1[i]];

     for(i=;i<n;i++)

     {

         scanf("%d%d",&x,&y);

         e[x].pb(y);e[y].pb(x);

     }

     LCA::dfs(,);dfs(,);

     for(i=;i<=dd[];i++)    bl[i]=(i-)/sz;

     sz1=bl[dd[]];

     for(i=;i<sz1;i++)    st[i]=i*sz+,ed[i]=(i+)*sz;

     st[sz1]=sz1*sz+;ed[sz1]=dd[];

     for(i=;i<=sz1;i++)

     {

         for(j=st[i];j<=ed[i];j++)    change(dd[j]);

         memcpy(vv[i],vis,sizeof(vis));

         memcpy(d[i],num,sizeof(num));

     }

     memset(num,,sizeof(num));

     memset(vis,,sizeof(vis));

     an=;

     for(i=;i<=sz1;i++)

     {

         for(j=i;j<=sz1;j++)

         {

             for(k=st[j];k<=ed[j];k++)    change(dd[k]);

             an1[i][j]=an;

         }

         memset(num,,sizeof(num));

         memset(vis,,sizeof(vis));

         an=;

     }

     for(i=;i<=m;i++)

     {

         scanf("%d%d",&aa,&bb);

         a=pl[aa];b=pl[bb];

         if(bl[a]==bl[b]||bl[a]+==bl[b])

         {

             an=;

             for(j=a;j<=b;j++)    change(dd[j]),h1[++tp1]=dd[j];

             l=lca(aa,bb);

             if(!vis[aa])    change(aa),h1[++tp1]=aa;

             if(!vis[bb])    change(bb),h1[++tp1]=bb;

             if(!vis[l])    change(l),h1[++tp1]=l;

         }

         else

         {

             #define GV(u) (vis[u]^vv[bl[a]][u]^vv[bl[b]-1][u])

             #define GN(u) (num[u]+d[bl[b]-1][u]-d[bl[a]][u])

             #define CG(u) {\

                 if(GV(u))\

                 {\

                     num[a1[u]]--;\

                     if(GN(a1[u])==)    an--;\

                 }\

                 else\

                 {\

                     if(GN(a1[u])==)    an++;\

                     num[a1[u]]++;\

                 }\

                 h1[++tp1]=u;\

                 vis[u]^=;\

             }

             an=an1[bl[a]+][bl[b]-];

             for(j=a;j<=ed[bl[a]];j++)    CG(dd[j]);

             for(j=st[bl[b]];j<=b;j++)    CG(dd[j]);

             if(!GV(aa))    CG(aa);

             if(!GV(bb))    CG(bb);

             l=lca(aa,bb);

             if(!GV(l))    CG(l);

         }

         lans=an;

         printf("%d\n",lans);

         for(j=;j<=tp1;j++)    num[a1[h1[j]]]=vis[h1[j]]=;

     }

     return ;

 }

卡常最终版本：

 #pragma GCC optimize(3)

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<map>

 #include<cmath>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,sz,m;

 vector<int> e[];

 int rt[],cnt,bl[];

 namespace GBLOCK

 {

 int st[],tp;

 void dfs(int u,int fa)

 {

     int i,ltp=tp;

     for(i=;i<e[u].size();++i)

         if(e[u][i]!=fa)

         {

             dfs(e[u][i],u);

             if(tp-ltp>=sz)

             {

                 rt[++cnt]=u;

                 while(tp!=ltp)    bl[st[tp--]]=cnt;

             }

         }

     st[++tp]=u;

 }

 void work()

 {

     dfs(,);

     ++cnt;rt[cnt]=;

     while(tp)    bl[st[tp--]]=cnt;

 }

 }

 int dd[];

 namespace LCA

 {

 int anc[][],dep[],l2n=;

 void dfs(int u,int fa)

 {

     int i;

     anc[u][]=fa;

     dep[u]=dep[fa]+;

     for(i=;i<=l2n;++i)

         anc[u][i]=anc[anc[u][i-]][i-];

     for(i=;i<e[u].size();++i)

         if(e[u][i]!=fa)

             dfs(e[u][i],u);

 }

 int lca(int x,int y)

 {

     int t,i;

     if(dep[x]<dep[y]){t=x;x=y;y=t;}

     for(t=dep[x]-dep[y],i=;t>;t>>=,++i)

         if(t&)    x=anc[x][i];

     if(x==y)    return x;

     for(i=l2n;i>=;--i)

         if(anc[x][i]!=anc[y][i])

         {

             x=anc[x][i];

             y=anc[y][i];

         }

     return anc[x][];

 }

 }

 int an1[][];

 int d[][];

 bool vv[][];

 int tt[];

 bool vis[];

 int an;

 void Change(int x)

 {

     if(vis[x])

     {

         --tt[dd[x]];

         if(tt[dd[x]]==)    --an;

     }

     else

     {

         ++tt[dd[x]];

         if(tt[dd[x]]==)    ++an;

     }

     vis[x]^=;

 }

 using LCA::lca;

 using LCA::anc;

 using LCA::dep;

 #define CLR(x) memset(x,0,sizeof(x))

 namespace PRE

 {

 vector<int> rts[];

 int s;

 void dfs1(int u,int fa)

 {

     int i;

     ++tt[dd[u]];vis[u]=;

     for(i=;i<rts[u].size();++i)

     {

         memcpy(d[rts[u][i]],tt,sizeof(tt));

         memcpy(vv[rts[u][i]],vis,sizeof(vis));

     }

     for(i=;i<e[u].size();++i)

         if(e[u][i]!=fa)

             dfs1(e[u][i],u);

     --tt[dd[u]];vis[u]=;

 }

 void dfs2(int u,int fa)

 {

     int i;

     Change(u);

     int l=lca(rt[s],u);

     Change(l);

     for(i=;i<rts[u].size();++i)

         an1[s][rts[u][i]]=an;

     Change(l);

     for(i=;i<e[u].size();++i)

         if(e[u][i]!=fa)

             dfs2(e[u][i],u);

     Change(u);

 }

 void work()

 {

     int i;

     for(i=;i<=cnt;++i)    rts[rt[i]].pb(i);

     dfs1(,);

     for(i=;i<=cnt;++i)

     {

         s=i;

         dfs2(rt[s],);

     }

 }

 }

 int t1[];

 map<int,int> ma;

 int h1[],*tp1=h1;

 inline void read(int &x) {

     x=;char ch=getchar();

     while(ch>''||ch<'')ch=getchar();

     while(ch>=''&&ch<=''){x*=;x+=(ch-'');ch=getchar();}

 }

 inline void write(int x) {

     if(x>) write(x/);

     putchar(x%+'');

 }

 int main()

 {

     //freopen("/tmp/2589/2.in","r",stdin);

     //freopen("/tmp/2589/2.ans","w",stdout);

     int i,bla,blb,bll,a,b,l,x,y,ra,rb,rl,lans=,*it;

     bool *vvbla,*vvblb;int *dbla,*dblb,*dbll;

     read(n);read(m);sz=;

     for(i=;i<=n;++i)    scanf("%d",&dd[i]),t1[++t1[]]=dd[i];

     sort(t1+,t1+t1[]+);t1[]=unique(t1+,t1+t1[]+)-t1-;

     for(i=;i<=t1[];++i)    ma[t1[i]]=i;

     for(i=;i<=n;++i)    dd[i]=ma[dd[i]];

     for(i=;i<n;++i)

     {

         read(a);read(b);

         e[a].pb(b);e[b].pb(a);

     }

     GBLOCK::work();LCA::dfs(,);

     PRE::work();

     for(i=;i<=m;++i)

     {

         read(a);read(b);a^=lans;

         if(bl[a]==bl[b])

         {

             an=;

             x=a;y=b;

             if(dep[x]<dep[y])    swap(x,y);

             while(dep[x]>dep[y])

             {

                 Change(x);*(++tp1)=x;

                 x=anc[x][];

             }

             while(x!=y)

             {

                 Change(x);Change(y);*(++tp1)=x;*(++tp1)=y;

                 x=anc[x][];y=anc[y][];

             }

             Change(x);*(++tp1)=x;

             lans=an;

         }

         else

         {

             bla=bl[a];blb=bl[b];

             ra=rt[bla];rb=rt[blb];

             l=lca(ra,rb);bll=bl[l];rl=rt[bll];

             dbla=d[bla];dblb=d[blb];dbll=d[bll];

             vvbla=vv[bla];vvblb=vv[blb];

             #define GD(i) (tt[i]+dbla[i]+dblb[i]-(dbll[i]<<1))

             #define GV(i) (vis[i]^vvbla[i]^vvblb[i])

             an=an1[bla][blb];

             x=l;

             while(x!=rl)

             {

                 tt[dd[x]]-=;*(++tp1)=x;

                 x=anc[x][];

             }

             x=a;y=ra;

             while(x!=y)

             {

                 if(GV(x))

                 {

                     --tt[dd[x]];

                     if(GD(dd[x])==)    --an;

                 }

                 else

                 {

                     ++tt[dd[x]];

                     if(GD(dd[x])==)    ++an;

                 }

                 *(++tp1)=x;

                 vis[x]^=;

                 x=anc[x][];

             }

             x=b;y=rb;

             while(x!=y)

             {

                 if(GV(x))

                 {

                     --tt[dd[x]];

                     if(GD(dd[x])==)    --an;

                 }

                 else

                 {

                     ++tt[dd[x]];

                     if(GD(dd[x])==)    ++an;

                 }

                 *(++tp1)=x;

                 vis[x]^=;

                 x=anc[x][];

             }

             x=lca(a,b);

             if(GV(x))

             {

                 --tt[dd[x]];

                 if(GD(dd[x])==)    --an;

             }

             else

             {

                 ++tt[dd[x]];

                 if(GD(dd[x])==)    ++an;

             }

             *(++tp1)=x;

             vis[x]^=;

             lans=an;

             #undef G

         }

         write(lans);putchar('\n');

         for(it=h1+;it<=tp1;++it)    tt[dd[*it]]=vis[*it]=;

         tp1=h1;

     }

     return ;

 }

最新文章

  1. html5快速入门（一）—— html简介
  2. git 教程（15）--分支管理策略
  3. #Deep Learning回顾#之2006年的Science Paper
  4. 探究JVM——垃圾回收
  5. Unity3D手游开发日记(8) - 运动残影效果
  6. vuejs常用指令
  7. cascading rollback 级联回滚
  8. Oracle EBS-SQL (BOM-13):检查未定义库存分的物料类.sql
  9. 在Sharepoint中批量删除大量条目
  10. POJ3090_Visible Lattice Points【欧拉函数】
  11. python中金额计算的小问题
  12. 树莓派.安装Redis环境
  13. zzuli oj 1135 算菜价
  14. intellij idea 编译 kafka 源码
  15. 对称加密----AES和DES加密、解密
  16. 程序员必备！Sonar代码质量管理工具
  17. String、StringBuffer与StringBuilder 复习回顾总结
  18. WPF 元素的查找
  19. 遇到的一个渲染的bug
  20. [Codeforces #172] Tutorial

热门文章

  1. ps 图层混合模式
  2. charles抓取线上接口数据替换为本地json格式数据
  3. fatal error C1902: 程序数据库管理器不匹配；请检查安装解决
  4. BestCoder3 1002 BestCoder Sequence(hdu 4908) 解题报告
  5. codeforces A. Fox and Box Accumulation 解题报告
  6. 如何修改Windows的默认安装路径
  7. 页面渲染——简化paint复杂程度和区域
  8. codeforces 701B B. Cells Not Under Attack(水题)
  9. 操作 AutoIT：界面与自动化操作结合来简化日常劳动: .Net Reactor验证License，设置License，创建License，截图AutoIt自动化实现。（六）
  10. COM组件开发实践（一）