#include <stdio.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#define inf 1000000000
using namespace std;
#define getch() getchar()
inline int F() {register int aa , bb , ch;
while(ch = getch() , (ch<''||ch>'') && ch != '-'); ch == '-' ? aa=bb= : (aa=ch-'',bb=);
while(ch = getch() , ch>=''&&ch<='') aa = aa* + ch-''; return bb ? aa : -aa;
}
const int Maxn = ;
queue<int> q;
int n , m , root , sz;
int fa[Maxn] , c[Maxn][] , mx[Maxn] , lx[Maxn] , rx[Maxn] , v[Maxn] , size[Maxn] , sum[Maxn] , a[Maxn] , id[Maxn];
bool lazy[Maxn] , rev[Maxn]; void update(int x) {
int lc = c[x][] , rc = c[x][];
sum[x] = sum[lc] + sum[rc] + v[x];
size[x] = size[lc] + size[rc] + ;
mx[x] = max(mx[lc] , mx[rc]);
mx[x] = max(mx[x] , rx[lc]+v[x]+lx[rc]);
lx[x] = max(lx[lc] , sum[lc] + v[x] + lx[rc]);
rx[x] = max(rx[rc] , sum[rc] + v[x] + rx[lc]);
} void downpush(int x) {
int lc = c[x][] , rc = c[x][];
if(lazy[x]) {
rev[x] = lazy[x] = ;
if(lc) lazy[lc] = , v[lc] = v[x] , sum[lc] = v[x]*size[lc];
if(rc) lazy[rc] = , v[rc] = v[x] , sum[rc] = v[x]*size[rc];
if(v[x] >= ) {
if(lc) lx[lc] = rx[lc] = mx[lc] = sum[lc];
if(rc) lx[rc] = rx[rc] = mx[rc] = sum[rc];
}
else {
if(lc) lx[lc] = rx[lc] = , mx[lc] = v[x];
if(rc) lx[rc] = rx[rc] = , mx[rc] = v[x];
}
}
if(rev[x]) {
rev[x] = ;
rev[lc] ^= ;
rev[rc] ^= ;
swap(lx[lc] , rx[lc]);
swap(lx[rc] , rx[rc]);
c[x][] = rc;
c[x][] = lc;
swap(lx[x] , rx[x]);
}
} void rotate(int&root , int x) {
int y = fa[x] , z = fa[y] , p , q;
if(x == c[y][]) p = ; else p = ;
q = p^;
if(y == root) root = x;
else {
if(c[z][] == y) c[z][] = x;
else c[z][] = x;
}
fa[x] = z; fa[y] = x; fa[c[x][q]] = y;
c[y][p] = c[x][q]; c[x][q] = y;
update(y); update(x);
}
void splay(int&root , int x) {
int y , z;
while(x != root) {
y = fa[x] , z = fa[y];
if(y != root) {
if((x == c[y][]) ^ (y == c[z][])) rotate(root , x);
else rotate(root , y);
}
rotate(root , x);
}
} int find(int x , int rk) {
downpush(x);
int lc = c[x][] , rc = c[x][];
if(size[lc] + == rk) return x;
if(size[lc] >= rk) return find(lc , rk);
else return find(rc , rk-size[lc]-);
} void rec(int x) {
if(!x) return ;
int lc = c[x][] , rc = c[x][];
rec(lc);rec(rc);q.push(x);
fa[x] = c[x][] = c[x][] = lazy[x] = rev[x] = ;
} int split(int k , int tot) {
int x = find(root , k);
splay(root , x);
x = find(root , k+tot+);
splay(c[root][] , x);
return c[ c[root][] ][];
} void query(int k , int tot) {
int x = split(k , tot);
printf("%d\n",sum[x]);
} void modify(int k , int tot , int val) {
int x = split(k , tot) , y = fa[x];
v[x] = val; lazy[x] = ; sum[x] = size[x]*val;
if(val >= ) lx[x] = rx[x] = mx[x] = sum[x];
else lx[x] = rx[x] = , mx[x] = val;
update(y); update(fa[y]);
} void reverse(int k , int tot) {
int x = split(k , tot);
if(!lazy[x]) {
rev[x] ^= ;
downpush(x);
update(fa[x]);
update(fa[fa[x]]);
}
} void erase(int k , int tot) {
int x = split(k , tot) , y = fa[x];
rec(x); c[y][] = ;
update(y); update(fa[y]);
}
void build(int l,int r,int f)
{
if(l>r)return;
int mid=(l+r)>>,now=id[mid],last=id[f];
if(l==r)
{
sum[now]=a[l];size[now]=;
lazy[now]=rev[now]=;
if(a[l]>=)lx[now]=rx[now]=mx[now]=a[l];
else lx[now]=rx[now]=,mx[now]=a[l];
}
else build(l,mid-,mid),build(mid+,r,mid);
v[now]=a[mid];fa[now]=last;update(now);
c[last][mid>=f]=now;
}
void insert(int k,int tot)
{
for(int i=;i<=tot;i++)a[i]=F();
for(int i=;i<=tot;i++)
if(!q.empty())id[i]=q.front(),q.pop();
else id[i]=++sz;
build(,tot,);int z=id[(+tot)>>];
int x=find(root,k+),y=find(root,k+);
splay(root,x);splay(c[x][],y);
fa[z]=y;c[y][]=z;
update(y);update(x);
} int main() {
n = F(); m = F();
mx[] = a[] = a[n+] = -inf;
for(int i=; i<=n; ++i) {
a[i+] = F();
}
for(int i=;i<=n+;i++)id[i]=i;
build(,n+,);
root = (n+) >> ;sz = n + ;
int k , tot , val;
char ch[];
while(m--) {
scanf("%s",ch);
if(ch[]!='M' || ch[] != 'X') k = F() , tot = F();
if(ch[] == 'I') insert(k , tot);
if(ch[] == 'D') erase(k , tot);
if(ch[] == 'M') {
if(ch[] == 'X') printf("%d\n",mx[root]);
else val = F() , modify(k , tot , val);
}
if(ch[] == 'R') reverse(k , tot);
if(ch[] == 'G') query(k , tot);
}
}
Splay的核心操作
void rotate(int&root , int x) {
int y = fa[x] , z = fa[y] , p , q;
if(x == c[y][]) p = ; else p = ;
q = p^;
if(y == root) root = x;
else {
if(c[z][] == y) c[z][] = x;
else c[z][] = x;
}
fa[x] = z; fa[y] = x; fa[c[x][q]] = y;
c[y][p] = c[x][q]; c[x][q] = y;
update(y); update(x);
}
void splay(int&root , int x) {
int y , z;
while(x != root) {
y = fa[x] , z = fa[y];
if(y != root) {
if((x == c[y][]) ^ (y == c[z][])) rotate(root , x);
else rotate(root , y);
}
rotate(root , x);
}
}