[NOI2005] 维护数列
题目
请写一个程序，要求维护一个数列，支持以下 6 种操作：（请注意，格式栏 中的下划线‘ _ ’表示实际输入文件中的空格）
操作编号
输入文件中的格式
说明
1. 插入
INSERT_posi_tot_c1_c2_..._ctot
在当前数列的第 posi 个数字后插入 tot
个数字：c1, c2, …, ctot；若在数列首插
入，则 posi 为 0
2. 删除
DELETE_posi_tot
从当前数列的第 posi 个数字开始连续
删除 tot 个数字
3. 修改
MAKE-SAME_posi_tot_c
将当前数列的第 posi 个数字开始的连
续 tot 个数字统一修改为 c
4. 翻转
REVERSE_posi_tot
取出从当前数列的第 posi 个数字开始
的 tot 个数字，翻转后放入原来的位置
5. 求和
GET-SUM_posi_tot
计算从当前数列开始的第 posi 个数字
开始的 tot 个数字的和并输出
6. 求和最
大的子列
MAX-SUM
求出当前数列中和最大的一段子列，
并输出最大和
INPUT
输入文件的第 1 行包含两个数 N 和 M，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第 2 行包含 N 个数字，描述初始时的数列。
以下 M 行，每行一条命令，格式参见问题描述中的表格。
OUTPUT
对于输入数据中的 GET-SUM 和 MAX-SUM 操作，向输出文件依次打印结果，每个答案（数字）占一行。
SAMPLE
INPUT
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUMOUTPUT
-1
10
1
10
解题报告
做这道题前请做好心理准备= =
比如说你会看到这样的评论：
QhelDIV：记得byvoid的博客上说这个题他当时写了整整一天，
我大约写了8个小时？
这种长代码程序结构一定要简单简单再简单，否则就是无限的调试了Chenyao2333：策爷：“splay/块状链表的自虐题。”。深刻理解到如果没有M倾向就不要去写这题了。。。
wumingshi：这道题太恶心辣
一定要处理好哨兵节点和null节点的数据，update时要注意！
【没有用哨兵节点的请随意
很裸的SpalySplay板子题，然而并不是那么好打= =
本来打了256行的数组板子
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum*f;
}
int ch[][],f[],key[],size[];
int sum[],maxl[],maxr[],maxn[];
int root,sz;
bool lazy[],rev[];
inline void clear(int x){
f[x]=ch[x][]=ch[x][]=size[x]=key[x]=sum[x]=;
lazy[x]=rev[x]=maxl[x]=maxr[x]=;
maxn[x]=-;
}
inline int get(int x){
return ch[f[x]][]==x;
}
inline int my_max(int a,int b){
return a>b?a:b;
}
inline void swp(int &a,int &b){
a^=b;
b^=a;
a^=b;
}
inline void update(int x){
int l(ch[x][]),r(ch[x][]);
sum[x]=sum[l]+sum[r]+key[x];
size[x]=size[l]+size[r]+;
maxn[x]=maxl[r]+key[x]+maxr[l];
if(l)
maxn[x]=my_max(maxn[x],maxn[l]);
if(r)
maxn[x]=my_max(maxn[x],maxn[r]);
maxl[x]=my_max(maxl[l],sum[l]+key[x]+maxl[r]);
maxr[x]=my_max(maxr[r],sum[r]+key[x]+maxr[l]);
}
inline void pushdown(int x){
int l(ch[x][]),r(ch[x][]);
if(lazy[x]){
rev[x]=lazy[x]=;
if(l){
lazy[l]=;
key[l]=key[x];
sum[l]=key[l]*size[l];
}
if(r){
lazy[r]=;
key[r]=key[x];
sum[r]=key[r]*size[r];
}
if(key[x]>=){
if(l)
maxl[l]=maxr[l]=maxn[l]=sum[l];
if(r)
maxl[r]=maxr[r]=maxn[r]=sum[r];
}
else{
if(l){
maxl[l]=maxr[l]=;
maxn[l]=key[l];
}
if(r){
maxl[r]=maxr[r]=;
maxn[r]=key[r];
}
}
}
if(rev[x]){
rev[x]=;
rev[l]^=;
rev[r]^=;
swp(maxl[l],maxr[l]);
swp(maxl[r],maxr[r]);
swp(ch[l][],ch[l][]);
swp(ch[r][],ch[r][]);
}
}
inline void rotate(int x){
int p(f[x]),g(f[p]),which(get(x));
pushdown(p);
pushdown(x);
ch[p][which]=ch[x][which^];
f[ch[p][which]]=p;
ch[x][which^]=p;
f[p]=x;
f[x]=g;
if(g)
ch[g][ch[g][]==p]=x;
update(p);
update(x);
}
inline void splay(int x,int y){
pushdown(x);
for(int fa=f[x];fa!=y;rotate(x),fa=f[x])
if(f[fa]!=y)
rotate(get(fa)==get(x)?fa:x);
if(!y)
root=x;
}
inline int find(int x){
int now(root);
while(){
pushdown(now);
if(x<=size[ch[now][]])
now=ch[now][];
else{
int tmp(size[ch[now][]]+);
if(x<=tmp)
return now;
x-=tmp;
now=ch[now][];
}
}
}
inline void build(int l,int r,int fa){
if(l>r)
return ;
if(l==r){
f[l]=fa;
size[l]=;
sum[l]=key[l];
if(key[l]>=)
maxl[l]=maxr[l]=maxn[l]=key[l];
else{
maxl[l]=maxr[l]=;
maxn[l]=key[l];
}
if(fa){
if(l<fa)
ch[fa][]=l;
else
ch[fa][]=l;
}
return;
}
int mid((l+r)>>);
build(l,mid-,mid);
build(mid+,r,mid);
f[mid]=fa;
update(mid);
if(fa){
if(mid<fa)
ch[fa][]=mid;
else
ch[fa][]=mid;
}
}
inline void erase(int x){
if(!x)
return;
erase(ch[x][]);
erase(ch[x][]);
clear(x);
}
char op[];
inline int gg(){
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
int n(read()),m(read());
key[++sz]=-;
for(int i=;i<=n;i++)
key[++sz]=read();
key[++sz]=-;
build(,n+,);
root=(n+)>>;
int all(n+);
while(m--){//cout<<'*'<<m<<endl;
scanf("%s",op);
if(op[]=='I'){
int pos(read()+),tot(read()),old(sz+);
int x(find(pos)),y(find(pos+));
splay(x,);
splay(y,x);
for(int i=;i<=tot;i++)
key[++sz]=read();
build(old,sz,);
int rt((old+sz)>>);
f[rt]=y;
ch[y][]=rt;
update(y);
update(x);
all+=tot;
continue;
}
if(op[]=='D'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
erase(ch[y][]);
update(y);
update(x);
all-=tot;
continue;
}
if(op[]=='R'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
int z(ch[y][]);
if(!lazy[z]){
rev[z]^=;
swp(ch[z][],ch[z][]);
swp(maxl[z],maxr[z]);
update(y);
update(x);
}
continue;
}
if(op[]=='G'){
int pos(read()),tot(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
printf("%d\n",sum[ch[y][]]);
continue;
}
if(op[]=='K'){
int pos(read()),tot(read()),c(read());
int x(find(pos)),y(find(pos+tot+));
splay(x,);
splay(y,x);
int z(ch[y][]);
lazy[z]=;
key[z]=c;
sum[z]=size[z]*c;
if(c>=)
maxl[z]=maxr[z]=maxn[z]=sum[z];
else{
maxl[z]=maxr[z]=;
maxn[z]=c;
}
update(y);
update(x);
}
if(op[]=='X'){
int x(find()),y(find(all));
splay(x,);
splay(y,x);
printf("%d\n",maxn[ch[y][]]);
}
}
return ;
}
int K(gg());
int main(){;}
然后成功在COGS上A了，然后我去了HZOJ、洛谷什么的。
MLE喵喵喵？？？我难道交了个MLE自动机喵喵喵？？？
//MLE自动机
int main(){
while()
long long *x=new long long[];
}
//请不要作死在自己电脑上以及他人电脑上使用
最后我发现，COGS上的限制是这样的：
时间限制：3 s 内存限制：256 MB
然而其他OJ的限制是这样的：
时间限制: 1 Sec 内存限制: 64 MB
数组就莫名GG了= =
所以我学（xiu）习（gai）了某司机的指针板子，成功的get√到了新板子= =
264行SpalySplay板子奉上
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
inline int read(){
int sum(),f();
char ch(getchar());
for(;ch<''||ch>'';ch=getchar())
if(ch=='-')
f=-;
for(;ch>=''&&ch<='';sum=sum*+(ch^),ch=getchar());
return sum*f;
}
const int inf(0x2FFFFFFF);
inline int my_max(int a,int b){
return a>b?a:b;
}
inline void swp(int &a,int &b){
a^=b;
b^=a;
a^=b;
}
class SplayTree{
private:
class Node{
public:
int k,sz,sm,lm,rm,ms;
bool set,rev;
Node *fa,*ch[];
Node(const int& key){
this->k=key;
this->sm=key;
this->ms=key;
this->lm=key>=?key:;
this->rm=key>=?key:;
this->sz=;
this->fa=NULL;
this->ch[]=NULL;
this->ch[]=NULL;
this->rev=false;
this->set=false;
}
~Node(){
if(this->ch[]!=NULL)
delete this->ch[];
if(this->ch[]!=NULL)
delete this->ch[];
}
inline void pushup(){
if(this!=NULL){
this->sz=this->ch[]->size()+this->ch[]->size()+;
this->sm=this->ch[]->sum()+this->ch[]->sum()+this->k;
this->lm=my_max(this->ch[]->lmax(),this->ch[]->sum()+this->k+this->ch[]->lmax());
this->rm=my_max(this->ch[]->rmax(),this->ch[]->sum()+this->k+this->ch[]->rmax());
this->ms=my_max(my_max(this->ch[]->maxsum(),this->ch[]->maxsum()),this->ch[]->rmax()+this->k+this->ch[]->lmax());
}
}
inline void Swap(){
if(this!=NULL){
this->rev=!this->rev;
swp(this->lm,this->rm);
swap(this->ch[],this->ch[]);
}
}
inline void Set(const int &key){
if(this!=NULL){
this->set=true;
this->k=key;
this->sm=key*this->sz;
this->lm=my_max(this->sm,);
this->rm=my_max(this->sm,);
this->ms=my_max(this->sm,this->k);
}
}
inline void pushdown(){
if(this->set){
this->set=this->rev=false;
this->ch[]->Set(this->k);
this->ch[]->Set(this->k);
}
if(this->rev){
this->rev=false;
this->ch[]->Swap();
this->ch[]->Swap();
}
}
inline int sum(){
return this?this->sm:;
}
inline int maxsum(){
return this?this->ms:-inf;
}
inline int key(){
return this?this->k:;
}
inline int lmax(){
return this?this->lm:;
}
inline int rmax(){
return this?this->rm:;
}
inline int size(){
return this?this->sz:;
}
}*root;
inline void rotate(Node *root,int k){
Node *tmp(root->ch[k^]);
root->pushdown();
tmp->pushdown();
tmp->fa=root->fa;
if(root->fa==NULL)
this->root=tmp;
else
if(root->fa->ch[]==root)
root->fa->ch[]=tmp;
else
root->fa->ch[]=tmp;
root->ch[k^]=tmp->ch[k];
if(tmp->ch[k]!=NULL)
tmp->ch[k]->fa=root;
tmp->ch[k]=root;
root->fa=tmp;
root->pushup();
tmp->pushup();
}
inline void Splay(Node *root,Node *fa=NULL){
while(root->fa!=fa){
int k(root->fa->ch[]==root);
if(root->fa->fa==fa)
rotate(root->fa,k);
else{
int d(root->fa->fa->ch[]==root->fa);
rotate(k==d?root->fa->fa:root->fa,k);
rotate(root->fa,d);
}
}
}
inline Node* build(const vector<int> &v,int l,int r){
if(l>r)
return NULL;
int mid((l+r)>>);
Node *tmp(new Node(v[mid]));
tmp->ch[]=build(v,l,mid-);
tmp->ch[]=build(v,mid+,r);
if(tmp->ch[]!=NULL)
tmp->ch[]->fa=tmp;
if(tmp->ch[]!=NULL)
tmp->ch[]->fa=tmp;
tmp->pushup();
return tmp;
}
public:
SplayTree():root(new Node(-inf)){
this->root->ch[]=new Node(-inf);
this->root->ch[]->fa=this->root;
}
SplayTree(const vector<int> &v){
this->root=build(v,,v.size()-);
}
~SplayTree(){
delete this->root;
}
Node* Kth(int pos){
++pos;
Node* root(this->root);//cout<<'+';
while(root!=NULL){
root->pushdown();
int k(root->ch[]->size()+);
if(pos<k)
root=root->ch[];
else
if(pos==k)
return root;
else{
pos-=k;
root=root->ch[];
}
}
return NULL;
}
inline int Sum(const int &pos,const int &len){
this->Splay(this->Kth(pos-));
this->Splay(this->Kth(pos+len),this->root);
return this->root->ch[]->ch[]->sum();
}
inline void Reverse(const int &pos,const int &len){
this->Splay(this->Kth(pos-));
this->Splay(this->Kth(pos+len),this->root);
this->root->ch[]->ch[]->Swap();
this->root->ch[]->pushup();
this->root->pushup();
}
inline void Set(const int &pos,const int &len,const int &d){
this->Splay(this->Kth(pos-));
this->Splay(this->Kth(pos+len),this->root);
this->root->ch[]->ch[]->Set(d);
this->root->ch[]->pushup();
this->root->pushup();
}
inline void Insert(const int &pos,SplayTree *data){
this->Splay(this->Kth(pos));
this->Splay(this->Kth(pos+),this->root);
Node *tmp(data->root);
data->root=NULL;
this->root->ch[]->ch[]=tmp;
tmp->fa=this->root->ch[];
this->root->ch[]->pushup();
this->root->pushup();
}
inline void Delete(const int &pos,const int &len){
this->Splay(this->Kth(pos-));
this->Splay(this->Kth(pos+len),this->root);
delete this->root->ch[]->ch[];
this->root->ch[]->ch[]=NULL;
this->root->ch[]->pushup();
this->root->pushup();
}
inline int maxsum(){
return this->root->maxsum();
}
};
SplayTree *tree(new SplayTree());
vector<int>v;
char op[];
int x,y;
inline int gg(){
freopen("seq2005.in","r",stdin);
freopen("seq2005.out","w",stdout);
int n(read()),m(read());
for(int i=;i<n;i++)
v.push_back(read());
tree->Insert(,new SplayTree(v));//cout<<'*';
while(m--){
scanf("%s",op);
if(op[]!='M'||op[]!='X')
x=read(),y=read();
if(op[]=='G')
printf("%d\n",tree->Sum(x,y));
else
if(op[]=='D')
tree->Delete(x,y);
else
if(op[]=='R')
tree->Reverse(x,y);
else
if(op[]=='I'){
v.clear();
while(y--)
v.push_back(read());
tree->Insert(x,new SplayTree(v));
}
else
if(op[]=='M'){
if(op[]=='K')
tree->Set(x,y,read());
else
printf("%d\n",tree->maxsum());
}
}
}
int K(gg());
int main(){;}
这题，真的虐心啊= =