CF1899 G. Unusual Entertainment [二维数点/二维偏序]

传送门:CF

[前题提要]:没什么好说的,区域赛爆炸之后发愤加训思维题.秒了div3 A~F的脑筋急转弯,然后被G卡了,树剖dfs序的想法已经想到了,题目也已经化简为两个线段是否存在一个合法位置了.但是MD不会二维数点,用一个树剖+扫描线搞来搞去最后还是Tle.果然如下图所说:科技还是十分重要的.

在这里插入图片描述


首先读完题意.不难想到本题应该是一道数据结构题.因为对于 x x x的儿子节点我们是可以直接使用 d f s dfs dfs序或者树链剖分直接维护出来编号的.所以对于我们的每一个询问,相当于求出区间 [ l , r ] [l,r] [l,r]是否存在一个点,它的 d f s dfs dfs序在x的子孙节点中.

设我们维护出来的 x x x的子孙节点(包括他自己)区间为 [ L x , R x ] [L_x,R_x] [Lx,Rx](这里需要提一句的是对于一个节点的所有儿子来说,它的 d f s dfs dfs序一定是连续的,具体证明此处略).设一个点 u u u d f s dfs dfs,为 d f n ( u ) dfn(u) dfn(u).那么现在这道题就是问是否存在一个点在序列中的位置为 k ∈ [ l , r ] k\in[l,r] k[l,r],然后 d f n ( k ) ∈ [ L x , R x ] dfn(k)\in[L_x,R_x] dfn(k)[Lx,Rx].

额.当时我就卡在了这个维护上.但其实这是一个很模板的二维偏序(二维数点)问题.模板题指路
我们将 x ∈ [ l , r ] x\in[l,r] x[l,r]看成横坐标,将所有 d f n ( x ) dfn(x) dfn(x)看成纵坐标.那么就是问你是否存在一个点 ( x , d f n ( x ) ) (x,dfn(x)) (x,dfn(x))在一个矩形区域内.这是一个很典型的二维数点问题.考虑将所有的询问矩形区域使用二维前缀和的思想进行化解,然后离线下来一个一个枚举,在枚举的过程中,将所有的点逐个加入到我们的树状数组中.只要保证所有点的横坐标小于当前询问区域,我们就可以将二维询问问题转化为一维询问,只要用树状数组维护一下就行了.


下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 200010
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
inline int lowbit(int x) {
	return x&(~x+1);
}
int tree[maxn];int n,q;
void Add(int pos,int val) {
	while(pos<=n) {
		tree[pos]+=val;
		pos+=lowbit(pos);
	}
}
int Query(int pos) {
	int ans=0;
	while(pos) {
		ans+=tree[pos];
		pos-=lowbit(pos);
	}
	return ans;
}
vector<int>edge[maxn];
int in[maxn],out[maxn];int tot=0;
void dfs(int u,int per_u) {
	in[u]=++tot;
	for(auto v:edge[u]) {
		if(v==per_u) continue;
		dfs(v,u);
	}
	out[u]=tot;
}
int Ans[maxn];int p[maxn];
int main() {
	int T=read();
	while(T--) {
		n=read();q=read();
		for(int i=1;i<n;i++) {
			int u=read();int v=read();
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++) {
			p[i]=read();p[i]=in[p[i]];
		}
		vector<tuple<int,int,int,int> >Q;
		for(int i=1;i<=q;i++) {
			int l=read();int r=read();int x=read();
			Q.push_back({l-1,in[x]-1,i,1});
			Q.push_back({l-1,out[x],i,-1});
			Q.push_back({r,in[x]-1,i,-1});
			Q.push_back({r,out[x],i,1});
		}
		sort(Q.begin(),Q.end());
		int cur=0;
		for(auto [a,b,id,val]:Q) {
			while(cur+1<=a) {
				cur++;
				Add(p[cur],1);
			}
			Ans[id]+=val*Query(b);
		}
		for(int i=1;i<=q;i++) {
			cout<<(Ans[i]>0?"YES":"NO")<<endl;
		}
		tot=0;
		for(int i=1;i<=n;i++) {
			tree[i]=0;
			edge[i].clear();in[i]=out[i]=0;
		}
		for(int i=1;i<=q;i++) {
			Ans[i]=0;
		}
	}
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162775.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Netty传输object并解决粘包拆包问题

⭐️ 前言 大家好&#xff0c;笔者之前写过一篇文章&#xff0c;《Netty中粘包拆包问题解决探讨》&#xff0c;就Netty粘包拆包问题及其解决方案进行了探讨&#xff0c;本文算是这篇博客的延续。探讨netty传输object的问题。 本文将netty结合java序列化来传输object并解决粘包…

3dMax2024新功能和工作流增强功能速览

3dMax2024新功能和工作流增强功能速览 Autodesk发布的3dMax2024引入了一系列新功能和工作流增强功能&#xff0c;如下所示&#xff1a; 更新的“指定控制器”卷展栏&#xff1a;这个现代化的功能为动画师提供了更高效的工作方式&#xff0c;简化了他们的动画流程。 布尔修饰符…

【DevOps】Git 图文详解(三):常用的 Git GUI

Git 图文详解&#xff08;三&#xff09;&#xff1a;常用的 Git GUI 1.SourceTree2.TortoiseGit3.VSCode 中的 Git 如果不想用命令行工具&#xff0c;完全可以安装一个 Git 的 GUI 工具&#xff0c;用的更简单、更舒服。不用记那么多命令了&#xff0c;极易上手&#xff0c;不…

二、ST-Link驱动的安装

1、灵动mm32单片机 (1)上海灵动微电子股份有限公司 (2)mm32单片机支持ST-Link下载程序。 2、ST-Link驱动的安装 (1)下载地址 ST-Link 官网下载地址 (2)点击获取软件下载ST-Link驱动。(需要登陆ST官网账户) (3)下载后解压&#xff0c;根据电脑位数安装 .exe 文件即可。 6…

若依前后端分离版,快速上手

哈喽~大家好&#xff0c;这篇来看看若依前后端分离版&#xff0c;快速上手&#xff08;肝了挺久的&#xff09;。 &#x1f947;个人主页&#xff1a;个人主页​​​​​ &#x1f948; 系列专栏&#xff1a;【Springboot和Vue全栈开发】…

Javaweb之Vue指令案例的详细解析

2.3.5 案例 需求&#xff1a; 如上图所示&#xff0c;我们提供好了数据模型&#xff0c;users是数组集合&#xff0c;提供了多个用户信息。然后我们需要将数据以表格的形式&#xff0c;展示到页面上&#xff0c;其中&#xff0c;性别需要转换成中文男女&#xff0c;等级需要…

QTableWidget——表格的合并与拆分

一、整体思路 表格的操作使用QTableView::setSpan可以实现表格的行和列的合并 表格拆分没有对应的处理函数 主要思路&#xff1a;对表格的属性、内容、拆分与合并的参数进行存储&#xff0c;在进行拆分时对表格内容进行重新创建&#xff08;不考虑效率问题&#xff09; 二、效…

MyBatis使用注解操作及XML操作

文章目录 1. 注解操作1.1 打印日志1.2 参数传递1.3 增&#xff08;Insert&#xff09;注意1&#xff1a;重命名注意2&#xff1a;返回主键 1.4 删&#xff08;Delete&#xff09;1.5 改&#xff08;Update&#xff09;1.6 查&#xff08;Select&#xff09;1. 配置&#xff0c;…

Windows10下Tomcat8.5安装教程

文章目录 1.首先查看是否安装JDK。2.下载3.解压到指定目录&#xff08;安装路径&#xff09;4.启动Tomcat5.常见问题5.1.如果出现报错或者一闪而过5.2.Tomcat乱码 1.首先查看是否安装JDK。 CMD窗口输入命令 java -version 2.下载 历史版本下载地址&#xff1a;https://archi…

量化交易:传统小市值策略 VS AI市值策略

在BigQuant平台上可以快速开发股票传统策略和股票AI策略&#xff0c;今天拿市值因子来练手&#xff0c;看看两个策略在2015-01-01到2016-12-31这两年时间各自的收益风险情形。 市值因子是国内股票市场能够带来超额收益的alpha因子&#xff0c;已经被验证为长期有效的因子&…

向pycdc项目提的一个pr

向pycdc项目提的一个pr 前言 pycdc这个项目&#xff0c;我之前一直有在关注&#xff0c;之前使用他反编译python3.10项目&#xff0c;之前使用的 uncompyle6无法反编译pyhton3.10生成的pyc文件&#xff0c;但是pycdc可以&#xff0c;但是反编译效果感觉不如uncompyle6。但是版…

Appium混合页面点击方法tap的使用

原生应用开发&#xff0c;是在Android、IOS等移动平台上利用官方提供的开发语言、开发类库、开发工具进行App开发&#xff1b;HTML5&#xff08;h5&#xff09;应用开发&#xff0c;是利用Web技术进行的App开发。目前&#xff0c;市面上很多app都是原生和h5混合开发&#xff0c…

SELinux

目录 1.概述 1.1.概念 1.2.作用 1.3. SELinux与传统的权限区别 2. SELinux工作原理 2.1.名词解释 2.1.1.主体(Subject) 2.1.2.目标(Object) 2.1.3.策略(Policy) 2.1.4.安全上下文(Security Context) 2.2.文件安全.上下文查看 2.2.1.命令: 2.2.2.分析 3. **SELinu…

Flutter 3.16 中带来的更新

Flutter 3.16 中带来的更新 目 录 1. 概述2. 框架更新2.1 Material 3 成为新默认2.2 支持 Material 3 动画2.3 TextScaler2.4 SelectionArea 更新2.5 MatrixTransition 动画2.6 滚动更新2.7 在编辑菜单中添加附加选项2.8 PaintPattern 添加到 flutter_test 3. 引擎更新&#xf…

BUUCTF 被偷走的文件 1

BUUCTF:https://buuoj.cn/challenges 题目描述&#xff1a; 一黑客入侵了某公司盗取了重要的机密文件&#xff0c;还好管理员记录了文件被盗走时的流量&#xff0c;请分析该流量&#xff0c;分析出该黑客盗走了什么文件。 密文&#xff1a; 下载附件&#xff0c;解压得到一个…

QT专栏1 -Qt安装教程

#本文时间2023年11月18日&#xff0c;Qt 6.6# Qt 安装简要说明&#xff1a; Qt有两个版本一个是商业版本&#xff08;收费&#xff09;&#xff0c;另一个是开源版本&#xff08;免费&#xff09;&#xff1b; 打开安装程序时&#xff0c;通过判断账号是否有公司&#xff0c;安…

【Linux系统化学习】进程的父子关系 | fork 进程

个人主页点击直达&#xff1a;小白不是程序媛 Linux专栏&#xff1a;Linux系统化学习 目录 前言&#xff1a; 父子进程 父子进程的引入 查看父子进程 查询进程的动态目录 更改进程的工作目录 fork创建进程 fork的引入 fork的使用 fork的原理 fork如何实现的&#…

搜索引擎ElasticSearch分布式搜索和分析引擎学习,SpringBoot整合ES个人心得

ElasticSearch Elasticsearch是一个基于Lucene的搜索服务器。它提供了一个分布式多用户能力的全文搜索引擎&#xff0c;基于RESTful web接口。Elasticsearch是用Java语言开发的&#xff0c;并作为Apache许可条款下的开放源码发布&#xff0c;是一种流行的企业级搜索引擎。Elas…

ajax,axios,fetch

文章目录 ajax工作原理ajax发请求四个步骤创建xmlhttprequest对象设置请求方式设置回调函数发送请求 自封装ajax axiosaxios 特性如何用配置拦截器fetch 三者区别 ajax 工作原理 Ajax的工作原理相当于在用户和服务器之间加了—个中间层(AJAX引擎)&#xff0c;使用户操作与服务…

MFC 常用控件

目录 一、控件的交互方式 二、CButton/CheckBox/RadioButton 三、EditControl 四、ListBox 五、ComBox 六、Progress/Timer 七、PictureController 八、ListControl 九、Tree 一、控件的交互方式 得到控件的类的对象&#xff0c;就可以通过这个对象来操作类 CWnd* G…