飘雪圣域 [树状数组(二维偏序)]

$飘雪圣域$

---

$color{red}{正解部分}$

$首先要知道:$
若给定一个区间 $[l, r]$, 设一条边的小端点为 $u$, 大端点为 $v$,
满足条件 $l le u and v le r$ 的边数为 $num$, 则联通块数量为 $r-l+1-num$ .

$现在的问题就是:$
给出若干区间, 如何去快速地去求出每个区间对应的 $num$ .

发现这是个 二维偏序 问题, 于是

• 对询问区间按 右端点 从大到小 排序, 边按 大端点 从大到小 排序, 保证 $v le r$ 的偏序 .
• 使用 树状数组 维护 $l le u$ 的偏序 .

---

$color{red}{实现部分}$

先将所有边以左端点为下标加入 树状数组,
对从大到小排好序的询问 逐一处理, 不断地将 $v > r$ 的区间从 树状数组 中删掉,
此时 树状数组 中的所有区间的 $v$ 全部都是 $le r$ 的, 于是只需要计算出 $u geq l$ 的区间个数,
为 $tot- (u le l-1区间个数)$ , 即 $Query(N) - Query(l-1)$ .

#include<bits/stdc++.h>
#define reg register

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 200005;

int N;
int Q_;
int Ans[maxn];

struct EDGE{ int u, v; } E[maxn];

struct Que{ int l, r, id; } que[maxn];

struct Bit_Tree{
        int v[maxn];
        void Add(int k, int x){ while(k <= N) v[k] += x, k += k&-k; }
        int Query(int k){ int s = 0; while(k >= 1) s += v[k], k -= k&-k; return s; }
} bit_t;

bool cmp_EDGE(EDGE a, EDGE b){ return a.v > b.v; }

bool cmp_Que(Que a, Que b){ return a.r > b.r; }

int main(){
        N = read(), Q_ = read();
        for(reg int i = 1; i < N; i ++){
                E[i].u = read(), E[i].v = read();
                if(E[i].u > E[i].v) std::swap(E[i].u, E[i].v);
        }
        for(reg int i = 1; i <= Q_; i ++) que[i].l = read(), que[i].r = read(), que[i].id = i;
        std::sort(que+1, que+Q_+1, cmp_Que), std::sort(E+1, E+N, cmp_EDGE);
        for(reg int i = 1; i < N; i ++) bit_t.Add(E[i].u, 1);
        int t = 1;
        for(reg int i = 1; i <= Q_; i ++){
                while(t <= N && E[t].v > que[i].r) bit_t.Add(E[t ++].u, -1);
                int num = bit_t.Query(N) - bit_t.Query(que[i].l-1);
                Ans[que[i].id] = que[i].r-que[i].l+1 - num;
        }
        for(reg int i = 1; i <= Q_; i ++) printf("%d
", Ans[i]);
        return 0;
}