1251: 序列终结者

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 3778  Solved: 1583

[][][]

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。

---

复习一下splay序列操作

rev翻转标记，打标记的节点还没进行

tag增加标记，打标记的节点已经进行了

然后这个序列一开始全0

然后那个print是debug用的

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;typedef long long ll;#define lc t[x].ch[0]#define rc t[x].ch[1]#define pa t[x].faconst int N=1e5+5,INF=1e9;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1; c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}    return x*f;}int n,Q,op,l,r,v;struct node{    int fa,ch[2],size,rev,mx,v,tag;}t[N];int root;inline int wh(int x){
    return t[pa].ch[1]==x;}inline void update(int x){    t[x].size=t[lc].size+t[rc].size+1;    t[x].mx=max(t[x].v,max(t[lc].mx,t[rc].mx));}inline void pushDown(int x){    if(t[x].rev){        swap(lc,rc);        if(lc) t[lc].rev^=1;        if(rc) t[rc].rev^=1;        t[x].rev=0;    }    if(t[x].tag){        int v=t[x].tag;        if(lc) t[lc].tag+=v,t[lc].v+=v,t[lc].mx+=v;        if(rc) t[rc].tag+=v,t[rc].v+=v,t[rc].mx+=v;        t[x].tag=0;    }}int build(int l,int r,int f){
    //printf("build %d %d %d\n",l,r,f);    if(l>r) return 0;    int x=(l+r)>>1;    lc=build(l,x-1,x);rc=build(x+1,r,x);    t[x].fa=f;    t[x].rev=t[x].tag=0;t[x].v=t[x].mx=0;    update(x);    return x;}inline void rotate(int x){    int f=t[x].fa,g=t[f].fa,c=wh(x);    if(g) t[g].ch[wh(f)]=x;t[x].fa=g;    t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f;    t[x].ch[c^1]=f;t[f].fa=x;    update(f);update(x);}void splay(int x,int tar){    for(;t[x].fa!=tar;rotate(x))        if(t[pa].fa!=tar) rotate(wh(x)==wh(pa)?pa:x);    if(tar==0) root=x;}inline int kth(int k){    int ls=0,x=root;    while(x){        pushDown(x);        int _=ls+t[lc].size;        if(_
           
            <=_+1) return x; if(k<=_) x=lc; else ls=_+1,x=rc; } return -1;}void add(int l,int r,int v){ //printf("add %d %d %d\n",l,r,v); int p=kth(l);splay(p,0); int x=kth(r+2);splay(x,root); t[lc].tag+=v;t[lc].v+=v;t[lc].mx+=v;}void rev(int l,int r){ int p=kth(l);splay(p,0); int x=kth(r+2);splay(x,root); t[lc].rev^=1;}void getmax(int l,int r){ int p=kth(l);splay(p,0); int x=kth(r+2);splay(x,root); printf("%d\n",t[lc].mx);}void print(int x){ if(x==0) return; pushDown(x); if(lc) print(lc); if(x!=1&&x!=n+2) printf("%d ",t[x].v); if(rc) print(rc);}int main(){ //freopen("in.txt","r",stdin); n=read();Q=read(); t[0].mx=-INF; root=build(1,n+2,0); //for(int i=1;i<=n+2;i++) printf("hi %d %d %d\n",i,t[i].v,t[i].size); while(Q--){ op=read();l=read();r=read(); if(op==1){v=read();add(l,r,v);} else if(op==2) rev(l,r); else if(op==3) getmax(l,r); //print(root);puts(""); }}