本文共 5437 字，大约阅读时间需要 18 分钟。
题意：
给定一个数组，对数组进行6种操作。
区间加，区间翻转，插入一个值，删除一个值，区间求最小值。
区间循环移位。
题解：
前5种属于伸展树的基本操作，区间循环移位需要转化成基本操作：
区间[l,r]循环右移T位(T=T%(r-l+1) )。相当于区间[l,r-T]和区间[r-T+1,r]
调换了位置。通过区间删除和插入可以完成。
注意：删除操作需要有内存回收。
#include#include #include #define ddd puts("111");using namespace std;#define keyv ch[ch[root][1]][0]const int INF = 0x3f3f3f3f;const int maxn = 2e5 + 99;int pre[maxn],sz[maxn],ch[maxn][2],addv[maxn],minv[maxn],key[maxn],rev[maxn],root,tot1;int s[maxn],tot2;///内存池，当有删除操作的时候进行回收int a[maxn];int n,q;void update_add(int r,int add){ if(r==0)return; key[r] += add; minv[r] += add; addv[r] += add;}void update_rev(int r){ if(r == 0)return; swap(ch[r][0],ch[r][1]); rev[r]^=1;///下面的反转次数+1。}void pushdown(int r){ if(rev[r]) { update_rev(ch[r][0]); update_rev(ch[r][1]); rev[r] = 0; } if(addv[r]) { update_add(ch[r][0],addv[r]); update_add(ch[r][1],addv[r]); addv[r] = 0; }}void pushup(int r){ sz[r] = 1 + sz[ch[r][0]]+sz[ch[r][1] ]; minv[r] = key[r]; if(ch[r][0])minv[r] = min(minv[r],minv[ch[r][0]]); if(ch[r][1])minv[r] = min(minv[r],minv[ch[r][1]]);}void newnode(int &r,int fa,int k){ if(tot2)r = s[tot2--]; else r = ++tot1; minv[r] = key[r] = k; pre[r] = fa; rev[r] = addv[r] = ch[r][0] = ch[r][1] = 0; sz[r] = 1;}void build(int &x,int l,int r,int fa){ if(l>r)return; int m = (l+r)>>1; newnode(x,fa,a[m]); build(ch[x][0],l,m-1,x); build(ch[x][1],m+1,r,x); pushup(x);}void init(){ root = tot1 = tot2 = 0; pre[root] = ch[root][1] = ch[root][0] = addv[root] = key[root] = rev[root] = sz[root] = 0; minv[root] = INF; newnode(root,0,INF); newnode(ch[root][1],root,INF); build(keyv,1,n,ch[root][1]); pushup(ch[root][1]); pushup(root);}void rotate(int x,int d){ int y = pre[x]; pushdown(y); pushdown(x); ch[y][!d] = ch[x][d]; pre[ch[x][d] ] = y; if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x; pre[x] = pre[y]; ch[x][d] = y; pre[y] = x; pushup(y);}void splay(int r,int goal){ while(pre[r] != goal) { if(pre[pre[r]] == goal) rotate(r,ch[pre[r]][0]==r); else { int y = pre[r]; int d = ch[pre[y]][0] == y; if(ch[y][d] == r) { rotate(r,!d); rotate(r,d); } else { rotate(y,d); rotate(r,d); } } } pushup(r); if(goal==0)root = r;}int kth(int r,int k){ pushdown(r); int t = sz[ch[r][0]]; if(t+1 == k) return r; else if(k<=t) return kth(ch[r][0],k); else return kth(ch[r][1],k-1-t);}int getmax(int r){ pushdown(r); while(ch[r][1]) { r = ch[r][1]; pushdown(r); } return r;}int getmin(int r){ pushdown(r); while(ch[r][0]) { r = ch[r][0]; pushdown(r); } return r;}/**本题*/void add(int l,int r,int v){ splay(kth(root,l),0); splay(kth(root,r+2),root); update_add(keyv,v); pushup(ch[root][1]); pushup(root);}void Reverse(int l,int r){ splay(kth(root,l),0); splay(kth(root,r+2),root); update_rev(keyv); pushup(ch[root][1]); pushup(root);}void revolve(int l,int r,int T)///区间循环移位{ int len = r-l+1; T = (T%len); if(T==0)return; int m = r - T;/**区间[l,m],[m+1,r]调换位置*/ splay(kth(root,m+1),0); splay(kth(root,r+2),root); int tmp = keyv; keyv = 0; pushup(ch[root][1]); pushup(root);///先把第二个区间删除。 splay(kth(root,l),0); splay(kth(root,l+1),root); keyv = tmp; pre[tmp] = ch[root][1]; pushup(ch[root][1]); pushup(root);///再插入第一个区间前。 这样做的前提是两个区间是相邻的！}void Insert(int x,int p)///插入{ splay(kth(root,x+1),0);///x后 splay(kth(root,x+2),root);///x+1前 newnode(keyv,ch[root][1],p); pushup(ch[root][1]); pushup(root);}void Erase(int r){ if(r) { s[++tot2] = r; Erase(ch[r][0]); Erase(ch[r][1]); }}void ddelete(int r)///删除{ splay(kth(root,r),0); splay(kth(root,r+2),root); Erase(keyv); pre[keyv] = 0; keyv = 0; pushup(ch[root][1]); pushup(root);}int mmin(int l,int r)///区间最小{ splay(kth(root,l),0); splay(kth(root,r+2),root); return minv[keyv];}void Treavel(int x){ if(x) { pushdown(x); Treavel(ch[x][0]); printf("%d ",key[x]); Treavel(ch[x][1]); }}int main(){ int x,y,z; char op[20]; while(scanf("%d",&n)==1) { for(int i=1;i<=n;i++) scanf("%d",a+i); init(); scanf("%d",&q); while(q--) { scanf("%s",op); if(strcmp(op,"ADD") == 0) { scanf("%d%d%d",&x,&y,&z); add(x,y,z); } else if(strcmp(op,"REVERSE")==0) { scanf("%d%d",&x,&y); Reverse(x,y); } else if(strcmp(op,"REVOLVE")==0) { scanf("%d%d%d",&x,&y,&z); revolve(x,y,z); } else if(strcmp(op,"DELETE")==0) { scanf("%d",&x); ddelete(x); } else if(strcmp(op,"MIN")==0) { scanf("%d%d",&x,&y); printf("%d\n",mmin(x,y)); } else if(strcmp(op,"INSERT")==0) { scanf("%d%d",&x,&y); Insert(x,y); } //Treavel(root); } }}
转载地址：http://nbyci.baihongyu.com/