Beyond the Void
BYVoid
Dynamic Rankings 動態排名系統 (zju 2112)
本文正體字版由OpenCC轉換

解決這個和問題,需要用到“樹套樹”。建立一棵線段樹,維護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

相關日誌