[CTSC2008]网络管理Network【树状数组+主席树】

题目链接

题意：有一棵N个点的树，每个点有对应的权值，现在有这样的操作，“0 a b”将a点的权值改成为b，“k a b”询问a到b的链上第k大的权值是几。

  我们可以用dfs序的树上差分的方式来解决这个问题，可以发现，求u到v的信息，其实就是求u到lca和v到lca的合并，所以我们得想办法把这条链上的第k大给处理出来，这时候可以使用主席树来进行操作，我们不妨给点u赋值的时候，赋值给dfn[u]~dfn[u]+siz[u]-1，是这棵子树上的所有的点都被给予了这个值，不妨在dfn[u]位置“+1”，dfn[u]+siz[u]的位置上“-1”，用dfs序的方式将他们放到了一条链上去进行差分。

  但是现在有了修改的操作，我们改变一个值的时候，实际上会对他的所有的子树造成影响，所以我们改成给原来的每个点都是一棵主席树，我们将原来的dfs序成的序列拿出来，看成一维轴的形式，然后，就是对这个一维的轴进行操作了。

  那么，我们可以利用树状数组，对这个前缀差分来进行操作，不妨在dfn[u]的点处先减去原来的点权的贡献，再换上新的点权，然后同理不要忘记dfn[u]+siz[u]这个位置的操作。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define eps 1e-8
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 8e4 + 7;
int N, Q, head[maxN], cnt, a[maxN], Lsan[maxN << 1], _UP;
vector<int> bin;
struct Eddge
{
    int nex, to;
    Eddge(int a=-1, int b=0):nex(a), to(b) {}
} edge[maxN << 1];
inline void addEddge(int u, int v)
{
    edge[cnt] = Eddge(head[u], v);
    head[u] = cnt++;
}
inline void _add(int u, int v) { addEddge(u, v); addEddge(v, u); }
struct Question
{
    int k, a, b;
    void In() { scanf("%d%d%d", &k, &a, &b); }
} ques[maxN];
int siz[maxN], fa[maxN], deep[maxN], Wson[maxN];
void dfs_1(int u, int father)
{
    siz[u] = 1; fa[u] = father; deep[u] = deep[father] + 1;
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == father) continue;
        dfs_1(v, u);
        if(siz[v] > siz[Wson[u]]) Wson[u] = v;
    }
}
int top[maxN], dfn[maxN], rid[maxN], tim, End_tim[maxN];
void dfs_2(int u, int topy)
{
    top[u] = topy; dfn[u] = ++tim; rid[tim] = u;
    if(Wson[u]) dfs_2(Wson[u], topy);
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa[u] || v == Wson[u]) continue;
        dfs_2(v, v);
    }
    End_tim[u] = tim;
}
int _LCA(int u, int v)
{
    while(top[u] ^ top[v])
    {
        if(deep[top[u]] < deep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    if(deep[u] > deep[v]) swap(u, v);
    return u;
}
const int max_T = maxN * 400;
int t[max_T], lc[max_T], rc[max_T], tot, root[maxN];
void Insert(int &now, int old, int l, int r, int pos, int val)
{
    if(!now) now = ++tot;
    t[now] = t[old] + val; lc[now] = lc[old]; rc[now] = rc[old];
    if(l == r) return;
    int mid = HalF;
    if(pos <= mid) Insert(lc[now], lc[old], l, mid, pos, val);
    else Insert(rc[now], rc[old], mid + 1, r, pos, val);
}
void Pre_update(int x, int pos, int val)
{
    while(x <= N)
    {
        Insert(root[x], root[x], 1, _UP, pos, val);
        x += lowbit(x);
    }
}
int tmp_1[maxN], tmp_2[maxN], t1, t2;
int query(int l, int r, int kth)
{
    int mid, sum;
    while(l ^ r)
    {
        mid = HalF; sum = 0;
        for(int i=1; i<=t1; i++) sum += t[rc[tmp_1[i]]];
        for(int i=1; i<=t2; i++) sum -= t[rc[tmp_2[i]]];
        if(sum >= kth)
        {
            for(int i=1; i<=t1; i++) tmp_1[i] = rc[tmp_1[i]];
            for(int i=1; i<=t2; i++) tmp_2[i] = rc[tmp_2[i]];
            l = mid + 1;
        }
        else
        {
            for(int i=1; i<=t1; i++) tmp_1[i] = lc[tmp_1[i]];
            for(int i=1; i<=t2; i++) tmp_2[i] = lc[tmp_2[i]];
            r = mid;
            kth -= sum;
        }
    }
    return l;
}
int Pre_Query(int u, int v, int kth)
{
    t1 = t2 = 0;
    for(int i=dfn[u]; i; i -= lowbit(i)) tmp_1[++t1] = root[i];
    for(int i=dfn[v]; i; i -= lowbit(i)) tmp_1[++t1] = root[i];
    int lca = _LCA(u, v);
    if(deep[u] + deep[v] - deep[lca] - deep[fa[lca]] < kth) return -1;
    for(int i=dfn[lca]; i; i -= lowbit(i)) tmp_2[++t2] = root[i];
    for(int i=dfn[fa[lca]]; i; i -= lowbit(i)) tmp_2[++t2] = root[i];
    return query(1, _UP, kth);
}
void dfs_3(int u, int ff)
{
    Pre_update(dfn[u], a[u], 1);
    Pre_update(End_tim[u] + 1, a[u], -1);
    for(int i=head[u], v; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == ff) continue;
        dfs_3(v, u);
    }
}
inline void init()
{
    cnt = 0; _UP = N; tim = 0; tot = 0;
    for(int i=1; i<=N; i++) head[i] = -1;
}
int main()
{
    scanf("%d%d", &N, &Q);
    for(int i=1; i<=N; i++) { scanf("%d", &a[i]); Lsan[i] = a[i]; }
    init();
    for(int i=1, u, v; i<N; i++)
    {
        scanf("%d%d", &u, &v);
        _add(u, v);
    }
    for(int i=1; i<=Q; i++) { ques[i].In(); if(!ques[i].k) Lsan[++_UP] = ques[i].b; }
    sort(Lsan + 1, Lsan + _UP + 1);
    _UP = (int)(unique(Lsan + 1, Lsan + _UP + 1) - Lsan - 1);
    for(int i=1; i<=N; i++) a[i] = (int)(lower_bound(Lsan + 1, Lsan + _UP + 1, a[i]) - Lsan);
    for(int i=1; i<=Q; i++) if(!ques[i].k) ques[i].b = (int)(lower_bound(Lsan + 1, Lsan + _UP + 1, ques[i].b) - Lsan);
    dfs_1(1, 0);
    dfs_2(1, 1);
    dfs_3(1, 0);
    int ans;
    for(int i=1; i<=Q; i++)
    {
        if(ques[i].k == 0)
        {
            Pre_update(dfn[ques[i].a], a[ques[i].a], -1);
            Pre_update(End_tim[ques[i].a] + 1, a[ques[i].a], 1);
            Pre_update(dfn[ques[i].a], ques[i].b, 1);
            Pre_update(End_tim[ques[i].a] + 1, ques[i].b, -1);
            a[ques[i].a] = ques[i].b;
        }
        else
        {
            ans = Pre_Query(ques[i].a, ques[i].b, ques[i].k);
            if(~ans)
            {
                printf("%d\n", Lsan[ans]);
            }
            else
            {
                printf("invalid request!\n");
            }
        }
    }
    return 0;
}