当前位置：网站首页>bzoj1251 序列终结者

bzoj1251 序列终结者

2022-08-08 16:22:00 【51CTO】

( http://www.elijahqi.win/2018/01/22/bzoj1251-%E5%BA%8F%E5%88%97%E7%BB%88%E7%BB%93%E8%80%85/%20%E2%80%8E)
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的一些基本操作注意0号节点的max1需要给-inf

       
       #include<cstdio>
       
#include<algorithm>
       
#define N 55000
       
#define inf 0x3f3f3f3f 
       
using namespace std;
       
inline char gc(){
       
    static char now[1<<16],*S,*T;
       
    if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
       
    return *S++;
       
}
       
inline int read(){
       
    int x=0,f=1;char ch=gc();
       
    while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();}
       
    while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
       
    return x*f;
       
}
       
int size[N],n,max1[N],c[N][2],rev[N],tag[N],fa[N],v[N],root,m;
       
inline void update(int x){
       
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
       
    max1[x]=max(max(max1[c[x][0]],max1[c[x][1]]),v[x]);
       
}
       
inline void pushdown(int x){
       
    int l=c[x][0],r=c[x][1];
       
    if (tag[x]){
       
        if (l) tag[l]+=tag[x],max1[l]+=tag[x],v[l]+=tag[x];
       
        if (r) tag[r]+=tag[x],max1[r]+=tag[x],v[r]+=tag[x];tag[x]=0;
       
    }
       
    if (rev[x]){
       
        if (l) rev[l]^=1,swap(c[l][1],c[l][0]);
       
        if (r) rev[r]^=1,swap(c[r][1],c[r][0]);rev[x]=0;
       
    }
       
}
       
inline void build(int f,int l,int r){
       
    if (l>r) return;
       
    if (l==r){size[l]=1;fa[l]=f;c[f][l>f]=l;return;}
       
    int mid=l+r>>1;build(mid,l,mid-1);build(mid,mid+1,r);
       
    fa[mid]=f;c[f][mid>f]=mid;update(mid);
       
}
       
inline int find(int x,int sz){
       
    pushdown(x);
       
    int l=c[x][0],r=c[x][1];
       
    if (size[l]+1==sz) return x;
       
    if (sz<=size[l]) return find(l,sz);else return find(r,sz-size[l]-1);
       
}
       
inline void rotate(int x,int &tar){
       
    int y=fa[x],z=fa[y];
       
    int l=c[y][1]==x,r=l^1;
       
    if (y==tar) tar=x;else c[z][c[z][1]==y]=x;
       
    fa[c[x][r]]=y;fa[y]=x;fa[x]=z;
       
    c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
       
}
       
inline void splay(int x,int &tar){
       
    while(x!=tar){
       
        int y=fa[x],z=fa[y];
       
        if (y!=tar){
       
            if ((c[y][0]==x)^(c[z][0]==y)) rotate(x,tar);else rotate(y,tar);
       
        }rotate(x,tar);
       
    }
       
}
       
inline int split(int x,int y){
       
    int xx=find(root,x),yy=find(root,y);
       
    splay(yy,root);splay(xx,c[root][0]);return c[xx][1];
       
}
       
inline void print(int x){
       
    if (c[x][0]) print(c[x][0]);
       
    printf("%d %d %d %d %d %d %d\n",x,c[x][0],c[x][1],v[x],max1[x],tag[x],rev[x]);
       
    if (c[x][1]) print(c[x][1]);
       
}
       
int main(){
       
    freopen("bzoj1251.in","r",stdin);
       
    n=read();m=read();build(0,1,n+2);root=n+3>>1;
       
    max1[0]=-inf;
       
    for (int i=1;i<=m;++i){
       
        int op=read();//print(root);puts("fds");
       
        if (op==1){
       
            int x=read(),y=read(),vv=read();
       
            int tmp=split(x,y+2);tag[tmp]+=vv;v[tmp]+=vv;max1[tmp]+=vv;
       
        }
       
        if (op==2){
       
            int x=read(),y=read();
       
            int tmp=split(x,y+2);rev[tmp]^=1;swap(c[tmp][0],c[tmp][1]);
       
        }   
       
        if (op==3){
       
            int x=read(),y=read();
       
            int tmp=split(x,y+2);printf("%d\n",max1[tmp]);
       
        }
       
    }
       
    return 0;
       
}
      
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15744996/5556235

当前位置：网站首页>bzoj1251 序列终结者

bzoj1251 序列终结者

边栏推荐

猜你喜欢

随机推荐