BZOJ3224 – Tyvj 1728 普通平衡树(线段树)

BZOJ3224

【题意】您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)

【分析】完全没必要用平衡树，可以用离线+离散线段树，或者在线的动态内存线段树都可以。

对于操作3就是查询<=x-1的数的个数，再加+1就是x的排名

对于操作4，直接线段树上二分第k大

对于操作5，查询<=x-1的个数sum，则查找第sum大的数便是前驱

对于操作6，查询<=x的个数sum，则查找第sum+1大的数就是后继

【AC CODE(离线线段树)】384ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = (1e5)+10;
struct NODE{
	int op,x;
}in[MAXN];
int a[MAXN],num[MAXN],n;

int sum[MAXN<<1];
inline int id(int x, int y){return x+y|x!=y;}
void update(int x, int y, int p, int v)
{
	if(x == y)
	{
		sum[id(x,y)] += v;
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) update(x,m,p,v);
	else update(m+1,y,p,v);
	sum[id(x,y)] = sum[id(x,m)]+sum[id(m+1,y)];
}
void find_rk(int x, int y, int v, int &ans)
{
	if(x == y)
	{
		ans += sum[id(x,y)];
		return;
	}
	int m = (x+y)>>1;
	if(v <= m) find_rk(x,m,v,ans);
	else
	{
		ans += sum[id(x,m)];
		find_rk(m+1,y,v,ans);
	}
}
int find_k(int x, int y, int k)
{
	if(x == y) return x;
	int m = (x+y)>>1, d = sum[id(x,m)];
	if(k <= d) return find_k(x,m,k);
	return find_k(m+1,y,k-d);
}

inline int mhash(int v){return lower_bound(num,num+n,v)-num;}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int q,cnt = 0;
	scanf("%d", &q);
	rep(i,0,q)
	{
		scanf("%d%d", &in[i].op, &in[i].x);
		if(4 != in[i].op)
			num[cnt++] = in[i].x;
	}
	num[cnt++] = -INF;num[cnt++] = INF;
	sort(num,num+cnt);
	n = unique(num,num+cnt)-num;
	rep(i,0,q)
	{
		if(1 == in[i].op) update(0,n-1,mhash(in[i].x),1);
		else if(2 == in[i].op) update(0,n-1,mhash(in[i].x),-1);
		else if(3 == in[i].op)
		{
			int ans = 0;
			find_rk(0,n-1,mhash(in[i].x)-1,ans);
			printf("%d\n", ans+1);
		}
		else if(4 == in[i].op) printf("%d\n", num[find_k(0,n-1,in[i].x)]);
		else if(5 == in[i].op)
		{
			int ans = 0;
			find_rk(0,n-1,mhash(in[i].x)-1,ans);
			printf("%d\n", num[find_k(0,n-1,ans)]);
		}
		else
		{
			int ans = 0;
			find_rk(0,n-1,mhash(in[i].x),ans);
			printf("%d\n", num[find_k(0,n-1,ans+1)]);
		}
	}
	return 0;
}

【AC CODE(在线动态内存线段树)】568ms

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = (1e5)+10,MAXM = MAXN*20+10;
int a[MAXN],n;

int sum[MAXM],lc[MAXM],rc[MAXM],tol;
inline void newnode(int &u, int x, int y)
{
	u = ++tol;
	lc[u] = 0;rc[u] = 0;
}
void update(int &u, int x, int y, int p, int v)
{
	if(!u) newnode(u,x,y);
	if(x == y)
	{
		sum[u] += v;
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) update(lc[u],x,m,p,v);
	else update(rc[u],m+1,y,p,v);
	sum[u] = sum[lc[u]]+sum[rc[u]];
}
void find_rk(int &u, int x, int y, int v, int &ans)
{
	if(!u) newnode(u,x,y);
	if(x == y)
	{
		ans += sum[u];
		return;
	}
	int m = (x+y)>>1;
	if(v <= m) find_rk(lc[u],x,m,v,ans);
	else
	{
		ans += sum[lc[u]];
		find_rk(rc[u],m+1,y,v,ans);
	}
}
int find_k(int u, int x, int y, int k)
{
	if(!u) newnode(u,x,y);
	if(x == y) return x-10000000;
	int m = (x+y)>>1, d = sum[lc[u]];
	if(k <= d) return find_k(lc[u],x,m,k);
	return find_k(rc[u],m+1,y,k-d);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int q,cnt = 0,n = 10000000*2;
	scanf("%d", &q);
	int rt;
	newnode(rt,0,n);
	rep(i,0,q)
	{
		int op,x;
		scanf("%d%d", &op,&x);
		if(4 != op)
			x += 10000000;
		if(1 == op) update(rt,0,n,x,1);
		else if(2 == op) update(rt,0,n,x,-1);
		else if(3 == op)
		{
			int ans = 0;
			find_rk(rt,0,n,x-1,ans);
			printf("%d\n", ans+1);
		}
		else if(4 == op) printf("%d\n", find_k(rt,0,n,x));
		else if(5 == op)
		{
			int ans = 0;
			find_rk(rt,0,n,x-1,ans);
			printf("%d\n",find_k(rt,0,n,ans));
		}
		else
		{
			int ans = 0;
			find_rk(rt,0,n,x,ans);
			printf("%d\n", find_k(rt,0,n,ans+1));
		}
	}
	return 0;
}