一无所|知的小|J f

一无所|知的小|J f

被分块了(划去

题解 P4175 【[CTSC2008]网络管理】

posted on 2019-08-19 07:33:15 | under 题解 |

一万年了。

小蒟蒻Jf终于更博啦>_<

感觉自己已经彻底变成一个鸽子了呢qwq。

———————————————以上是闲话—————————————————————————

这里提供一个树分块的题解。 其时间复杂度为(m+n) sqrt (n) 空间复杂度为n sqrt (n)

前置芝士: O1lca(这个挺基础的吧) 值域分块(可以参考小蒟蒻之前的blog

那么废话不多说, 直接开始讲实现方法。

在树上选出T个关键点(选取的方法和性质后面会说), 在把这些关键点之间的LCA也设成关键点,然后将值域分块,处理出这些关键点到根的路径中的一些信息:

cnt1(i, j)表示第i个关键点到根的路径中, 权值在第j个值域块中的点的数量

cnt2(i, j) 表示第i个关键点到根的路径中, 权值为j的点的数量

显然上面的两个数组可以在T n 的时间内处理完成。 然后关于这T个点的选取, 我们想让其拥有这样的性质: 从树上的任何一个点出发向根跳最多跳T(常数)次就可以跳到一个关键点。

显然可以通过贪心来选取这T个点, 然后小Jf比较懒, 就随机了T个点, 据某毒瘤说复杂度也是正确的qwq。(贪心的具体方法本文不进行具体介绍, 可以参考2015年邹逍遥的国家集训队论文)

有了上面的性质, 问题就简单了。 我们先对树进行染色。 将树上向根上跳第一个遇到的关键点相同 染上相同的颜色。 那么对于询问x,y,k。 如果xy的颜色相同, 那么显然可以在O(T)的实现内暴力进行查询(记录下路径上经过的点用值域分块进行查询)。 对于颜色不同的x,y, 我们可以进行如下的讨论:

pic1.jpg

情况1: 如上图,记x的颜色为xx, y的颜色为yy, xx和yy并非祖先-后代关系。 这种情况是最简单的, 直接处理一下散块(x到xx, y到yy)的信息(蓝色) 然后xx到yy的信息(红色) 可以通过xx到根的信息 + yy到根的信息 - *2lca(xx, yy)到根的信息** 来得到。 然后值域分块来求k大就可以了。

pic2.png

情况2:如上图,记x的颜色为xx, y的颜色为yy, xx和yy是祖先=后代关系, lca(x,y) 是xx,yy中的一个点的祖先, 同时是其中另外一个点的后代。

这种情况下, 如果我们和之前一样处理散块(x到xx,y到yy)的信息(蓝色)和xx到yy的信息(红色)的话, 就会发现多处理了图上<红蓝色>的部分, 而且多处理了两次。 这个时候我们只需要在处理散块信息的时候特殊处理一下就行了。

恩。 那么查询就讲完了qwq 其实修改也很简单, 直接判断一下所有关键点到根的路径中是否经过修改的点, 如果经过的话就在处理的信息中单次O1进行修改就可以了>_< (注意这里需要O1查询的lca, 不然复杂度带log)效率为O(T)

当T取sqrt(n)时, 算法的时间复杂度为(n+m)sqrt(n) 空间复杂度为n sqrt(n)

貌似就没有什么啦qwq 有什么问题的话欢迎来私信小蒟蒻啊qwqwq

那么代码如下:


#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <ctime>
#define maxn 400010
#define maxs 330
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
#define DFR(i, l, r) for(re int i = l; i >= r; --i)
using namespace std;

int n, m, c, r, t, x, y, k, tot;
int sq1, sq2, num, cnt, col, theone, fh, lastans;
int a[maxn], b[maxn], depth[maxn], cnt1[maxs*2][maxs], cnt2[maxs*2][maxn];
int qwq[maxn], san1[maxn], san2[maxn], dis[maxn], head[maxn], numb[maxn];
int fa[maxn], near[maxn], z[maxn], z1[maxn], q[maxn][3];
int f[maxn][20], lg[maxn], id[maxn], vis[maxn], Depth[maxn];
struct hz {
    int next;
    int to;
}h[maxn*2];

inline int read(){
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c==-1) return 0;
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x*f;
}

inline void add(int from, int to) {
    h[++num].next = head[from];
    h[num].to = to;
    head[from] = num;
}

void dfs(int x, int ff, int dep) {
    fa[x] = ff;
    id[x] = ++tot;
    depth[x] = depth[ff]+1;
    vis[tot] = x;
    Depth[tot] = dep;
    for(re int i = head[x]; i != 0; i = h[i].next) {
        if(h[i].to == ff)
          continue;
        dfs(h[i].to, x, dep+1);
        vis[++tot] = x;
        Depth[tot] = dep;
    }
}

void RMQ() {
    FOR(i, 1, tot)
      lg[i] = lg[i-1]+(1 << lg[i-1] == i);
    FOR(i, 1, tot)
      f[i][0] = i;
    for(int i = 1; (1<<i) <= tot; i++) {
        for(int j = 1; j+(1 << i)-1 <= tot; j++) {
            int A = f[j][i-1];
            int B = f[j+(1 << (i-1))][i-1];
            if(Depth[A] <= Depth[B])
              f[j][i] = A;
            else
              f[j][i] = B;
        }
    }
}

int lca(int x, int y) {
    int r = id[x];
    int l = id[y];
    if(r < l)
      swap(r, l);
    int k = lg[r-l+1]-1;
    int A = f[l][k];
    int B = f[r-(1<<k)+1][k];
    if(Depth[A] <= Depth[B])
      return vis[A];
    else
      return vis[B];
}

void dfs3(int x, int color) { //染色 
    if(numb[x] != 0)
      color = numb[x];
    near[x] = color; //属于什么管辖范围 
    for(re int i = head[x]; i != 0; i = h[i].next) {
        if(h[i].to == fa[x]) 
          continue;
        dfs3(h[i].to, color);
    }
} 

inline void deal(int x, int times) {
    while(x != 0) {
        ++cnt1[times][b[a[x]]];
        ++cnt2[times][a[x]];
        x = fa[x];  
    }
} 

int query(int x, int y, int k) { //求k大 
    //xy在一个颜色块里, 则直接暴力跳到lca
    //xy不在一个颜色块里, 且一部分路径重复计算-> 经过lca后转化加减法 
    if(near[x] == near[y]) {  
        int lc = lca(x, y), xx = x, yy = y, anss = 0;
        while(x != lc) 
          ++san1[b[a[x]]], ++san2[a[x]], x = fa[x]; 
        while(y != fa[lc]) 
          ++san1[b[a[y]]], ++san2[a[y]], y = fa[y];
        int tot = 0, now = 1;
        while(tot+san1[now] < k)
          tot += san1[now], ++now;
        FOR(j, (now-1)*sq1+1, now*sq1) 
          if((tot += san2[j]) >= k) {
              anss = z[j];
              break;
          }
        while(xx != lc) 
          --san1[b[a[xx]]], --san2[a[xx]], xx = fa[xx]; 
        while(yy != fa[lc]) 
          --san1[b[a[yy]]], --san2[a[yy]], yy = fa[yy];
        return anss;
    } 

    int lc = lca(x, y), LC = lca(z1[near[x]], z1[near[y]]), xx = x, yy = y;
    theone = -1, fh = 1;
    if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案 
        theone = lc;
        san1[b[a[LC]]]--, san2[a[LC]]--;
    }
    while(near[fa[xx]] == near[x]) {
        if(xx == theone) {
            fh *= -1;
        }
        else {
        san1[b[a[xx]]] += fh, san2[a[xx]] += fh;   
        }
        if(xx == 0)
          exit(0);
        xx = fa[xx];
    }
    fh = 1;
    while(near[fa[yy]] == near[y]) {
        if(yy == theone) {
            fh *= -1;   
            yy = fa[yy];
            continue;
        } 
        san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy]; 
    }

    ++san1[b[a[LC]]];
    ++san2[a[LC]]; 
    int tot = 0, now = 1, anss = 0;
    while(tot+san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now] < k)
      tot += san1[now]+cnt1[near[x]][now]+cnt1[near[y]][now]-2*cnt1[numb[LC]][now], ++now;
    FOR(j, (now-1)*sq1+1, now*sq1)  
      if((tot += san2[j]+cnt2[near[x]][j]+cnt2[near[y]][j]-2*cnt2[numb[LC]][j]) >= k) {
          anss = z[j];
          break;
      }
    fh = -1, xx = x, yy = y;
    while(near[fa[xx]] == near[x]) {
        if(xx == theone) {
            fh *= -1;
            xx = fa[xx];
            continue;
        }  
        san1[b[a[xx]]] += fh, san2[a[xx]] += fh, xx = fa[xx];   
    }
    fh = -1;
    while(near[fa[yy]] == near[y]) {
        if(yy == theone) {
            fh *= -1;
            yy = fa[yy];
            continue;
        } 
        san1[b[a[yy]]] += fh, san2[a[yy]] += fh, yy = fa[yy]; 
    }
    --san1[b[a[LC]]];
    --san2[a[LC]]; 
    if(lca(z1[near[x]], z1[near[y]]) == LC && (lca(lc, z1[near[x]]) == lc || lca(lc, z1[near[y]])) && lc != LC) { //需要转化加减答案 
        san1[b[a[LC]]]++, san2[a[LC]]++;
    }
    return anss;
}

signed main() {
    srand(19260817);
    srand(rand());
    srand(rand());
    n = read(), m = read();
    FOR(i, 1, n) {
        a[i] = read(), z[++z[0]] = a[i];
        qwq[i] = i;
    }
    FOR(i, 1, n-1) {
        x = read(), y = read();
        add(x, y);
        add(y, x);
    } 
    dfs(1, 0, 1);
    RMQ();
    FOR(i, 1, m) {
        q[i][0] = read(), q[i][1] = read(), q[i][2] = read();
        if(q[i][0] == 0)
          z[++z[0]] = q[i][2];
    }

    sort(z+1, z+z[0]+1);
    z[0] = unique(z+1, z+z[0]+1)-z-1;
    FOR(i, 1, n) 
      a[i] = lower_bound(z+1, z+z[0]+1, a[i])-z;
    sq1 = sqrt(z[0]); //值域分块 
    FOR(i, 1, z[0])
      b[i] = (i-1)/sq1+1; 

    random_shuffle(qwq+1, qwq+n+1); //选取前sq个点 
    sq2 = sqrt(n); //关键点的数量 
    FOR(i, 1, sq2) 
      z1[++z1[0]] = qwq[i];  
    FOR(i, 1, sq2) 
      FOR(j, i+1, sq2)
        z1[++z1[0]] = lca(qwq[i], qwq[j]);
    sort(z1+1, z1+z1[0]+1); //关键点排序并去重 
    z1[0] = unique(z1+1, z1+z1[0]+1)-z1-1;
    FOR(i, 1, z1[0]) 
      numb[z1[i]] = i; //关键点的新序号 
    dfs3(1, -2); //染色

    FOR(i, 1, z1[0]) //枚举所有新关键点(sq个) 进行处理;
      deal(z1[i], i);  

    FOR(i, 1, m) {
        k = q[i][0], x = q[i][1], y = q[i][2];
        int sizz = depth[x]+depth[y]-2*depth[lca(x, y)]+1;
        if(k == 0) {
            y = lower_bound(z+1, z+z[0]+1, q[i][2])-z;
            FOR(j, 1, z1[0]) {
                if(lca(z1[j], x) != x)
                  continue;
                --cnt1[j][b[a[x]]];
                --cnt2[j][a[x]];
                ++cnt1[j][b[y]];
                ++cnt2[j][y];
            }
            a[x] = y;
            continue;
        }
        if(sizz < k) {
            puts("invalid request!");
            continue;
        }
        printf("%d\n", query(x, y, sizz-k+1));
    }
}