1251. 序列终结者【平衡树-splay】-白红宇

1251. 序列终结者【平衡树-splay】

阅读量：5834 次

发布时间：2019-06-18

本文共 4023 字，大约阅读时间需要 13 分钟。

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

【数据范围】

N<=50000，M<=100000。

splay区间操作模板

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
          5 #define MAXN (1000000+10)  6 using namespace std;  7 int Father[MAXN];  8 int Son[MAXN][2];  9 int Key[MAXN]; 10 int Size[MAXN]; 11 int Root,sz,n,m; 12 int Max[MAXN],Val[MAXN],Add[MAXN],Rev[MAXN]; 13 using namespace std; 14  15 inline int Get(int x) 16 { 17     return Son[Father[x]][1]==x; 18 } 19  20 inline void Update(int x) 21 { 22     Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1; 23     Max[x]=max(Val[x],max(Max[Son[x][0]],Max[Son[x][1]])); 24 } 25  26 inline void Pushdown(int x) 27 { 28     if (Add[x]) 29     { 30         if (Son[x][0]) 31         { 32             Max[Son[x][0]]+=Add[x]; 33             Val[Son[x][0]]+=Add[x]; 34             Add[Son[x][0]]+=Add[x]; 35         } 36         if (Son[x][1]) 37         { 38             Max[Son[x][1]]+=Add[x]; 39             Val[Son[x][1]]+=Add[x]; 40             Add[Son[x][1]]+=Add[x]; 41         } 42         Add[x]=0; 43     } 44     if (Rev[x]) 45     { 46         Rev[x]=0; 47         swap(Son[x][0],Son[x][1]); 48         Rev[Son[x][0]]^=1; 49         Rev[Son[x][1]]^=1;     50     } 51 } 52  53 inline void Rotate(int x) 54 { 55     Pushdown(Father[x]); 56     Pushdown(x); 57     int wh=Get(x); 58     int fa=Father[x],fafa=Father[fa]; 59     Son[fa][wh]=Son[x][wh^1]; 60     Father[fa]=x; 61     if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 62     Son[x][wh^1]=fa; 63     Father[x]=fafa; 64     if (fafa) Son[fafa][Son[fafa][1]==fa]=x; 65     Update(fa); 66     Update(x); 67 } 68  69 inline void Splay(int x,int tar) 70 { 71     for (int fa;(fa=Father[x])!=tar;Rotate(x)) 72         if (Father[fa]!=tar) 73             Rotate(Get(fa)==Get(x)?fa:x); 74     if (!tar) Root=x; 75 } 76  77 void Build(int l,int r,int fa) 78 { 79     if (l>r) return; 80     if (l==r) 81     { 82         Size[l]=1; 83         Father[l]=fa; 84         Son[fa][l>fa]=l; 85         return; 86     } 87     int mid=(l+r)>>1; 88     Build(l,mid-1,mid); 89     Build(mid+1,r,mid); 90     Father[mid]=fa; 91     Son[fa][mid>fa]=mid; 92     Update(mid); 93 } 94  95 int Findx(int x) 96 { 97     int now=Root; 98     while (1) 99     {100         Pushdown(now);101         if (Size[Son[now][0]]>=x)102             now=Son[now][0];103         else104         {105             x-=Size[Son[now][0]];106             if (x==1)107             {108                 Splay(now,0);109                 return now;110             }111             x--;112             now=Son[now][1];113         }114     }115 }116 117 inline int Split(int x,int y)118 {119     int xx=Findx(x),yy=Findx(y);120     Splay(xx,0);121     Splay(yy,xx);122     return Son[yy][0];123 }124 125 int main()126 {127     int p,l,r,x;128     scanf("%d%d",&n,&m);129     Build(1,n+2,0);130     Root=(n+3)>>1;131     Max[0]=-0x7fffffff;132     for (int i=1;i<=m;++i)133     {134         scanf("%d",&p);135         if (p==1)136         {137             scanf("%d%d%d",&l,&r,&x);138             int node=Split(l,r+2);139             Val[node]+=x; 140             Max[node]+=x; 141             Add[node]+=x;142         }143         if (p==2)144         {145             scanf("%d%d",&l,&r);146             int node=Split(l,r+2);147             Rev[node]^=1;148         }149         if (p==3)150         {151             scanf("%d%d",&l,&r);152             int node=Split(l,r+2);153             printf("%d\n",Max[node]);154         }155     }156 }

转载于:https://www.cnblogs.com/refun/p/8679181.html

你可能感兴趣的文章