【题解】P2710 数列

秒速五厘米 2021-10-26 12:00 349阅读 0赞

> 区间操作集大成者……？

> 可能吧……

by某位不愿意透露姓名的巨学  
\*\*\*  
本题需要实现：

*  INSERT
 *  DELETE
 *  REVERSE
 *  MAKE-SAME
 *  GET-SUM
 *  GET
 *  MAX-SUM

共七个操作

全部操作都涉及到序列

于是我们考虑使用splay或者FHQ-treap实现

这里使用FHQ-treap  
\*\*\*  
前置芝士

*  FHQ-treap

蛤？不会？左转度娘/必应娘/谷歌娘

*  区间翻转

左转P3391题解区，包教包会，不会不要钱本来就不要钱吧

*  最大子段和

左转P4513  
\*\*\*  
非必要

*  笛卡尔树建树

实际上不用这个方法用暴力插入也能过，但可能需要卡卡常

*  卡常技巧  
    \*\*\*  
    0.初始定义

struct note { int val;//节点权值 int rd;//优先值 int siz;//子树大小 int ch[2];//左右儿子 int tag;//翻转标记 int cvr;//make-same标记 int sum;//区间和 int lmax,rmax,mmax;//最大子段和 note() { ch[0]=ch[1]=val=siz=sum=tag=0; cvr=inf; } inline void clear() { ch[0]=ch[1]=val=siz=sum=tag=0; cvr=inf; } };

--------------------

\-1.信息上传，标记下放

inline void up(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; t[o].siz=t[ls].siz+t[rs].siz+1; t[o].sum=t[o].val+t[ls].sum+t[rs].sum; t[o].lmax=max(0,max(t[ls].lmax,t[ls].sum+t[rs].lmax+t[o].val)); t[o].rmax=max(0,max(t[rs].rmax,t[rs].sum+t[ls].rmax+t[o].val)); t[o].mmax=max(t[o].val,t[ls].rmax+t[rs].lmax+t[o].val); if (ls) { t[o].mmax=max(t[o].mmax,t[ls].mmax); } if (rs) { t[o].mmax=max(t[o].mmax,t[rs].mmax); } } inline void flip(int o) { swap(t[o].ch[0],t[o].ch[1]); swap(t[o].lmax,t[o].rmax); t[o].tag^=1; } inline void cvr(int o,int val) { t[o].cvr=t[o].val=val; t[o].sum=t[o].siz*val; t[o].mmax=max(t[o].val,t[o].sum); t[o].lmax=t[o].rmax=max(0,t[o].sum); } inline void down(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; if (t[o].tag) { if (ls) { flip(ls); } if (rs) { flip(rs); } } if (t[o].cvr!=inf) { if (ls) { cvr(ls,t[o].cvr); } if (rs) { cvr(rs,t[o].cvr); } } t[o].tag=0; t[o].cvr=inf; }

--------------------

1.插入操作

第一个要实现的操作，然而并不是最简单的

我们可以选择暴力插入，但……

这样子做的时间复杂度是O(qlogn)的，其中q为插入序列中数的个数

如何优化？

笛卡尔树建树！

自行度娘具体方法，这里直接给出代码

inline int build(int len,int a[]) { top=0; int temp=new_node(a[1]); stk[++top]=temp; for(int i=2;i<=len;i++) { int last=0; int cur=new_node(a[i]); while(top&&t[stk[top]].rd>t[cur].rd) { up(stk[top]); last=stk[top]; stk[top--]=0; } t[cur].ch[0]=last; up(cur); if (top) { t[stk[top]].ch[1]=cur; up(stk[top]); } stk[++top]=cur; } while(top) { up(stk[top--]); } return stk[1]; }

返回的是新建树的根

有了这个函数，insert就非常好写了

inline void insert(int pos,int len,int a[]) { int root1=build(len,a); int x,y; split(root,pos,x,y); root=merge(merge(x,root1),y); }

时间复杂度O(q+logn),其中q为序列中数的个数  
\*\*\*  
2.delete操作

把要删除的区间提取出来直接中序历删除即可

注意垃圾回收

void recycle(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; if (!o) { return; } if (ls) { recycle(ls); } trash.push(o); if (rs) { recycle(rs); } } inline void remove(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); recycle(u); root=merge(z,y); }

时间复杂度O(logn+q)  
\*\*\*  
3.REVERSE操作

左转文艺平衡树

注意标记下放

inline void reverse(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); t[u].tag^=1; swap(t[u].lmax,t[u].rmax); swap(t[u].ch[0],t[u].ch[1]); root=merge(merge(z,u),y); return; }

时间复杂度O(logn)  
\*\*\*  
4.MAKE-SAME操作

全场最烦操作（因为要手动更新

inline void cover(int pos,int len,int val) { int x,y,u,z; split(root,pos+len-1,x,y); split(x,pos-1,z,u); t[u].val=t[u].cvr=val; t[u].sum=val*t[u].siz; t[u].lmax=t[u].rmax=max(0,t[u].sum); t[u].mmax=max(t[u].val,t[u].sum); t[u].tag=0; root=merge(merge(z,u),y); }

时间复杂度O(logn)  
\*\*\*  
5.三大询问

因为代码都很无脑就放一起了

inline int get_sum(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); int ans=t[u].sum; root=merge(merge(z,u),y); return ans; } inline int get_max_sum(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); int ans=t[u].mmax; root=merge(merge(z,u),y); return ans; } inline int ask_point(int pos) { int x,y,z,u; split(root,pos,x,y); split(x,pos-1,z,u); int ans=t[u].val; root=merge(merge(z,u),y); return ans; }

时间复杂度O(logn)  
\*\*\*  
最后，让我们看看核心函数：merge和split

void split(int x,int k,int &a,int &b) { if (!x||!k) { a=0; b=x; return; } down(x); if (k>t[t[x].ch[0]].siz) { a=x; split(t[x].ch[1],k-t[t[x].ch[0]].siz-1,t[x].ch[1],b); up(x); } else { b=x; split(t[x].ch[0],k,a,t[x].ch[0]); up(x); } } int merge(int x,int y) { if (x) { down(x); } if (y) { down(y); } if (!x||!y) { return x^y; } if (t[x].rd<t[y].rd) { t[x].ch[1]=merge(t[x].ch[1],y); up(x); return x; } else { t[y].ch[0]=merge(x,t[y].ch[0]); up(y); return y; } }

遵循原则：用时间换安全

具体来讲，在写这两个函数的时候，能上传下放就上传下放，保障安全  
\*\*\*  
最后的最后，一点个人感想

前前后后调了半个寒假，还是很有收获的

up,down,merge,split四个核心函数一定要好好理解，不然一出bug就……

放总体代码 我知道你们只想看这个

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cstdlib> #include <ctime> #include <queue> #include <string> using namespace std; inline int Random() { return (rand()<<15)|rand(); } inline void read(int &x) { x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if (ch=='-') { f=-1; } ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+ch-'0'; ch=getchar(); } x*=f; } queue<int> trash;//???????? int root;//??????? const int inf=2e9; struct note { int val;//?? int rd;//??????? int siz;//????? int ch[2];//??????? int tag;//???????? int cvr;//???????? int sum;//??? int lmax,rmax,mmax;//?????? note() { ch[0]=ch[1]=val=siz=sum=tag=0; cvr=inf; } inline void clear() { ch[0]=ch[1]=val=siz=sum=tag=0; cvr=inf; } }; int stk[500010],top; struct fhq_treap { note t[200010]; int cnt; //?????? inline int q_malloc() { int x; return (!trash.empty()) ? (x=trash.front(),t[x].clear() , trash.pop() , x) : (++cnt); } //?????? inline int new_node(int val) { int x=q_malloc(); t[x].val=t[x].sum=t[x].mmax=val; t[x].lmax=t[x].rmax=max(0,val); t[x].rd=Random(); t[x].siz=1; return x; } //????? inline void up(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; t[o].siz=t[ls].siz+t[rs].siz+1; t[o].sum=t[o].val+t[ls].sum+t[rs].sum; t[o].lmax=max(0,max(t[ls].lmax,t[ls].sum+t[rs].lmax+t[o].val)); t[o].rmax=max(0,max(t[rs].rmax,t[rs].sum+t[ls].rmax+t[o].val)); t[o].mmax=max(t[o].val,t[ls].rmax+t[rs].lmax+t[o].val); if (ls) { t[o].mmax=max(t[o].mmax,t[ls].mmax); } if (rs) { t[o].mmax=max(t[o].mmax,t[rs].mmax); } } //???? inline void flip(int o) { swap(t[o].ch[0],t[o].ch[1]); swap(t[o].lmax,t[o].rmax); t[o].tag^=1; } //???????????? inline void cvr(int o,int val) { t[o].cvr=t[o].val=val; t[o].sum=t[o].siz*val; t[o].mmax=max(t[o].val,t[o].sum); t[o].lmax=t[o].rmax=max(0,t[o].sum); } //????? inline void down(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; if (t[o].tag) { if (ls) { flip(ls); } if (rs) { flip(rs); } } if (t[o].cvr!=inf) { if (ls) { cvr(ls,t[o].cvr); } if (rs) { cvr(rs,t[o].cvr); } } t[o].tag=0; t[o].cvr=inf; } //??? //len:??????a[]:????????? //????????? inline int build(int len,int a[]) { top=0; int temp=new_node(a[1]); stk[++top]=temp; for(int i=2;i<=len;i++) { int last=0; int cur=new_node(a[i]); while(top&&t[stk[top]].rd>t[cur].rd) { up(stk[top]); last=stk[top]; stk[top--]=0; } t[cur].ch[0]=last; up(cur); if (top) { t[stk[top]].ch[1]=cur; up(stk[top]); } stk[++top]=cur; } while(top) { up(stk[top--]); } return stk[1]; } //?????? //a??????? //b??????? //x??????????? //k?????????? void split(int x,int k,int &a,int &b) { if (!x||!k) { a=0; b=x; return; } down(x); if (k>t[t[x].ch[0]].siz) { a=x; split(t[x].ch[1],k-t[t[x].ch[0]].siz-1,t[x].ch[1],b); up(x); } else { b=x; split(t[x].ch[0],k,a,t[x].ch[0]); up(x); } } //?????? //x?????????? //y?????????? int merge(int x,int y) { if (x) { down(x); } if (y) { down(y); } if (!x||!y) { return x^y; } if (t[x].rd<t[y].rd) { t[x].ch[1]=merge(t[x].ch[1],y); up(x); return x; } else { t[y].ch[0]=merge(x,t[y].ch[0]); up(y); return y; } } //????? void recycle(int o) { int ls=t[o].ch[0],rs=t[o].ch[1]; if (!o) { return; } if (ls) { recycle(ls); } trash.push(o); if (rs) { recycle(rs); } } //????? //pos?????? //len???????? //a[]??? inline void insert(int pos,int len,int a[]) { int root1=build(len,a); int x,y; split(root,pos,x,y); root=merge(merge(x,root1),y); } //?????? //pos??????????? //len???????? inline void remove(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); recycle(u); root=merge(z,y); } //?????? //pos??????????? //len???????? inline void reverse(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); t[u].tag^=1; swap(t[u].lmax,t[u].rmax); swap(t[u].ch[0],t[u].ch[1]); root=merge(merge(z,u),y); return; } //????? //pos?????????? //len??????? //val????? inline void cover(int pos,int len,int val) { int x,y,u,z; split(root,pos+len-1,x,y); split(x,pos-1,z,u); t[u].val=t[u].cvr=val; t[u].sum=val*t[u].siz; t[u].lmax=t[u].rmax=max(0,t[u].sum); t[u].mmax=max(t[u].val,t[u].sum); t[u].tag=0; root=merge(merge(z,u),y); } inline int get_sum(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); int ans=t[u].sum; root=merge(merge(z,u),y); return ans; } inline int get_max_sum(int pos,int len) { int x,y,z,u; split(root,pos+len-1,x,y); split(x,pos-1,z,u); int ans=t[u].mmax; root=merge(merge(z,u),y); return ans; } inline int ask_point(int pos) { int x,y,z,u; split(root,pos,x,y); split(x,pos-1,z,u); int ans=t[u].val; root=merge(merge(z,u),y); return ans; } }; fhq_treap ft; int n,m; inline void read_str(char p[]) { char ch=getchar(); int len=0; while(!isalpha(ch)&&ch!='-') { ch=getchar(); } while(isalpha(ch)||ch=='-') { p[len++]=ch; ch=getchar(); } } int a[4000010]; int main() { srand((unsigned)time(0)); read(n),read(m); for(int i=1;i<=n;i++) { read(a[i]); } root=ft.build(n,a); int pos,len,val; string s; for(int i=1;i<=m;i++) { cin>>s; if (s=="INSERT") { read(pos),read(len); for(int i=1;i<=len;i++) { read(a[i]); } ft.insert(pos,len,a); } else if(s=="DELETE") { read(pos),read(len); ft.remove(pos,len); } else if (s=="REVERSE") { read(pos),read(len); ft.reverse(pos,len); } else if (s=="MAKE-SAME") { read(pos),read(len),read(val); ft.cover(pos,len,val); } else if (s=="MAX-SUM"){ read(pos),read(len); printf("%d\n",ft.get_max_sum(pos,len)); } else if (s=="GET-SUM") { read(pos),read(len); printf("%d\n",ft.get_sum(pos,len)); } else { read(pos); printf("%d\n",ft.ask_point(pos)); } } return 0; }

转载于:https://www.cnblogs.com/tt66ea-blog/p/10991879.html