【题目简介】
Description
网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列 要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样 我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列，每个序列的元素是一个整数（废话）。要支持以下三种操作： 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转，比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。
Input
第一行两个整数N，M。M为操作个数。 以下M行，每行最多四个整数，依次为K，L，R，V。K表示是第几种操作，如果不是第1种操作则K后面只有两个数。
Output
对于每个第3种操作，给出正确的回答。
Sample Input
4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
Sample Output
2
【数据范围】
N<=50000，M<=100000。
HINT
Source
【题解】
对此窝还能说什么呢。。。
由于之前的模板写得过于臭长，于是参考（抄写）了Hzwer的Splay模板。
【Codes】
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=100010;
int n,m,i,cnt,root,l,r,x,opt;
int fa[M],son[M][2],tag[M],rev[M],data[M],size[M],mx[M];
void pushup(int p){
int l=son[p][0],r=son[p][1];
mx[p]=max(max(mx[l],mx[r]),data[p]);
size[p]=size[l]+size[r]+1;
}
void pushdown(int p){
int l=son[p][0],r=son[p][1],t=tag[p];
if (t){
tag[p]=0;
if (l){tag[l]+=t;mx[l]+=t;data[l]+=t;}
if (r){tag[r]+=t;mx[r]+=t;data[r]+=t;}
}
if (rev[p]){
rev[p]=0;
rev[l]^=1;rev[r]^=1;
swap(son[p][0],son[p][1]);
}
}
void build(int l,int r,int p){
if(l>r)return;
if (l==r){
fa[l]=p;size[l]=1;
if (l<p)son[p][0]=l;else son[p][1]=l;
return;
}
int mid=l+r>>1;
build(l,mid-1,mid);
build(mid+1,r,mid);
fa[mid]=p;pushup(mid);
if (mid<p)son[p][0]=mid;else son[p][1]=mid;
}
void rotate(int x,int &k){
int y=fa[x],z=fa[y],l,r;
if (son[y][0]==x)l=0;else l=1;r=l^1;
if (y==k)k=x;
else {if (son[z][0]==y)son[z][0]=x;else son[z][1]=x;}
fa[x]=z;fa[y]=x;fa[son[x][r]]=y;
son[y][l]=son[x][r];son[x][r]=y;
pushup(y);pushup(x);
}
void splay(int x,int &k){
while (x!=k){
int y=fa[x],z=fa[y];
if (y!=k){
if (son[y][0]==x^son[z][0]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int findkth(int k,int rank){
if (tag[k]||rev[k])pushdown(k);
int l=son[k][0],r=son[k][1];
if (size[l]+1==rank)return k;
else if (size[l]>=rank)return findkth(l,rank);
else return findkth(r,rank-size[l]-1);
}
void update(int l,int r,int val){
int x=findkth(root,l),y=findkth(root,r+2);
splay(x,root);splay(y,son[x][1]);
int z=son[y][0];
tag[z]+=val;data[z]+=val;mx[z]+=val;
}
void reverse(int l,int r){
int x=findkth(root,l),y=findkth(root,r+2);
splay(x,root);splay(y,son[x][1]);
int z=son[y][0];
rev[z]^=1;
}
void query(int l,int r){
int x=findkth(root,l),y=findkth(root,r+2);
splay(x,root);splay(y,son[x][1]);
int z=son[y][0];
printf("%d\n",mx[z]);
}
int main(){
mx[0]=-1000000007;
scanf("%d%d",&n,&m);
build(1,n+2,0);root=(n+3)>>1;cnt=n+2;
for (i=1;i<=m;i++){
scanf("%d",&opt);
switch(opt){
case 1:scanf("%d%d%d",&l,&r,&x);update(l,r,x);break;
case 2:scanf("%d%d",&l,&r);reverse(l,r);break;
case 3:scanf("%d%d",&l,&r);query(l,r);break;
}
}
}
评论 (0)
