ZOJ2112 – Dynamic Rankings(分块||树套树||主席树)

在 上张贴 由 dawxy发表回复

题目链接：ZOJ2112

【题意】可以单点修改的区间第k大。

【分析】这题有三种方法可以做：1.分块+二分(最好写)q*sqrt(n)*logn*logn  2.线段树套Treap+二分q*logn*logn*logn 3.树状数组+主席树q*logn*logn;

首先第一种：分块+二分。把区间分块，每个块排序，然后二分第k大的值域即可。

【AC CODE】1590ms O(q*sqrt(n)*logn*logn)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
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 = 50000+10, SIZE = 305;
int block[MAXN/SIZE+10][SIZE], cnt, len[MAXN/SIZE+10], a[MAXN], mi, mx;

void update(int p, int v)//logn*SIZE
{
	int x = p/SIZE;
	int c = lower_bound(block[x],block[x]+len[x],a[p])-block[x];
	block[x][c] = a[p] = v;
	sort(block[x],block[x]+len[x]);
	mx = max(mx,v), mi = min(mi,v);
}
int tmp[SIZE<<1],tol;
bool find_k(int st, int ed, int v, int kk)
{
	int sum = upper_bound(tmp,tmp+tol,v)-tmp;
	if(sum >= kk) return true;
	rep(i,st+1,ed)
	{
		sum += upper_bound(block[i],block[i]+len[i],v)-block[i];
		if(sum >= kk) return true;
	}
	return false;
}
int query(int x, int y, int k)
{
	int bx = x/SIZE, by = y/SIZE;
	tol = 0;
	if(bx == by)//SIZE*logn
	{
		repe(i,x,y) tmp[tol++] = a[i];
		sort(tmp,tmp+tol);
		return tmp[k-1];
	}
	rep(i,x%SIZE,len[bx]) tmp[tol++] = a[bx*SIZE+i];
	repe(i,0,y%SIZE) tmp[tol++] = a[by*SIZE+i];
	sort(tmp,tmp+tol);//SIZE*logn
	int l = mi,r = mx, ans = -1;
	while(l <= r)
	{
		int m = (l+r)>>1;
		if(find_k(bx,by,m,k))
		{
			ans = m;
			r = m-1;
		}
		else l = m+1;
	}
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		int n,q;
		scanf("%d %d", &n, &q);
		cnt = 0;
		clc(len,0);
		mx = -1, mi = INF;
		rep(i,0,n)
		{
			scanf("%d", &a[i]);
			block[cnt][len[cnt]++] = a[i];
			mx = max(mx,a[i]);
			mi = min(mi,a[i]);
			if(len[cnt] == SIZE) cnt++;
		}
		rep(i,0,cnt)
			sort(block[i],block[i]+len[i]);
		char op[10];
		while(q--)
		{
			scanf("%s", op);
			if('C' == op[0])
			{
				int p,v;
				scanf("%d %d%*c", &p, &v);
				update(p-1,v);
			}
			else
			{
				int x,y,k;
				scanf("%d %d %d%*c",&x, &y,&k);
				printf("%d\n", query(x-1,y-1,k));
			}
		}
	}
	return 0;
}

第二种：线段树套Treap，这个也很好理解，每个线段树结点套一个Treap维护这个结点所表示的区间的所有值，然后和分块一样二分第k大的值域即可。

【AC CODE】1110ms O(q*logn*logn*logn)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
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 = 50000+10;
struct NODE{
	NODE *ch[2];
	int r, v, sum, cnt;
}node[MAXN*20];
int a[MAXN], mi, mx, tol;
NODE *rt[MAXN<<1];

int cmp(const NODE *a, int x){
	if(x == a->v) return -1;
	return x<a->v?0:1;
}
void push_up(NODE *u){
	u->sum = u->cnt;
	if(u->ch[0]) u->sum += u->ch[0]->sum;
	if(u->ch[1]) u->sum += u->ch[1]->sum;
}
NODE *newnode(int a){
	node[tol].v = a,node[tol].ch[0] = node[tol].ch[1] = NULL, node[tol].r = rand();
	node[tol].sum = node[tol].cnt = 1;
	return &node[tol++];
}
void clear(NODE* &u)//清空树
{
	u = NULL;
}
void rotate(NODE* &u, int d)//旋转，d = 0左旋,d = 1右旋
{
	NODE *k = u->ch[d^1];
	u->ch[d^1] = k->ch[d], k->ch[d] = u;
	push_up(u), push_up(k);  //更新sum,先更新u
	u = k;
}
void insert(NODE* &u, int v)//插入键值v(不需要保证v是否存在)
{
	if(!u) u = newnode(v);
	else
	{
		int d = cmp(u,v);//不要使用cmp(),可能已经存在相同的v
		if(-1 == d)//已经存在该点
		{
			u->cnt++;
			u->sum++;
			return;
		}
		insert(u->ch[d], v);
		if(u->r < u->ch[d]->r) //如果儿子的r比当前大则需要旋转
			rotate(u,d^1);//左儿子则右旋，右儿子左旋
	}
	push_up(u);//更新sum
}
void del(NODE* &u, int v)//删除键值v
{
	int d = cmp(u,v);
	if(~d)//没找到继续往下找
		del(u->ch[d],v);
	else
	{
		if(u->cnt > 1)
		{
			u->cnt--;
			u->sum--;
			return;
		}
		NODE *o = u;
		if(u->ch[0] && u->ch[1])//左右儿子都存在
		{
			int d2 = u->ch[0]->r > u->ch[1]->r?1:0;//优先级大的儿子旋转为根
			rotate(u,d2);
			del(u->ch[d2],v);
		}
		else
		{
			if(!u->ch[0]) u = u->ch[1];//只有右儿子
			else u = u->ch[0];//只有左儿子
			//delete o;
			//u = NULL;
		}
	}
	if(u) push_up(u);
}
int upper(NODE *u, int v)//v在树中排第几,即有几个<=v
{
	if(!u) return 0;
	if(v == u->v) return u->cnt+(u->ch[0]?u->ch[0]->sum:0);
	if(v < u->v) return upper(u->ch[0], v);
	return upper(u->ch[1],v)+(u->ch[0]?u->ch[0]->sum:0)+u->cnt;
}
void pt(NODE *u)
{
	if(NULL == u) return;
	pt(u->ch[0]);
	rep(i,0,u->cnt)
		printf("%d\n", u->v);
	pt(u->ch[1]);
}

inline int id(int x, int y){return x+y|x!=y;}
void bulid(int x, int y)
{
	int u = id(x,y);
	clear(rt[u]);
	repe(i,x,y) insert(rt[u],a[i]);
	if(x == y) return;
	int m = (x+y)>>1;
	bulid(x,m);
	bulid(m+1,y);
}
int tmp;
void update(int x, int y, int p, int v)
{
	if(x == y)
	{
		int u = id(x,y);
		tmp = rt[u]->v;
		rt[u]->v = v;
		return;
	}
	int m = (x+y)>>1;
	if(p <= m) update(x,m,p,v);
	else update(m+1,y,p,v);
	int u = id(x,y);
	del(rt[u],tmp);
	insert(rt[u],v);
}
int query(int x, int y, int ql, int qr, int v)
{
	if(ql <= x && y <= qr)
	{
		int u = id(x,y);
		return upper(rt[u],v);
	}
	int m = (x+y)>>1, ans = 0;
	if(ql <= m) ans += query(x,m,ql,qr,v);
	if(qr > m) ans += query(m+1,y,ql,qr,v);
	return ans;
}
int n;
int sloved(int x, int y, int k)
{
	int l = mi, r = mx, ans;
	while(l <= r)
	{
		int m = (l+r)>>1;
		if(query(0,n-1,x,y,m) >= k)
			ans = m, r = m-1;
		else l = m+1;
	}
	return ans;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d%*c", &t);
	while(t--)
	{
		int q;
		scanf("%d %d%*c", &n, &q);
		mi = INF, mx = -1;
		tol = 0;
		rep(i,0,n)
		{
			scanf("%d%*c", &a[i]);
			mi = min(mi,a[i]);
			mx = max(mx,a[i]);
		}
		bulid(0,n-1);
		while(q--)
		{
			char op[10];
			scanf("%s",op);
			if('C' == op[0])
			{
				int p,v;
				scanf("%d %d", &p,&v);
				p--;
				update(0,n-1,p,v);
				mi = min(mi,v);
				mx = max(mx,v);
			}
			else
			{
				int x,y,k;
				scanf("%d %d %d",&x, &y, &k);
				x--,y--;
				printf("%d\n", sloved(x,y,k));
			}
		}
	}
	return 0;
}

第三种：树状数组+主席树，这个是刚刚学的，觉得好神奇，还是看这个博客讲得比较好。

http://blog.finaltheory.info/algorithm/Chairman-Tree.html#content-heading

【AC CODE】120ms O(q*logn*logn)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
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 = 50000+10, MAXQ = 10000+10,MAXM = MAXN*30;
struct IN{
	bool f;
	int a,b,k;
}in[MAXQ];
int lc[MAXM], rc[MAXM], sum[MAXM], tol;//主席树内存池
int num[MAXN+MAXQ], sot[MAXN+MAXQ], cnt;//离散
int rt[MAXN<<1], a[MAXN], n;//rt[]保存各个版本的线段树根,rt[1~n]保存树状数组套的主席树,后面的保存初始的n个前缀主席树

inline int mhash(int v){return lower_bound(sot+1,sot+1+cnt,v)-sot;}
void init_hash(int cc)
{
	sort(num+1,num+1+cc);
	sot[1] = num[1];
	cnt = 1;
	repe(i,2,cc) if(num[i] != num[i-1]) sot[++cnt] = num[i];
}
inline int newnode(int _lc, int _rc, int _sum)
{
	lc[tol] = _lc, rc[tol] = _rc, sum[tol] = _sum;
	return tol++;
}
void bulid(int &u, int x, int y, int p)//在前一个版本基础上添加一个新的结点v,成为一棵新树
{
	u = newnode(lc[u],rc[u],sum[u]+1);
	if(x == y) return;
	int m = (x+y)>>1;
	if(p <= m) bulid(lc[u],x,m,p);
	else bulid(rc[u],m+1,y,p);
}
void t_update(int &u, int x, int y, int p, int v)//树状数组中每个结点所套的主席树,更新到才新建，省内存
{
	if(!u) u = newnode(0,0,0);
	sum[u] += v;
	if(x == y) return;
	int m = (x+y)>>1;
	if(p <= m) t_update(lc[u],x,m,p,v);
	else t_update(rc[u],m+1,y,p,v);
}
/*树状数组记录区间[1,n]每个数字出现的次数,次数用值域主席树记录*/
inline int lowbit(int x){return x&-x;}
void add(int x, int v)//树状数组添加或删除元素a[x]
{
	int p = a[x];
	while(x <= n)
	{
		t_update(rt[x],1,cnt,p,v);
		x += lowbit(x);
	}
}
int tx[50], ty[50], len[2];//查询用到的所有树
int t_query(int x, int y, int k)
{
	if(x == y) return x;
	int d = 0;
	rep(i,0,len[1]) d += sum[lc[ty[i]]];
	rep(i,0,len[0]) d -= sum[lc[tx[i]]];
	int m = (x+y)>>1;
	if(d >= k)
	{
		rep(i,0,len[1]) ty[i] = lc[ty[i]];
		rep(i,0,len[0]) tx[i] = lc[tx[i]];
		return t_query(x,m,k);
	}
	rep(i,0,len[1]) ty[i] = rc[ty[i]];
	rep(i,0,len[0]) tx[i] = rc[tx[i]];
	return t_query(m+1,y,k-d);
}
/*====== 调用操作 ======*/
void init(int cc)//logn*n新建初始前缀树
{
	init_hash(cc);
	repe(i,1,n) a[i] = mhash(a[i]);//把所有a[i]变成离散值
	tol = 1;
	clc(rt,0);
	rt[0] = sum[0] = lc[0] = rc[0] = 0;//只需要用一个结点代表第0颗树
	repe(i,1,n)
	{
		rt[i+n] = rt[i+n-1];
		bulid(rt[i+n],1,cnt,a[i]);
	}
}
void update(int p, int v)//更新a[p] -> v
{
	add(p,-1);
	a[p] = mhash(v);
	add(p,1);
}
int query(int x, int y, int k)//查询区间[x,y]的第k大元素
{
	/*把所有表示区间y的树减去区间x-1的树存起来查询*/
	len[0] = len[1] = 1;
	tx[0] = rt[x-1?x-1+n:0], ty[0] = rt[y+n];//先把初始的一棵树加进去
	for(int i = x-1; i > 0; i -= lowbit(i)) tx[len[0]++] = rt[i];//树状数组求区间[x,y]和就是sum(y)-sum(x-1)则，把多个这样的点一起在主席树中算就可以了
	for(int i = y; i > 0; i -= lowbit(i)) ty[len[1]++] = rt[i];
	return t_query(1,cnt,k);
}

int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int q;
		scanf("%d %d", &n, &q);
		int cc = 0;//所有值没去重的数量
		repe(i,1,n) scanf("%d", &a[i]), num[++cc] = a[i];
		char op[10];
		rep(i,0,q)
		{
			scanf("%s", op);
			if('Q' == op[0])
			{
				in[i].f = 0;
				scanf("%d %d %d",&in[i].a, &in[i].b, &in[i].k);
			}
			else
			{
				in[i].f = 1;
				scanf("%d %d", &in[i].a, &in[i].b);
				num[++cc] = in[i].b;
			}
		}
		init(cc);
		rep(i,0,q)
		{
			if(!in[i].f) printf("%d\n", sot[query(in[i].a,in[i].b,in[i].k)]);
			else update(in[i].a,in[i].b);
		}
	}
	return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

请输入正确的验证码