BZOJ 3159: 决战

1 sec 512MB

题意：

给你一颗\(n\)个点，初始点权为\(0\)的有跟树，要求支持

• Increase x y w 将路径\(x\)到\(y\)所有点点权加上\(w\)
• Sum x y 询问路径\(x\)到\(y\)的点权和
• Major x y 询问从路径\(x\)到\(y\)最大点权
• Minor x y 询问最小点权
• Invert x y 将路径上的点权翻转

有个性质，修改操作一定满足\(x\)为\(y\)祖先或者\(y\)为\(x\)祖先（实际没什么用处）

\(n\le 50000,|w|\le 1000\)

输入格式

第一行有三个整数\(N\)、\(M\)和\(R\)，分别表示树的节点数、指令和询问总数，以及树的跟。

接下来\(N-1\)行，每行两个整数\(u\)和\(v\)，表示一条边。

接下来\(M\)行，每行描述一个指令或询问，格式见题意描述。

输出格式

对于每个询问操作，输出所求的值。

---

老年菜鸡选手实在写不动大数据结构题...

有两个做法，暂时只写了一种，有可能一会儿会把另一种补充一下。

考虑树链剖分，但是不能维护翻转

考虑平衡树可以维护翻转

于是我们可以拿平衡树维护树剖的每条链

然后每次修改只有\(\log\)条链，我们把每条链要修改的地方拎出来，然后塞到一个平衡树里面，打一个翻转tag，再塞回去就可以了

用fhqtreap实现起来比较方便

说起来蛮简单，写起来还是蛮难受的的

---

Code:

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define ll long longconst int SIZE=1<<21;char ibuf[SIZE],*iS,*iT;//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iS++)#define gc() getchar()template 
        
         void read(T &x){    int f=0;x=0;char c=gc();    while(!isdigit(c)) f|=c=='-',c=gc();    while(isdigit(c)) x=x*10+c-'0',c=gc();    if(f) x=-x;}void reads(char *s){    int k=0;char c=gc();    while(c<'A'||c>'Z') c=gc();    while((c>='a'&&c<='z')||(c>='A'&&c<='Z')) s[k++]=c,c=gc();}const int N=5e4+10;inline void ckmax(int &x,int y){x=x>y?x:y;}inline void ckmin(int &x,int y){x=x
         
          dep[top[y]]) { ret+=querysum(num[x],1,rk[x]); x=par[top[x]]; } else { ret+=querysum(num[y],1,rk[y]); y=par[top[y]]; } } if(dep[x]
          
           dep[top[y]]) { ckmax(ret,querymx(num[x],1,rk[x])); x=par[top[x]]; } else { ckmax(ret,querymx(num[y],1,rk[y])); y=par[top[y]]; } } if(dep[x]
           
            dep[top[y]]) { ckmin(ret,querymi(num[x],1,rk[x])); x=par[top[x]]; } else { ckmin(ret,querymi(num[y],1,rk[y])); y=par[top[y]]; } } if(dep[x]
           
          
         
        
       
      
     
    

---

2019.5.22