BZOJ 1500 NOI 2005 维修数列 Splay
发布日期：2021-10-02 10:57:35
浏览次数：20
分类：技术文章
本文共 13691 字，大约阅读时间需要 45 分钟。
题意：见下图
传说级别的NOI数据结构神题，像我这种弱渣花了一下午的时间才A掉，最后发现竟然是边界值的问题没处理好。。
这个题对Splay的所有操作基本是全了。
插入：新建一颗Splay Tree，然后把对应节点Splay到根的右儿子上，再把新建的树连上。
删除：把要删除的区间Splay到根的右儿子的左儿子上，递归free掉。（这里可以用数组优化，可以避免递归free节省时间）
修改，翻转：打标记，在需要的时候下传标记，和线段树差不多，翻转标记下传时，要将左右儿子的左右儿子分别交换。
求和：维护一个sum域。
求最大子列和：与线段树类似。维护一个区间从左边开始连续最大值，从右边开始连续最大值，整体的连续最大值。更新的时候注意下细节。不会的可以先去写vijos的小白逛公园，线段树的最大子列和，要比这个简单一些。详情见代码。
CODE（BZOJ5988ms）：
#include#include #include #include #define MAX 600010#define INF 0x7f7f7f7fusing namespace std;const char INSERT[] = "INSERT";const char DELETE[] = "DELETE";const char REVERSE[] = "REVERSE";const char GET_SUM[] = "GET-SUM";const char MAX_SUM[] = "MAX-SUM";const char MAKE_SAME[] = "MAKE-SAME"; struct Complex{ int val,size; bool change,reverse; int change_into; int sum; int l,r,all; Complex *son[2],*father; bool Check() { return father->son[1] == this; } void Combine(Complex *a,bool dir) { son[dir] = a; a->father = this; } void Reverse() { reverse ^= 1; swap(son[0],son[1]); swap(l,r); } void Change(int x) { val = x; sum = x * size; l = r = all = max(sum,val); change = true; change_into = x; }}none,*nil = &none,*root = nil; void Pretreatment();inline Complex *NewComplex(int x); inline void Rotate(Complex *a,bool dir);inline void Splay(Complex *a,Complex *aim);Complex *BuildTree(int l,int r);inline void SplaySeg(int st,int ed); inline void PushUp(Complex *a); inline void PushDown(Complex *a);void Delete(Complex *a);Complex *FindK(Complex *a,int k); void Print(Complex *a){ if(a == nil) return ; PushDown(a); PushUp(a); Print(a->son[0]); printf("%d ",a->val); Print(a->son[1]);} int cnt,asks;int pos,num; int temp[MAX];char s[20]; int main(){ cin >> cnt >> asks; Pretreatment(); for(int i = 1;i <= cnt; ++i) scanf("%d",&temp[i]); root = BuildTree(0,cnt + 1); root->father = nil; for(int i = 1;i <= asks; ++i) { scanf("%s",s); if(!strcmp(s,INSERT)) { scanf("%d%d",&pos,&cnt),pos++; for(int i = 1;i <= cnt; ++i) scanf("%d",&temp[i]); Splay(FindK(root,pos),nil); Splay(FindK(root,pos + 1),root); root->son[1]->Combine(BuildTree(1,cnt),false); PushUp(root->son[1]),PushUp(root); } else if(!strcmp(s,DELETE)) { scanf("%d%d",&pos,&cnt); SplaySeg(pos,pos + cnt - 1); Delete(root->son[1]->son[0]); root->son[1]->son[0] = nil; PushUp(root->son[1]),PushUp(root); } else if(!strcmp(s,MAKE_SAME)) { scanf("%d%d%d",&pos,&cnt,&num); SplaySeg(pos,pos + cnt - 1); root->son[1]->son[0]->Change(num); PushUp(root->son[1]),PushUp(root); } else if(!strcmp(s,REVERSE)) { scanf("%d%d",&pos,&cnt); SplaySeg(pos,pos + cnt - 1); root->son[1]->son[0]->Reverse(); PushUp(root->son[1]),PushUp(root); } else if(!strcmp(s,GET_SUM)) { scanf("%d%d",&pos,&cnt); SplaySeg(pos,pos + cnt - 1); printf("%d\n",root->son[1]->son[0]->sum); } else if(!strcmp(s,MAX_SUM)) { int temp = root->size; Splay(FindK(root,1),nil); Splay(FindK(root,temp),root); printf("%d\n",root->son[1]->son[0]->all); } } return 0;} void Pretreatment(){ nil->son[0] = nil->son[1] = nil; nil->father = nil; nil->size = 0; nil->all = -INF; temp[0] = temp[cnt + 1] = -INF;} inline Complex *NewComplex(int x){ Complex *re = new Complex(); re->son[0] = re->son[1] = nil; re->size = 1; re->sum = re->l = re->r = re->all = re->val = x; re->change = re->reverse = false; return re;} inline void Rotate(Complex *a,bool dir){ Complex *f = a->father; PushDown(f),PushDown(a); f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; PushUp(f); if(root == f) root = a;} inline void Splay(Complex *a,Complex *aim){ while(a->father != aim) { if(a->father->father == aim) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) { Rotate(a->father,true); Rotate(a,true); } else { Rotate(a,false); Rotate(a,true); } } else { if(a->Check()) { Rotate(a->father,false); Rotate(a,false); } else { Rotate(a,true); Rotate(a,false); } } PushUp(a); }} Complex *BuildTree(int l,int r){ if(l > r) return nil; int mid = (l + r) >> 1; Complex *now = NewComplex(temp[mid]); now->Combine(BuildTree(l,mid - 1),false); now->Combine(BuildTree(mid + 1,r),true); if(l != r) PushUp(now); return now;} void Delete(Complex *a){ if(a == nil) return ; Delete(a->son[0]),Delete(a->son[1]); free(a);} inline void SplaySeg(int st,int ed){ st += 1,ed += 1; Splay(FindK(root,st - 1),nil); Splay(FindK(root,ed + 1),root);} Complex *FindK(Complex *a,int k){ PushDown(a); if(k <= a->son[0]->size) return FindK(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; --k; return FindK(a->son[1],k);} inline void PushDown(Complex *a){ if(a == nil) return ; if(a->change) { if(a->son[0] != nil) a->son[0]->Change(a->change_into); if(a->son[1] != nil) a->son[1]->Change(a->change_into); a->change = false; } if(a->reverse) { if(a->son[0] != nil) a->son[0]->Reverse(); if(a->son[1] != nil) a->son[1]->Reverse(); a->reverse = false; }} inline void PushUp(Complex *a){ if(a == nil) return ; a->size = a->son[0]->size + a->son[1]->size + 1; a->sum = a->son[0]->sum + a->son[1]->sum + a->val; a->l = max(a->son[0]->l,a->son[0]->sum + a->val + max(0,a->son[1]->l)); a->r = max(a->son[1]->r,a->son[1]->sum + a->val + max(0,a->son[0]->r)); a->all = max(max(a->son[0]->all,a->son[1]->all),a->val+max(0,a->son[0]->r)+max(0,a->son[1]->l));}
奉上读入优化版本，因为有的OJ卡这个题的常数（比如我们学校自己的oj）
同学帮着写的，效率十分可观，BZOJ3472ms就过了
CODE（读入优化）：
#include#include #include #include #include #define MAX 600010 #define INF 0x7f7f7f7f using namespace std; inline int getc() { static const int L = 1 << 15; static char buf[L], *S = buf, *T = buf; if (S == T) { T = (S = buf) + fread(buf, 1, L, stdin); if (S == T) return EOF; } return *S++;}inline int getint() { int c; while(!isdigit(c = getc()) && c != '-'); bool sign = c == '-'; int tmp = sign ? 0 : c - '0'; while(isdigit(c = getc())) tmp = (tmp << 1) + (tmp << 3) + c - '0'; return sign ? -tmp : tmp;}struct Twochar { char c0, c1; Twochar(char _c0 = 0, char _c1 = 0):c0(_c0),c1(_c1){}};inline Twochar getch() { int c; while((c = getc()) != 'I' && c != 'D' && c != 'M' && c != 'R' && c != 'G'); int c2 = getc(); c2 = getc(); if(c == 'I'&&c2=='S')getc(),getc(),getc(); if(c == 'D'&&c2=='L')getc(),getc(),getc(); if(c=='M'&&c2=='K')getc(),getc(),getc(),getc(),getc(); if(c=='R'&&c2=='V')getc(),getc(),getc(),getc(); if(c=='G'&&c2=='T')getc(),getc(),getc(),getc(); if(c=='M'&&c2=='X')getc(),getc(),getc(),getc(); return Twochar(c, c2);} struct Complex{ int val,size; bool change,reverse; int change_into; int sum; int l,r,all; Complex *son[2],*father; bool Check() { return father->son[1] == this; } void Combine(Complex *a,bool dir) { son[dir] = a; a->father = this; } void Reverse() { reverse ^= 1; swap(son[0],son[1]); swap(l,r); } void Change(int x) { val = x; sum = x * size; l = r = all = max(sum,val); change = true; change_into = x; } }none,*nil = &none,*root = nil; void Pretreatment(); inline Complex *NewComplex(int x); inline void Rotate(Complex *a,bool dir); inline void Splay(Complex *a,Complex *aim); Complex *BuildTree(int l,int r); inline void SplaySeg(int st,int ed); inline void PushUp(Complex *a); inline void PushDown(Complex *a); void Delete(Complex *a); Complex *FindK(Complex *a,int k); int cnt,asks; int pos,num; int temp[MAX]; int main() { cnt = getint(); asks = getint(); Pretreatment(); for(int i = 1;i <= cnt; ++i) temp[i] = getint(); root = BuildTree(0,cnt + 1); root->father = nil; Twochar s; for(int i = 1;i <= asks; ++i) { s = getch(); if(s.c0 == 'I' && s.c1 == 'S') { pos=getint(),cnt=getint(),pos++; for(int i = 1;i <= cnt; ++i) temp[i]=getint(); Splay(FindK(root,pos),nil); Splay(FindK(root,pos + 1),root); root->son[1]->Combine(BuildTree(1,cnt),false); PushUp(root->son[1]),PushUp(root); } else if(s.c0 == 'D' && s.c1 == 'L') { pos=getint(),cnt=getint(); SplaySeg(pos,pos + cnt - 1); Delete(root->son[1]->son[0]); root->son[1]->son[0] = nil; PushUp(root->son[1]),PushUp(root); } else if(s.c0 == 'M' && s.c1 == 'K') { pos=getint(),cnt=getint(),num=getint(); SplaySeg(pos,pos + cnt - 1); root->son[1]->son[0]->Change(num); PushUp(root->son[1]),PushUp(root); } else if(s.c0 == 'R' && s.c1 == 'V') { pos=getint(),cnt=getint(); SplaySeg(pos,pos + cnt - 1); root->son[1]->son[0]->Reverse(); PushUp(root->son[1]),PushUp(root); } else if(s.c0 == 'G' && s.c1 == 'T') { pos=getint(),cnt=getint(); SplaySeg(pos,pos + cnt - 1); printf("%d\n",root->son[1]->son[0]->sum); } else if(s.c0 == 'M' && s.c1 == 'X') { int temp = root->size; Splay(FindK(root,1),nil); Splay(FindK(root,temp),root); printf("%d\n",root->son[1]->son[0]->all); } } return 0; } void Pretreatment() { nil->son[0] = nil->son[1] = nil; nil->father = nil; nil->size = 0; nil->all = -INF; temp[0] = temp[cnt + 1] = -INF; } inline Complex *NewComplex(int x) { Complex *re = new Complex(); re->son[0] = re->son[1] = nil; re->size = 1; re->sum = re->l = re->r = re->all = re->val = x; re->change = re->reverse = false; return re; } inline void Rotate(Complex *a,bool dir) { Complex *f = a->father; PushDown(f),PushDown(a); f->son[!dir] = a->son[dir]; f->son[!dir]->father = f; a->son[dir] = f; a->father = f->father; f->father->son[f->Check()] = a; f->father = a; PushUp(f); if(root == f) root = a; } inline void Splay(Complex *a,Complex *aim) { while(a->father != aim) { if(a->father->father == aim) Rotate(a,!a->Check()); else if(!a->father->Check()) { if(!a->Check()) { Rotate(a->father,true); Rotate(a,true); } else { Rotate(a,false); Rotate(a,true); } } else { if(a->Check()) { Rotate(a->father,false); Rotate(a,false); } else { Rotate(a,true); Rotate(a,false); } } } PushUp(a); } Complex *BuildTree(int l,int r) { if(l > r) return nil; int mid = (l + r) >> 1; Complex *now = NewComplex(temp[mid]); now->Combine(BuildTree(l,mid - 1),false); now->Combine(BuildTree(mid + 1,r),true); if(l != r) PushUp(now); return now; } void Delete(Complex *a) { if(a == nil) return ; Delete(a->son[0]),Delete(a->son[1]); free(a); } inline void SplaySeg(int st,int ed) { st += 1,ed += 1; Splay(FindK(root,st - 1),nil); Splay(FindK(root,ed + 1),root); } Complex *FindK(Complex *a,int k) { PushDown(a); if(k <= a->son[0]->size) return FindK(a->son[0],k); k -= a->son[0]->size; if(k == 1) return a; --k; return FindK(a->son[1],k); } inline void PushDown(Complex *a) { if(a == nil) return ; if(a->change) { if(a->son[0] != nil) a->son[0]->Change(a->change_into); if(a->son[1] != nil) a->son[1]->Change(a->change_into); a->change = false; } if(a->reverse) { if(a->son[0] != nil) a->son[0]->Reverse(); if(a->son[1] != nil) a->son[1]->Reverse(); a->reverse = false; } } inline void PushUp(Complex *a) { if(a == nil) return ; a->size = a->son[0]->size + a->son[1]->size + 1; a->sum = a->son[0]->sum + a->son[1]->sum + a->val; a->l = max(a->son[0]->l,a->son[0]->sum + a->val + max(0,a->son[1]->l)); a->r = max(a->son[1]->r,a->son[1]->sum + a->val + max(0,a->son[0]->r)); a->all = max(max(a->son[0]->all,a->son[1]->all),a->val+max(0,a->son[0]->r)+max(0,a->son[1]->l)); }
转载地址：https://blog.csdn.net/jiangyuze831/article/details/39098481 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
路过按个爪印，很不错，赞一个！
[***.219.124.196]2024年04月16日 12时20分10秒
关于作者
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！
推荐文章
解决 nginx: [error] open() “/usr/local/nginx/logs/nginx.pid“ failed (2: No such file or directory) 问题
2019-04-27
LeetCode-122. 买卖股票的最佳时机 II(Goland实现)
2019-04-27
LeetCode-136. 只出现一次的数字(Goland实现)
2019-04-27
go-递归实现二叉树的三种排序方式(前序、中序、后序)【详细】
2019-04-27
LeetCode-409. 最长回文串(Goland实现)
2019-04-27
LeetCode-LCP 18. 早餐组合(Goland实现)
2019-04-27
C++从入门到进阶近100本书推荐电子书pdf
2019-04-28
蓝桥杯 - [2014年第五届真题]分糖果(模拟)
2019-04-28
蓝桥杯 - [2013年第四届真题]大臣的旅费(DFS)
2019-04-28
蓝桥杯 - [2013年第四届真题]带分数(全排列)
2019-04-28
蓝桥杯 - [2013年第四届真题]幸运数(模拟)
2019-04-28
蓝桥杯 - [2013年第四届真题]横向打印二叉树(排序二叉树)
2019-04-28
蓝桥杯 - [历届试题]网络寻路(枚举)
2019-04-28
牛客网 - [中南林业科技大学第十一届程序设计大赛]兑换零钱(背包问题)
2019-04-28
HDU - Robberies(01背包)
2019-04-28
HDU - 最大报销额(01背包|贪心)
2019-04-28
HDU - Coins(完全背包)
2019-04-28
JXFCZX — 砝码称重1(DFS+背包)
2019-04-28
JXFCZX — 质数和分解(完全背包)
2019-04-28
JXFCZX — 花店橱窗(动态规划)
2019-04-28
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 308202141 位访客
访问时间: 2024-04-27 01:03:22
访问IP: 18.224.59.231
Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1
手机版