为啥时间差那么多
查看原帖
为啥时间差那么多
1062683
lottle1212__楼主2025/1/2 21:18

一份是早上写的,一份是晚上写的,没有啥区别,但是一个 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
*/
2025/1/2 21:18
加载中...