飘雪圣域


<mstyle mathcolor="red"> </mstyle> \color{red}{正解部分}

: 首先要知道: :
若给定一个区间 [ l , r ] [l, r] [l,r], 设一条边的小端点为 u u u, 大端点为 v v v,
满足条件 l u <mtext>   </mtext> a n d <mtext>   </mtext> v r l \le u\ and\ v \le r lu and vr 的边数为 n u m num num, 则联通块数量为 r l + 1 n u m r-l+1-num rl+1num .

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

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

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

<mstyle mathcolor="red"> </mstyle> \color{red}{实现部分}

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

#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\n", Ans[i]);
        return 0;
}