传送门
一道很全的splay模板题,自己搞了半天都不对,只能考别人的代码感受一下AC的味道,真香。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
/* TDD */
#define il inline
#define pb push_back
#define fi first
#define se second
#define ms(_data,v) memset(_data,v,sizeof(_data))
#define sc(n) scanf("%d",&n)
#define SC(n,m) scanf("%d %d",&n,&m)
#define SZ(a) int((a).size())
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define drep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-9;
const int N=2e5+7;
struct tree {
int key,size,fa,MIN,add,son[2];
bool flag;
} t[N];
int tot,root;
il void vis(int x) { // Debug
if (!x) return;
printf("节点:%2d : 左儿子 %2d 右儿子 %2d key值 %2d size值 %2d filp: %d\n",x,t[x].son[0],t[x].son[1],t[x].key,t[x].size,t[x].flag);
printf("节点:%2d : 最小值 %2d \n",x,t[x].MIN);
vis(t[x].son[0]);
vis(t[x].son[1]);
}
int A[N],n;
il void pushup(int x) {
t[x].size=t[t[x].son[0]].size+t[t[x].son[1]].size+1;
t[x].MIN=t[x].key;
if (t[x].son[0]) t[x].MIN=min(t[x].MIN,t[t[x].son[0]].MIN);
if (t[x].son[1]) t[x].MIN=min(t[x].MIN,t[t[x].son[1]].MIN);
}
il void pushdown(int x) {
if (t[x].flag) {
t[x].flag=false;
swap(t[x].son[0],t[x].son[1]);
t[t[x].son[0]].flag^=1;
t[t[x].son[1]].flag^=1;
}
if (t[x].add>0) {
if (t[x].son[0]) {
t[t[x].son[0]].key+=t[x].add;
t[t[x].son[0]].add+=t[x].add;
t[t[x].son[0]].MIN+=t[x].add;
}
if (t[x].son[1]) {
t[t[x].son[1]].key+=t[x].add;
t[t[x].son[1]].add+=t[x].add;
t[t[x].son[1]].MIN+=t[x].add;
}
t[x].add=0;
}
}
void rotate(int x,int p) {
int y=t[x].fa;
pushdown(y),pushdown(x);
t[y].son[!p]=t[x].son[p];
t[t[x].son[p]].fa=y;
t[x].fa=t[y].fa;
if (t[x].fa) t[t[x].fa].son[t[t[x].fa].son[1]==y]=x;
t[x].son[p]=y,t[y].fa=x;
pushup(y),pushup(x);
}
void Splay(int x,int to) {
while (t[x].fa!=to) {
if (t[t[x].fa].fa==to)
rotate(x,t[t[x].fa].son[0]==x);
else {
int y=t[x].fa,z=t[y].fa;
int p=(t[z].son[0]==y);
if (t[y].son[p]==x) rotate(x,!p),rotate(x,p);
else rotate(y,p),rotate(x,p);
}
}
if (to==0) root=x;
}
int newnode(int key,int fa) {
++tot;
t[tot].key=key,t[tot].fa=fa;
t[tot].size=1,t[tot].MIN=key;
t[tot].add=0,t[tot].flag=false;
t[tot].son[0]=t[tot].son[1]=0;
return tot;
}
int get_kth(int k) { //获得第k个元素的坐标
int x=root;
while(1){
pushdown(x);
if (k==t[t[x].son[0]].size+1) break;
if (k>t[t[x].son[0]].size+1) {
k-=t[t[x].son[0]].size+1;
x=t[x].son[1];
}
else x=t[x].son[0];
}
return x;
}
int bulid(int L,int R,int fa) {
if (L>R) return 0;
int mid=(L+R)>>1,x;
x=newnode(A[mid],fa);
t[x].son[0]=bulid(L,mid-1,x);
t[x].son[1]=bulid(mid+1,R,x);
pushup(x);
return x;
}
void add(int L,int R,int d) { //[l,r]区间都加上d
L=get_kth(L),R=get_kth(R+2);
Splay(L,0),Splay(R,L);
t[t[R].son[0]].key+=d;
t[t[R].son[0]].MIN+=d;
t[t[R].son[0]].add+=d;
pushup(R),pushup(L);
}
void reverse(int L,int R) { //翻转[l,r]区间
L=get_kth(L),R=get_kth(R+2);
Splay(L,0), Splay(R,L);
t[t[R].son[0]].flag^=1;
}
void revolve(int L,int R,int k) { //将[l,r]区间绕环转k次
k=(k%(R-L+1)+(R-L+1))%(R-L+1);
if (!k) return;
int x=get_kth(R-k+1),y=get_kth(R+2);
Splay(x,0),Splay(y,x);
int tmp=t[y].son[0];
t[y].son[0]=0;
pushup(y),pushup(x);
x=get_kth(L),y=get_kth(L+1);
Splay(x,0),Splay(y,x);
t[y].son[0]=tmp;
t[tmp].fa=y;
pushup(y),pushup(x);
}
void insert(int x,int p) { //在第x后面插入p
Splay(get_kth(x+1),0);
Splay(get_kth(x+2),root);
t[t[root].son[1]].son[0]=newnode(p,t[root].son[1]);
pushup(t[root].son[1]);
pushup(root);
}
void del(int x) { //删除第x个节点
Splay(get_kth(x),0);
Splay(get_kth(x+2),root);
t[t[root].son[1]].son[0]=0;
pushup(t[root].son[1]);
pushup(root);
}
int query(int L,int R) { //查询[l,r]区间的最小值
int x=get_kth(L);
int y=get_kth(R+2);
Splay(x,0);
Splay(y,x);
return t[t[y].son[0]].MIN;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&A[i]);
A[0]=A[n+1]=inf; //建树要加上虚点
root=bulid(0,n+1,0);
int m,x,y,z;
char ch[20];
scanf("%d",&m);
while (m--) {
scanf("%s",ch);
switch (ch[0]) {
case 'A':
scanf("%d %d %d",&x,&y,&z);
add(x,y,z);
break;
case 'R':
if (ch[3]=='E') {
scanf("%d %d",&x,&y);
reverse(x,y);
} else {
scanf("%d %d %d",&x,&y,&z);
revolve(x,y,z);
}
break;
case 'I':
scanf("%d %d",&x,&y);
insert(x,y);
break;
case 'D':
scanf("%d",&x);
del(x);
break;
case 'M':
scanf("%d %d",&x,&y);
printf("%d\n",query(x,y));
break;
}
}
return 0;
}
更多推荐
(POJ) 3580 SuperMemo
发布评论