1251: 序列终结者
Time Limit: 20 Sec Memory Limit: 162 MBSubmit: 4431 Solved: 1875
[Submit][Status][Discuss]
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
1 1 3 2
1 2 4 -1
2 1 3
3 2 4
Sample Output
2
【数据范围】
N<=50000，M<=100000。
【数据范围】
N<=50000，M<=100000。
HINT
Source
很裸的splay
妈的，调了我一下午，太弱了
#include <bits/stdc++.h>
#define inf 10000010
#define ll long long
using namespace std;
inline int read(){
int x=0;int f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int MAXN=1e6+10;
namespace Splay{
struct splaytree{
int son[2],siz,delta,v,fa,id,rev,key,maxn;
}T[MAXN];
int tot,root,n,m,sz=0;
inline void update(int x){
if(x){
T[x].siz=1;
if(T[x].son[0]) T[x].siz+=T[T[x].son[0]].siz;
if(T[x].son[1]) T[x].siz+=T[T[x].son[1]].siz;
T[x].maxn=T[x].v;
if(T[x].son[1]) T[x].maxn=max(T[x].maxn,T[T[x].son[1]].maxn);
if(T[x].son[0]) T[x].maxn=max(T[x].maxn,T[T[x].son[0]].maxn);
}
}
inline void push_up(int x){
if(T[x].delta!=0){
T[T[x].son[0]].delta+=T[x].delta;T[T[x].son[1]].delta+=T[x].delta;
T[T[x].son[0]].v+=T[x].delta;T[T[x].son[1]].v+=T[x].delta;
T[T[x].son[0]].maxn+=T[x].delta;T[T[x].son[1]].maxn+=T[x].delta;
T[x].delta=0;
}
if(T[x].rev){
swap(T[x].son[0],T[x].son[1]);
T[T[x].son[1]].rev^=T[x].rev;
T[T[x].son[0]].rev^=T[x].rev;
T[x].rev=0;
}
}
inline int getfather(int x){
return x==T[T[x].fa].son[1];
}
inline void rota(int x){
int oldl=T[x].fa;int oldf=T[oldl].fa;int wei=getfather(x);
T[oldl].son[wei]=T[x].son[wei^1];T[T[x].son[wei^1]].fa=oldl;
T[x].son[wei^1]=oldl;T[oldl].fa=x;T[x].fa=oldf;
if(oldf){
T[oldf].son[oldl==T[oldf].son[1]]=x;
}
update(oldl);update(x);
}
inline void splay(int x,int tal){
for(int fa;(fa=T[x].fa)!=tal;rota(x)){
if(T[fa].fa!=tal){
rota(getfather(x)==getfather(fa)?fa:x);
}
}
if(tal==0) root=x;
}
inline int find(int x){
int now=root;
while(1){
push_up(now);
if(x<=T[T[now].son[0]].siz){
now=T[now].son[0];
}
else{
x-=T[T[now].son[0]].siz+1;
if(x==0) return now;
now=T[now].son[1];
}
}
}
inline int build(int leftt,int rightt,int root){
if(leftt>rightt) return 0;
int mid=(leftt+rightt)>>1;
int now=++sz;
T[now].fa=root;
T[now].id=mid;T[now].delta=0;T[now].v=0;T[now].rev=0;T[now].delta=0;T[now].maxn=0;
int lefttchild=build(leftt,mid-1,now);
int righttchild=build(mid+1,rightt,now);
T[now].son[0]=lefttchild;T[now].son[1]=righttchild;
update(now);
return now;
}
inline void insert(int leftt,int rightt,int vv){
leftt=find(leftt);rightt=find(rightt+2);
splay(leftt,0);splay(rightt,leftt);
int now=T[rightt].son[0];
T[now].delta+=vv; T[now].v+=vv;T[now].maxn+=vv;
}
inline void getmax(int leftt,int rightt){
leftt=find(leftt);rightt=find(rightt+2);
splay(leftt,0);splay(rightt,leftt);
int now=T[rightt].son[0];
printf("%d
",T[now].maxn);
}
inline void reserve(int leftt,int rightt){
if(leftt>=rightt) return;
leftt=find(leftt);rightt=find(rightt+2);
splay(leftt,0);splay(rightt,leftt);
int now=T[rightt].son[0];
T[now].rev^=1;
}
inline void print(){
for(int i=1;i<=n+2;i++){
cout<<T[i].fa<<' '<<T[i].v<<' '<<T[i].id<<' '<<T[i].maxn<<endl;
}
}
void init(){
n=read();m=read();
root=build(1,n+2,0);
}
void solve(){
while(m--){
int vv=read();
if(vv==1){
int leftt=read();int rightt=read();int vv=read();
insert(leftt,rightt,vv);
}
if(vv==2){
int leftt=read();int rightt=read();
reserve(leftt,rightt);
}
if(vv==3){
int leftt=read();int rightt=read();
getmax(leftt,rightt);
}
}
}
}
int main(){
//freopen("All.in","r",stdin);
//freopen("a.out","w",stdout);
using namespace Splay;
init();
solve();
return 0;
}