P2137 题解

chenxinyang2006 · 2021-04-01 20:24:45 · 题解

来一个时间 O(m \sqrt n)，空间 O(n) 的解法

首先先讲一下如何 O(n) 预处理，O(\sqrt n) 在线查询区间 [l,r] 内有多少个数 \le x

对序列、值域都按照块长 \sqrt n 进行分块，注意值域是从小到大排序后，每 \sqrt n 个划分一块，因此两个相同的数可能在不同的块中

计 s_{i,j} 为前 i 个块有多少个数落在第 j 个值域块，这部分不难 O(n) 预处理

记 l,r 落在 fl,fr 块，x 落在 fx，先算出 \sum\limits_{i=1}^{fx-1} s_{fr - 1,i} - s_{fl,i}

然后扫一遍两个边角块，算出有多少个数 \le x

接下来对于第 fx 个值域块，扫一遍其中的每个值，计算有多少个数满足条件，且当前未被计数，也就是不在边角块

接下来回到本问题

对时间轴分块的问题就不赘述了，唯一的问题就是 O(1) 查询两个点是否有祖辈关系

我们称最后一次重构前加入的点为旧点，新加入的点为新点

如果这两个点都是旧点，那么根据 dfs 序可以直接判断

如果两个点都是新点，相邻两次重构间只会有 O(n) 对这样的关系，可以在加入 x 点后不断往上跳，每次记下 x 的祖先中哪些是新点，只会跳 O(\sqrt n) 次

如果一个是旧点，一个是新点，唯一的情况就是旧点是新点的祖先，记录旧点往上跳到的第一个新点，如果这两个点存在祖辈关系，那么这对点也存在祖辈关系

最后提个小事：你会发现 O(n) 重构的前提是你有排序后的数组，这个可以每次归并来维护

似乎是因为常数太大，这个理论复杂度比较优秀的算法成功拿下次劣解

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_set>
#include <vector>
#define ll long long
using namespace std;

struct range_rank_query{
    int n;
    int a[100005];
    struct num{
        int id,val;
    }b[100005];//从小到大排序 
    int s[350][350];
    #define S 317
    #define from(x) ((x - 1) / S + 1)
    #define L(x) (x * S - S + 1)
    #define R(x) (x * S)
    void init(){
        memset(s,0,sizeof(s));
        for(int i = 1;i <= n;i++) s[from(b[i].id)][from(i)]++;
        for(int i = 1;i <= from(n);i++){
            for(int j = 1;j <= from(n);j++){
                s[i][j] += s[i - 1][j];
            }
        }
    }
    int slv(int r,int v){
        int x = 0;
        for(int i = 17;i >= 0;i--) if(x + (1 << i) <= n && b[x + (1 << i)].val <= v) x += 1 << i;
        int fr = from(r),fx = from(x),ans = 0;
        for(int i = 1;i <= fx - 1;i++) ans += s[fr - 1][i];
        for(int i = L(fr);i <= r;i++) ans += a[i] <= v;
        for(int i = L(fx);i <= x;i++) ans += from(b[i].id) < fr;
        return ans;
    }
    int query(int l,int r,int x) {return (r - l + 1) - (slv(r,x) - slv(l - 1,x));}
}DS;
int n,m;
int a[100005];

int ecnt;
int head[200005];
struct eg{
    int to,nxt;
}edge[200005];

void make(int u,int v){
    edge[++ecnt].to = v;
    edge[ecnt].nxt = head[u];
    head[u] = ecnt;
}

int cnt,f[100005],dfn[100005],siz[100005],tag[100005],cg[100005],tp[100005];

void dfs(int now,int fa){
    dfn[now] = ++cnt;
    f[now] = fa;
    siz[now] = 1;
    for(int i = head[now];i;i = edge[i].nxt){
        if(edge[i].to == fa) continue;
        dfs(edge[i].to,now);
        siz[now] += siz[edge[i].to];
    }
}

struct num{
    int id,val;
}b[100005],c[100005],d[100005];

bool cmp(num a,num b){
    return a.val < b.val;
}

struct opt{
    int id,w,val;
};
vector <opt> Q;
unordered_set <ll> anc;

int solve(int u,int x){
    int ans = DS.query(dfn[u],dfn[u] + siz[u] - 1,x);
    for(int i = 0;i < Q.size();i++){
        int v = Q[i].id;
        //u 为 v 的祖先 
        if(tag[u] && tag[v]){
            if(dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + siz[u] - 1 && Q[i].w > x) ans += Q[i].val;
        }else if(tag[u] && !tag[v]){
            v = tp[v];
            if(dfn[u] <= dfn[v] && dfn[v] <= dfn[u] + siz[u] - 1 && Q[i].w > x) ans += Q[i].val;
        }else if(!tag[u] && !tag[v]){
            if(anc.count((ll)u * 200000 + v) && Q[i].w > x) ans += Q[i].val;
        }
    }
    return ans;
}

void modify(int u,int x){
    cg[u] = 0;
    Q.push_back({u,a[u],-1});
    Q.push_back({u,x,1});
    a[u] = x;
}

void add(int u,int x){
    ++n;
    f[n] = u;
    make(u,n);
    if(tag[u]) tp[n] = u;
    else tp[n] = tp[u];
    a[n] = x;
    b[n] = {n,x};
    Q.push_back({n,x,1});
    int v = n;
    while(!tag[v]){
        anc.insert((ll)v * 200000 + n);
        v = f[v];
    }
}

void rebuild(){
    int l1 = 0,l2 = 0,l = 0;
    for(int i = 1;i <= n;i++){
        if(cg[b[i].id]) c[++l1] = b[i];
        else d[++l2] = {b[i].id,a[b[i].id]};
    }
    sort(d + 1,d + l2 + 1,cmp);
    int i = 1,j = 1;
    while(i <= l1 && j <= l2){
        if(c[i].val < d[j].val){
            b[++l] = c[i++];
        }else{
            b[++l] = d[j++];
        }
    }
    while(i <= l1) b[++l] = c[i++];
    while(j <= l2) b[++l] = d[j++];
    cnt = 0;
    dfs(1,0);
    DS.n = n;
    for(int i = 1;i <= n;i++){
        DS.a[dfn[i]] = a[i];
        DS.b[i].val = b[i].val;
        DS.b[i].id = dfn[b[i].id];
    }
    DS.init();
    Q.clear();
    anc.clear();
    for(int i = 1;i <= n;i++){
        tp[i] = 0;
        tag[i] = cg[i] = 1;
    }
}

int main(){
    scanf("%d",&n);
    for(int i = 1;i < n;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        make(u,v);make(v,u);
    }
    for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
    for(int i = 1;i <= n;i++) b[i] = {i,a[i]};
    dfs(1,0);
    sort(b + 1,b + n + 1,cmp);
    DS.n = n;
    for(int i = 1;i <= n;i++){
        DS.a[dfn[i]] = a[i];
        DS.b[i].val = b[i].val;
        DS.b[i].id = dfn[b[i].id];
    }
    DS.init();
    for(int i = 1;i <= n;i++) tag[i] = 1;
    for(int i = 1;i <= n;i++) cg[i] = 1;
    scanf("%d",&m);
    int op,u,x,last = 0;
    for(int i = 1;i <= m;i++){
        scanf("%d%d%d",&op,&u,&x);
        u ^= last;x ^= last;
        if(op == 0){
            last = solve(u,x);
            printf("%d\n",last);
        }else if(op == 1){
            modify(u,x);
        }else{
            add(u,x);
        }
        if(Q.size() == 300) rebuild();
    }
    return 0;
}