什么毒瘤......
题意：模拟一棵单旋splay，求每次插入，splay最值，删除最值的操作次数。
解：乍一看感觉很神，又因为是LCT题单上的，然后就折磨了我好久，最后跑去看题解...
居然是手玩找规律题！我疯了。
是这样的，因为它只会单旋，而且只会splay最值，手玩一下就发现整个树的形态不变......就是把一个节点拿上去当根了，然后它的子节点代替它的位置。
插入，根据普通splay插入可知它一定接在前驱/后继的下面。找到深度大的那个就行了。
具体来说，用一棵值域线段树维护每个权值的深度。同时还要记录根，fa，son，树中节点数...
线段树要支持区间加，单点修改，查询第k大，区间求和，单点查询等功能。
大力分类讨论，注意一波细节，然后就A了...
1 #include2 #include 3 4 const int N = 100010; 5 6 struct Node { 7 int f, x; 8 }node[N]; 9 10 int tag[N * 4], sum[N * 4], fa[N], s[N][2], X[N], temp; 11 12 inline void pushdown(int o) { 13 if(tag[o]) { 14 tag[o << 1] += tag[o]; 15 tag[o << 1 | 1] += tag[o]; 16 tag[o] = 0; 17 } 18 return; 19 } 20 21 int ask(int p, int l, int r, int o) { 22 if(l == r) { 23 if(!sum[o]) { 24 tag[o] = 0; 25 } 26 return tag[o]; 27 } 28 pushdown(o); 29 int mid = (l + r) >> 1; 30 if(p <= mid) { 31 return ask(p, l, mid, o << 1); 32 } 33 else { 34 return ask(p, mid + 1, r, o << 1 | 1); 35 } 36 } 37 38 void change(int p, int v, int l, int r, int o) { 39 if(l == r) { 40 if(v == -1) { 41 sum[o] = tag[o] = 0; 42 } 43 else { 44 sum[o] = 1; 45 tag[o] = v; 46 } 47 return; 48 } 49 pushdown(o); 50 int mid = (l + r) >> 1; 51 if(p <= mid) { 52 change(p, v, l, mid, o << 1); 53 } 54 else { 55 change(p, v, mid + 1, r, o << 1 | 1); 56 } 57 sum[o] = sum[o << 1] + sum[o << 1 | 1]; 58 return; 59 } 60 61 int getK(int k, int l, int r, int o) { 62 if(l == r) { 63 return r; 64 } 65 int mid = (l + r) >> 1; 66 if(k <= sum[o << 1]) { 67 return getK(k, l, mid, o << 1); 68 } 69 else { 70 return getK(k - sum[o << 1], mid + 1, r, o << 1 | 1); 71 } 72 } 73 74 int getSum(int L, int R, int l, int r, int o) { 75 if(L <= l && r <= R) { 76 return sum[o]; 77 } 78 int mid = (l + r) >> 1, ans = 0; 79 if(L <= mid) { 80 ans += getSum(L, R, l, mid, o << 1); 81 } 82 if(mid < R) { 83 ans += getSum(L, R, mid + 1, r, o << 1 | 1); 84 } 85 return ans; 86 } 87 88 void add(int L, int R, int v, int l, int r, int o) { 89 if(L <= l && r <= R) { 90 tag[o] += v; 91 return; 92 } 93 pushdown(o); 94 int mid = (l + r) >> 1; 95 if(L <= mid) { 96 add(L, R, v, l, mid, o << 1); 97 } 98 if(mid < R) { 99 add(L, R, v, mid + 1, r, o << 1 | 1);100 }101 return;102 }103 104 int main() {105 int q, f, x, siz = 0, rt;106 scanf("%d", &q);107 for(int i = 1; i <= q; i++) {108 scanf("%d", &node[i].f);109 if(node[i].f == 1) {110 scanf("%d", &node[i].x);111 X[++temp] = node[i].x;112 }113 }114 std::sort(X + 1, X + temp + 1);115 temp = std::unique(X + 1, X + temp + 1) - X - 1;116 for(int i = 1; i <= q; i++) {117 f = node[i].f;118 if(f == 1) {119 x = std::lower_bound(X + 1, X + temp + 1, node[i].x) - X;120 int k = getSum(1, x, 1, temp, 1), d;121 if(!siz) {122 d = 1;123 rt = x;124 }125 else if(!k) {126 int r = getK(1, 1, temp, 1);127 d = ask(r, 1, temp, 1) + 1;128 fa[x] = r;129 s[r][0] = x;130 }131 else if(k == siz) {132 int l = getK(siz, 1, temp, 1);133 d = ask(l, 1, temp, 1) + 1;134 fa[x] = l;135 s[l][1] = x;136 }137 else {138 int l = getK(k, 1, temp, 1); 139 int r = getK(k + 1, 1, temp, 1);140 int dl = ask(l, 1, temp, 1);141 int dr = ask(r, 1, temp, 1);142 if(dl > dr) {143 d = dl + 1;144 fa[x] = l;145 s[l][1] = x;146 }147 else {148 d = dr + 1;149 fa[x] = r;150 s[r][0] = x;151 }152 }153 change(x, d, 1, temp, 1);154 printf("%d\n", d);155 siz++;156 }157 else if(f == 2) { // splay small 158 x = getK(1, 1, temp, 1);159 int d = ask(x, 1, temp, 1);160 if(d > 1) {161 int r = fa[x];162 if(s[x][1]) {163 fa[s[x][1]] = r;164 }165 s[r][0] = s[x][1];166 add(r, temp, 1, 1, temp, 1);167 change(x, 1, 1, temp, 1);168 fa[x] = 0;169 s[x][1] = rt;170 fa[rt] = x;171 rt = x;172 }173 printf("%d\n", d);174 }175 else if(f == 3) {176 x = getK(siz, 1, temp, 1);177 int d = ask(x, 1, temp, 1);178 if(d > 1) {179 int l = fa[x];180 if(s[x][0]) {181 fa[s[x][0]] = l;182 }183 s[l][1] = s[x][0];184 add(1, l, 1, 1, temp, 1);185 change(x, 1, 1, temp, 1);186 fa[x] = 0;187 s[x][0] = rt;188 fa[rt] = x;189 rt = x;190 }191 printf("%d\n", d);192 }193 else if(f == 4) {194 x = getK(1, 1, temp, 1);195 int d = ask(x, 1, temp, 1);196 if(d > 1) {197 int r = fa[x];198 if(s[x][1]) {199 fa[s[x][1]] = r;200 } 201 s[r][0] = s[x][1];202 add(1, r - 1, -1, 1, temp, 1);203 }204 else {205 add(1, temp, -1, 1, temp, 1);206 rt = s[x][1];207 fa[s[x][1]] = 0;208 }209 change(x, -1, 1, temp, 1);210 printf("%d\n", d);211 siz--;212 }213 else if(f == 5) {214 x = getK(siz, 1, temp, 1);215 int d = ask(x, 1, temp, 1);216 if(d > 1) {217 int l = fa[x];218 if(s[x][0]) {219 fa[s[x][0]] = l;220 }221 s[l][1] = s[x][0];222 add(l + 1, temp, -1, 1, temp, 1);223 }224 else {225 add(1, temp, -1, 1, temp, 1);226 rt = s[x][0];227 fa[s[x][0]] = 0;228 }229 change(x, -1, 1, temp, 1);230 printf("%d\n", d);231 siz--;232 }233 }234 return 0;235 }