LuoguP1503题解

发表于

简单的Splay操作题

Description

描述 县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来

1、消息为D x：鬼子将x号房子摧毁了，地道被堵上。

2、消息为R ：村民们将鬼子上一个摧毁的房子修复了。

3、消息为Q x：有一名士兵被围堵在x号房子中。

李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。

Samples

Input #1

1
2
3
4
5
6
7
8
9
10
7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

Output #1

1
2
3
4
1
0
2
4

Solution

Splay裸题.

首先对于摧毁操作D x, 我们把一个val = x的节点插入Splay.

这样可以让Q x操作转化为查询x的后继 - x的前趋 + 1.

R操作就直接用一个栈维护插入的数, 然后把栈顶Remove掉就完了.

注意: 初始化时应插入0和n+1两个节点, 以确保所以点都有前趋和后继

Code

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
/* Headers */
#include<algorithm>
#include<iostream>
#include<cstring>
#include<climits>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
    const int BUFSIZE = 1 << 20;
    char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
    char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
    inline char getch(){
        if(is == its)
            its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is == its)?EOF:*is++;
    }
    inline int getint(){
        int res = 0,neg = 0,ch = getch();
        while(!(isdigit(ch) || ch == '-') && ch != EOF)
            ch = getch();
        if(ch == '-'){
            neg = 1;ch = getch();
        }
        while(isdigit(ch)){
            res = (res << 3) + (res << 1)+ (ch - '0');
            ch = getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os - obuf,stdout);
        os = obuf;
    }
    inline void putch(char ch){
        *os++ = ch;
        if(os == ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res == 0) putch('0');
        else if(res < 0){putch('-');res = -res;}
        int top = 0;
        while(res){
            q[top++] = res % 10 + '0';
            res /= 10;
        }
        while(top--)	putch(q[top]);
    }
    inline void space(bool x){
    	if(!x) putch('\n');
    	else putch(' ');
    }
}
inline void read(int &x){
    int rt = FastIO::getint();
    x = rt;
}
inline void print(int x,bool enter){
    FastIO::putint(x);
    FastIO::flush();
    FastIO::space(enter);
}
/* definitions */
const int MAXN = 5e4 + 10;
struct Tree{
	int ch[2], size, cnt, val, fa;
	#define Lef(x, k) Splay[Splay[x].ch[0]].k
	#define Rig(x, k) Splay[Splay[x].ch[1]].k
}Splay[MAXN];
int n, m, root, Node;
std::stack<int> room;
/* functions */
inline bool FIND(int x) {
	return (Splay[Splay[x].fa].ch[1] == x);
}
inline void pushUp(int k) {
	Splay[k].size = Lef(k, size) + Rig(k, size) + Splay[k].cnt;	
}
inline void Rotate(int x) {
	int fx = Splay[x].fa, fy = Splay[fx].fa;
	int chx = FIND(x), chy = Splay[x].ch[chx ^ 1];
	Splay[fx].ch[chx] = chy; Splay[chy].fa = fx;
	Splay[fy].ch[FIND(fx)] = x; Splay[x].fa = fy;
	Splay[x].ch[chx ^ 1] = fx; Splay[fx].fa = x;
	pushUp(fx); pushUp(x);
}
inline void splay(int x, int rt = 0) {
	while(Splay[x].fa != rt) {
		int fx = Splay[x].fa, fy = Splay[fx].fa;
		if(fy != rt) {
			if(FIND(x) == FIND(fx)) Rotate(fx);
			else Rotate(x);
		}
		Rotate(x);
	}
	if(!rt) root = x;
}
inline void Insert(int x) {
	int rt = root, p = 0;
	while(rt && Splay[rt].val != x) {
		p = rt;
		rt = Splay[rt].ch[x > Splay[rt].val];
	}
	if(rt) Splay[rt].cnt++;
	else {
		rt = ++Node;
		if(p) Splay[p].ch[x > Splay[p].val] = rt;
		Splay[rt].ch[0] = Splay[rt].ch[1] = 0;
		Splay[rt].fa = p; Splay[rt].val = x;
		Splay[rt].cnt = Splay[rt].cnt = 1;
	}
	splay(rt);
}
inline void LowerX(int x) {
	int rt = root;
	while(Splay[rt].ch[x > Splay[rt].val] && x != Splay[rt].val)
		rt = Splay[rt].ch[x > Splay[rt].val];
	splay(rt);
}
inline int Querypre(int x) {
	LowerX(x);
	if(Splay[root].val < x) return root;
	int rt = Splay[root].ch[0];
	while(Splay[rt].ch[1]) rt = Splay[rt].ch[1];
	return rt;
}
inline int Querysuf(int x) {
	LowerX(x);
	if(Splay[root].val > x) return root;
	int rt = Splay[root].ch[1];
	while(Splay[rt].ch[0]) rt = Splay[rt].ch[0];
	return rt;
}
inline void Remove(int x) {
	int last = Querypre(x), next = Querysuf(x);
	splay(last), splay(next, last);
	int del = Splay[next].ch[0];
	if(Splay[del].cnt > 1) {Splay[del].cnt--; splay(del);}
	else Splay[next].ch[0] = 0;
}
int main(int argc,char *argv[]){
	scanf("%d %d", &n, &m);
	Insert(0); Insert(n + 1);
	FOR(i, 1, m, 1) {
		char opt; std::cin>>opt;
		if(opt == 'D') {
			int x; scanf("%d", &x);
			Insert(x); room.push(x);
		}
		if(opt == 'R') {
			Remove(room.top()); 
			room.pop();
		}
		if(opt == 'Q') {
			int x; scanf("%d", &x);
			LowerX(x);
			if(Splay[root].val == x) puts("0");
			else {
				int last = Querypre(x), next = Querysuf(x);
				int ans = Splay[next].val - Splay[last].val - 1;
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}

THE END