supermemo bzoj-1895 Pku-3580
題目大意：給定一個n個數的序列，需支援：區間加，區間翻轉，區間平移，單點插入，單點删除，查詢區間最小值。
注釋：$1\le n\le 6.1\cdot 10^6$。
想法：
這資料範圍給的我真是醉了。
顯然用平衡樹，這裡用非旋轉Treap，題目讓你幹什麼你就幹什麼。
區間加：撕出子樹區間後打标記維護區間加。
區間翻轉：撕出子樹區間後打标記維護區間翻轉。
區間平移：相當于兩段相鄰區間交換，是以撕成四部分：左邊，第一個區間，第二個區間，右邊。然後按照左邊，第二個區間，第一個區間，右邊合并即可。
單點插入：将一個點當成一個非旋轉Treap，在插入位置左右撕開後将這個點放進去然後合上。
單點删除：同理，删除位置左，删除節點，右撕開後，不管這個點，直接把左邊右邊合上。
最後，附上醜陋的代碼... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1210010
using namespace std;
struct Node
{
int ls,rs; int val,key;
int size; int add,rev;
int minn;
}a[N]; int tot;
struct par{int x,y;};
inline void pushup(int x)
{
int ls=a[x].ls,rs=a[x].rs;
a[x].size=1; a[x].minn=a[x].val;
if(ls) a[x].size+=a[ls].size,a[x].minn=min(a[x].minn,a[ls].minn);
if(rs) a[x].size+=a[rs].size,a[x].minn=min(a[x].minn,a[rs].minn);
}
inline void pushdown(int x)
{
int ls=a[x].ls,rs=a[x].rs;
if(a[x].rev)
{
if(ls) a[ls].rev^=1,swap(a[ls].ls,a[ls].rs);
if(rs) a[rs].rev^=1,swap(a[rs].ls,a[rs].rs);
a[x].rev=0;
}
if(a[x].add)
{
if(ls) a[ls].add+=a[x].add,a[ls].minn+=a[x].add,a[ls].val+=a[x].add;
if(rs) a[rs].add+=a[x].add,a[rs].minn+=a[x].add,a[rs].val+=a[x].add;
a[x].add=0;
}
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
pushdown(x); pushdown(y);
if(a[x].key>a[y].key)
{
a[x].rs=merge(a[x].rs,y); pushup(x);
return x;
}
else
{
a[y].ls=merge(x,a[y].ls); pushup(y);
return y;
}
}
par split(int x,int k)
{
if(!k) return (par){0,x};
pushdown(x);
int ls=a[x].ls,rs=a[x].rs;
if(k==a[ls].size)
{
a[x].ls=0; pushup(x);
return (par){ls,x};
}
else if(k==a[ls].size+1)
{
a[x].rs=0; pushup(x);
return (par){x,rs};
}
else if(k<a[ls].size)
{
par t=split(ls,k);
a[x].ls=t.y; pushup(x);
return (par){t.x,x};
}
else
{
par t=split(rs,k-a[ls].size-1);
a[x].rs=t.x; pushup(x);
return (par){x,t.y};
}
}
inline int newnode(int val)
{
tot++; a[tot].val=a[tot].minn=val;
a[tot].ls=a[tot].rs=0;
a[tot].size=1; a[tot].key=rand()*rand();
a[tot].rev=a[tot].add=0;
return tot;
}
inline void update(int x,int val)
{
a[x].add+=val; a[x].minn+=val; a[x].val+=val;
}
inline void rev(int x)
{
a[x].rev^=1; swap(a[x].ls,a[x].rs);
}
int insert(int x,int k,int val)
{
par t=split(x,k);
return merge(t.x,merge(newnode(val),t.y));
}
void output(int x)
{
int ls=a[x].ls,rs=a[x].rs;
if(ls) output(ls);
printf("%d ",a[x].val);
if(rs) output(rs);
}
int main()
{
// freopen("1895.in","r",stdin);
// freopen("1895.out","w",stdout);
srand(19260817);
int n; cin >> n ; int root=1; int x; scanf("%d",&x); root=newnode(x);
for(int i=2;i<=n;i++)
{
scanf("%d",&x);
root=merge(root,newnode(x));
}
int y,z; char opt[100];
int m; cin >> m ; for(int i=1;i<=m;i++)
{
scanf("%s",opt+1);
if(opt[1]=='A')
{
scanf("%d%d",&x,&y);
par t1=split(root,x-1);
par t2=split(t1.y,y-x+1);
scanf("%d",&z);
update(t2.x,z);
root=merge(t1.x,merge(t2.x,t2.y));
}
else if(opt[1]=='R'&&opt[4]=='E')
{
scanf("%d%d",&x,&y);
par t1=split(root,x-1);
par t2=split(t1.y,y-x+1);
rev(t2.x);
root=merge(t1.x,merge(t2.x,t2.y));
}
else if(opt[1]=='R'&&opt[4]=='O')
{
scanf("%d%d%d",&x,&y,&z);
par t1=split(root,x-1);
par t2=split(t1.y,y-x+1);
par t3=split(t2.x,a[t2.x].size-(z%a[t2.x].size));
root=merge(t1.x,merge(merge(t3.y,t3.x),t2.y));
}
else if(opt[1]=='I')
{
scanf("%d%d",&x,&y);
y=newnode(y);
par t=split(root,x);
root=merge(t.x,merge(y,t.y));
}
else if(opt[1]=='D')
{
scanf("%d",&x);
par t1=split(root,x-1);
par t2=split(t1.y,1);
root=merge(t1.x,t2.y);
}
else if(opt[1]=='M')
{
scanf("%d%d",&x,&y);
par t1=split(root,x-1);
par t2=split(t1.y,y-x+1);
printf("%d\n",a[t2.x].minn);
root=merge(t1.x,merge(t2.x,t2.y));
}
}
return 0;
}
小結：非旋轉Treap就是比splay優越！
轉載于:https://www.cnblogs.com/ShuraK/p/9716194.html