义乌中学暑假集训 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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇