义乌中学暑假集训 2021.07.10 D
Description
给定一棵 n 个节点的树，有 m 个询问，每次给定 l,r，查询若只保留点编号在 [l,r] 的点，边编号在 [l,r] 的边，有多少个连通块。
此时点 a 与点 b 连通当且仅当 lleq a,bleq r，且 a,b 在树上的简单路径中所有的点与边的编号都在 [l,r] 之间。
1leq n,mleq 10^6。
Solution
考虑连通块个数=点数-边数。
而点数 =r-l 1 是确定的，那么只需要考虑如何维护边数即可。
那么如何判断是否是有用的边？
其实就等价于对于边 i，满足 lleq ileq r，并且 i 连接的两个点 x,y，满足 lleq x,yleq r。
也就是说，对于边 i，需要满足 lleq min(i,x,y)leq max(i,x,y)leq r。
然后这题就成了二维数点问题。
可以先把询问离线。
按照 r 从小到大，依次加入点与边。
然后用树状数组维护即可。
Code
代码语言：javascript复制#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 '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;
}
