ACM-ICPC 2018 沈阳赛区网络预赛 J. Ka Chang-白红宇

ACM-ICPC 2018 沈阳赛区网络预赛 J. Ka Chang

阅读量：5036 次

发布时间：2019-06-12

本文共 3814 字，大约阅读时间需要 12 分钟。

题目链接：

我参考的博客：

这题写了两次，第二次写，我居然对这题没有一点印象，完全不知道以前写过......

第二次的代码用了分块和二分，加上一堆vector。

题意：给出一棵有n个点的树，每个点的初始值都是0，m次查询，如果op==1，那么后面接两个数字，表示把第a层的点的值增加b，如果op==2，那么后面接一个数a，表示查询以点a为根节点的这颗子树的所有点的值的和，输出这个值。

思路：因为n，m都可能达到1e5，因为要查找一棵树所有点的和，并且还要修改，如果用树结构查找肯定不方便，那么我们可以用DFS序把树转化为线性结构，用每个点的DSF序来表示这个点，那么查找的时候一棵子树就是一个连续区间，那么我们就可以用树状数组来查找一段区间的和，如果只用树状数组的单点更新，那么极端情况下某一层的点数非常多，更新就会超时；为了解决某一层点非常多并且要更新的情况，我们就可以使用分块的思想来减少更新所需的时间。把所有的层分成大块（点非常多）和小块（点比较少），如果是小块，我们就用树状数组来处理它，更新时暴力更新这一层所有点。如果是大块，我们就用标记数组来记录该层增加的值，因为我们用树的DFS序来代表点，并且DFS序是升序的的，我们就可以用二分查找每个大块来计算目标子树的和。

第一次看了博客的代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                  using namespace std;typedef long long LL;#define eps 1e-8#define INF 0x3f3f3f3f#define maxn 100005/*struct point{ int u,w;};bool operator <(const point &s1,const point &s2){ if(s1.w!=s2.w) return s1.w>s2.w; else return s1.u>s2.u;}*/struct node{ int v,next;}edge[maxn*2];int head[maxn],L[maxn],R[maxn],pre[maxn];//L[i]和R[i]数组表示i点DFS序的左右边界，pre[i]数组记录i的父亲，这里用来判断有没有走过 LL c[maxn],up[maxn];//c数组就是树状数组，up数组用来记录点数很多的层数(大块)的增加值 int n,m,k,r,cnt,Time,max_deep,block;//Time就是DFS序，max_deep记录最大的层数，block用来分块 vector
                 
                  ve[maxn];//ve[deep]记录在第deep层的点 vector
                  
                   vv; //vv存大块所在的层 void init(){ fill(head,head+maxn-1,-1); fill(pre,pre+maxn-1,0); fill(c,c+maxn-1,0); fill(up,up+maxn-1,0); for(int i=0;i<=n;i++) ve[i].clear(); vv.clear(); Time=cnt=max_deep=0; block=sqrt(n);}void DFS(int u,int deep){ L[u]=++Time;//记录左边界 max_deep=max(max_deep,deep); ve[deep].push_back(Time);//把u点的DFS序值存入第deep层，我们用DFS序把把树转化为线性，然后用树状数组求区间和 for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(pre[v]) continue; pre[v]=u; DFS(v,deep+1); } R[u]=Time;//存右边界，注意Time不要加，因为一个点不用记录多个DFS序 }void add(int u,int v){ edge[++cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt; }int lowbit(int x){ return x&(-x);}void Add(int x,int b)//树状数组单点更新 { for(int i=x;i<=n;i+=lowbit(i)) c[i]+=b;}LL sum(int x)//树状数组求区间和 { if(x<=0) return 0; LL ans=0; while(x>0) { ans+=c[x]; x-=lowbit(x); } return ans;}int main(){ while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i=1;i
                   
                    block) vv.push_back(i); } int op; for(int i=1;i<=m;i++) { scanf("%d",&op); if(op==1) { int a,b; scanf("%d%d",&a,&b); if(ve[a].size()>block)//如果a层是大块 { up[a]+=b; } else//a层不是大块 { for(int i=0;i

第二次代码：

也是分块，但是用vector做了一些有点麻烦的操作

#include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                  using namespace std;typedef long long LL;#define eps 1e-8#define INF 0x3f3f3f3f#define maxn 100005struct node{ int v,next;}edge[maxn*2];vector
                 
                  dep[maxn],ve;int n,m,k,t,cnt,block,Time;int L[maxn],R[maxn],zu[maxn],de[maxn],head[maxn];//L和R数组存的是第一次和最后一次到达i的时间，其中L[i]也带比奥i的编号//这里用来分块，所以zu[i]代表编号i所在的块，de[i]代表编号i对应的深度 LL a[maxn],sum[maxn],tag[maxn];//a[i]表示i这个编号上的点权，sum[i]表示第i个块上的和(只包括同一深度下点数小于block的) //tag[i]表示深度i上的点要加的值 void init(){ memset(head,-1,sizeof(head)); memset(tag,0,sizeof(tag)); memset(sum,0,sizeof(sum)); for(int i=0;i<=n;i++) dep[i].clear(); ve.clear(); cnt=0,Time=0; block=sqrt(n); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++){ zu[i]=(i-1)/block+1; }}void add(int u,int v){ edge[++cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt;}void DFS(int u,int depth,int pre){ L[u]=++Time;//记录u第一次到达的时间 ，当成u的编号，之后只用u的编号了 dep[depth].push_back(Time);//u的编号在深度为depth的编号集合中 ，把相同深度的编号放在一个集合中 de[Time]=depth;//保存一下编号Time的深度 ，de代表编号的深度 for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].v; if(v==pre) continue; DFS(v,depth+1,u); } R[u]=Time;//右边界，L和R就是一个线性的区间 }void change(int x,int b){ //暴力更新深度为x的所有点上的值 for(int i=0;i
                  
                   =block) ve.push_back(i); }/* for(int i=0;i

转载于:https://www.cnblogs.com/6262369sss/p/9732675.html

你可能感兴趣的文章