【BZOJ1251】序列终结者 Splay

一道模板题,一直没发现自己的快速读入读不了负数,我竟然能活到现在真是万幸。

 #include <iostream>
#include <cstdio>
#define inf -0x7fffffff
#define N 50010
using namespace std;
struct SplayNode
{
SplayNode();
SplayNode *fa,*ch[];
//SplayNode(int x);
int data,maxn,size,add;
bool rev;
void push();
bool chr() {return this==fa->ch[];}
void updata()
{
size=ch[]->size+ch[]->size+;
maxn=max(max(ch[]->maxn,ch[]->maxn),data);
}
void setc(SplayNode *x,int t) {this->ch[t]=x; x->fa=this;}
}*null;
SplayNode::SplayNode() {fa=ch[]=ch[]=null; rev=;data=add=size=; maxn=inf;}
void SplayNode::push()
{
if (rev)
{
if (ch[]!=null) ch[]->rev^=;
if (ch[]!=null) ch[]->rev^=;
swap(ch[],ch[]);
rev=;
}
if (add!=)
{
if (ch[]!=null)
{
ch[]->add+=add;
ch[]->maxn+=add;
ch[]->data+=add;
}
if (ch[]!=null)
{
ch[]->add+=add;
ch[]->maxn+=add;
ch[]->data+=add;
}
add=;
}
}
int n,m;
//inline int read() {int ans=0; char c; while ((c=getchar())=='\r' || c=='\n' || c==' '); ans=c-'0'; while (isdigit(c=getchar())) ans=ans*10+c-'0'; return ans;}
namespace Splay
{
SplayNode *Root;
SplayNode pool[N];
int poolnum=;
SplayNode *NewNode()
{
poolnum++;
pool[poolnum]=SplayNode();
return &pool[poolnum];
}
SplayNode *BuildTree(int l,int r)
{
if (l>r) return null;
SplayNode *re=NewNode();
int mid=(l+r)>>;
re->data=;
re->ch[]=BuildTree(l,mid-);
re->ch[]=BuildTree(mid+,r);
re->ch[]->fa=re;
re->ch[]->fa=re;
re->updata();
return re;
}
void rotate(SplayNode *x)
{
SplayNode *r=x->fa;
if (x==null || r==null) return;
int t=x->chr();
x->push(); r->push();
if (r->fa==null) x->fa=r->fa,Root=x;
else r->fa->setc(x,r->chr());
r->setc(x->ch[t^],t);
x->setc(r,!t);
r->updata();
x->updata();
}
void splay(SplayNode *x,SplayNode *y)
{
for (;x->fa!=y;rotate(x))
if (x->fa->fa!=y)
if (x->chr()==x->fa->chr()) rotate(x->fa);
else rotate(x);
}
SplayNode *Kth(int k)
{
SplayNode *r=Root;
while (r!=null)
{
r->push();
if (k<=r->ch[]->size) r=r->ch[];
else if (k==r->ch[]->size+) return r;
else
{
k-=r->ch[]->size+;
r=r->ch[];
}
}
return null;
}
void reverse(int l,int r)
{
SplayNode *p=Kth(l);
SplayNode *s=Kth(r+);
p->push();
splay(p,null);
s->push();
splay(s,p);
s->ch[]->rev^=;
}
void Add(int l,int r,int v)
{
SplayNode *p=Kth(l);
SplayNode *s=Kth(r+);
p->push();
splay(p,null);
s->push();
splay(s,p);
s->ch[]->add+=v;
s->ch[]->data+=v;
s->ch[]->maxn+=v;
}
void query(int l,int r)
{
SplayNode *p=Kth(l);
SplayNode *s=Kth(r+);
p->push();
splay(p,null);
s->push();
splay(s,p);
printf("%d\n",s->ch[]->maxn);
}
}
void init() {null=Splay::NewNode(); *null=SplayNode(); Splay::Root=Splay::BuildTree(,n+);}
int main()
{
scanf("%d%d",&n,&m);
init();
//for (int i=1;i<=n;i++) a[i]=read();
//Splay::BuildTree(1,n);
for (int i=;i<=m;i++)
{
int temp,x,y;
scanf("%d%d%d",&temp,&x,&y);
//temp=read(); x=read(); y=read();
if (temp==)
{
int v;
scanf("%d",&v);
Splay::Add(x,y,v);
}
if (temp==) Splay::reverse(x,y);
if (temp==) Splay::query(x,y);
}
return ;
}

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。

HINT

 

Source

 
上一篇:配置Tomcat的访问日志格式化输出


下一篇:android线程池ThreadPoolExecutor的理解