1500: [NOI2005]维修数列
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 15112 Solved: 4996
[Submit][Status][Discuss]
Description
Input
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
HINT
题解
非常恶心的一道题。。。
用fhq Treap完成的话
1、把原有的平衡树从pos处拆开，把新加的点新建一颗小平衡树合并进去
2、把原有平衡树从pos和pos+num处拆开，合并左右中间不要【但是记得回收下标】
3、把原有平衡树从pos和pos+num处拆开，在中间打上标记cov
4、把原有平衡树从pos和pos+num处拆开，在中间打上标记mark
5、把原有平衡树从pos和pos+num处拆开，输出sum[中间]
6、输出ma[rt];
【注意fhq Treap的lazy标记和线段树的不一样，线段树的标记是标而不改，fhq Treap是标时即改，不然在split和merge时可能不会改变之前标记的根节点】
注：spli是我校大神，用函数名调戏一下他hhh
代码
//by 减维
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<map>
#include<bitset>
#include<algorithm>
#define inf 1<<30
#define ll long long
using namespace std; int n,m,rt,sz,siz[],son[][],val[],lm[],rm[],ma[],sum[],mark[],cov[],pri[];
int a[];
char ch[];
queue<int>q; int newnode(int v)
{
int x;
if(!q.empty())
x=q.front(),q.pop();
else x=++sz;
siz[x]=;
son[x][]=son[x][]=mark[x]=;
cov[x]=inf;pri[x]=rand();
val[x]=sum[x]=ma[x]=v;
lm[x]=rm[x]=v;
return x;
} void upda(int x)
{
if(!x)return ;
siz[x]=siz[son[x][]]+siz[son[x][]]+;
sum[x]=sum[son[x][]]+sum[son[x][]]+val[x];
ma[x]=max(max(,rm[son[x][]])+val[x]+max(,lm[son[x][]]),max(ma[son[x][]],ma[son[x][]]));
lm[x]=max(lm[son[x][]],sum[son[x][]]+val[x]+max(,lm[son[x][]]));
rm[x]=max(rm[son[x][]],sum[son[x][]]+val[x]+max(,rm[son[x][]]));
} void covered(int x,int v)
{
val[x]=v;
sum[x]=siz[x]*v;
lm[x]=rm[x]=max(,sum[x]);
ma[x]=max(sum[x],val[x]);
cov[x]=v;
} void zhuan(int now)
{
swap(son[now][],son[now][]);
swap(lm[now],rm[now]);
mark[now]^=;
} void pd(int now)
{
if(mark[now]){
if(son[now][])zhuan(son[now][]);
if(son[now][])zhuan(son[now][]);
}
if(cov[now]!=inf){
if(son[now][])covered(son[now][],cov[now]);
if(son[now][])covered(son[now][],cov[now]);
}
mark[now]=;cov[now]=inf;
} int build(int l,int r)
{
if(l>r)return ;
int mid=(l+r)>>,v=a[mid];
int now=newnode(v);
son[now][]=build(l,mid-);
son[now][]=build(mid+,r);
upda(now);
return now;
} void dfs(int now)
{
if(!now)return;
dfs(son[now][]);
printf("%d ",val[now]);
dfs(son[now][]);
} void spli(int now,int k,int &x,int &y)
{
if(!now)x=y=;
else{
pd(now);
if(k<=siz[son[now][]])
y=now,spli(son[now][],k,x,son[now][]);
else
x=now,spli(son[now][],k-siz[son[now][]]-,son[now][],y);
upda(now);
}
} int merge(int x,int y)
{
if(!x||!y)return x+y;
pd(x),pd(y);
if(pri[x]<pri[y])
{
son[x][]=merge(son[x][],y);
upda(x);
return x;
}else{
son[y][]=merge(x,son[y][]);
upda(y);
return y;
}
} void rudui(int x)
{
if(!x)return ;
q.push(x);
rudui(son[x][]);
rudui(son[x][]);
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)scanf("%d",&a[i]);
sum[]=siz[]=mark[]=cov[]=;
ma[]=val[]=-inf;
rt=build(,n);
int pos,num,x,y,z,k,b,c,d;
for(int i=;i<=m;++i)
{
//dfs(rt);printf("\n");
scanf("%s",ch+);
if (ch[]=='I'){
scanf("%d %d",&pos,&num);
for(int i=;i<=num;++i)scanf("%d",&a[i]);
z=build(,num);
spli(rt,pos,x,y);
rt=merge(merge(x,z),y);
}else if (ch[]=='D'){
scanf("%d%d",&pos,&num);
spli(rt,pos-,x,y);
spli(y,num,b,c);
rt=merge(x,c);
rudui(b);//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
}else if (ch[]=='M' && ch[] =='K'){
scanf("%d%d%d",&pos,&num,&k);
spli(rt,pos-,x,y);
spli(y,num,b,c);
covered(b,k);
rt=merge(x,merge(b,c));
}else if (ch[]=='R'){
scanf("%d%d",&pos,&num);
spli(rt,pos-,x,y);
spli(y,num,b,c);
zhuan(b);
rt=merge(x,merge(b,c));
}else if (ch[]=='G'){
scanf("%d%d",&pos,&num);
spli(rt,pos-,x,y);
spli(y,num,b,c);
printf("%d\n",sum[b]);
rt=merge(x,merge(b,c));
}else{
printf("%d\n",ma[rt]);
}
}
return ;
}