[BZOJ 1500]维修数列 [Splay Tree从进阶到住院]

历尽艰辛终于A掉了这题QwQ

贴COGS评论区几句话=.=

策爷：“splay/块状链表的自虐题。”。深刻理解到如果没有M倾向就不要去写这题了。。

　　-Chenyao2333

记得byvoid的博客上说这个题他当时写了整整一天，
我大约写了8个小时？
这种长代码程序结构一定要简单简单再简单，否则就是无限的调试了

　　-QhelDIV

这道题太恶心辣
一定要处理好哨兵节点和null节点的数据，update时要注意！
【没有用哨兵节点的请随意

　　 -wumingshi

这题确实恶心还特喵的是个板子...

用Splay写的话思路非常明确,但是必须处理好两边的虚拟结点和空结点的标记值...(猝不及防的细节题...?)

算了算了先贴题面

1500: [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 14422  Solved: 4692

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。

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-SUM

Sample Output

-1
10
1
10

HINT

首先简单梳理一下,题目要求支持的操作有:$Reverse/Set/Sum/MaxSum/Delete/Insert$.

其中需要下传标记的是$Set$和$Reverse$,分别使用两个$bool$型标记即可.其中$Set$操作标记的处理优先于$Reverse$因为$Set$操作会将整个区间设置为同一个值,翻转不翻转都一样233

我们注意到有$MaxSum$操作,这时我们需要分析一下.我们可以使用三个变量来存储有关信息:$lmax$存储以该区间左端开始向右的最大和,$rmax$存储以该区间右端为结尾向左的最大和,$maxSum$存储该区间内的最大连续和的值.这样就可以将$maxSum$分为三种情况:左子树的$maxSum$;右子树的$maxSum$;左子树$rmax$,右子树$lmax$和该节点的键值之和.分别代表完全位于左区间/完全位于右区间/跨越中间的最大连续和(此部分的分治策略可参见算法导论第三版中文版的4.1节).$lmax$和$rmax$则分别对应两种情况,以$lmax$为例,对应左子树的$lmax$值与左子树的$sum$值,该结点的键值和右子树的$lmax$值之和的最大值.$rmax$同理.

对于空结点要注意maxSum为-INF,其他值为0.(这个-INF坑死人了QwQ总是WA那一个点...)

更新时对于$sum<0$的情况要更新$lmax$与$rmax$为0,$maxSum$为键值.

代码非常锻炼码力...还有调试能力w...

对于调试可以参考一下我在下面代码中的 class SplayTree 里写的$Print$函数,按前序遍历顺序打印整棵树并按深度缩进...调试的时候帮了我不少忙来着w

袋马时间~~

GitHub

 /**************************************
       Judge Result: Accepted

 **************************************/
 #include <cstdio>
 #include <vector>
 #include <cstring>
 #include <cstring>
 #include <iostream>
 #include <algorithm>

 #define lch chd[0]
 #define rch chd[1]
 #define kch chd[k]
 #define xch chd[k^1]

 const int INF=0x2FFFFFFF;

 class SplayTree{
 private:
     struct Node{
         int k;
         int sz;
         int sm;
         int lm;
         int rm;
         int ms;
         bool set;
         bool rev;
         Node* prt;
         Node* chd[];
         Node(const int& key){
             this->k=key;
             this->sm=key;
             this->ms=key;
             this->lm=key>=?key:;
             this->rm=key>=?key:;
             this->sz=;
             this->prt=NULL;
             this->lch=NULL;
             this->rch=NULL;
             this->rev=false;
             this->set=false;
         }
         ~Node(){
             if(this->lch!=NULL)
                 delete this->lch;
             if(this->rch!=NULL)
                 delete this->rch;
         }
         inline void Maintain(){
             if(this!=NULL){
                 this->sz=this->lch->size()+this->rch->size()+;
                 this->sm=this->lch->sum()+this->rch->sum()+this->k;
                 this->lm=std::max(this->lch->lmax(),this->lch->sum()+this->k+this->rch->lmax());
                 this->rm=std::max(this->rch->rmax(),this->rch->sum()+this->k+this->lch->rmax());
                 this->ms=std::max(std::max(this->lch->maxSum(),this->rch->maxSum()),this->lch->rmax()+this->k+this->rch->lmax());
             }
         }
         inline void Swap(){
             if(this!=NULL){
                 this->rev=!this->rev;
                 std::swap(this->lm,this->rm);
                 std::swap(this->lch,this->rch);
             }
         }
         inline void Set(const int& key){
             if(this!=NULL){
                 this->set=true;
                 this->k=key;
                 this->sm=key*this->sz;
                 this->lm=std::max(this->sm,);
                 this->rm=std::max(this->sm,);
                 this->ms=std::max(this->sm,this->k);
             }
         }
         inline void PushDown(){
             if(this->set){
                 this->set=this->rev=false;
                 this->lch->Set(this->k);
                 this->rch->Set(this->k);
             }
             if(this->rev){
                 this->rev=false;
                 this->lch->Swap();
                 this->rch->Swap();
             }
         }
         inline int sum(){
             return this==NULL?:this->sm;
         }
         inline int maxSum(){
             return this==NULL?-INF:this->ms;
         }
         inline int key(){
             return this==NULL?:this->k;
         }
         inline int lmax(){
             return this==NULL?:this->lm;
         }
         inline int rmax(){
             return this==NULL?:this->rm;
         }
         inline int size(){
             return this==NULL?:this->sz;
         }
     }*root;
     inline void Rotate(Node* root,int k){
         Node* tmp=root->xch;
         root->PushDown();
         tmp->PushDown();
         tmp->prt=root->prt;
         if(root->prt==NULL)
             this->root=tmp;
         else if(root->prt->lch==root)
             root->prt->lch=tmp;
         else
             root->prt->rch=tmp;
         root->xch=tmp->kch;
         if(tmp->kch!=NULL)
             tmp->kch->prt=root;
         tmp->kch=root;
         root->prt=tmp;
         root->Maintain();
         tmp->Maintain();
     }
     void Splay(Node* root,Node* prt=NULL){
         while(root->prt!=prt){
             int k=root->prt->lch==root;
             if(root->prt->prt==prt){
                 Rotate(root->prt,k);
             }
             else{
                 int d=root->prt->prt->lch==root->prt;
                 Rotate(k==d?root->prt->prt:root->prt,k);
                 Rotate(root->prt,d);
             }
         }
     }
     Node* Build(const std::vector<int>& v,int l,int r){
         if(l>r)
             return NULL;
         int mid=(l+r)>>;
         Node* tmp=new Node(v[mid]);
         tmp->lch=Build(v,l,mid-);
         tmp->rch=Build(v,mid+,r);
         if(tmp->lch!=NULL)
             tmp->lch->prt=tmp;
         if(tmp->rch!=NULL)
             tmp->rch->prt=tmp;
         tmp->Maintain();
         return tmp;
     }
     void PrintTree(Node* root,int deep){
         for(int i=;i<deep;i++)
             fputc(' ',stderr);
         fprintf(stderr, "(root=0x%X,key=%d,sum=%d,size=%d,lmax=%d,rmax=%d,maxSum=%d)\n", root,root->key(),root->sum(),root->size(),root->lmax(),root->rmax(),root->maxSum());
         if(root==NULL)
             return;
         PrintTree(root->lch,deep+);
         PrintTree(root->rch,deep+);
     }
 public:
     SplayTree(){
         this->root=new Node(-INF);
         this->root->rch=new Node(-INF);
         this->root->rch->prt=this->root;
     }
     SplayTree(const std::vector<int>& v){
         this->root=Build(v,,v.size()-);
     }
     ~SplayTree(){
         delete this->root;
     }
     Node* Kth(int pos){
         ++pos;
         Node* root=this->root;
         while(root!=NULL){
             root->PushDown();
             int k=root->lch->size()+;
             if(pos<k)
                 root=root->lch;
             else if(pos==k)
                 return root;
             else{
                 pos-=k;
                 root=root->rch;
             }
         }
         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->rch->lch->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->rch->lch->Swap();
         this->root->rch->Maintain();
         this->root->Maintain();
     }
     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->rch->lch->Set(d);
         this->root->rch->Maintain();
         this->root->Maintain();
     }
     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->rch->lch=tmp;
         tmp->prt=this->root->rch;
         this->root->rch->Maintain();
         this->root->Maintain();
     }
     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->rch->lch;
         this->root->rch->lch=NULL;
         this->root->rch->Maintain();
         this->root->Maintain();
     }
     inline int MaxSum(){
         return this->root->maxSum();
     }
     void Print(){
         this->PrintTree(this->root,);
     }
 };

 int FastRead();

 int main(){
     SplayTree* tree=new SplayTree();
     std::vector<int> v;
     int n=FastRead();
     int m=FastRead();
     int a,b;
     char buf[];
     for(int i=;i<n;i++){
         v.push_back(FastRead());
     }
     tree->Insert(,new SplayTree(v));
     for(int i=;i<m;i++){
         scanf("%s",buf);
         if(*buf!='M'||buf[]!='X'){
             a=FastRead();
             b=FastRead();
         }
         if(*buf=='G'){
             printf("%d\n",tree->Sum(a,b));
         }
         else if(*buf=='D')
             tree->Delete(a,b);
         else if(*buf=='R')
             tree->Reverse(a,b);
         else if(*buf=='I'){
             v.clear();
             while(b--)
                 v.push_back(FastRead());
             tree->Insert(a,new SplayTree(v));
         }
         else if(*buf=='M'){
             if(buf[]=='K')
                 tree->Set(a,b,FastRead());
             else
                 printf("%d\n",tree->MaxSum());
         }
         // tree->Print();
     }
     return ;
 }

 int FastRead(){
     int ans=;
     bool neg=false;
     register char ch=getchar();
     while(!isdigit(ch)){
         if(ch=='-')
             neg=true;
         ch=getchar();
     }
     while(isdigit(ch)){
         ans=ans*+ch-'';
         ch=getchar();
     }
     if(neg)
         ans=-ans;
     return ans;
 }

Backup

然后该放图了来着w