题目：单点更新查询区间第k大
按照主席树的思想，要主席树套树状数组。即按照每个节点建立主席树，然后利用树状数组的方法来更新维护前缀和。然而，这样的做法在实际中并不能AC，原因即卡空间。
因此我们采用一种叫做整体二分的方法。
说一下具体做法：
首先要离线处理
我们把原数列也当成单点更新的操作，而更改值我们则看成两个操作，第一个是删掉原来位置的值，第二个是把新的值放置在这个位置，这样一来我们就可以得到最长n*3的操作序列。
然后就是我们的整体二分步骤了，首先我们对答案进行二分，这时我们会获得一个mid值。此时对于某个询问，如果我们发现在区间内不大于mid的值的个数少于k的时候，我们显然要在比mid大的区间进行二分查找答案，然而我们这次的查找怎么办呢？答案就是记录下来。我们发现在比mid大的区间查找答案的时候，我们之前这次的查找必然也会对下次的查找做出同样的贡献，因此我们只要把这次查找的结果存下来，下次就可以避免重复查找。而另外一种情况，就不大于mid的值的个数大于等于k的时候，我们显然就需要在比mid小的区间进行查找啦，此时我们之前的查找信息只能作废。
据说整体二分的时间复杂度和询问的长度是线性相关的，然而我却认为是nlogn的，这里还不太懂，希望有大神解答...
ZOJ 2112 Dynamic Rankings链接如下：
此题卡主席树的空间，但是用此代码结果如下：
代码如下：
#include#include #include #define inf 1000000000using namespace std;int T, n, m, tot, cnt;int a[50010], ans[10010], tree[50010], cur[70010];char str[5];void updata(int pos, int val) { while (pos <= n) { tree[pos] += val; pos += pos & (-pos); }}int read(int pos) { int tmp = 0; while (pos > 0) { tmp += tree[pos]; pos -= pos & (-pos); } return tmp;}struct N { int l, r, k, id, cur, tp; N() {} N(int _l, int _r, int _k, int _id, int _cur, int _tp): l(_l), r(_r), k(_k), id(_id), cur(_cur), tp(_tp) {}};N q[70010], q1[70010], q2[70010];void ask(int fro, int las, int l, int r) { if (fro > las) return ; if (l == r) { for (int i = fro; i <= las; i++) { if (q[i].tp == 3) ans[q[i].id] = l; } return ; } int mid = (l + r) / 2; for (int i = fro; i <= las; i++) { if (q[i].tp == 1 && q[i].k <= mid) updata(q[i].l, 1); else if (q[i].tp == 2 && q[i].k <= mid) updata(q[i].l, -1); else if (q[i].tp == 3) cur[i] = read(q[i].r) - read(q[i].l - 1); } for (int i = fro; i <= las; i++) { if (q[i].tp == 1 && q[i].k <= mid) updata(q[i].l, -1); else if (q[i].tp == 2 && q[i].k <= mid) updata(q[i].l, 1); } int t1 = 0, t2 = 0; for (int i = fro; i <= las; i++) { if (q[i].tp == 3) { if (q[i].cur + cur[i] >= q[i].k) { q1[t1++] = q[i]; } else { q[i].cur += cur[i]; q2[t2++] = q[i]; } } else { if (q[i].k <= mid) q1[t1++] = q[i]; else q2[t2++] = q[i]; } } for (int i = 0; i < t1; i++) q[fro + i] = q1[i]; for (int i = 0; i < t2; i++) q[fro + t1 + i] = q2[i]; ask(fro, fro + t1 - 1, l, mid); ask(fro + t1, las, mid + 1, r);}int main() { //freopen("in.in", "r", stdin); //freopen("out.out", "w", stdout); scanf("%d", &T); while (T--) { memset(tree, 0, sizeof(tree)); scanf("%d %d", &n, &m); tot = cnt = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); q[tot++] = N(i, i, a[i], 0, 0, 1); } int l, r, k; for (int i = 0; i < m; i++) { scanf("%s", str); if (str[0] == 'Q') { scanf("%d %d %d", &l, &r, &k); q[tot++] = N(l, r, k, ++cnt, 0, 3); } else { scanf("%d %d", &l, &k); q[tot++] = N(l, l, a[l], 0, 0, 2); q[tot++] = N(l, l, k, 0, 0, 1); a[l] = k; } } //printf("tot = %d cnt = %d\n", tot, cnt); ask(0, tot - 1, 0, inf); for (int i = 1; i <= cnt; i++) printf("%d\n", ans[i]); } return 0;}
最后，为神马csdn没有发首页的功能了呢，酱紫我的博客谁来看啊
