4763: 雪辉[点分治+可持久化分块]

4763: 雪辉

Time Limit: 39 Sec  Memory Limit: 666 MB
Submit: 85  Solved: 51
[Submit][Status][Discuss]

Description

上次立下的NOIP退役Flag没有成功

 

这次就立一个WC狗牌的Flag

 

三周目的由乃被钦定成为了卡密，她立刻赶去二周目的世界寻找雪辉

 

但是按照设定，两个平行世界是没法互相影响的，也就是原则上由乃是没法去二周目世界的

 

这时候Deus又跳出来说，其实设定是作者骗你的，只要爱的力量足够强大什么都可以做到（好狗血）

 

Deus：由乃你为了雪辉是不是什么都可以做呀

 

yuno：当然啦这还用想

 

Deus：那你帮我做个题吧

 

yuno：只要不是数据结构，什么题我都做

 

Deus：出题人是那个nzhtl1477呀，他出（抄）的题除了傻逼数据结构还有啥。。。

 

yuno：你说的很有道理。。。

 

Deus：上次那个题你不是两分钟就秒了吗，这个题比那个还简单

 

yuno：（小声）其实那个是bzoj上面的大佬帮我做的

 

Deus：好吧就这么愉快的钦定了

 

给一个n个点的树，点有点权，有m次询问，每次询问多条链的并有多少种不同的点权以及它的mex

 

mex就是一个集合中最小的没有出现的非负整数，注意0要算

 

比如说集合是1,9,2,6,0,8,1,7，则出现了0,1,2,6,7,8,9这7种不同的点权，因为没有3所以mex是3

Input

第一行三个数n，m，意义如题所述，和一个数f

 

如果f是0，代表Deus没有使用膜法，如果f是1，代表Deus使用了膜法

 

之后一行n个数，表示点权

 

之后n-1行，每行两个数x，y，表示x和y节点之间有一条边，保证是一个树

 

之后m行，每行先是一个数a，表示这次输入a条链，紧接着2a个数(x1,y1)(x2,y2)...表示每条树链

 

如果数据被Deus施了膜法，这2a个数都要异或上上一个询问的答案lastans，如果是第一次询问则这个lastans = 0，因为每次询问有两个答案，lastans为这两个答案的和

 

如果没有膜法，则-1s并且不异或

 

数据范围：

 

设a的和为q

 

对于20%的数据，n,q<=1000，f=0

 

对于另外30%的数据，n,q<=100000，树是一条链，f=0

 

对于所有数据n,q<=100000,且点权<=30000

Output

m行，每行两个数表示点权种类数以及mex

Sample Input

10 1 1
0 0 1 0 0 2 2 0 0 0
2 3
1 2
4 5
3 4
7 8
6 7
5 6
9 10
8 9
4
1 7
3 3
1 1
9 3

Sample Output

3 3

HINT

可爱（口径）即正义~

Source

By nzhtl1477

 

 

• 如果是一个序列，每次询问区间的mex怎么做
• 分块，预处理任意两块之间的bitset，然后每个询问只需要加入  个数就可以了，复杂度 
• 树上同理
• 在树上选择  个点当作关键点，有一个贪心的方法可以保证任意两个关键点之间的距离是  的
• 按深度从大到小枚举树上的每个点，将点x标记为关键点当且仅当  的子树中有一个点到  的距离大于  且不为关键点
• 或者直接随机  个点当作关键点也可以保证复杂度
• 考虑预处理关键点之间的bitset，发现不能套用序列上的做法，因为dfs涉及到撤销，如果套用序列上的做法就需要使用可持久化bitset，复杂度变为 
• 考虑将原树重构为  个点的新树，即只有关键点的新树
• 重构树中两点之间连有边当且仅当这两个关键点在原树中形成的链上没有其他关键点
• 重构树的边权是一个bitset，存有这两个关键点之间的数
• 通过这个新的树，可以在  的时间预处理任意两点之间的bitset
• 每个询问是多个树链的并，那么可以搞出每个树链的bitset之后在把他们或起来
• 树链  的答案即相当于  的答案或  的答案， 为  的lca
• 至于为什么不能直接求  的答案，因为预处理的两个点之间的bitset是相对于重构树的，有可能会加入多余的点
• 与序列上的处理方法相似，每个询问只需要加入  个数即到达一个关键点
• 总复杂度 
• 因为stl的bitset没法支持询问mex，所以要手写bitset

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define OPT __attribute__((optimize("O2")))
using namespace std;
typedef unsigned long long ll;
template <typename T>
OPT inline void read(T &x){
    T f=1;char ch=getchar();x=0;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}
const ll inf=~0ULL;
const int N=1e5+5,M=480,T=7e5+5;
struct edge{int v,next;}e[N<<1];int tot=1,head[N];
struct P{
    int x,y,d,o;
    P(){}
    P(int _x,int _y,int _d,int _o){
        x=_x;y=_y;d=_d;o=_o;
    }
};
int n,m,type,mx,sum,root;
int A,B,last;
int a[N],b[N];
int f[N],siz[N],dep[N];bool vis[N];
int cnt,cur[30],pos[T][30];
ll pool[T][16],bit[M];
vector<P>G[N];
OPT inline bool cmp(const P &c,const P &d){//按子树根节点排序
    return c.x<d.x;
}    
OPT inline void add(int x,int y){
    e[++tot].v=y;e[tot].next=head[x];head[x]=tot;
    e[++tot].v=x;e[tot].next=head[y];head[y]=tot;
}    
OPT inline void findroot(int x,int fa){//找重心
    siz[x]=1;f[x]=0;
    for(int i=head[x];i;i=e[i].next){
        if(vis[e[i].v]||e[i].v==fa) continue;
        findroot(e[i].v,x);
        siz[x]+=siz[e[i].v];
        f[x]=max(f[x],siz[e[i].v]);
    }
    f[x]=max(f[x],sum-siz[x]);
    if(f[x]<f[root]) root=x;
}
//对于每个点
//记录(重心，重心到它第一个点，距离，可持久)
OPT inline void getdep(int x,int y,int z){//算深度
    f[x]=y;dep[x]=z;
    if(z>mx) mx=z;
    for(int i=head[x];i;i=e[i].next){
        if(vis[e[i].v]||e[i].v==y) continue;    
        getdep(e[i].v,x,z+1);
    }
}
//30块，每块16个数
OPT inline void dfs1(int x,int y,int z){
    if(y==root) z=x;
    //修改第b[x]个位置
      //把bitset的第b[x]>>4个位置的第b[x]&15或上1ULL<<(a[x]&63)
    int t=cur[b[x]>>4];
    cur[b[x]>>4]=++cnt;
    for(int i=0;i<16;i++) pool[cnt][i]=pool[t][i];
    pool[cnt][b[x]&15]|=1ULL<<(a[x]&63);
    for(int i=0;i<30;i++) pos[cnt][i]=cur[i];
    G[x].push_back(P(root,z,dep[x],cnt));
    for(int i=head[x];i;i=e[i].next){
        if(vis[e[i].v]||e[i].v==y) continue;    
        dfs1(e[i].v,x,z);
    }
    cur[b[x]>>4]=t;//还原 
}
OPT inline void dfs2(int x,int y,int z){
    if(y==root) z=x;
    G[x].push_back(P(root,z,dep[x],0));
    for(int i=head[x];i;i=e[i].next){
        if(vis[e[i].v]||e[i].v==y) continue;    
        dfs2(e[i].v,x,z);
    }
}
OPT inline void solve(int x){
    vis[x]=1;mx=0;
    getdep(x,0,0);
    if(mx>M) dfs1(x,0,0);else dfs2(x,0,0);
    for(int i=head[x];i;i=e[i].next){
        if(vis[e[i].v]) continue;
        f[0]=sum=siz[e[i].v];findroot(e[i].v,root=0);solve(root);
    }
}
OPT inline void visit(int x){//标记状态，即某颜色是否出现了 
    x=a[x];
    bit[x>>6]|=1ULL<<(x&63);
}
OPT inline void chain(int x,int y,int d,int o){//统计x->y这条链状态 
    if(d>M){
        for(int i=0;i<30;i++)
            for(int j=0,k=pos[o][i];j<16;j++)
                bit[i<<4|j]|=pool[k][j];
        return ;
    }
    for(;x!=y;x=f[x]){
        if(dep[x]<dep[y]) swap(x,y);
        visit(x);
    }
    visit(x);
}
OPT inline void work(int x,int y){//拆成链 
    if(x==y){visit(x);return ;}
    vector<P>::iterator i=G[x].begin(),j=G[y].begin();
    vector<P>::iterator p=G[x].end(),q=G[y].end();
    while(i!=p&&j!=q){
        if(i->x<j->x){i++;continue;}
        if(i->x>j->x){j++;continue;}
        if(i->y==j->y){i++;j++;continue;}
        if(i->x!=x) chain(x,i->x,i->d,i->o);
        if(i->x!=y) chain(y,j->x,j->d,j->o);
        i++;j++;
    }
}
OPT inline int ask(){//直接查询有多少个“1” 
    int res=0;
    for(int i=0;i<M;i++) res+=__builtin_popcountll(bit[i]);
    return res;
}
OPT inline int mex(){//按块枚举 
    for(int i=0;;i++) if(bit[i]!=inf)
        for(int j=0;;j++) if(bit[i]>>j&1^1)
            return (i<<6)|j;
}
OPT inline void DFS(int x,int y){//点分治之后，还原树 
    dep[x]=dep[y]+1;f[x]=y;
    for(int i=head[x];i;i=e[i].next){
        if(e[i].v==y) continue;    
        DFS(e[i].v,x);
    }
}
OPT int main(){
    read(n);read(m),read(type);
    for(int i=1;i<=n;i++) read(a[i]),b[i]=a[i]>>6;;//0<=a[i]<=30000
    for(int i=1,x,y;i<n;i++) read(x),read(y),add(x,y);
    f[0]=sum=n;findroot(1,root=0);solve(root);
    for(int i=1;i<=n;i++) sort(G[i].begin(),G[i].end(),cmp);
    DFS(1,0);
    for(int k,x,y;m--;memset(bit,0,sizeof bit)){
        for(read(k);k--;){
            read(x);read(y);
            if(type) x^=last,y^=last;
            work(x,y);    
        }
        A=ask();B=mex();
        printf("%d %d
",A,B);
        last=A+B;
    }
    return 0;
}