CodeChef2014AprilChallenge-Chef的最终对决：数据结构与整体二分的应用

问题描述

给定一棵树，包含n个节点（编号为1到n），每个节点有一个初始值wi (1 ≤ wi ≤ 10^9)，以及q次操作。每次操作可能是更新某个节点的值或询问某个子树内非正数节点的数量。要求支持高效的数据结构来处理这些操作。

具体参数范围：
n, q, V ≤ 100,000
wi ≤ 10^9

解决方案

本题的核心难点在于处理带有下取整运算的时间相关修改。这类问题通常需要考虑不同时间点的影响累积方式，而不是简单地将所有变化叠加在一起。

我们观察到，一次更新操作的影响范围有限，仅限于距离不超过log(n)的节点。基于此特性，我们可以设计一个复杂度为O(q log n log² V)的初步算法：

• 对于子树内的节点，根据BFS序维护受影响区间的减法操作。
• 对于被修改节点的祖先节点，同样按照其对应深度进行相应调整，注意去除重复影响。

为了进一步优化，我们引入了一种更高效的策略：首先不直接处理子树，而是每次只修改当前节点及其祖先节点。通过记录tag[i,j]表示节点i对其第j级子孙的影响，可以将每次修改的复杂度降低至O(log²)。

针对查询子树内非正数节点的问题，可以采用整体二分或CDQ分治的方法。具体来说，我们将所有操作按时间分治，在每个分治区间[l,r]中，标记出哪些节点在此期间变为非正数。通过递归处理左右两个子区间，确保每个节点最多只会被检查O(log n)次。

此外，为了避免频繁插入和撤销操作带来的额外开销，我们使用持久化tag数组存储每次改变的时间戳。这样不仅减少了不必要的计算量，还将总的时间复杂度降至O(Q log² n)。

代码实现

#include 
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 100005
#define LL long long
using namespace std;

int fs[N], nt[2*N], dt[2*N], pr[N], n, m, w[N], dfw[N], sz[N], dfn[N], ans[N], m1, ask[N][3], f[N], dep[N];
LL sm[N];
//tree_array
int c[N];

int lowbit(int k) {
    return k & -k;
}

int get(int k) {
    int s = 0;
    while (k) s += c[k], k -= lowbit(k);
    return s;
}

void put(int k) {
    while (k <= n) c[k]++, k += lowbit(k);
}

void link(int x, int y) {
    nt[++m1] = fs[x];
    dt[fs[x] = m1] = y;
}

void dfs(int k, int fa) {
    f[k] = fa;
    dfw[dfn[k] = ++dfn[0]] = k;
    dep[k] = dep[fa] + 1;
    sz[k] = 1;
    for (int i = fs[k]; i; i = nt[i]) {
        int p = dt[i];
        if (p != fa) dfs(p, k), sz[k] += sz[p];
    }
}

struct node {
    LL v, t;
};

vector tag[N][32];
int le[N][32], now[N][32], d[N], u1[N], u2[N], ts[N];

void ins(int k, int s, int ti) {
    if (!s || !k) return;
    int v = s;
    for (int c = 0; v; c++) {
        int vl = (f[k]) ? v - (v >> 2) : v;
        if (le[k][c] == 0) tag[k][c].push_back((node){vl, ti});
        else tag[k][c].push_back((node){vl + tag[k][c][le[k][c] - 1].v, ti});
        le[k][c]++;
        v >>= 1;
    }
    ins(f[k], s >> 1, ti);
}

LL query(int k, int ti) {
    LL s = 0;
    for (int p = 0; p <= 31 && k; k = f[k], p++) {
        while (now[k][p]         while (now[k][p] > 0 && tag[k][p][now[k][p]].t > ti) now[k][p]--;
        if (now[k][p]     }
    return s;
}

void doit(int l, int r, int x, int y) {
    if (x > y) return;
    if (l == r) {
        fo(i, x, y) ts[d[i]] = l;
        return;
    }
    int mid = (l + r) >> 1;
    u1[0] = u2[0] = 0;
    fo(i, x, y) {
        if (pr[d[i]] <= query(d[i], mid)) u1[++u1[0]] = d[i];
        else u2[++u2[0]] = d[i];
    }
    fo(j, 1, u1[0]) d[x + j - 1] = u1[j];
    fo(j, 1, u2[0]) d[x + u1[0] + j - 1] = u2[j];
    int md = x + u1[0] - 1;
    doit(l, mid, x, md);
    doit(mid + 1, r, md + 1, y);
}

bool cmp(int x, int y) {
    return ts[x] }

int main() {
    cin >> n;
    fo(i, 1, n) scanf("%d", &pr[i]);
    fo(i, 1, n - 1) {
        int x, y;
        scanf("%d%d", &x, &y);
        link(x, y), link(y, x);
    }
    dfs(1, 0);
    int q;
    cin >> q;
    fo(i, 1, q) {
        scanf("%d%d", &ask[i][0], &ask[i][1]);
        if (ask[i][0] == 1) {
            scanf("%d", &ask[i][2]);
            ins(ask[i][1], ask[i][2], i);
        }
    }
    fo(i, 1, n) d[i] = i;
    doit(1, q + 1, 1, n);
    sort(d + 1, d + n + 1, cmp);
    for (int i = 1, j = 1; i <= q; i++) {
        while (j <= n && ts[d[j]] <= i) put(dfn[d[j]]), j++;
        if (ask[i][0] == 2) printf("%d\n", get(dfn[ask[i][1]] + sz[ask[i][1]] - 1) - get(dfn[ask[i][1]] - 1));
    }
}