Post 36

Veröffentlicht am | Edited on

BZOJ#1901 Dynamic Rankings

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1

],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改

变后的a继续回答上面的问题。

Input

第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。

分别表示序列的长度和指令的个数。

第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。

接下来的m行描述每条指令

每行的格式是下面两种格式中的一种。

Q i j k 或者 C i t

Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1）

表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。

C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t

m,n≤10000

Output

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Sample Input

5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output

3

6

题解

昨天本来很垃圾，也就秒想出待修改整体二分怎么搞还算好点。

昨天已经写好题解了，不过在这里再说下理解。

整体二分就是把操作序列分治成和值域相关的子问题，不管是修改还是查询。

一个有趣的细节：

img

img

这两个都是正确的。

原因是整体二分由于右边的永远不会影响左边的，所以覆盖掉左边的位置并不会错。

确实挺好写，1A

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 100005
int n , ans[maxn] , bit[maxn] , m , val[maxn];
const int RANGE = (int)1e9;
struct Node{
	int tp , l , r , v , id;
}q[maxn<<2] , lq[maxn<<2] , rq[maxn<<2];

inline void update(int pos , int val){
	if(pos == 0) return ;
	for( ; pos <= n ; pos += pos & -pos)
		bit[pos] += val;
}
inline int query(int pos){
	if(!pos) return 0;
	int ans = 0;
	for( ; pos ; pos -= pos & -pos)
		ans += bit[pos];
	return ans;
}

void VDC(int vl , int vr , Node* cur , int al , int ar)
{
	if(vl == vr)
	{
		for(int i = al ; i <= ar ; ++i)
			if(cur[i].tp == 1)
				ans[cur[i].id] = vl;
		return;
	}
	if(ar - al + 1 == 0) return ;

	int mid = vl + vr >> 1 , lqt = 0 , rqt = 0;

	for(int i = al ; i <= ar ; ++i)
	{
		if(cur[i].tp == 0)
		{
			if(cur[i].v <= mid) 
			{
				update(cur[i].l , cur[i].r);
				lq[++lqt] = cur[i];
			}
			else rq[++rqt] = cur[i];
		}
		else if(cur[i].tp == 1)
		{
			int l = cur[i].l , r = cur[i].r , v = cur[i].v;
			int cnt = query(r) - query(l-1);
			if(cnt >= v) lq[++lqt] = cur[i];
			else cur[i].v -= cnt , rq[++rqt] = cur[i];
		}
	}
	for(int i = al ; i <= ar ; ++i)
		if(cur[i].tp == 0 && cur[i].v <= mid)
			update(cur[i].l , -cur[i].r);
	for(int i = 1 ; i <= lqt ; ++i)
		cur[i] = lq[i];
	for(int i = 1 ; i <= rqt ; ++i)
		cur[i+lqt] = rq[i];
	VDC(vl , mid , cur , 1 , lqt);
	VDC(mid + 1 , vr , cur , 1 + lqt  , lqt + rqt);
}

int main()
{
	scanf("%d%d",&n,&m);
	int t = 0;
	for(int i = 1 ; i <= n ; ++i)
	{
		scanf("%d",&val[i]);
		q[++t].tp = 0 , q[t].l = i , q[t].r = 1 , q[t].v = val[i];
	}
	int tot = 0;
	for(int i = 1 ; i <= m ; ++i)
	{
		int l , r , v;
		char op;
		scanf("\n%c",&op);
		if(op == 'Q') scanf("%d%d%d",&l,&r,&v) , q[++t].tp = 1 , q[t].id = ++tot , q[t].l = l , q[t].r = r , q[t].v = v;
		else {
			scanf("%d%d",&l,&r) , q[++t].tp = 0 , q[t].l = l , q[t].r = -1 , q[t].v = val[q[t].l] , q[++t].tp = 0 , q[t].l = l , q[t].r = 1 , q[t].v = r , val[q[t].l] = r;
		}
	}
	VDC(-RANGE,RANGE,q,1,t);
	for(int i = 1 ; i <= tot ; ++i)
		printf("%d\n",ans[i]);
}

上午luogu有场比赛，感觉还挺有意思，就参加了一下。

暂时前十qwq？
img