题目描述

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

题目分析

裸题

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[101000*3],size[101000*3],key[101000*3],lson[101000*3],rson[101000*3];
int add[101000*3],lazy[101000*3],maxx[101000*3];    
int tot,root;
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
    maxx[x]=val[x];
    if(lson[x]) maxx[x]=max(maxx[x],maxx[lson[x]]);
    if(rson[x]) maxx[x]=max(maxx[x],maxx[rson[x]]);
}
void pushdown(int x)
{
    if(add[x])
    {
        add[lson[x]]+=add[x],add[rson[x]]+=add[x];
        val[lson[x]]+=add[x],val[rson[x]]+=add[x];
        maxx[lson[x]]+=add[x],maxx[rson[x]]+=add[x];
        add[x]=0;
    }
    if(lazy[x])
    {
        swap(lson[x],rson[x]);
        lazy[lson[x]]^=1,lazy[rson[x]]^=1;
        lazy[x]=0;
    }
}
int merge(int x,int y)
{
    if(x==0||y==0) return x|y;
    pushdown(x),pushdown(y);
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        size[++tot]=1,key[tot]=rand()*rand(),val[tot]=0,root=merge(root,tot);
    for(int i=1;i<=m;i++)
    {
        int tmp,x,y,c;
        scanf("%d%d%d",&tmp,&x,&y);
        par t1,t2;
        t2=split(root,y);
        t1=split(t2.first,x-1);
        if(tmp==1)
        {
            scanf("%d",&c);
            add[t1.second]+=c,val[t1.second]+=c,maxx[t1.second]+=c;
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(tmp==2)
        {
            lazy[t1.second]^=1;
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(tmp==3)
        {
            printf("%d\n",maxx[t1.second]);
            root=merge(merge(t1.first,t1.second),t2.second);
        }   
    }
}