义乌中学暑假集训 2021.07.10 D

yzxoi

发布于 2022-09-19 13:30:36

3240

发布于 2022-09-19 13:30:36

文章被收录于专栏：OI

义乌中学暑假集训 2021.07.10 D

Description

给定一棵 n 个节点的树，有 m 个询问，每次给定 l,r，查询若只保留点编号在 [l,r] 的点，边编号在 [l,r] 的边，有多少个连通块。

此时点 a 与点 b 连通当且仅当 l\leq a,b\leq r，且 a,b 在树上的简单路径中所有的点与边的编号都在 [l,r] 之间。

1\leq n,m\leq 10^6。

Solution

考虑连通块个数=点数-边数。

而点数 =r-l+1 是确定的，那么只需要考虑如何维护边数即可。

那么如何判断是否是有用的边？

其实就等价于对于边 i，满足 l\leq i\leq r，并且 i 连接的两个点 x,y，满足 l\leq x,y\leq r。

也就是说，对于边 i，需要满足 l\leq \min(i,x,y)\leq \max(i,x,y)\leq r。

然后这题就成了二维数点问题。

可以先把询问离线。

按照 r 从小到大，依次加入点与边。

然后用树状数组维护即可。

Code

#include<bits/stdc++.h>
#define I inline
#define W while
#define RI register int 
#define Cn const
#define CI Cn int& 
#define gc getchar
#define pc putchar
#define LL long long
using namespace std;
I void read(int& x){RI f=1;char c=gc();x=0;W(!('0'<=c&&c<='9')) f=c^'-'?f:-1,c=gc();W('0'<=c&&c<='9') x=x*10+(c-'0'),c=gc();x*=f;}
I void write(RI x){x<0&&(pc('-'),x=-x),x>=10&&(write(x/10),0),pc(x%10+'0');}
Cn int N=1e6+10;
int n,m,Ans[N];
struct Edge{int x,y;}e[N];
struct Que{int x,y,id;}q[N];
I bool cmp(Cn Edge& x,Cn Edge& y){return x.x>y.x;}
I bool cmp2(Cn Que& x,Cn Que& y){return x.x>y.x;}
class TreeArray{
    private:
        int c[N];
        #define lowbit(x) (x&(-x))
    public:
        I void U(CI x,CI y){RI i;for(i=x;i<=n;i+=lowbit(i)) c[i]+=y;}
        I int Q(CI x){RI i,S=0;for(i=x;i;i-=lowbit(i)) S+=c[i];return S;}
}T;
int main(){
    RI i,j,l,r;for(read(n),read(m),i=1;i<n;i++) read(l),read(r),e[i]=(Edge){min(min(l,r),i),max(max(l,r),i)};
    for(i=1;i<=m;i++) read(q[i].x),read(q[i].y),q[i].id=i;
    for(j=1,sort(e+1,e+n,cmp),sort(q+1,q+m+1,cmp2),i=1;i<=m;i++){
        W(j<n&&e[j].x>=q[i].x) T.U(e[j].y,1),j++;
        Ans[q[i].id]=q[i].y-q[i].x+1-T.Q(q[i].y);
    }for(i=1;i<=m;i++) write(Ans[i]),pc('\n');
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-07-22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

max