「SCOI2014」方伯伯的Oj - 动态开点线段树 | Bill Yang's Blog
0%

「SCOI2014」方伯伯的Oj - 动态开点线段树

题目大意

    方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
    Oj上注册了$n$个用户,编号为$1\sim n$,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:

  1. 操作格式为$1 \ x \ y$,意味着将编号为$x$的用户编号改为$y$,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证$x$必然出现在队列中,同时$y$是一个当前不在排名中的编号。
  2. 操作格式为$2 \ x$,意味着将编号为$x$的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为$x$用户的排名。
  3. 操作格式为$3 \ x$,意味着将编号为$x$的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为$x$用户的排名。
  4. 操作格式为$4 \ k$,意味着查询当前排名为$k$的用户编号,执行完该操作后需要输出当前操作用户的编号。

    但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:
    $1 \ x+a \ y+a$
    $2 \ x+a$
    $3 \ x+a$
    $4 \ k+a$
    其中$a$为上一次操作得到的输出,一开始$a=0$。
    例如:
    上一次操作得到的输出是$5$
    这一次操作的输入为:$1 \ 13 \ 15$
    因为这个输入是经过加密后的,所以你应该处理的操作是$1 8 10$
    现在你截获丁方伯伯的所有操作,希望你能给出结果。


题目分析

这道题做法很多,什么两个splay,两个treap,map+treap/splay都可以做。
然而我用的动态开点线段树。

和NOIP2017D2T3类似,将排名移动到第一位或最后一位用动态开点线段树维护。
线段树左右边界开大一点,每次移动排名时往前和往后移动当前区间边界。
统计下size就可以搞事情了。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;

inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}

const int L=-2e8,R=2e8; //boundary limit

struct Tree {
Tree *ls,*rs;
int size,val;
Tree(int l=0,int r=0) {size=r-l+1;}
} *root=new Tree(L,R);

struct Segment_Tree {
#define mid ((left+right)>>1)
void newnode(Tree *&now,int left,int right) {if(!now)now=new Tree(left,right);}
void insert(Tree *&now,int left,int right,int tar,int val) {
newnode(now,left,right);
if(left==right) {now->val=val;return;}
newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
if(tar<=now->ls->size)insert(now->ls,left,mid,tar,val);
else insert(now->rs,mid+1,right,tar-now->ls->size,val);
}
void remove(Tree *&now,int left,int right,int tar) {
if(!now)now=new Tree(left,right);
now->size--;
if(left==right)return;
newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
if(tar<=now->ls->size)remove(now->ls,left,mid,tar);
else remove(now->rs,mid+1,right,tar-now->ls->size);
}
int query(Tree *&now,int left,int right,int tar) {
if(!now)now=new Tree(left,right);
if(left==right)return now->val?now->val:left;
newnode(now->ls,left,mid),newnode(now->rs,mid+1,right);
if(tar<=now->ls->size)return query(now->ls,left,mid,tar);
else return query(now->rs,mid+1,right,tar-now->ls->size);
}
int sum(Tree *&now,int left,int right,int Left,int Right) {
if(Right<left||Left>right)return 0;
if(!now)now=new Tree(left,right);
if(Left<=left&&Right>=right)return now->size;
return sum(now->ls,left,mid,Left,Right)+sum(now->rs,mid+1,right,Left,Right);
}
} st;

map<int,int> id;
int n,m,ans=0;

int main() {
n=Get_Int();
m=Get_Int();
int left=1,right=n;
for(int i=1; i<=m; i++) {
int opt=Get_Int();
if(opt==1) {
int x=Get_Int()-ans,y=Get_Int()-ans;
id[y]=id.count(x)?id[x]:x;
st.insert(root,L,R,st.sum(root,L,R,L,id[y]),y); //insert at id[y]
printf("%d\n",ans=st.sum(root,L,R,left,id[y]));
} else if(opt==2) {
int x=Get_Int()-ans;
ans=st.sum(root,L,R,left,id.count(x)?id[x]:x);
printf("%d\n",ans);
st.remove(root,L,R,left-L+ans);
st.insert(root,L,R,left-L,x);
id[x]=--left;
} else if(opt==3) {
int x=Get_Int()-ans;
ans=st.sum(root,L,R,left,id.count(x)?id[x]:x);
printf("%d\n",ans);
st.remove(root,L,R,left-L+ans);
st.insert(root,L,R,st.sum(root,L,R,L,right)+1,x);
id[x]=++right;
} else {
int k=Get_Int()-ans;
printf("%d\n",ans=st.query(root,L,R,left-L+k));
}
}
return 0;
}
姥爷们赏瓶冰阔落吧~