蛋疼的splay
维护信息：子树中：{左起最大值，右起最大值，最大值，和}
其他的和普通spaly一样，试了试自顶向下的，貌似冬哥的同样的数组版自底向上要快一点点 囧
注意maintain中要多些一些东西，翻转的时候要先交换 左起最大值和右起最大值 而不是等down的时候再交换！
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<string> 7 #include<cmath> 8 #include<ctime> 9 #include<queue> 10 #include<stack> 11 #include<map> 12 #include<set> 13 #define rre(i,r,l) for(int i=(r);i>=(l);i--) 14 #define re(i,l,r) for(int i=(l);i<=(r);i++) 15 #define Clear(a,b) memset(a,b,sizeof(a)) 16 #define inout(x) printf("%d",(x)) 17 #define douin(x) scanf("%lf",&x) 18 #define strin(x) scanf("%s",(x)) 19 #define LLin(x) scanf("%lld",&x) 20 #define op operator 21 #define CSC main 22 typedef unsigned long long ULL; 23 typedef const int cint; 24 typedef long long LL; 25 using namespace std; 26 int inf=2147483647; 27 void inin(int &ret) 28 { 29 ret=0;int f=0;char ch=getchar(); 30 while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();} 31 while(ch>='0'&&ch<='9')ret*=10,ret+=ch-'0',ch=getchar(); 32 ret=f?-ret:ret; 33 } 34 int H[500010],top; 35 int ch[500050][2],w[500050],s[500050],rev[500050],add[500050]; 36 int root,ll[500050],rr[500050],Max[500050],sum[500050]; 37 void maintain(int k) 38 { 39 if(!k)return ; 40 s[k]=s[ch[k][0]]+s[ch[k][1]]+1; 41 sum[k]=sum[ch[k][0]]+sum[ch[k][1]]+w[k]; 42 ll[k]=max(ll[ch[k][0]],w[k]+sum[ch[k][0]]+ll[ch[k][1]]); 43 rr[k]=max(rr[ch[k][1]],w[k]+sum[ch[k][1]]+rr[ch[k][0]]); 44 Max[k]=max(max(Max[ch[k][0]],Max[ch[k][1]]),rr[ch[k][0]]+w[k]+ll[ch[k][1]]); 45 } 46 void addtag(int k,int v) 47 { 48 if(!k)return ; 49 add[k]=w[k]=v; 50 sum[k]=s[k]*v; 51 if(v>=0)Max[k]=ll[k]=rr[k]=s[k]*v; 52 else Max[k]=v,ll[k]=rr[k]=0; 53 } 54 void down(int k) 55 { 56 if(!k)return ; 57 if(add[k]>-inf) 58 { 59 addtag(ch[k][0],add[k]); 60 addtag(ch[k][1],add[k]); 61 add[k]=-inf; 62 } 63 if(rev[k]) 64 { 65 swap(ch[k][0],ch[k][1]); 66 swap(ll[ch[k][0]],rr[ch[k][0]]); 67 swap(ll[ch[k][1]],rr[ch[k][1]]); 68 rev[ch[k][0]]^=1,rev[ch[k][1]]^=1; 69 rev[k]=0; 70 } 71 } 72 int newnode(int v) 73 { 74 int ret=H[top--]; 75 s[ret]=1,Max[ret]=sum[ret]=w[ret]=v; 76 if(v>=0)ll[ret]=rr[ret]=v; 77 else ll[ret]=rr[ret]=0; 78 add[ret]=-inf,rev[ret]=0; 79 return ret; 80 } 81 int com(int k,int kk) 82 { 83 int pp=s[ch[k][0]]+1; 84 if(kk==pp)return -1; 85 return kk<pp?0:1; 86 } 87 void init() 88 { 89 top=500000; 90 re(i,1,500000)H[i]=top-i+1; 91 Max[0]=-inf; 92 } 93 void rotate(int &k,int d) 94 { 95 int p=ch[k][!d]; 96 ch[k][!d]=ch[p][d]; 97 ch[p][d]=k; 98 maintain(k); 99 maintain(p);k=p; 100 } 101 void splay(int &k,int f) 102 { 103 down(k); 104 int d=com(k,f); 105 if(d==-1)return ; 106 if(d==1)f-=s[ch[k][0]]+1; 107 int &c=ch[k][d]; 108 down(c); 109 int d2=com(c,f); 110 if(d2!=-1) 111 { 112 if(d2==1)f-=s[ch[c][0]]+1; 113 splay(ch[c][d2],f); 114 if(d==d2)rotate(k,!d); 115 else rotate(c,!d2); 116 } 117 rotate(k,!d); 118 } 119 void split(int k,int x,int &L,int &R) 120 { 121 splay(k,x); 122 L=k,R=ch[k][1]; 123 ch[k][1]=0; 124 maintain(k); 125 } 126 int merge(int l,int r) 127 { 128 splay(l,s[l]); 129 ch[l][1]=r; 130 maintain(l); 131 return l; 132 } 133 int a[500050]; 134 void build(int &k,int l,int r) 135 { 136 if(l>r)return k=0,void(); 137 int mid=(l+r)>>1; 138 k=newnode(a[mid]); 139 build(ch[k][0],l,mid-1); 140 build(ch[k][1],mid+1,r); 141 maintain(k); 142 } 143 void del(int &k) 144 { 145 if(!k)return ; 146 del(ch[k][0]); 147 del(ch[k][1]); 148 H[++top]=k; 149 k=0; 150 } 151 //void print(int k) 152 //{ 153 // if(!k)return ; 154 // down(k); 155 // print(ch[k][0]); 156 // printf("%d ",w[k]); 157 // print(ch[k][1]); 158 //} 159 int n,m; 160 int CSC() 161 { 162 freopen("in.in","r",stdin); 163 inin(n),inin(m); 164 re(i,1,n)inin(a[i]); 165 init(); 166 build(root,0,n); 167 char opt[22]; 168 int q,ww,mid,l,r,k,c; 169 re(i,1,m) 170 { 171 strin(opt); 172 if(opt[0]=='M'&&opt[2]=='X') 173 { 174 splay(root,1); 175 printf("%d ",Max[ch[root][1]]); 176 } 177 else 178 { 179 inin(q),inin(ww); 180 if(!ww) 181 { 182 if(opt[0]=='G')puts("0"); 183 continue; 184 } 185 if(opt[0]=='I') 186 { 187 re(i,1,ww)inin(a[i]); 188 build(mid,1,ww); 189 split(root,q+1,l,r); 190 root=merge(merge(l,mid),r); 191 continue; 192 } 193 split(root,q,l,k); 194 split(k,ww,mid,r); 195 if(opt[0]=='D') 196 { 197 del(mid); 198 root=merge(l,r); 199 } 200 else 201 { 202 if(opt[0]=='M') 203 { 204 inin(c); 205 addtag(mid,c); 206 } 207 else if(opt[0]=='R')rev[mid]^=1,swap(ll[mid],rr[mid]); 208 else printf("%d ",sum[mid]); 209 root=merge(merge(l,mid),r); 210 } 211 } 212 } 213 return 0; 214 }