题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1500
题目思路:splay ,包括区间插入,区间删除,回收内存,区间反转,区间和,区间最大子段,成段更新等操作。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 110
#define M 501000
#define keytree ch[ch[root][1]][0]
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int p[M],ch[M][2],v[M],s[M],lm[M],rm[M],ma[M],same[M],rev[M],sum[M],vst[M],a[M];
int top1,top2,root,n,m;
void visit(int x)
{
if(!x) return;
// printf(" x %d p %d ch0 %d ch1 %d v %d s %d rev %d sum %d lm %d rm %d ma %d \n",
// x,p[x],ch[x][0],ch[x][1],v[x],s[x],rev[x],sum[x],lm[x],rm[x],ma[x]);
vst[++top2]=x;
visit(ch[x][0]);
visit(ch[x][1]);
}
void up(int x)
{
int l=ch[x][0],r=ch[x][1];
s[x]=1+s[l]+s[r];
sum[x]=sum[l]+v[x]+sum[r];
lm[x]=max(lm[l],sum[l]+v[x]+max(0,lm[r]));
rm[x]=max(rm[r],sum[r]+v[x]+max(0,rm[l]));
ma[x]=max(0,rm[l])+v[x]+max(0,lm[r]);
ma[x]=max(ma[x],max(ma[l],ma[r]));
}
void datasame(int x,int val)
{
if(!x) return;
same[x]=1;
v[x]=val;
sum[x]=s[x]*val;
lm[x]=rm[x]=ma[x]=max(val,sum[x]);
}
void datarev(int x)
{
if(!x) return;
rev[x]^=1;
swap(lm[x],rm[x]);
swap(ch[x][0],ch[x][1]);
}
void down(int x)
{
int l=ch[x][0],r=ch[x][1];
if(same[x])
{
datasame(l,v[x]);
datasame(r,v[x]);
}
if(rev[x])
{
datarev(l);
datarev(r);
}
same[x]=rev[x]=0;
}
void newnode(int &x,int val,int pre)
{
if(top2)
x=vst[top2--];
else
x=++top1;
p[x]=pre;
s[x]=1;
ch[x][0]=ch[x][1]=same[x]=rev[x]=0;
lm[x]=rm[x]=ma[x]=v[x]=sum[x]=val;
}
void build(int &x,int l,int r ,int pre)
{
if(l>r)return;
int mid=(l+r)>>1;
newnode(x,a[mid],pre);
build(ch[x][0],l,mid-1,x);
build(ch[x][1],mid+1,r,x);
up(x);
}
void init()
{
top1=top2=p[0]=ch[0][0]=ch[0][1]=v[0]=s[0]=sum[0]=0;
lm[0]=rm[0]=ma[0]=-inf;
newnode(root,-inf,0);
newnode(ch[root][1],-inf,root);
s[root]=2;
build(keytree,1,n,ch[root][1]);
up(ch[root][1]);
up(root);
}
void rot(int x,int f)
{
int y=p[x];
p[ch[x][f]]=y;
ch[y][!f]=ch[x][f];
p[x]=p[y];
if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x;
p[y]=x;
ch[x][f]=y;
up(y);
}
void splay(int x,int goal)
{
while(p[x]!=goal)
{
if(p[p[x]]==goal)rot(x,ch[p[x]][0]==x);
else
{
int y=p[x],f=ch[p[y]][0]==y;
if(ch[y][f]==x)
rot(x,!f);
else
rot(y,f);
rot(x,f);
}
}
if(!goal) root=x;
up(x);
}
void rotto(int k,int goal)
{
int x=root;
down(x);
while(s[ch[x][0]]!=k)
{
if(s[ch[x][0]]>k)
x=ch[x][0];
else
{
k-=s[ch[x][0]]+1;
x=ch[x][1];
}
down(x);
}
splay(x,goal);
}
void Same(int pos,int num,int c)
{
rotto(pos-1,0);
rotto(pos+num,root);
datasame(keytree, c);
}
void Rev(int pos,int num)
{
rotto(pos-1,0);
rotto(pos+num,root);
datarev(keytree);
}
void getsum(int pos,int num)
{
rotto(pos-1,0);
rotto(pos+num,root);
printf("%d\n",sum[keytree]);
}
void maxsum()
{
rotto(0,0);
rotto(s[root]-1,root);
printf("%d\n",ma[keytree]);
}
void eraser(int x)
{
visit(x);
}
void insert(int pos,int num)
{
rotto(pos,0);
rotto(pos+1,root);
build(keytree,1,num,ch[root][1]);
up(ch[root][1]);
up(root);
}
void del(int pos,int num)
{
rotto(pos-1,0);
rotto(pos+num,root);
eraser(keytree);
keytree=0;
up(ch[root][1]);
up(root);
}
int main()
{
int i,pos,num,c;
char op[20];
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
init();
while(m--)
{
scanf("%s",op);
switch(op[0])
{
case 'I': scanf("%d%d",&pos,&num);
for(i=1;i<=num;i++)
scanf("%d",&a[i]);
insert(pos,num); break;
case 'D': scanf("%d%d",&pos,&num);del(pos,num);break;
case 'M':if(op[2]=='X') maxsum();
else
{
scanf("%d%d%d",&pos,&num,&c);
Same(pos,num,c);
}
break;
case 'R':scanf("%d%d",&pos,&num);Rev(pos,num);break;
case 'G':scanf("%d%d",&pos,&num);getsum(pos,num);break;
}
}
}
return 0;
}
分享到:
相关推荐
维护数列 【问题描述】 请写一个程序,要求维护一个数列,支持以下 6 种操作:(请注意,格式栏 中的下划线‘ _ ’表示实际输入文件中的空格) 操作编号 输入文件中的格式 说明 1. 插入 INSERT_posi_tot_c1_c2_.....
noi2005测试数据
NOI 2005年-2009年试题。 第二十二届至第二十六届全国信息学奥林匹克竞赛(NOI)试题。
【ACM/NOI/CSP】NOI嘉年华 solution and code of NOI比赛经验分享&代码程序资源 ACM/NOI/CSP比赛经验分享&代码程序资源 说明:solution and code of NOI 文件列表: NOI嘉年华\NOI嘉年华.docx (61480, -04-26) NOI...
关于NOI NOI是全国青少年信息学奥林匹克竞赛(National Olympiad in Informatics),是中国的一项顶级计算机科学竞赛。下面是关于NOI的一些解释和在比赛中取得好成绩的一些建议: NOI比赛的作用:NOI旨在选拔和...
NOI是全国青少年信息学奥林匹克竞赛(National Olympiad in Informatics),是中国的一项顶级计算机科学竞赛。下面是关于NOI的一些解释和在比赛中取得好成绩的一些建议: NOI比赛的作用:NOI旨在选拔和培养优秀的...
NOI题库1.6一些题目,可供初学者参考
ACM NOI 信息学竞赛 国家集训队2005论文集
为给选手提供一个锻炼的机会,CCF拟举办一场NOI Online能力测试。测试分为入门组和提高组,每组限额报名3万人,人数报满关闭系统,每组成功报名选手在同一时间参加线上测试。 一、测试时间: 提高组:3月7日8:30-...
NOI大纲NOI大纲NOI大纲.pdf
NOI收录了1001~2009年的试题、解析与测试数据。NOIP收录了1995~2018年的初赛试题与参考答案。收录了1995~2018年的复赛试题、测试数据与部分参考程序。书《全国青少年信息学(计算机)奥林匹克分区联赛试题解析(中学...
NOI在线能力测试【入门组】-3月7日14:30-18:00 NOI在线能力测试【入门组】-3月7日14:30-18:00
NOI2021Day2
NOI 2012 测试数据 day1: random, bicycling, chess day2: park, delicacy, tritown
内容:NOI2008冬令营资料 刘汝佳1(文件太大,分两次) 讲稿 <br>由于文件大小问题,请谅解。 <br>如果你参加国家级电脑语言竞赛,对你有很大帮助。
noi2010测试数据
noi2009测试数据
对于数列维护问题,我们常用的一种手段是线段树。但使用线段树有一定的局限性,本文介绍运用伸展树解决这类问题,并且可以实现更多...(3 )实例分析——NOI 2005 维护数列(Sequence ) (4 )和线段树的比较 by Crash
noi2006测试数据
NOI2004测试数据