#3985. 飘雪圣域(icekingdom)

news/2024/4/18 9:49:10

题目描述
IcePrincess_1968 和 IcePrince_1968 长大了,他们开始协助国王 IceKing_1968 管理国内事物。

IcePrincess_1968 和 IcePrince_1968 住在一个宁静悠远的王国:IceKingdom —— 飘雪圣域。飘雪圣域有 n 个城镇,编号 1,2,3…n。有些城镇之间有道路,且满足任意两点之间有且仅有一条路径。飘雪圣域风景优美,但气候并不是太好。根据 IcePrince_1968 的气候探测仪,将来会发生 q 场暴风雪。每场暴风雪可以用两个整数 li,ri 刻画,表示这场暴风雪之后,只有编号属于[li,ri]的城市没有受到暴风雪的影响。

在暴风雪的影响下迅速确定王国的农业生产方案是非常重要的事情。IceKing_1968 认为,一个农业生产地域应该是一个极大连通块,满足每个节点都没有被暴风雪影响。这里极大连通块的定义是:不存在一个不属于该点集的未被暴风雪影响的点与该连通块连通。

IcePrincess_1968 要负责算出每次暴风雪后,王国能拥有多少个农业生产地域。注意这里每次暴风雪是独立的,即每次暴风雪过后,直到每个城镇重新焕发生机,下一次暴风雪才会到来。

正如上文所述,IcePrincess_1968 擅长文学但不擅长计算机,于是请你帮忙。

输入格式
第一行包含两个正整数 n,q,表示 IceKingdom 的城镇个数和暴风雪次数。

第2至第 n 行,每行两个正整数 x,y,表示城镇 x 和城镇 y 之间有一条道路。

第n+1 至第 n+q 行,每行两个正整数 li,ri,描述一场暴风雪,含义如题面所述。

输出格式
输出文件共有 q 行,第 i 行表示在第 i 场暴风雪之后农业生产地域的个数。

样例
样例输入
4 3
1 2
2 3
2 4
1 2
1 3
3 4
样例输出
1
1
2
数据范围与提示
【输入输出样例 1 解释】

第一次询问,只有(1,2)一个连通块。

第二次询问,只有(1,2,3)一个连通块。

第三次询问,有 3 和 4 两个连通块。

【输入输出样例 2】

见选手目录下的icekingdom/icekingdom2.in 和icekingdom/icekingdom2.ans。

【数据规模和约定】

对于30%的数据:n<=100,q<=100;

对于50%的数据:n<=2,000,q<=2,000;

对于100%的数据:n<=200,000,q<=200,000,对于所有的暴风雪,li<=ri。

来源
noip2018模拟-南外
题解:
不知为何,可能在洞穴探测的影响下,我成功的跑偏,走上了一条不归路
首先,给出一个性质:
树上两个连通块间有且只有一条连边!!
所以我们可以根据边的个数来判断有几个连通块!!!
这样就自然地想到离线。
orz

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 200005
using namespace std;
int n,q;
struct node
{int x,y;
}bian[N];int c[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int val){for(;x<=n;x+=lowbit(x))c[x]+=val;
}struct Ask
{int l,r,i;
}ask[N];
inline int get(int x){int sum=0;for(;x;x-=lowbit(x))sum+=c[x];return sum;
}
int ans[N];
bool cmp(node a,node b){return a.y<b.y;}
bool cm(Ask a,Ask b){return a.r<b.r;}
int main()
{cin>>n>>q;for(int i=1;i<n;++i){cin>>bian[i].x>>bian[i].y;if(bian[i].x>bian[i].y)swap(bian[i].x,bian[i].y);}sort(bian+1,bian+n,cmp);for(int i=1;i<=q;++i){cin>>ask[i].l>>ask[i].r;ask[i].i=i;}sort(ask+1,ask+1+q,cm);for(int i=1,j=1;i<=q;++i){while(bian[j].y<=ask[i].r&&j<n){add(bian[j].x,1);++j;}ans[ask[i].i]=ask[i].r-ask[i].l+1-get(ask[i].r)+get(ask[i].l-1);}for(int i=1;i<=q;++i)cout<<ans[i]<<endl;return 0;
}

http://www.ppmy.cn/news/600885.html

相关文章

青云诀2显示登录服务器超时,青云诀2游戏突然显示数据包损坏怎么办 解决方案分享...

青云诀2游戏突然显示数据包损坏怎么办 解决方案分享。青云诀2是一款非常好玩的游戏&#xff0c;许多玩家被其优秀的内容和有趣的玩法所吸引。但是近日有小伙伴反应青云诀2游戏突然显示数据包损坏&#xff0c;小编这里整理了一些青云诀2游戏突然显示数据包损坏的原因和方法&…

赤月传说2mysql_赤月传说2快速升级全攻略

2016年6月2日赤月传说2快速升级全攻略! 进入到赤月传说2的新玩家&#xff0c;不要想着装备、PK这些不现实的事儿&#xff0c;当务之急是提升角色的等级&#xff0c;只有等级上去了你才能穿戴强力的装备&#xff0c;在PK中占居上风。同时新开服的冲级奖励也是富到流油&#xff0…

大话西游2在线人工服务器,大话西游2服务器地址列表

楼主 字太多了 我给不了你 你把QQ给我 我发给你 先给你部分 1 1 1 东海渔村 218.107.63.60 34688 2 220.181.30.10 34688 1 222.28.155.130 34688 3 3 欢迎进入大话西游II 1 3 1 小窗幽记 220.181.28.160 22588 1 202.108.8.22 22588 2 222.28.155.130 22588 3 3 欢迎进入大话西…

OpenGL glBegin()函数学习

接此&#xff0c; OpenGL视口学习_bcbobo21cn的博客-CSDN博客 把VC6生成的代码中的材质部分注释掉&#xff1b;然后程序运行起来是如下&#xff1b; 把原先GLCube函数的代码替换为如下&#xff1b;下面代码是绘制线框&#xff0c;没有面&#xff1b;它是给出顶点坐标和顶点序…

华为状态栏图标替换_华为手机状态栏图标都是干嘛用的?华为手机图标含义大集合...

华为手机那么多图标都是什么意思呢&#xff1f;都有什么用&#xff1f;哪里才能打开关闭&#xff1f;相信很多小伙伴会有这样的疑问&#xff0c;今天带大家走进华为手机图标大集合。看看怎么用吧。 看第一行大家都知道的&#xff0c;分别是WIFI网络、蓝牙、数据(这个手机没放卡…

鸿蒙系统是手机系统还是电脑系统,鸿蒙系统能兼容手机电脑和智能设备,这是怎样实现的?...

鸿蒙系统它本身支持两种模式&#xff0c;一种是手机模式&#xff0c;一种是电脑模式。 就比如现在华为、荣耀的高端手机&#xff0c;单独使用就是手机模式&#xff0c;通过HDMI线连接显示器或者电视屏幕的时候&#xff0c;它就变成了一台电脑。再配合蓝牙或者无线鼠标和键盘&am…

华为电脑Linux版送u盘吗,没有华为电脑不要紧,一个U盘让你用上国产操作系统!...

目前华为笔记本已经搭载了国产深度deepin操作系统&#xff0c;很多朋友问我要不要买一台来体验一下&#xff0c;我告诉大家其实手里没有华为笔记本不要紧&#xff0c;只要你手里有一个U盘就可以体验到国产deepin操作系统给你带来的震撼&#xff0c;安装步骤如下。 首先我们要准…

电脑浏览android,直接在电脑上浏览操作安卓手机

直接在电脑上浏览操作安卓手机 2020-10-30 19:46:18 15点赞 168收藏 4评论 前些时间我们介绍了坚果手机 R2 和 TNT系统。 这个方案可以让我们将手机插上屏幕,在办公桌前「假装」在使用一台桌面电脑。 虽然,火箭君知道华为等手机已经可以在自家设备中实现:手机投射到笔记本上…

华为手机的计算机删除了怎么恢复,技巧 | 如何让手机秒变电脑?误删文件怎么恢复?...

全新的人工智能手机华为Mate 10上市后被视为年度最佳旗舰手机的有力竞争者&#xff0c;其原因除了全球首颗移动AI芯片外&#xff0c;与华为Mate 10所创造颠覆式的办公体验有着密切关系。华为Mate 10自主研发的电脑模式可以通过数据线将手机画面投射到大屏上&#xff0c;大大简化…

游戏服务器的架构演进、多进程架构通信

系列文章目录 文章目录 系列文章目录前言一、游戏服务器特征二、游戏服务器架构要素三、服务器演化进程1.卡牌等休闲游戏弱交互游戏2.长链接游戏服务器1.第一代网游服务器&#xff08;单线程无阻塞&#xff09;2.第二代网游服务器&#xff08;分区分服&#xff09;3.第三代网游…

华为云计算机系统是什么,你了解什么是华为云电脑吗,它有什么用

随着轻薄笔记本以及平板电脑的普及,对于商务人士的每次出差的“旅行重量”得到了不少的减轻,但笔记本电脑或者平板这样的设备还是必不可少。随着手机性能越来越强大,不少手机都具备了PC模式,手机连接上底座提供视频输出功能,能实现类似电脑的桌面,能实现简单的PPT演示和简…

网络游戏服务器源文件消除,网络游戏服务器端源程序

网络游戏服务器端源程序 内容精选 换一换 #服务端技术进阶( 四)一篇文读懂分布式系统本质&#xff1a;高吞吐、高可用、可扩展 ##承载量是分布式系统存在的原因   当一个互联网业务获得大众欢迎的时候&#xff0c;最显著碰到的技术问题&#xff0c;就是服务器非常繁忙。当每天…

连接游戏服务器ip不稳定怎么办,连接游戏服务器ip

连接游戏服务器ip 内容精选 换一换 在本章节中,您将会把游戏应用部署到CCE云容器引擎中,您需要执行以下操作:创建集群:集群是运行应用的逻辑分组,包含一组云服务器资源,每个节点对应一台云服务器。首次使用CCE时,您需要创建一个初始集群,并添加一个节点。部署mysql数据…

游戏服务器性能报告,游戏服务器测试报告

游戏服务器测试报告 内容精选 换一换 传统的HPC使用中存在如下问题&#xff1a;投资成本高&#xff0c;扩容部署复杂&#xff0c;重复利用已有投资十分困难。应用复杂&#xff0c;资源预测困难&#xff0c;灵活性差&#xff0c;亟待提升效率。效率低下导致决策缓慢&#xff0c;…

1块钱30分钟利用华为云服务器配置一台云电脑并搭建一个简易网站(步步截图较详细)

1块钱30分钟利用华为云服务器配置一台云电脑并搭建一个简易网站&#xff08;步步截图较详细&#xff09; 在这篇文章你将会接触到&#xff1a;熟悉华为云的云产品对应价位以及如何配置好适合自己的情况的产品和基本产品操作流程。步步截图的服务器云电脑搭建&#xff0c;利用云…

50台电脑文件服务器,50台电脑云桌面用什么服务器

50台电脑云桌面用什么服务器 内容精选 换一换 在配置完问答数据、词典、数据标注和模型训练后&#xff0c;您可以通过对话体验或者API的方式直接调用对话机器人&#xff0c;为您的客户提供问答服务。问答机器人面向客户的问答界面需要您根据自己业务需求进行开发&#xff0c;前…

手把手教您快速运行Unity华为游戏(GameService)

背景介绍 华为Game Service SDK提供了游戏应用自升级检测、获取玩家信息、游戏浮标、防沉迷、成就、排行榜等多个能力&#xff0c;Unity为了方便全球开发者快速集成该些能力并发布华为渠道&#xff0c;提供了HMS Core App Services SDK和demo。 本帖子先行试水&#xff0c;试…

华为游戏显示加载服务器,网狐游戏服务器加载空白

网狐游戏服务器加载空白 内容精选 换一换 如果遇到电脑浏览器或手机浏览器提示证书不可信的问题&#xff0c;请确认您所购买的数字证书品牌和提示证书不可信的终端类型。部分品牌的数字证书在某些终端上是不被支持的&#xff0c;请参考该品牌的数字证书的官网中的相关介绍。目前…

华为荣耀电脑桌面计算机的符号是哪个,别浪费了你的华为手机,这个功能很多人都不知道,一秒变电脑...

原标题&#xff1a;别浪费了你的华为手机&#xff0c;这个功能很多人都不知道&#xff0c;一秒变电脑 都知道华为手机主打的是功能&#xff0c;那么大家知道华为手机的功能有哪些吗&#xff1f;如果不仔细摸索的话&#xff0c;还真的不知道华为到底有多少隐藏的功能呢。小编最近…

华为正式推出快游戏,Cocos 率先支持

华为快游戏正式发布&#xff0c;进一步推动了小游戏生态的发展&#xff01; 2018 年 12 月 25 日&#xff0c;华为宣布其 2018 年智能手机出货量成功将突破两亿台&#xff0c;为 2018 年的表现画上了一个辉煌的句号。 庞大的出货量背后是庞大的用户数量&#xff0c;今日&…