Beyond the Void
BYVoid
Dynamic Rankings 动态排名系统 (zju 2112)

解决这个和问题,需要用到“树套树”。建立一棵线段树,维护N的节点的所有区间,每个线段树节点上有一个平衡树,用来维护当前区间内所有数的动态排名。很显然,每个线段树节点上的平衡树,都是这个线段树节点的两个子节点的平衡树的合并。由于我们无法实现高效的平衡树合并,只好用这种以空间换时间的方法。

对于每个修改操作,只需先在线段树找出单位区间[i,i]上平衡树中的唯一节点,就是A[i]的原值,然后把线段树从根到该节点路径上所有节点的平衡树中都删除掉A[i]的原值,然后插入新值j。

查询操作为比较特殊,因为给定的区间[i,j]可能对应线段树中若干个区间的并,所以首先找出这对应的q区间的平衡树T[1],T[2],T[3],…,T[q],找出其中的最大值Max和最小值Min,然后在[Min,Max]之间二分答案。对于给定的答案r,判断是符合要求,否则按照单调性缩小二分区间。

如何求给定的r值的总排名,由于r可能不在某些甚至所有的q个平衡树中,所以有时求r的排名是没有意义的,换而我们可以求r在所有平衡树中后继的最小值MinSucc的排名。对于第i个平衡树,要求r在T[i]中的后继(不大于r的最小值)的排名S[i],MinSucc的排名就是k1=Σ{S[i]-1} + 1。但是相同的MinSucc的值可能会有多个,所以MinSucc的排名实际上是属于一个区间的,应在所有的平衡树中找出MinSucc一共的个数Count,MinSucc的最大排名就是k2=k1+Count-1。如果k属于[k1,k2],那么结果就是MinSucc。如果k2<k,则应向增大的方向二分答案,否则向减小的方向二分答案。

代码很长,最后一句话,细节决定成败!

感谢slxg,正如你所说的,我写错了。现在错误已经修正。看来zju的数据还是不够强大,原来有点错的也能AC。

/* 
 * Problem: Zju2112 dynrank
 * Author: Guo Jiabao
 * Time: 2009.2.9 14:14
 * State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

struct treap_node
{
	treap_node *left,*right;
	int v,fix,size,weight;
	inline int lsize() {return left ?left ->size:0;}
	inline int rsize() {return right?right->size:0;}
};

struct sgt_node
{
	sgt_node *left,*right;
	int a,b;
	treap_node *treap;
};

const int MAXN=50001,MAXM=10001,INF=0x7FFFFFFF/2;
const int MAXTN=(MAXN+MAXM)*16,MAXSN=MAXN*2;
treap_node TS[MAXTN];
sgt_node SS[MAXSN];
int D,N,M,TC,SC,Tcnt;
sgt_node *sgt_root;
treap_node *T[MAXN];

inline treap_node* new_treap_node(int v)
{
	TS[++TC].v=v;
	TS[TC].left=TS[TC].right=0;
	TS[TC].size=TS[TC].weight=1;
	TS[TC].fix=rand();
	return &TS[TC];
}

inline void treap_rotate_right(treap_node *&p)
{
	treap_node *q=p->left;
	p->left=q->right;
	q->right=p;
	p=q;
	q=p->right;
	q->size=q->lsize() + q->rsize() +q->weight;
	p->size=p->lsize() + p->rsize() +p->weight;
}

inline void treap_rotate_left(treap_node *&p)
{
	treap_node *q=p->right;
	p->right=q->left;
	q->left=p;
	p=q;
	q=p->left;
	q->size=q->lsize() + q->rsize() +q->weight;
	p->size=p->lsize() + p->rsize() +p->weight;
}

int treap_find(treap_node *p,int v)
{
	if (!p)
		return 0;
	else if (v<p->v)
		return treap_find(p->left,v);
	else if (v>p->v)
		return treap_find(p->right,v);
	else
		return p->weight;
}

void treap_insert(treap_node *&p,int v)
{
	if (!p)
		p=new_treap_node(v);
	else
	{
		p->size++;
		if (v < p->v)
		{
			treap_insert(p->left,v);
			if (p->left->fix < p->fix)
				treap_rotate_right(p);
		}
		else if (v > p->v)
		{
			treap_insert(p->right,v);
			if (p->right->fix < p->fix)
				treap_rotate_left(p);
		}
		else
			p->weight++;
	}
}

void treap_delete(treap_node *&p) //real deletion
{
	if (p->left && p->right)
	{
		if (p->left->fix < p->right->fix)
		{
			treap_rotate_right(p);
			treap_delete(p->right);
		}
		else
		{
			treap_rotate_left(p);
			treap_delete(p->left);
		}
	}
	else
	{
		if (p->left)
			p=p->left;
		else
			p=p->right;
	}
}

void treap_delete(treap_node *&p,int v) //lazy deletion
{
	if (v==p->v)
	{
		p->weight--;
		p->size--;
		if (p->weight==0)
			treap_delete(p);
	}
	else
	{
		if (v < p->v)
			treap_delete(p->left,v);
		else
			treap_delete(p->right,v);
		p->size--;
	}
}

void treap_succ(treap_node *p,int v,int &rs)
{
	if (!p) return;
	if (p->v >= v)
	{
		rs=p->v;
		treap_succ(p->left,v,rs);
	}
	else
		treap_succ(p->right,v,rs);
}

int treap_getmin(treap_node *p)
{
	while (p->left)
		p=p->left;
	return p->v;
}

int treap_getmax(treap_node *p)
{
	while (p->right)
		p=p->right;
	return p->v;
}

void treap_rank(treap_node *p,int v,int cur,int &rank)
{
	if (v == p->v)
		rank=p->lsize() + cur + 1;
	else if (v < p->v)
		treap_rank(p->left,v,cur,rank);
	else
		treap_rank(p->right,v,p->lsize() + cur + p->weight,rank);
}

inline sgt_node* new_sgt_node()
{
	SS[++SC].treap=0;
	SS[SC].a=SS[SC].b=0;
	SS[SC].left=SS[SC].right=0;
	return &SS[SC];
}

void sgt_build(sgt_node *&p,int a,int b)
{
	p=new_sgt_node();
	if (a==b)
		p->a=p->b=a;
	else
	{
		int m=(a+b) >> 1;
		sgt_build(p->left,a,m);
		sgt_build(p->right,m+1,b);
		p->a=a;p->b=b;
	}
}

int sgt_edit(sgt_node *p,int k,int v,bool del)
{
	int delter=0;
	if (p->a==p->b)
	{
		if (del)
			delter=p->treap->v;
	}
	else
	{
		int m=(p->a+p->b) >> 1;
		if (k>=p->a && k<=m)
			delter=sgt_edit(p->left,k,v,del);
		else
			delter=sgt_edit(p->right,k,v,del);
	}
	if (del)
		treap_delete(p->treap,delter);
	treap_insert(p->treap,v);
	return delter;
}

void sgt_get(sgt_node *p,int a,int b)
{
	if (p->a==a && p->b==b)
		T[++Tcnt]=p->treap;
	else
	{
		int m=(p->a+p->b) >> 1;
		if (b<=m)
			sgt_get(p->left,a,b);
		else if (a>=m+1)
			sgt_get(p->right,a,b);
		else
		{
			sgt_get(p->left,a,m);
			sgt_get(p->right,m+1,b);
		}
	}
}

void init()
{
	int i,v;
	TC=SC=-1;
	sgt_root=0;
	scanf("%d%d",&N,&M);
	sgt_build(sgt_root,1,N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&v);
		sgt_edit(sgt_root,i,v,false); //non-deletion
	}
}

int check(int result,int k)
{
	int totalrankL,totalrankR,minsucc=INF;
	int i,rank,succ,totalrank=0,totalcount=0;
	for (i=1;i<=Tcnt;i++)
	{
		succ=INF;
		treap_succ(T[i],result,succ);
		if (succ==INF)
			rank=T[i]->size+1;
		else
			treap_rank(T[i],succ,0,rank);
		totalrank+=rank-1;
		if (succ < minsucc)
			minsucc=succ;
	}
	for (i=1;i<=Tcnt;i++)
		totalcount+=treap_find(T[i],minsucc);
	totalrankL=++totalrank;
	totalrankR=totalrank+totalcount-1;
	if (k>=totalrankL && k<=totalrankR)
	{
		printf("%dn",minsucc);
		return 0;
	}
	else if (totalrankL > k)
		return 1;
	else
		return -1;
}

void binary(int a,int b,int k)
{
	int Min=INF,Max=0,i,m,r;
	Tcnt=0;
	sgt_get(sgt_root,a,b);
	for (i=1;i<=Tcnt;i++)
	{
		m=treap_getmax(T[i]);
		if (m>Max)
			Max=m;
		m=treap_getmin(T[i]);
		if (m<Min)
			Min=m;
	}
	m=(Max+Min)>>1;
	do
	{
		r=check(m,k); //-1=smaller 1=bigger
		if (r<0)
		{
			Min=m;
			m=(m+Max+1)>>1;
		}
		else if (r>0)
		{
			Max=m;
			m=(Min+m)>>1;
		}
	}while (r!=0);
}

void request()
{
	int i,a,b,c,j=0;
	for (i=1;i<=M;i++)
	{
		do c=getchar(); while (c==10 ||c==13);
		if (c=='C')
		{
			scanf("%d%d",&a,&b);
			sgt_edit(sgt_root,a,b,true);
		}
		else
		{
			scanf("%d%d%d",&a,&b,&c);
			binary(a,b,c);
		}
	}
}

int main()
{
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	scanf("%d",&D);
	for (int i=1;i<=D;i++)
	{
		init();
		request();
	}
	return 0;
}

我的转述 动态排名系统

[问题描述]
给定一个长度为N的已知序列A[i](1&lt;=i&lt;=N),要求维护这个序列,能够支持以下两种操作:
1、查询A[i],A[i+1],A[i+2],...,A[j](1&lt;=i&lt;=j&lt;=N)中,升序排列后排名第k的数。
2、修改A[i]的值为j。

所谓排名第k,指一些数按照升序排列后,第k位的数。例如序列{6,1,9,6,6},排名第3的数是6,排名第5的数是9。

[输入格式]
第一行包含一个整数D(0&lt;=D&lt;=4),表示测试数据的数目。接下来有D组测试数据,每组测试数据中,首先是两个整数N(1&lt;=N&lt;=50000),M(1&lt;=M&lt;=10000),表示序列的长度为N,有M个操作。接下来的N个不大于1,000,000,000正整数,第i个表示序列A[i]的初始值。然后的M行,每行为一个操作
Q i j k 或者
C i j
分别表示查询A[i],A[i+1],A[i+2],...,A[j](1&lt;=i&lt;=j&lt;=N)中,升序排列后排名第k的数,和修改A[i]的值为j。

[输出格式]
对于每个查询,输出一行整数,为查询的结果。测试数据之间不应有空行。

[样例输入]
2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

[样例输出]
3
6
3
6

题目原貌

Dynamic Rankings

Time limit: 10 Seconds Memory limit: 65536K

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], …, a[N], you can ask it like : what is the k-th smallest number of a[i], a[i+1], …, a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

- Reads N numbers from the input (1<=N<=50,000)

- Processes M instructions of the input (1<=M<=10,000). These instructions include querying the k-th smallest number of a[i], a[i+1], …, a[j] and change some a[i] to t.

Input

The first line of the input is a single number X (0<X<=4), the number of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers and M instruction. It is followed by N lines. The (i+1)-th line represents the number a[i]. Then M lines that is in the following format

<p align="left"><span><span><span>Q i j k           or
C i t</span></span></span>
<p align="left"><span><span><span>It represents to query the k-th number of a[i], a[i+1],..., a[j] and change some a[i] to t, respectively. It is guaranteed that at any time of the operation. Any number a[i] is a non-negative integer that is less than 1,000,000,000.</span></span></span></p>
<p align="left"><span><span>There're NO breakline between two continuous test cases.</span></span></p>
<p align="left"><span><span><strong>Output</strong></span></span></p>
<p align="left"><span><span>For each querying operation, output one integer to represent the result. (i.e. the k-th smallest number of a[i], a[i+1],..., a[j])</span></span></p>
<p align="left"><span><span><strong>There're NO breakline between two continuous test cases.</strong></span></span></p>
<p align="left"><span><span><strong>Sample Input</strong></span></span></p>

<p align="left"><span><span><span>2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3</span></span></span>
<p align="left"><span><span><strong>Sample Output</strong></span></span></p>

<p align="left"><span><span><span>3
6
3
6</span></span></span>
<p align="left"><span><span><span><strong>Author:</strong></span></span><span><span> XIN, Tao (chief editor), ZHU, Zeyuan (subeditor), PAN, Zhenhao (adviser)</span></span></span></p>
<p align="left"><span><span><span><strong>Site: </strong></span></span><span><span>http://zhuzeyuan.hp.infoseek.co.jp/index.files/our_contest_20040619.htm</span></span></span></p>

上次修改时间 2017-05-22

相关日志