一份是早上写的,一份是晚上写的,没有啥区别,但是一个 200+ms,一个 500+ms。谁能帮忙看看为啥。
200+ms:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
res=0; bool f=false; char ch=getchar();
while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int inf=0x3f3f3f3f;
const int maxn=1e5;
const int N=maxn+10;
int rt, idx;
//wmr
struct node {
int fa, ch[2], v, cnt, sz;
void init(int _fa, int _v) {
fa=_fa, v=_v;
cnt=sz=1;
}
} t[N];
#define ls(x) (t[x].ch[0])
#define rs(x) (t[x].ch[1])
#define sz(x) (t[x].sz)
#define cnt(x) (t[x].cnt)
#define fa(x) (t[x].fa)
#define v(x) (t[x].v)
void pushup(int x) { sz(x)=sz(ls(x))+sz(rs(x))+cnt(x); }
void rotate(int x) {
int y=fa(x), z=fa(y), k=(x==rs(y));
t[y].ch[k]=t[x].ch[k^1];
fa(t[x].ch[k^1])=y;
t[x].ch[k^1]=y;
fa(y)=x;
t[z].ch[rs(z)==y]=x;
fa(x)=z;
pushup(x), pushup(y);
}
void splay(int x, int k) {
while (fa(x)!=k) {
int y=fa(x), z=fa(y);
if (z!=k) (ls(z)==y)^(ls(y)==x)?rotate(x):rotate(y);
rotate(x);
}
if (!k) rt=x;
}
void insert(int v) {
int p=0, x=rt;
while (x&&v(x)!=v) p=x, x=t[x].ch[v>v(x)];
if (x) ++cnt(x);
else {
x=++idx;
t[x].init(p, v);
t[p].ch[v>v(p)]=x;
}
splay(x, 0);
}
void find(int v) {
int x=rt;
while (t[x].ch[v>v(x)]&&v!=v(x)) x=t[x].ch[v>v(x)];
splay(x, 0);
}
int get_pre(int v) {
find(v);
if (v(rt)<v) return rt;
int x=ls(rt);
while (rs(x)) x=rs(x);
splay(x, 0);
return x;
}
int get_suc(int v) {
find(v);
if (v(rt)>v) return rt;
int x=rs(rt);
while (ls(x)) x=ls(x);
splay(x, 0);
return x;
}
void del(int v) {
int pre=get_pre(v), suc=get_suc(v);
splay(pre, 0); splay(suc, pre);
int del=ls(suc); --cnt(del);
if (cnt(del)) splay(del, 0);
else ls(suc)=0, splay(suc, 0);
}
int get_rk(int v) {
insert(v);
int res=sz(ls(rt));
del(v);
return res;
}
int kth(int k) {
int x=rt;
while (true) {
if (k<=sz(ls(x))) x=ls(x);
else if (k<=sz(ls(x))+cnt(x)) break;
else k-=sz(ls(x))+cnt(x), x=rs(x);
}
splay(x, 0);
return x;
}
//incra
//lottle
signed main() {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("P3369.in", "r", stdin);
freopen("P3369.out", "w", stdout);
insert(-inf); insert(inf);
int T; rd(T);
while (T--) {
int opt, x; rd(opt, x);
if (opt==1) insert(x);
else if (opt==2) del(x);
else if (opt==3) printf("%d\n", get_rk(x));
else if (opt==4) printf("%d\n", v(kth(x+1)));
else if (opt==5) printf("%d\n", v(get_pre(x)));
else printf("%d\n", v(get_suc(x)));
}
return 0;
}
/*
input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
output
106465
84185
492737
*/
500+ms:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
res=0; bool f=false; char ch=getchar();
while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int inf=0x3f3f3f3f;
const int maxn=1e5;
const int N=maxn+10;
int rt, idx;
//wmr
struct node {
int ch[2], sz, cnt, fa, v;
void init(int _fa, int _v) {
fa=_fa, v=_v;
sz=cnt=1;
}
} t[N];
#define s(x) (t[x].sz)
#define fa(x) (t[x].fa)
#define cnt(x) (t[x].cnt)
#define ls(x) (t[x].ch[0])
#define rs(x) (t[x].ch[1])
#define v(x) (t[x].v)
void pushup(int p) { s(p)=s(ls(p))+s(rs(p))+cnt(p); }
void rotate(int x) {
int y=fa(x), z=fa(y), k=(x==rs(y));
t[y].ch[k]=t[x].ch[k^1];
fa(t[x].ch[k^1])=y;
t[x].ch[k^1]=y;
fa(y)=x;
t[z].ch[y==rs(z)]=x;
fa(x)=z;
pushup(x), pushup(y);
}
void splay(int x, int k) {
while (fa(x)!=k) {
int y=fa(x), z=fa(y);
if (k!=z) (ls(z)==y)^(ls(y)==x)?rotate(x):rotate(y);
rotate(x);
}
if (k==0) rt=x;
}
void insert(int v) {
int p=0, x=rt;
while (v(x)!=v&&x) p=x, x=t[x].ch[v>v(x)];
if (x) ++cnt(x);
else {
x=++idx;
t[x].init(p, v);
t[p].ch[v>v(p)]=x;
}
splay(x, 0);
}
void find(int v) {
int x=rt;
while (v!=v(x)&&t[x].ch[v>v(x)]) x=t[x].ch[v>v(x)];
splay(x, 0);
}
int get_pre(int v) {
find(v);
if (v(rt)<v) return rt;
int x=ls(rt);
while (rs(x)) x=rs(x);
splay(x, 0);
return x;
}
int get_suc(int v) {
find(v);
if (v(rt)>v) return rt;
int x=rs(rt);
while (ls(x)) x=ls(x);
splay(x, 0);
return x;
}
void del(int v) {
int pre=get_pre(v), suc=get_suc(v);
splay(pre, 0); splay(suc, pre);
int del=ls(suc); --cnt(del);
if (!cnt(del)) ls(suc)=0, splay(suc, 0);
else splay(del, 0);
}
int get_rk(int v) {
insert(v);
int res=s(ls(rt));
del(v);
return res;
}
int kth(int k) {
int x=rt;
while (true) {
if (k<=s(ls(x))) x=ls(x);
else if (k<=s(ls(x))+cnt(x)) break;
else k-=s(ls(x))+cnt(x), x=rs(x);
}
splay(x, 0);
return x;
}
//incra
//lottle
signed main() {
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("P3369.in", "r", stdin);
freopen("P3369.out", "w", stdout);
int T; rd(T);
insert(-inf); insert(inf);
while (T--) {
cerr << "xyy";
int opt, x; rd(opt, x);
if (opt==1) insert(x);
else if (opt==2) del(x);
else if (opt==3) printf("%d\n", get_rk(x));
else if (opt==4) printf("%d\n", v(kth(x+1)));
else if (opt==5) printf("%d\n", v(get_pre(x)));
else printf("%d\n", v(get_suc(x)));
}
return 0;
}
/*
input
20
1 964673
5 968705
4 1
3 964673
5 965257
1 915269
1 53283
3 964673
3 53283
3 53283
1 162641
5 973984
1 948119
2 915269
2 53283
6 959161
1 531821
1 967521
2 531821
1 343410
output
964673
964673
1
964673
3
1
1
964673
964673
*/