52pts,WA #6 - #11
我的代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<climits>
#include<algorithm>
#define int long long
using namespace std;
const int MaxN = 100005;
int n, sum = 0, root = 0;
struct Treap{
int subtreeSize, value, number, son[2], rand;
}treap[MaxN];
inline int read(){
char x;
int num;
while(x=getchar(),x<'0'||x>'9');
num=x-'0';
while(x=getchar(),x>='0'&&x<='9') num*=10,num+=x-'0';
return num;
}
inline void PushUp(int x){
treap[x].subtreeSize = treap[treap[x].son[0]].subtreeSize + treap[treap[x].son[1]].subtreeSize + treap[x].number;
}
inline void Rotate(int &x, int d){
int k = treap[x].son[d^1];
treap[x].son[d^1] = treap[k].son[d];
treap[k].son[d] = x;
PushUp(x);
PushUp(k);
x = k;
}
inline void Insert(int &x, int y){
if(!x){
x = ++sum;
treap[x].subtreeSize = treap[x].number = 1;
treap[x].value = y;
treap[x].rand = rand();
return;
}
if(treap[x].value == y){
treap[x].number++;
treap[x].subtreeSize++;
return;
}
int d = (y > treap[x].value);
Insert(treap[x].son[d], y);
if(treap[x].rand < treap[treap[x].son[d]].rand) Rotate(x, d^1);
PushUp(x);
}
inline void Delete(int &x, int y){
if(!x) return;
if(y < treap[x].value) Delete(treap[x].son[0], y);
else if(y > treap[x].value) Delete(treap[x].son[1], y);
else{
if(!treap[x].son[0] && !treap[x].son[1]){
treap[x].number--;
treap[x].subtreeSize--;
if(treap[x].number == 0) x = 0;
}
else if(treap[x].son[0] && !treap[x].son[1]){
Rotate(x, 1);
Delete(treap[x].son[1], y);
}
else if(!treap[x].son[0] && treap[x].son[1]){
Rotate(x, 0);
Delete(treap[x].son[0], y);
}
else if(treap[x].son[0] && treap[x].son[1]){
int d = (treap[treap[x].son[0]].rand > treap[treap[x].son[1]].rand);
Rotate(x, d);
Delete(treap[x].son[d], y);
}
}
PushUp(x);
}
inline int Rank(int x, int y){
if(!x) return 0;
if(treap[x].value == y) return treap[treap[x].son[0]].subtreeSize + 1;
else if(treap[x].value < y) return treap[treap[x].son[0]].subtreeSize + treap[x].number + Rank(treap[x].son[1], y);
else return Rank(treap[x].son[0], y);
}
inline int Find(int x, int y){
if(!x) return 0;
if(treap[treap[x].son[0]].subtreeSize >= y) return Find(treap[x].son[0], y);
else if(treap[treap[x].son[0]].subtreeSize + treap[x].number < y) return Find(treap[x].son[1], y - treap[x].number - treap[treap[x].son[0]].subtreeSize);
else return treap[x].value;
}
inline int Predecessor(int x, int y){
if(!x) return -INT_MAX;
if(treap[x].value >= y) return Predecessor(treap[x].son[0], y);
else return max(treap[x].value, Predecessor(treap[x].son[1], y));
}
inline int Successor(int x, int y){
if(!x) return INT_MAX;
if(treap[x].value <= y) return Successor(treap[x].son[1], y);
else return min(treap[x].value, Successor(treap[x].son[0], y));
}
signed main(){
freopen("Treap.in","r",stdin);
freopen("std.out","w",stdout);
n = read();
while(n--){
int op = read(), x = read();
if(op == 1) Insert(root, x);
else if(op == 2) Delete(root, x);
else if(op == 3) printf("%lld\n", Rank(root, x));
else if(op == 4) printf("%lld\n", Find(root, x));
else if(op == 5) printf("%lld\n", Predecessor(root, x));
else printf("%lld\n", Successor(root, x));
}
return 0;
}