【BZOJ3757】苹果树(树上莫队)

点此看题面

大致题意: 每次问你树上两点之间路径中有多少种颜色,每次询问可能会将一种颜色\(a\)看成\(b\)


树上莫队

这题是一道树上莫队板子题。

毕竟求区间中有多少种不同的数是莫队算法的经典应用啊。


关于将颜色\(a\)看成\(b\)

这操作其实很好处理。

只要判断\(cnt_a\)\(cnt_b\)是否同时\(>0\)即可。

但要注意特判\(a==b\)的情况。


代码

#include<bits/stdc++.h>
#define N 50000
#define Q 100000
#define add(x,y) (e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y)
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,query_tot,col[N+5];
int ee,lnk[N+5];
struct edge
{
    int to,nxt;
}e[(N<<1)+5];
class Class_FIO
{
    private:
        #define Fsize 100000
        #define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
        #define pc(ch) (void)(FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))
        int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];
    public:
        Class_FIO() {A=B=Fin;}
        inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
        inline void writeln(int x) {if(!x) return pc('0'),pc('\n');while(x) Stack[++Top]=x%10+48,x/=10;while(Top) pc(Stack[Top--]);pc('\n');}
        inline void clear() {fwrite(Fout,1,FoutSize,stdout),FoutSize=0;}
}F;
class Class_CaptainMotao_on_Tree//树上莫队
{
    private:
        #define bp(x) (((x)-1)/S+1)
        #define F5(x) ((op[t=x]^=1)?(!cnt[col[t]]++&&++res):(!--cnt[col[t]]&&--res))//插入或删除一个数,其实可以合并成一个函数
        int S,op[N+5],cnt[N+5],ans[N+5];//cnt统计每种数字出现次数,ans记录答案
        class Class_Dfser//DFS预处理
        {
            private:
                #define LogN 16
                int cnt,Depth[N+5],fa[N+5][LogN+5];
            public:
                int s[(N<<1)+5],I[N+5],O[N+5]; 
                inline void Init(int x=0,int lst=-1)
                {
                    register int i;
                    for(s[I[x]=++cnt]=x,i=1;i<=LogN;++i) fa[x][i]=fa[fa[x][i-1]][i-1];
                    for(i=lnk[x];i;i=e[i].nxt) e[i].to^lst&&(Depth[e[i].to]=Depth[fa[e[i].to][0]=x]+1,Init(e[i].to,x),0);
                    s[O[x]=++cnt]=x;
                }
                inline int LCA(int x,int y)
                {
                    register int i;
                    for(Depth[x]<Depth[y]&&swap(x,y),i=0;Depth[x]^Depth[y];++i) ((Depth[x]^Depth[y])&(1<<i))&&(x=fa[x][i]);
                    if(!(x^y)) return x;
                    for(i=LogN;~i;--i) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);
                    return fa[x][0];
                }
        }D;
        struct Query
        {
            int l,r,pos,bl,flag,s1,s2;
            Query(int x=0,int y=0,int p=0,int b=0,int f=0,int t1=0,int t2=0):l(x),r(y),pos(p),bl(b),flag(f),s1(t1),s2(t2){}
            inline friend bool operator < (Query x,Query y) {return x.bl^y.bl?x.bl<y.bl:(x.bl&1?x.r<y.r:x.r>y.r);}
        }q[Q+5];
    public:
        inline void Solve()
        {
            int i,x,y,s1,s2,z,t,L=1,R=0,res=0;
            for(D.Init(),S=sqrt(n),i=1;i<=query_tot;++i) 
            {
                F.read(x),F.read(y),F.read(s1),F.read(s2),D.I[x]>D.I[y]&&swap(x,y),//读入,保证I[x]<=I[y]
                q[i]=(z=D.LCA(x,y))^x?Query(D.O[x],D.I[y],i,bp(D.O[x]),z,s1,s2):Query(D.I[x],D.I[y],i,bp(D.I[x]),0,s1,s2);//存储询问
            }
            for(sort(q+1,q+query_tot+1),i=1;i<=query_tot;++i)//处理询问
            {
                while(R<q[i].r) F5(D.s[++R]);while(L>q[i].l) F5(D.s[--L]);while(R>q[i].r) F5(D.s[R--]);while(L<q[i].l) F5(D.s[L++]);//移动区间
                q[i].flag&&F5(q[i].flag),ans[q[i].pos]=res-(q[i].s1^q[i].s2&&cnt[q[i].s1]&&cnt[q[i].s2]),q[i].flag&&F5(q[i].flag);//判断是否要增加LCA的贡献,并处理将颜色a看成b的情况
            }
            for(i=1;i<=query_tot;++i) F.writeln(ans[i]);//输出答案
        }
}C;
int main()
{
    register int i,x,y;
    for(F.read(n),F.read(query_tot),i=1;i<=n;++i) F.read(col[i]);
    for(i=1;i<=n;++i) F.read(x),F.read(y),add(x,y),add(y,x);
    return C.Solve(),F.clear(),0;
}

【BZOJ3757】苹果树(树上莫队)

上一篇:APPium连接真机输入框中输入的内容与代码中不一致


下一篇:Android Studio 发布 APK