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。
题解:
维护区间翻转和add的标记即可
注意有负数
//by sdfzchy
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ls t[x].ch[0]
#define rs t[x].ch[1]
#define pa t[x].fa
using namespace std;
typedef long long LL;
const int inf=(1<<30),N=100010;
int n,m,root;
inline int in()
{
char ch=getchar();
int f=1,tmp=0;
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {tmp=(tmp<<1)+(tmp<<3)+(ch-'0');ch=getchar();}
return tmp*f;
}
struct node
{
int ch[2],cnt,val,fa,rev,col,mx,siz;
}t[N];
inline int gi(int x) {return t[pa].ch[1]==x;}
inline void upd(int x)
{
t[x].siz=t[ls].siz+t[rs].siz+t[x].cnt;
t[x].mx=max(max(t[ls].mx,t[rs].mx),t[x].val);
}
inline void pushdown(int x)
{
if(t[x].rev)
{
swap(ls,rs);
if(ls) t[ls].rev^=1;
if(rs) t[rs].rev^=1;
t[x].rev=0;
}
if(t[x].col)
{
int w=t[x].col;
if(ls) t[ls].col+=w,t[ls].val+=w,t[ls].mx+=w;
if(rs) t[rs].col+=w,t[rs].val+=w,t[rs].mx+=w;
t[x].col=0;
}
}
int build(int l,int r)
{
if(l>r) return 0;
int x=(l+r)>>1;
ls=build(l,x-1),rs=build(x+1,r);
t[ls].fa=t[rs].fa=x;
t[x].siz=t[x].cnt=1;
upd(x);
return x;
}
void rot(int x)
{
int f=pa,g=t[f].fa,o=gi(x);
t[f].ch[o]=t[x].ch[!o];
t[t[x].ch[!o]].fa=f;
t[x].ch[!o]=f;
t[f].fa=x;
t[x].fa=g;
if(g) t[g].ch[t[g].ch[1]==f]=x;
upd(f),upd(x);////////
}
void splay(int x,int tar)
{
for(;pa!=tar;rot(x))
if(t[pa].fa!=tar)
rot((gi(x)==gi(pa)?pa:x));
if(!tar) root=x;
}
int kth(int k)
{
int x=root;
while(1)
{
pushdown(x);
if(k<=t[ls].siz&&ls) x=ls;
else
{
int tmp=t[ls].siz+t[x].cnt;
if(k<=tmp) return x;
k-=tmp,x=rs;
}
}
}
void rev(int l,int r)
{
splay(kth(l),0);
int x=kth(r+2);
splay(x,root);
t[ls].rev^=1;
}
void add(int l,int r,int v)
{
splay(kth(l),0);
int x=kth(r+2);
splay(x,root);
t[ls].col+=v;
t[ls].mx+=v;
t[ls].val+=v;
}
int gmax(int l,int r)
{
splay(kth(l),0);
int x=kth(r+2);
splay(x,root);
printf("%d\n",t[ls].mx);
}
void print(int x)
{
if(!x) return;
pushdown(x);
if(ls) print(ls);
if(x!=1&&x!=n+2) printf("%d ",t[x].val);
if(rs) print(rs);
}
int main()
{
n=in(),m=in();
t[0].mx=-inf;////
root=build(1,n+2);
for(int i=1,op,l,r,x;i<=m;i++)
{
op=in(),l=in(),r=in();
switch(op)
{
case 1:x=in();add(l,r,x);break;
case 2:rev(l,r);break;
case 3:gmax(l,r);break;
}
// print(root);
// cout<<endl;
}
return 0;
}