#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <queue>
#define oo 1000000000
#define lc(x) son[x][0]
#define rc(x) son[x][1]
using namespace std;
int i,j,k,n,m,s,t,ans;
];
struct node
{
int set,rever;
} tag[];
][];
];
];
];
];
];
];
];
];
queue <int> q;
int root,cnt,pos;
void update(int x)
{
size[x] = size[lc(x)]+size[rc(x)]+;
tsum[x] = tsum[lc(x)]+tsum[rc(x)]+key[x];
lmax[x] = max(lmax[lc(x)],tsum[lc(x)]+key[x]+lmax[rc(x)]);
rmax[x] = max(rmax[rc(x)],tsum[rc(x)]+key[x]+rmax[lc(x)]);
tmax[x] = max(max(tmax[lc(x)],tmax[rc(x)]),lmax[rc(x)]+key[x]+rmax[lc(x)]);
}
void Round(int x)
{
swap(lc(x),rc(x));
swap(lmax[x],rmax[x]);
}
void build(int l,int r,int &x)
{
if (l>r)
{
x = ;
return;
}
if (l==r)
{
if (!q.empty())
{
x = q.front();
q.pop();
} else x = ++cnt;
tag[x].rever = ;
tag[x].;
key[x] = tsum[x] = tmax[x] = a[l];
lmax[x] = rmax[x] = max(,a[l]);
size[x] = ;
lc(x) = rc(x) = ;
return;
}
;
if (!q.empty())
{
x = q.front();
q.pop();
} else x = ++cnt;
key[x] = a[mid];
tag[x].rever = ;
tag[x].;
lc(x) = rc(x) = ;
build(l,mid-,lc(x));
build(mid+,r,rc(x));
) fa[lc(x)] = x;
) fa[rc(x)] = x;
update(x);
}
void pushdown(int x)
{
)
{
tag[x].rever = ;
tag[lc(x)].rever ^= ;
tag[rc(x)].rever ^= ;
Round(lc(x));
Round(rc(x));
}
)
{
)
{
tag[lc(x)].set = tag[x].set;
key[lc(x)] = tag[x].set;
tsum[lc(x)] = tag[x].set*size[lc(x)];
) tmax[lc(x)] = lmax[lc(x)] = rmax[lc(x)] = tsum[lc(x)];
else
{
tmax[lc(x)] = tag[x].set;
lmax[lc(x)] = rmax[lc(x)] = ;
}
}
)
{
tag[rc(x)].set = tag[x].set;
key[rc(x)] = tag[x].set;
tsum[rc(x)] = tag[x].set*size[rc(x)];
) tmax[rc(x)] = lmax[rc(x)] = rmax[rc(x)] = tsum[rc(x)];
else
{
tmax[rc(x)] = tag[x].set;
lmax[rc(x)] = rmax[rc(x)] = ;
}
}
tag[x].;
}
}
int find(int x,int k)
{
pushdown(x);
==k) return x;
else if (size[lc(x)]>=k) return find(lc(x),k);
);
}
void rotate(int x)
{
int y = fa[x],z = fa[y],w = lc(y)==x;
pushdown(y);
pushdown(x);
fa[son[x][w]] = y;son[y][w^] = son[x][w];
fa[x] = z;) son[z][rc(z)==y] = x;
son[x][w] = y;fa[y] = x;
update(y);
update(x);
}
void splay(int x,int s)
{
pushdown(x);
while (fa[x]!=s)
{
int y = fa[x],z = fa[y];
if (z!=s) rotate(lc(z)==y^lc(y)==x?x:y);
rotate(x);
}
update(x);
) root = x;
}
void insert(int pos)
{
int z;
build(,n,z);
int x = find(root,pos);
);
splay(x,);
splay(y,root);
lc(y) = z;
fa[z] = y;
update(y);
update(x);
}
void del(int x)
{
) return;
del(lc(x));
q.push(x);
del(rc(x));
}
void erase(int pos,int n)
{
);
int y = find(root,pos+n);
splay(x,);
splay(y,root);
del(lc(y));
lc(y) = ;
update(y);
update(x);
}
int main()
{
scanf("%d%d",&n,&m);
a[] = a[n+] = -oo;
tmax[] = -oo;
;i<=n+;i++) scanf("%d",&a[i]);
build(,n+,root);
while (m--)
{
];
scanf();
]=='I')
{
scanf("%d%d",&pos,&n);
;i<=n;i++)
scanf("%d",&a[i]);
insert(pos+);
} ]=='D')
{
scanf("%d%d",&pos,&n);
erase(pos+,n);
} ]==]=='K')
{
int c;
scanf("%d%d%d",&pos,&n,&c);
int x = find(root,pos);
);
splay(x,);
splay(y,root);
tag[lc(y)].set = c;
key[lc(y)] = c;
tsum[lc(y)] = c*size[lc(y)];
) tmax[lc(y)] = lmax[lc(y)] = rmax[lc(y)] = tsum[lc(y)];
else
{
tmax[lc(y)] = c;
lmax[lc(y)] = rmax[lc(y)] = ;
}
update(y);
update(x);
} ]=='R')
{
scanf("%d%d",&pos,&n);
int x = find(root,pos);
);
splay(x,);
splay(y,root);
tag[lc(y)].rever ^= ;
Round(lc(y));
update(y);
update(x);
} ]=='G')
{
scanf("%d%d",&pos,&n);
int x = find(root,pos);
);
splay(x,);
splay(y,root);
printf("%d\n",tsum[lc(y)]);
} else printf("%d\n",tmax[root]);
}
;
}
BZOJ1500 维修数列