rt,调不出来了QAQ,现在同一份代码分数36到52不等,反复横跳。。。。。
代码如下:
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#define int long long
#define inlind inline void
#define inlinl inline bool
#define inlint inline int
#define inlinc inline char
#define inlins inline string
#define mem0(a) memset(a,0,sizeof(a))
#define memf(a) memset(a,0x3f,sizeof(a))
#define mem_f(a) memset(a,0x80,sizeof(a))
#define mem_1(a) memset(a,-1,sizeof(a))
#define pb(a,b) a.push_back(b)
#define mp(a,b) make_pair(a,b)
#define p1(x) x.first
#define p2(x) x.second
using namespace std;
const int M = 19260817;
inlind re(int &x) {
x = 0;
bool f = 0;
int w = getchar();
while (w < '0' || w > '9') {
if (w == '-')
f = 1;
w = getchar();
}
while (w <= '9' && w >= '0') {
x = (x << 3) + (x << 1) + w - '0';
x %= M;
w = getchar();
}
if (f)
x = -x;
}
inlind wr(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
struct node {
int s[2], si, x, val;
} a[1000030];
int n;
inlind upd(int i) {
a[i].si = a[a[i].s[1]].si + a[a[i].s[0]].si + 1;
}
inlind sw(int &i, bool p) {
int t = a[i].s[p];
a[i].s[p] = a[t].s[!p];
a[t].s[!p] = i;
upd(t);
upd(i);
i = t;
}
int cnt = 0;
inlind ins(int &i, int x) {
if (!i) {
i = ++cnt;
a[i].si = 1;
a[i].x = x;
a[i].val = rand();
return ;
}
a[i].si++;
if (x > a[i].x){
ins(a[i].s[1], x);
if (a[i].val > a[a[i].s[1]].val)
sw(i, 1);
}
else{
ins(a[i].s[0], x);
if (a[i].val > a[a[i].s[0]].val)
sw(i, 0);
}
}
inlind del(int &i, int x) {
if (x == a[i].x) {
if (a[i].s[1] == 0) {
i = a[i].s[0];
return ;
}
else if (a[i].s[0] == 0) {
i = a[i].s[1];
return ;
}
else {
if (a[a[i].s[0]].val > a[a[i].s[1]].val)
sw(i, 1), del(a[i].s[0], x);
else
sw(i, 0), del(a[i].s[1], x);
}
}
else if (x < a[i].x)
del(a[i].s[0], x);
else
del(a[i].s[1], x);
upd(i);
}
inlint fi(int i, int x) {
if (!i)
return 1;
if (x > a[i].x)
return a[a[i].s[0]].si + 1 + fi(a[i].s[1], x);
else
return fi(a[i].s[0], x);
}
inlint ge(int i, int x) {
if (a[a[i].s[0]].si == x - 1)
return a[i].x;
if (a[a[i].s[0]].si >= x)
return ge(a[i].s[0], x);
else
return ge(a[i].s[1], x - a[a[i].s[0]].si - 1);
}
inlint lt(int i, int x) {
if (!i)
return -2e9-10;
if (x > a[i].x)
return max(a[i].x, lt(a[i].s[1], x));
else
return lt(a[i].s[0], x);
}
inlint nt(int i, int x) {
if (!i)
return 2e9+10;
if (x < a[i].x)
return min(nt(a[i].s[0], x), a[i].x);
else
return nt(a[i].s[1], x);
}
int st;
signed main() {
srand(time(0)+3);
re(n);
for (int i = 1; i <= n; i++) {
int op, x;
re(op);
re(x);
switch (op) {
case 1:
ins(st, x);
break;
case 2:
del(st, x);
break;
case 3:
printf("%lld\n", fi(st, x));
break;
case 4:
printf("%lld\n", ge(st, x));
break;
case 5:
printf("%lld\n", lt(st, x));
break;
case 6:
printf("%lld\n", nt(st, x));
break;
}
}
return 0;
}