首页 > 代码库 > BZOJ1251·序列终结者

BZOJ1251·序列终结者

2024-07-13 14:03:30   218人阅读

好像不能附传送门了。。这是道sb权限题。。

1251: 序列终结者

Time Limit: 20 Sec  Memory Limit: 162 MB

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，维护区间最大值，翻转信息。
学习了链式建树，但是后来实验发现nlogn建树和链式建树效率基本相同（链式建树后面需要反转的次数较多）
HINT:T[0].Max = -2147483647,这点很重要。。如果某点没有前驱，那么更新最大值的时候。。→＿→
Codes:
  1 #include <set>  2 #include <queue>  3 #include <cmath>  4 #include <cstdio>  5 #include <cstdlib>  6 #include <cstring>  7 #include <iostream>  8 #include <algorithm>  9 using namespace std; 10 const int N = 50010; 11 #define fa(i) T[i].p 12 #define L(i) T[i].s[0] 13 #define R(i) T[i].s[1] 14 #define Loc(i) (T[fa(i)].s[1]==i) 15 #define Sets(a,b,c) {T[a].s[c] = b; fa(b) = a;} 16 #define For(i,n) for(int i=1;i<=n;i++) 17 #define Rep(i,l,r) for(int i=l;i<=r;i++) 18  19 struct tnode{ 20     int s[2],size,p,markp,markr,Max,v; 21 }T[N]; 22  23 int n,m,root = 1,tot; 24 int l,r,op,delta; 25  26 void Pushdown(int i){ 27     if(T[i].markp){ 28         if(L(i))  {T[L(i)].markp+=T[i].markp;T[L(i)].Max  +=T[i].markp;T[L(i)].v+=T[i].markp;} 29         if(R(i))  {T[R(i)].Max  +=T[i].markp;T[R(i)].markp+=T[i].markp;T[R(i)].v+=T[i].markp;} 30         T[i].markp = 0; 31     } 32     if(T[i].markr){ 33         if(L(i)) T[L(i)].markr ^= 1; 34         if(R(i)) T[R(i)].markr ^= 1; 35         swap(L(i),R(i)); 36         T[i].markr = 0; 37     } 38 } 39  40 void Rot(int x){ 41     int y = fa(x) , z = fa(y); 42     int lx = Loc(x) , ly = Loc(y); 43     Pushdown(y);Pushdown(x); 44     Sets(y,T[x].s[lx^1],lx); 45     Sets(z,x,ly); 46     Sets(x,y,lx^1); 47     T[y].size = T[L(y)].size + T[R(y)].size + 1; 48     T[y].Max  = max(max(T[L(y)].Max,T[R(y)].Max),T[y].v); 49 } 50  51 void Splay(int i,int goal){ 52     while(fa(i)!=goal){ 53         if(fa(fa(i))!=goal) Rot(fa(i)); 54         Rot(i); 55     } 56     if(!goal) root = i; 57     T[i].size = T[L(i)].size + T[R(i)].size + 1; 58     T[i].Max  = max(max(T[L(i)].Max,T[R(i)].Max),T[i].v); 59 } 60  61 inline int Rank(int i,int rank){ 62     Pushdown(i); 63     if(T[L(i)].size + 1 == rank)   return i; 64     else  if(T[L(i)].size >= rank) return Rank(L(i),rank); 65     else                           return Rank(R(i),rank-T[L(i)].size - 1); 66 } 67  68 /*inline void Build(){//链式建树  69     For(i,n+2) { 70         T[i].p=i-1; 71         T[i].s[1]=i+1; 72         T[i].size=n+3-i; 73         T[i].v=T[i].s[0]=T[i].markr=T[i].markp=T[i].Max=0; 74     } 75     T[n+2].s[1]=0; 76     T[0].Max=-2147483647;     77 }*/  78  79 inline void Build(int l,int r,int &i,int p){ 80     if(l>r) return; 81     int m = (l+r)>>1; 82     i=++tot; 83     T[i].p = p; T[i].size = 1;T[i].markp = T[i].markr = T[i].v = T[i].Max = 0;     84     Build(l,m-1,L(i),i);Build(m+1,r,R(i),i); 85     T[i].size = T[L(i)].size + T[R(i)].size + 1; 86 } 87  88 inline void Reserve(int l,int r){ 89     Splay(Rank(root,l),0); 90     Splay(Rank(root,r+2),root); 91     T[L(R(root))].markr ^= 1; 92 } 93  94 inline void Plus(int l,int r,int delta){ 95     Splay(Rank(root,l),0); 96     Splay(Rank(root,r+2),root); 97     T[L(R(root))].markp+=delta; 98     T[L(R(root))].Max += delta; 99     T[L(R(root))].v+=delta;100 }101 102 inline void Query(int l,int r){103     Splay(Rank(root,l),0);104     Splay(Rank(root,r+2),root);105     printf("%d\n",T[L(R(root))].Max);106 }107 108 int main(){109     scanf("%d%d",&n,&m);110     Build(0,n+1,root,0);T[0].Max = -2147483647;111    // Build();112     For(i,m){113         scanf("%d",&op);114         if(op==1) {115             scanf("%d%d%d",&l,&r,&delta);116             Plus(l,r,delta);117         }118         else{119             scanf("%d%d",&l,&r);120             if(op==2) Reserve(l,r);121             else      Query(l,r);    122         }123     }124     return 0;125 }

 


联系
我们