最近补基础数据结构的最后一题，说实话，这题比上一题简单多了。这里面有一个右移T次的操作，其实就是把数列分成[l,r-T],[r-T+1,r]然后把前一段插到后一段后面。这题我写傻逼了，wa了5发，发现我把右移写成了左移。。。
明天回家了，待会买点东西，回来写个Splay树小结！！！
下面附上这道题的AC代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
#define INF 0x3fffffff
#define LL long long
#define FOR(i,x,y) for(int i = x;i < y;i ++)
#define IFOR(i,x,y) for(int i = x;i > y;i --)
#define Key_Tree ch[ch[root][1]][0]
#define MAXN 550000
using namespace std;
int n,m;
int num[MAXN];
struct SplayTree{
int ch[MAXN][2],sz[MAXN],s[MAXN],pre[MAXN],key[MAXN],root,tot1,tot2,add[MAXN],minx[MAXN];
int flip[MAXN];
//固定部分，不需要修改
void Rotate(int x,int kind){
int y = pre[x];
Push_Down(y);
Push_Down(x);
ch[y][!kind] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y]){
ch[pre[y]][ch[pre[y]][1] == y] = x;
}
pre[x] = pre[y];
ch[x][kind] = y;
pre[y] = x;
Push_Up(y);
}
void Splay(int x,int goal){
Push_Down(x);
while(pre[x] != goal){
Push_Down(pre[pre[x]]); Push_Down(pre[x]); Push_Down(x);
if(pre[pre[x]] == goal){
Rotate(x,ch[pre[x]][0] == x);
}
else{
int y = pre[x];
int kind = (ch[pre[y]][0] == y);
if(ch[y][kind] == x){
Rotate(x,!kind);
Rotate(x,kind);
}
else{
Rotate(y,kind);
Rotate(x,kind);
}
}
}
Push_Up(x);
if(!goal) root = x;
}
void RotateTo(int k,int goal){
int x = root;
Push_Down(x);
while(sz[ch[x][0]] != k){
if(k < sz[ch[x][0]]){
x = ch[x][0];
}
else{
k -= (sz[ch[x][0]]+1);
x = ch[x][1];
}
Push_Down(x);
}
Splay(x,goal);
}
//以上为固定部分，不需要修改！！！
//debug部分copy from hh
void Treaval(int x) {
//Push_Down(x);
if(x) {
Push_Down(x);
Treaval(ch[x][0]);
printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d
",x,ch[x][0],ch[x][1],pre[x],sz[x],key[x]);
Treaval(ch[x][1]);
}
}
void debug() {printf("%d
",root);Treaval(root);}
//以上debug
void NewNode(int& x,int father,int k){
if(tot2) x = s[tot2--];
else x = ++tot1;
pre[x] = father;
minx[x] = key[x] = k;
ch[x][0] = ch[x][1] = 0;
add[x] = 0;
sz[x] = 1;
flip[x] = 0;
}
void Update_Add(int x,int value){
if(!x) return;
add[x] += value;
key[x] += value;
minx[x] += value;
}
void Update_Flip(int x){
if(!x) return;
swap(ch[x][0],ch[x][1]);
flip[x] ^= 1;
}
void Push_Up(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
minx[x] = min(min(minx[ch[x][0]],minx[ch[x][1]]),key[x]);
}
void Push_Down(int x){
if(add[x]){
Update_Add(ch[x][0],add[x]);
Update_Add(ch[x][1],add[x]);
add[x] = 0;
}
if(flip[x]){
Update_Flip(ch[x][0]);
Update_Flip(ch[x][1]);
flip[x] = 0;
}
}
void Build(int& x,int l,int r,int father){
if(l > r) return;
int mid = (l+r) >> 1;
NewNode(x,father,num[mid]);
Build(ch[x][0],l,mid-1,x);
Build(ch[x][1],mid+1,r,x);
Push_Up(x);
}
void Init(){
minx[0] = INF;
pre[0] = add[0] = sz[0] = 0;
root = tot1 = tot2 = 0;
NewNode(root,0,INF);
NewNode(ch[root][1],root,INF);
sz[root] = 2;
Build(Key_Tree,0,n-1,ch[root][1]);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Add(int l,int r,int value){
RotateTo(l-1,0);
RotateTo(r+1,root);
Update_Add(Key_Tree,value);
}
void Erase(int x){
if(!x) return;
s[++tot2] = x;
Erase(ch[x][0]);
Erase(ch[x][1]);
}
void Insert(int x,int value){
RotateTo(x,0);
RotateTo(x+1,root);
NewNode(Key_Tree,ch[root][1],value);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Delete(int x){
RotateTo(x-1,0);
RotateTo(x+1,root);
Erase(Key_Tree);
Key_Tree = 0;
Push_Up(ch[root][1]);
Push_Up(root);
}
void Reverse(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
Update_Flip(Key_Tree);
Push_Up(ch[root][1]);
Push_Up(root);
}
void Revolve(int l,int r,int k){
k = (k%(r-l+1)+(r-l+1))%(r-l+1);
if(!k) return;
RotateTo(l-1,0);
RotateTo(r+1,root);
RotateTo(r-k,ch[root][1]);
int y = ch[Key_Tree][1];
pre[ch[Key_Tree][1]] = 0;
ch[Key_Tree][1] = 0;
Push_Up(Key_Tree);
Push_Up(ch[root][1]);
Push_Up(root);
RotateTo(l,ch[root][1]);
pre[y] = Key_Tree;
ch[Key_Tree][0] = y;
Push_Up(Key_Tree);
Push_Up(ch[root][1]);
Push_Up(root);
}
int Min(int l,int r){
RotateTo(l-1,0);
RotateTo(r+1,root);
return minx[Key_Tree];
}
int Get_Pre(int x){
Push_Down(x);
x = ch[x][0];
while(x){
Push_Down(x);
while(ch[x][1]){
x = ch[x][1];
Push_Down(x);
}
return x;
}
return -1;
}
int Get_Next(int x){
Push_Down(x);
x = ch[x][1];
while(x){
Push_Down(x);
while(ch[x][0]){
x = ch[x][0];
Push_Down(x);
}
return x;
}
return -1;
}
}spt;
int main()
{
//freopen("test.in","r",stdin);
while(~scanf("%d",&n)){
FOR(i,0,n) scanf("%d",&num[i]);
spt.Init();
scanf("%d",&m);
char op[10];
//spt.debug();
FOR(i,0,m){
scanf("%s",op);
if(!strcmp(op,"ADD")){
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
spt.Add(x,y,v);
}
else if(!strcmp(op,"REVERSE")){
int x,y;
scanf("%d%d",&x,&y);
spt.Reverse(x,y);
}
else if(!strcmp(op,"REVOLVE")){
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
spt.Revolve(x,y,t);
}
else if(!strcmp(op,"INSERT")){
int x,p;
scanf("%d%d",&x,&p);
spt.Insert(x,p);
}
else if(!strcmp(op,"DELETE")){
int x;
scanf("%d",&x);
spt.Delete(x);
}
else{
int x,y;
scanf("%d%d",&x,&y);
printf("%d
",spt.Min(x,y));
}
//spt.debug();
}
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。