更新一下代码,现在T变成WA了
```cpp
#include<iostream>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int N = 1e5 + 5;
int root, n;
struct node {
int son[2];
int val;
int rd;
int size;
int sum;
}tree[N];
stack<int> stk;
void init() { for(int i = n; i; --i) stk.push(i); }
void maintain(int x) { tree[x].size = tree[tree[x].son[0]].size + tree[tree[x].son[1]].size + tree[x].sum; }
void split(int now, int k, int &x, int &y) {
if(!now) x = y = 0;
else {
if(tree[now].val <= k) {
x = now;
split(tree[x].son[1], k, tree[x].son[1], y);
} else {
y = now;
split(tree[y].son[0], k, x, tree[y].son[0]);
}
maintain(now);
}
}
int merge(int x, int y) {
if(!x || !y) return x + y;
if(tree[x].rd < tree[y].rd) {
tree[x].son[1] = merge(tree[x].son[1], y);
maintain(x);
return x;
} else {
tree[y].son[0] = merge(x, tree[y].son[0]);
maintain(y);
return y;
}
}
int mknew (int x) {
int a = stk.top();
stk.pop();
tree[a].rd = rand();
tree[a].val = x;
//cout<<tree[a].val<<" "<<x<<" "<<a<<endl;
tree[a].son[1] = 0;
tree[a].son[0] = 0;
tree[a].size = 1;
tree[a].sum = 1;
//cout<<x<<" "<<tree[a].val<<" "<<tree[a].rd<<endl;
return a;
}
void update(int x) {
int a, b, c;
split(root, x, a, b);
split(a, x - 1, a, c);
//cout<<a<<" "<<b<<" "<<c<<endl;
if(c) ++tree[c].sum;
else c = mknew(x);
//cout<<c<<" "<<tree[c].val<<endl;
root = merge(merge(a, c), b);
}
void delet(int x) {
int a, b, c;
split(root, x, a, b);
split(a, x - 1, a, c);
if(--tree[c].sum) root = merge(merge(a, c), b);
else {
stk.push(c);
root = merge(a, b);
}
}
int find1(int x) {
int a, b;
split(root, x - 1, a, b);
int rt = tree[a].size + 1;
root = merge(a, b);
return rt;
}
int find2(int x, int now) {
int sm = 0;
while(now) {
//cout << tree[now].val << " " << tree[now].sum << " " << tree[now].son[1] << " " << tree[now].son[2] << " " << sm <<endl;
if(tree[now].sum + tree[tree[now].son[0]].size + sm < x) sm += tree[now].sum + tree[tree[now].son[0]].size, now = tree[now].son[1];
else if(tree[now].sum + tree[tree[now].son[0]].size + sm > x) {
if(tree[tree[now].son[0]].size + sm < x) return tree[now].val;
now = tree[now].son[0];
}
else return tree[now].val;
}
return -1;
}
int qq(int x) {
int a, b, as;
split(root, x - 1, a, b);
as = find2(tree[a].size, a);
root = merge(a, b);
return ~as ? as : x;
}
int hj(int x) {
int a, b, as;
split(root, x, a, b);
//cout<<tree[b].size<<" "<<tree[b].val<<endl;
as = find2(1, b);
root = merge(a, b);
return ~as ? as : x;
}
int main() {
srand(time(NULL));
scanf("%d", &n);
init();
for(int i = n; i; --i) {
int opt, x;
scanf("%d%d", &opt, &x);
if(opt == 6) printf("%d\n", hj(x));
else if(opt == 5) printf("%d\n", qq(x));
else if(opt == 4) printf("%d\n", find2(x, root));
else if(opt == 2) delet(x);
else if(opt ^ 1) printf("%d\n", find1(x));
else update(x);
//cout<<root<<endl;
}
return 0;
}
```
by chrisgr @ 2023-12-02 12:04:54
此贴终结,已过
by chrisgr @ 2023-12-02 14:58:36