BZOJ 1251: 序列终结者 [splay]

时间：2024-07-04 12:35:50

1251: 序列终结者

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 3778  Solved: 1583
[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

Sample Output

2
【数据范围】
N<=50000，M<=100000。
复习一下splay序列操作
rev翻转标记，打标记的节点还没进行
tag增加标记，打标记的节点已经进行了
然后这个序列一开始全0
然后那个print是debug用的
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

#define lc t[x].ch[0]

#define rc t[x].ch[1]

#define pa t[x].fa

const int N=1e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,op,l,r,v;

struct node{

    int fa,ch[],size,rev,mx,v,tag;

}t[N];

int root;

inline int wh(int x){return t[pa].ch[]==x;}

inline void update(int x){

    t[x].size=t[lc].size+t[rc].size+;

    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^=;

        if(rc) t[rc].rev^=;

        t[x].rev=;

    }

    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=;

    }

}

int build(int l,int r,int f){//printf("build %d %d %d\n",l,r,f);

    if(l>r) return ;

    int x=(l+r)>>;

    lc=build(l,x-,x);rc=build(x+,r,x);

    t[x].fa=f;

    t[x].rev=t[x].tag=;t[x].v=t[x].mx=;

    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^];t[t[f].ch[c]].fa=f;

    t[x].ch[c^]=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==) root=x;

}

inline int kth(int k){

    int ls=,x=root;

    while(x){

        pushDown(x);

        int _=ls+t[lc].size;

        if(_<k&&k<=_+) return x;

        if(k<=_) x=lc;

        else ls=_+,x=rc;

    }

    return -;

}

void add(int l,int r,int v){//printf("add %d %d %d\n",l,r,v);

    int p=kth(l);splay(p,);

    int x=kth(r+);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,);

    int x=kth(r+);splay(x,root);

    t[lc].rev^=;

}

void getmax(int l,int r){

    int p=kth(l);splay(p,);

    int x=kth(r+);splay(x,root);

    printf("%d\n",t[lc].mx);

}

void print(int x){

    if(x==) return;

    pushDown(x);

    if(lc) print(lc);

    if(x!=&&x!=n+) printf("%d ",t[x].v);

    if(rc) print(rc);

}

int main(){

    //freopen("in.txt","r",stdin);

    n=read();Q=read();

    t[].mx=-INF;

    root=build(,n+,);

    //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==){v=read();add(l,r,v);}

        else if(op==) rev(l,r);

        else if(op==) getmax(l,r);

        //print(root);puts("");

    }

}

相关文章