> 建议使用$Redblack\ tree$,不过你的代码去哪了
by arfa @ 2018-08-22 21:46:25
```cpp
#include<bits/stdc++.h>
using namespace std;
struct splaynode{
int l, r, ch[2], f, size, cnt;
}a[10000000];
int last = 0;
class hash{
private:
int tot, root;
struct hashnode{
int l, r, ch[2], f;
}a[10000000];
void con(int x, int f, int son){
a[x].f = f;a[f].ch[son] = x;
}
bool get(int x){
return x == a[a[x].f].ch[1];
}
void rotate(int x){
int f = a[x].f, gf = a[f].f, son = get(x), gson = get(f);
con(a[x].ch[son^ 1], f, son);
con(f, x, son ^ 1);
con(x, gf, gson);
}
void splay(int x, int to){
int fa = a[to].f;
while(a[x].f != fa){
if(a[x].f == to){
rotate(x);
return;
}
if(get(x) == get(a[x].f)){
rotate(a[x].f);rotate(x);
}
else{
rotate(x);rotate(x);
}
}
}
public:
void insert(int l, int r){
if(!root){
root = ++tot;
a[tot].l = l;a[tot].r = r;
return;
}
int now = root;
while(1){
int la = now;
now = a[now].ch[a[now].l < l];
if(!now){
++tot;
a[tot].l = l;a[tot].r = r;con(tot, la, a[la].l < l);
splay(tot, root);root = tot;return;
}
}
}
int find(int x){
int now = root;
while(1){
if(a[now].l <= x && a[now].r >= x){
splay(now, root);root = now;
return now;
}
now = a[now].ch[a[now].l < x];
}
return 0;
}
void delet(int x){
int now = find(x);
if(a[now].l == a[now].r){
if(!a[now].ch[0]){
a[a[now].ch[1]].f =0;root = a[now].ch[1];
return;
}
int x = a[now].ch[0];
while(a[x].ch[1])x = a[x].ch[1];
splay(x, a[now].ch[0]);
con(a[now].ch[1], x, 1);
a[x].f = 0;root = x;
return;
}
if(a[now].l == x){
a[now].l++;return;
}
if(a[now].r == x){
a[now].r--;return;
}
int r = a[now].r;
a[now].r = x - 1;
insert(x + 1, r);
}
void print(int x, int d){
if(x == 0) return;
print(a[x].ch[0], d + 1);
for(int i =1; i <= d; i++)printf(" ");printf("%d %d %d\n", x, a[x].l, a[x].r);
print(a[x].ch[1], d + 1);
}
void pr(){
printf("\n\n");
printf("root = %d\n", root);
print(root, 1);
printf("\n\n");
}
}h;
```
by 13813812138xixixixi @ 2018-08-22 21:46:33
```
int tot, root;
void update(int x){
a[x].size = a[a[x].ch[0]].size + a[a[x].ch[1]].size + a[x].cnt;
}
void con(int x, int f, int son){
a[x].f = f;a[f].ch[son] = x;
}
bool get(int x){
return x == a[a[x].f].ch[1];
}
void rotate(int x){
int f = a[x].f, gf = a[f].f, son = get(x), gson = get(f);
con(a[x].ch[son^ 1], f, son);
con(f, x, son ^ 1);
con(x, gf, gson);
update(f);update(x);
}
void splay(int x, int to){
int fa = a[to].f;
while(a[x].f != fa){
if(a[x].f == to){
rotate(x);
return;
}
if(get(x) == get(a[x].f)){
rotate(a[x].f);rotate(x);
}
else{
rotate(x);rotate(x);
}
}
}
void newtr(int n){
root = ++tot;
a[tot].l = 1;a[tot].r = n;a[tot].size = 1;
h.insert(1, n);
}
int caozuo1(int x, int y){
int now = h.find(x);
splay(now, root);root = now;
if(a[now].l == a[now].r){
++tot;root = tot;
a[tot] = a[now];con(a[now].ch[0], tot, 0);con(a[now].ch[1], tot, 1);a[tot].l = a[tot].r = y;
h.delet(x);h.insert(y, y);
return last = a[a[tot].ch[0]].size + 1;;
}
if(a[now].l == x){
a[now].l++;a[now].cnt--;
h.delet(x);h.insert(y, y);
++tot;
con(a[now].ch[0], tot, 0);a[now].ch[0] = 0;
con(now, tot, 1);a[tot].l = a[tot].r = y;a[tot].cnt = 1;root = tot;
update(now);update(tot);
return last = a[a[tot].ch[0]].size + 1;;
}
if(a[now].r == x){
a[now].r--;a[now].cnt--;
h.delet(x);h.insert(y, y);
++tot;
con(a[now].ch[1], tot, 1);a[now].ch[1] = 0;
con(now, tot, 0);a[tot].l = a[tot].r = y;a[tot].cnt = 1;root = tot;
update(now);update(tot);
return last = a[a[tot].ch[0]].size + 1;;
}
int r = a[now].r;
a[now].r = x - 1;a[now].cnt = (x - 1) - a[now].l + 1;
++tot;a[tot].l = x + 1;a[tot].r = r;a[tot].cnt = r - x;int rs = tot;
++tot;a[tot].l = a[tot].r = y;a[tot].cnt = 1;con(a[now].ch[1], rs, 1);root = tot;a[now].ch[1] = 0;
con(now, tot, 0);con(rs, tot, 1);
h.delet(x);h.insert(y, y);
update(rs);update(now);update(tot);
return last = a[a[tot].ch[0]].size + 1;
}
void caozuo2(int x){
caozuo1(x, x);
int now = root;
if(!a[now].ch[1]){
a[now].ch[1] = a[now].ch[0];
a[now].ch[0] = 0;
return ;
}
now = a[now].ch[1];
while(a[now].ch[0])now = a[now].ch[0];
splay(now, a[root].ch[1]);
a[now].ch[0] = a[root].ch[0];a[root].ch[0] = 0;a[a[now].ch[0]].f = now;
update(now);
}
void caozuo3(int x){
caozuo1(x, x);
int now = root;
if(!a[now].ch[0]){
a[now].ch[0] = a[now].ch[1];
a[now].ch[1] = 0;
return ;
}
now = a[now].ch[0];
while(a[now].ch[1])now = a[now].ch[1];
splay(now, a[root].ch[0]);
a[now].ch[1] = a[root].ch[1];a[root].ch[1] = 0;a[a[now].ch[1]].f = now;
update(now);
}
int find(int x){
int now = root;
while(1){
if(a[a[now].ch[0]].size >= x) now = a[now].ch[0];
else{
int temp = a[a[now].ch[0]].size + a[now].cnt;
if(temp >= x){
splay(now, root);root = now;
return x - a[a[now].ch[0]].size;
}
x -= temp;now = a[now].ch[1];
}
}
}
void print(int x, int d){
if(x == 0) return;
print(a[x].ch[0], d + 1);
for(int i =1; i <= d; i++)printf(" ");printf("%d %d %d\n", x, a[x].l, a[x].r);
print(a[x].ch[1], d + 1);
}
void pr(){
printf("\n\n");
printf("root = %d\n", root);
print(root, 1);
printf("\n\n");
}
int main(){
int n, m;
scanf("%d%d", &n, &m);
newtr(n);
last = 0;
for (int i = 1; i <= m; i++){
int x, y;
scanf("%d", &x);
switch(x){
case 1:{
int z;
scanf("%d%d", &y, &z);
caozuo1(y - last, z - last);
printf("%d\n", last);
break;
}
case 2:{
scanf("%d",&y);
caozuo2(y - last);
printf("%d\n", last);
break;
}
case 3:{
scanf("%d", &y);
caozuo3(y - last);
printf("%d\n", last);
break;
}
case 4:{
scanf("%d", &y);
int k = find(y - last);
printf("%d", last = a[root].l + k - 1);
break;
}
}
// h.pr();
// pr();
}
}
```
by 13813812138xixixixi @ 2018-08-22 21:47:02
不会红黑树呀， 只会splay
by 13813812138xixixixi @ 2018-08-22 21:47:34
膜拜大佬QWQ
by 御坂如此报告 @ 2018-08-22 21:48:40
太长分两次发
by 13813812138xixixixi @ 2018-08-22 21:49:19
两个splay一个维护编号，一个维护排名
by 13813812138xixixixi @ 2018-08-22 21:50:25
lxl五分钟手打rbt！
by ustze @ 2018-08-22 21:55:29
大佬太强了没法比
by 13813812138xixixixi @ 2018-08-22 21:56:22
真心求教
by 13813812138xixixixi @ 2018-08-22 21:58:31