【FHQ-Treap】P4146 序列终结者

题意：

　　给定一个序列，支持区间加，区间反转，区间max询问

裸的平衡树题，这里采用FHQ-Treap

每个节点多记录一个max值和两个lazy_tag，暴力Push_Down即可（大常数选手）

打完这道模板题可怜的Leven就要去准备初赛了qwq

 1 #include<bits/stdc++.h>
 2 #define writeln(x)  write(x),puts("")
 3 #define writep(x)   write(x),putchar(' ')
 4 using namespace std;
 5 inline int read(){
 6     int ans=0,f=1;char chr=getchar();
 7     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 8     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
 9     return ans*f;
10 }void write(int x){
11     if(x<0) putchar('-'),x=-x;
12     if(x>9) write(x/10);
13     putchar(x%10+'0');
14 }const int M = 1e5+5;
15 struct P{int l,r,sz,x,s,lz1,lz2,key;}s[M];
16 int n,m,a[M],root,x,y,z,cnt;
17 inline void Push_Up(int x){
18     s[x].sz=s[s[x].l].sz+s[s[x].r].sz+1;
19     s[x].s=s[x].x;
20     if(s[x].l)s[x].s=max(s[x].s,s[s[x].l].s);
21     if(s[x].r)s[x].s=max(s[x].s,s[s[x].r].s);
22 }inline void Push_Down1(int x){
23     if(!s[x].lz1)return;
24     swap(s[x].l,s[x].r);
25     s[s[x].l].lz1^=1;
26     s[s[x].r].lz1^=1;
27     s[x].lz1=0;
28 }inline void Push_Down2(int x){
29     Push_Down1(x);
30     if(!s[x].lz2)return;
31     s[s[x].l].lz2+=s[x].lz2;
32     s[s[x].l].x+=s[x].lz2;
33     s[s[x].r].lz2+=s[x].lz2;
34     s[s[x].l].s+=s[x].lz2;
35     s[s[x].r].x+=s[x].lz2;
36     s[s[x].r].s+=s[x].lz2;
37     s[x].lz2=0;
38 }inline int Merge(int x,int y){
39     if(!x||!y)return x+y;
40     Push_Down2(x),Push_Down2(y);
41     if(s[x].key<s[y].key){
42         s[x].r=Merge(s[x].r,y);
43         Push_Up(x);return x;
44     }s[y].l=Merge(x,s[y].l);
45     Push_Up(y);return y;
46 }inline void Split(int now,int sz,int &x,int &y){
47     if(!now)return x=y=0,void();
48     Push_Down2(now);
49     if(s[s[now].l].sz>=sz)y=now,Split(s[now].l,sz,x,s[now].l);
50     else x=now,Split(s[now].r,sz-s[s[now].l].sz-1,s[now].r,y);
51     Push_Up(now);
52 }inline void Add(){
53     int l=read(),r=read(),p=read();
54     Split(root,l-1,x,y),Split(y,r-l+1,y,z);
55     s[y].lz2+=p;s[y].s+=p;s[y].x+=p;
56     root=Merge(Merge(x,y),z);
57 }inline void Reverse(){
58     int l=read(),r=read();
59     Split(root,l-1,x,y),Split(y,r-l+1,y,z);
60     s[y].lz1^=1;
61     root=Merge(Merge(x,y),z);
62 }inline void Query(){
63     int l=read(),r=read();
64     Split(root,l-1,x,y),Split(y,r-l+1,y,z);
65     printf("%d
",s[y].s);
66     root=Merge(Merge(x,y),z);
67 }inline void Insert(int val){
68     s[++cnt]=(P){0,0,1,val,val,0,0,rand()};
69     root=Merge(cnt,root);
70 }int main(){
71     srand(unsigned(time(0)));
72     n=read(),m=read();
73     for(int i=1;i<=n;i++)Insert(0);
74     while(m--){
75         int opt=read();
76         if(opt==1)Add();
77         else if(opt==2)Reverse();
78         else Query();
79     }return 0;
80 }