ZOJ2112 Dynamic Rankings(整体二分)

今天学习了一个奇技淫巧－－整体二分。关于整体二分的一些理论性的东西，可以参见XRH的《浅谈数据结构题的几个非经典解法》。然后下面是一些个人的心得体会吧，写下来希望加深一下自己的理解，或者如果有人看了或许也有些帮助。

ZOJ2112是一道典型的带修改的区间第k大的问题，有一些树套树等的数据结构可以在线处理这样的问题。但是当题目并不要求在线处理的时候，其实我们可以选择一下整体二分的思想。

个人对整体二分的理解是这样子的，首先对于修改，即把a[xi]=yi（1<=yi<=C）的时候，我们可以把修改的操作划分成两部分，一部分是yi<=mid,另一部分是yi>mid。首先我们忽略掉yi>mid的操作，将yi<=mid以及询问操作按照输入的顺序执行一遍，这样我们就可以知道<=mid的操作对所有询问的贡献，接下来我们就要根据贡献对修改操作划分成两部分，一部分是答案在<=mid里面的，另外一部分是答案在>mid里面的，对于<=mid的，显然我们可以递归求解（因为>mid的操作对那些<=mid是没有影响的），而对于>mid的来说，<=mid的操作是有影响的，但是<=mid所造成的影响已经算过一遍了，所以对于>mid的来说，其实也是独立的。所以如果我们把答案二分的范围的大小设为C，操作的总数设为n，那么划分到<=mid的操作是n1,>mid的操作是n2时（n1+n2=n）

有 T(n,C)=T(n1,C/2)+T(n2,C/2)+O(nlogC) T(n)=nlogC^2...（也不知道复杂度对不对，可以画一个图来YY一下）

好吧，其实我也不知道上面说了什么，感觉真的蛮难用一两段话将整个思路说出来的。其实总的抽象的来说，就是一开始维护的可能答案的区间是[l,r]，

然后我们将所有<=mid的操作作一遍，然后将答案落在[l,mid]的操作（询问和修改）划到一边，将答案落在[mid+1,r]的操作（询问和修改）划到另一边。

#pragma warning(disable:4996)

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <string>

#include <vector>

#include <queue>

using namespace std;

#define maxn 300000

struct Query

{

	int x, y; // qt==3 [x,y]  qt==1||2 a[x]=y

	int qt; // query type 1 for increase 2 for decrease 3 for query

	int cur; // the current contribution

	int k; // the query is the k-th smalleset

	int index;

}q[maxn];

int qtop;

int a[maxn];

int b[maxn];

int bsize;

int n, m;

int tot;

int ans[maxn];

int ansid;

int tmp[maxn];

Query q1[maxn], q2[maxn];

int bit[maxn];

void add(int x, int v)

{

	while (x <= n){

		bit[x] += v;

		x += x&(-x);

	}

}

int query(int x)

{

	int ret = 0;

	while (x > 0){

		ret += bit[x];

		x -= x&(-x);

	}

	return ret;

}

void solve(int head, int tail, int l, int r)

{

	if (head > tail) return;

	if (l == r){

		for (int i = head; i <= tail; ++i){

			if (q[i].qt == 3) ans[q[i].index] = l;

		}

		return;

	}

	int mid = (l + r) >> 1;

	// 将所有<=mid的操作作一遍，tmp[i]存的是[head,tail]里<=mid的操作对询问的贡献

	for (int i = head; i <= tail; ++i){

		if (q[i].qt == 1 && q[i].y <= mid){

			add(q[i].x, 1);

		}

		else if (q[i].qt == 2 && q[i].y <= mid){

			add(q[i].x, -1);

		}

		else{

			tmp[i] = query(q[i].y) - query(q[i].x - 1);

		}

	}

	// 将操作撤销一下

	for (int i = head; i <= tail; ++i){

		if (q[i].qt == 1 && q[i].y <= mid){

			add(q[i].x, -1);

		}

		else if (q[i].qt == 2 && q[i].y <= mid){

			add(q[i].x, 1);

		}

	}

	// 将操作划分成两部分

	int l1=0, l2 = 0;

	for (int i = head; i <= tail; ++i){

		if (q[i].qt == 3){

			// 如果前面的数加上当前的数>=q[i].k，说明该询问的可行区间在[l,mid]，往左划分

			if (q[i].cur + tmp[i] >= q[i].k){

				q1[++l1] = q[i];

			}

			else{

				// 否则往右划分，并记下贡献

				q[i].cur += tmp[i];

				q2[++l2] = q[i];

			}

		}

		else{

			if (q[i].y <= mid) q1[++l1] = q[i];

			else q2[++l2] = q[i];

		}

	}

	for (int i = 1; i <= l1; ++i) {

		q[head + i - 1] = q1[i];

	}

	for (int i = 1; i <= l2; ++i){

		q[head + l1 + i - 1] = q2[i];

	}

	solve(head, head + l1 - 1, l, mid);

	solve(head + l1, tail, mid + 1, r);

}

int main()

{

	int T; cin >> T;

	while (T--)

	{

		scanf("%d%d", &n, &m);

		qtop = 0;tot = 0;

		for (int i = 1; i <= n; ++i){

			scanf("%d", a + i);

			b[tot++] = a[i];

			q[++qtop].qt = 1;

			q[qtop].x = i;

			q[qtop].y = a[i];

		}

		char cmd[4];

		int xi, yi,ki;

		ansid = 0;

		for (int i = 0; i < m; ++i){

			scanf("%s", cmd);

			if (cmd[0] == 'Q'){

				scanf("%d%d%d", &xi, &yi, &ki);

				q[++qtop].x = xi; q[qtop].y = yi; q[qtop].k = ki;

				q[qtop].qt = 3; q[qtop].cur = 0; q[qtop].index = ++ansid;

			}

			else{

				scanf("%d%d", &xi, &yi);

				q[++qtop].x = xi; q[qtop].y = a[xi]; q[qtop].qt = 2;

				q[++qtop].x = xi; q[qtop].y = yi; q[qtop].qt = 1;

				a[xi] = yi;

				b[tot++] = yi;

			}

		}

		sort(b, b + tot);

		bsize = unique(b, b + tot) - b;

		for (int i = 1; i <= qtop; ++i){

			if (q[i].qt == 1 || q[i].qt == 2){

				q[i].y = lower_bound(b, b + bsize, q[i].y) - b + 1;

			}

		}

		solve(1, qtop, 1, bsize);

		for (int i = 1; i <= ansid; ++i){

			printf("%d\n", b[ans[i]-1]);

		}

	}

	//system("pause");

	return 0;

}

巴特西

ZOJ2112 Dynamic Rankings(整体二分)

最新文章

热门文章