题意

一颗有根树，每个点有黑白两种颜色和阀值ai，若它的子树中（不包括自己）的黑色数量大于ai，则产生一点贡献。每次将一个点的颜色取反，求每次修改后的贡献。n，q<=1E5。

思考

树剖后直接分块就行了。复杂度约为O((n+q)sqrt(nlogn))，但似乎更小？

代码

 #pragma GCC optimize 2

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1E5+;

 ///////////////////////////////////////////////////////////////////////////////

 int wait[maxn],wait_R[maxn],wait_C[maxn],wait_W[maxn];

 template<class T>inline void copy(T*A,T*B,int l,int r)

 {

     for(int i=l;i<=r;++i)

         A[i-l+]=B[i];

 }

 struct block

 {

     int n,pos,layer,now;

     bool created;

     int*f,*c;

     block()

     {

         created=now=;

     }

     void init(int x,int where,int*A)

     {

         if(created)

             delete f,delete c;

         created=;

         for(int i=;i<=x;++i)

             wait_R[i]=A[i],wait_C[i]=;

         sort(wait_R+,wait_R+x+);

         int size=;

         for(int i=;i<=x;++i)

         {

             if(wait_R[i]!=wait_R[i-]||i==)

                 wait_W[++size]=wait_R[i];

             ++wait_C[size];

         }

         n=size;

         f=new int[n+];

         c=new int[n+];

         now=c[]=f[]=c[n+]=f[n+]=;

         layer=where;

         pos=;

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

             f[i]=wait_W[i],c[i]=wait_C[i];

         while(f[pos]<layer)

             now+=c[pos],++pos;

     }

     inline int get()

     {

         return now;

     }

     inline void add()

     {

         if(layer+==f[pos]+)

             now+=c[pos],++pos;

         ++layer;

     }

     inline void remove()

     {

         if(pos&&layer-==f[pos-])

             now-=c[pos-],--pos;

         --layer;

     }

 };

 struct sequence

 {

     int*a,*tag,*bel,*tail;

     block*B;

     int n,sqr,tot;

     void init(int x,int*A)

     {

         n=x;

         sqr=sqrt(n+0.5);

         a=new int[n+];

         bel=new int[n+];

         tag=new int[sqr+];

         tail=new int[sqr+];

         for(int i=;i<=sqr+;++i)

             tail[i]=tag[i]=;

         a[]=;

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

             a[i]=A[i];

         int L=,R=sqr;

         B=new block[sqr+];

         tot=;

         while(L<=n)

         {

             int len=min(n,R)-L+;

             copy(wait,a,L,min(n,R));

             B[++tot].init(len,,wait);

             for(int i=L;i<=R;++i)

                 bel[i]=tot;

             tail[tot]=min(n,R);

             L+=sqr,R+=sqr;

         }

     }

     inline int get()

     {

         int sum=;

         for(int i=;i<=tot;++i)

             sum+=B[i].now;

         return sum;

     }

     inline void add(int x)

     {

         int i=;

         for(i=;bel[i]!=bel[x];i+=sqr)

             B[bel[i]].add();

         int L=i,R=tail[bel[x]];

         int len=R-L+;

         for(int i=L;i<=R;++i)

             wait[i-L+]=a[i]-B[bel[x]].layer;

         for(int i=L;i<=x;++i)

             --wait[i-L+];

         for(int i=L;i<=R;++i)

             a[i]=wait[i-L+];

         B[bel[x]].init(len,,wait);

     }

     inline void remove(int x)

     {

         int i=;

         for(i=;bel[i]!=bel[x];i+=sqr)

             B[bel[i]].remove();

         int L=i,R=tail[bel[x]];

         int len=R-L+;

         for(int i=L;i<=R;++i)

             wait[i-L+]=a[i]-B[bel[x]].layer;

         for(int i=L;i<=x;++i)

             ++wait[i-L+];

         for(int i=L;i<=R;++i)

             a[i]=wait[i-L+];

         B[bel[x]].init(len,,wait);

     }

     inline void addDot(int x,int y)

     {

         int i=;

         while(bel[i]!=bel[x])

             i+=sqr;

         int L=i,R=tail[bel[x]];

         int len=R-L+;

         for(int i=L;i<=R;++i)

             wait[i-L+]=a[i]-B[bel[x]].layer;

         wait[x-L+]+=y;

         for(int i=L;i<=R;++i)

             a[i]=wait[i-L+];

         B[bel[x]].init(len,,wait);

     }

 }S[maxn];

 ///////////////////////////////////////////////////////////////////////////////

 int n,q,a[maxn];

 int size,head[maxn*];

 int sum[maxn],fa[maxn],son[maxn],top[maxn],where[maxn],dfn[maxn],low[maxn],ti;

 int tot,ans;

 bool c[maxn];

 struct edge

 {

     int to,next;

 }E[maxn*];

 void dfs1(int u,int F)

 {

     fa[u]=F,sum[u]=;

     for(int i=head[u];i;i=E[i].next)

     {

         int v=E[i].to;

         if(v==F)

             continue;

         dfs1(v,u);

         sum[u]+=sum[v];

         if(sum[son[u]]<sum[v])

             son[u]=v;

     }

 }

 void dfs2(int u,int F)

 {

     low[u]=dfn[u]=++ti;

     if(son[F]==u)

         top[u]=top[F];

     else

         top[u]=u;

     if(son[u])

     {

         dfs2(son[u],u);

         low[u]=low[son[u]];

     }

     for(int i=head[u];i;i=E[i].next)

     {

         int v=E[i].to;

         if(v==F||v==son[u])

             continue;

         dfs2(v,u);

         low[u]=low[v];

     }

 }

 void get(int u)

 {

     wait[where[u]=++tot]=a[u];

     if(son[u])

         get(son[u]);

 }

 void add(int u,int v)

 {

     E[++size].to=v;

     E[size].next=head[u];

     head[u]=size;

 }

 void addChain(int x)

 {

     while(x)

     {

         S[top[x]].add(where[x]);

         x=fa[top[x]];

     }

 }

 void removeChain(int x)

 {

     while(x)

     {

         S[top[x]].remove(where[x]);

         x=fa[top[x]];

     }

 }

 int askChain(int x)

 {

     int sum=;

     while(x)

     {

         sum+=S[top[x]].get();

         x=fa[top[x]];

     }

     return sum;

 }

 ///////////////////////////////////////////////////////////////////////////////

 int main()

 {

     ios::sync_with_stdio(false);

     int num;

     cin>>num;

     cin>>n>>q;

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

     {

         int x;

         cin>>x;

         add(x,i);

         add(i,x);

     }

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

         cin>>a[i];

     dfs1(,);

     dfs2(,);

     fa[]=;

     for(int u=;u<=n;++u)

         if(top[u]==u)

         {

             tot=;

             get(u);

             S[u].init(tot,wait);

         }

     while(q--)

     {

         int x;

         cin>>x;

         if(c[x])

         {

             int last=askChain(x);

             removeChain(fa[x]);

             S[top[x]].addDot(where[x],-);

             int now=askChain(x);

             ans+=now-last;

         }

         else

         {

             int last=askChain(x);

             addChain(fa[x]);

             S[top[x]].addDot(where[x],);

             int now=askChain(x);

             ans+=now-last;

         }

         c[x]^=;

         cout<<ans<<" ";

     }

     return ;

 }

最新文章

  1. 使用Xmanager访问CentOS远程桌面
  2. 《Entity Framework 6 Recipes》中文翻译系列 (29) ------ 第五章 加载实体和导航属性之过滤预先加载的实体集合和修改外键关联
  3. Android集成支付宝的坑
  4. Wps 方框里面加勾
  5. C++：对象声明
  6. 【XS128】Link error L1822 symbol _FADD / _FSUB/ _FDIV/ _FMUL.....错误解决的方法
  7. Web性能压力测试工具之Siege详解
  8. 1090. Highest Price in Supply Chain (25)
  9. [liu yanling]软件测试的分类
  10. ubuntu下SVN服务器安装配置
  11. PHP 判断数据类型
  12. hdu 4961 Boring Sum（数学题）
  13. 智能指针之 unique_ptr
  14. C++对txt文本进行读写操作
  15. Intent之跳转总结
  16. POJ3094 Quicksum
  17. Leetcode 969. 煎饼排序
  18. 能力成熟度模型（CMM）
  19. C++程序文件链接
  20. macOS Sierra上Opencv的安装与使用

热门文章

  1. You are using the runtime-only build of Vue where the template compiler is not available. Either pre-compile the templates into render functions, or use the compiler-included build.
  2. Java 学习笔记(8)——匿名对象与内部类
  3. 第二阶段：2.商业需求文档MRD：2.MRD-目标市场分析
  4. codefoces 22E 图论
  5. flask修改数据库字段的类型和长度
  6. CSV 文件的存取
  7. 20191024-3 互评Alpha阶段作品——都是为了生活组
  8. 【原创】够强！一行代码就修复了我提的Dubbo的Bug。
  9. 线程池：ThreadPoolExecutor的使用
  10. 小技巧（2） 查询自己博客的SEO（如果违规，请先提醒）