当前位置： 首页 > news >正文

1080 F. Katya and Segments Sets 主席树

news 来源：原创 2023/6/7 4:56:48

题目链接：https://codeforces.com/contest/1080/problem/F

题意：有k个线段所属在n个集合中，每次询问a b x y，问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内

题解：按照每个线段的有区间排序，然后按照右区间建立主席树，每个节点保存该位置的最右左区间，然后查询的时候即为对应所有位置的最右左区间的最小值，看是否大于x

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
struct node1 {int l, r, id;bool operator <(const node1 &bb) const {return r < bb.r;}
}a[N];
struct node {int l, r;int val;
}tree[N * 22];
int n, m, k;
int b[N], len;
int root[N], tot;
int update(int pre, int l, int r, int pos, int val) {int cur = ++tot;tree[cur] = tree[pre];if(l == r) {//	cout << l << " -- " << val << endl;tree[cur].val = max(tree[cur].val, val);return cur;}int mid = (l + r) >> 1;if(pos <= mid) tree[cur].l = update(tree[pre].l, l, mid, pos, val);else tree[cur].r = update(tree[pre].r, mid + 1, r, pos, val);tree[cur].val = min(tree[tree[cur].l].val, tree[tree[cur].r].val);return cur; 
}
int query(int rt, int l, int r, int pl, int pr) {if(pl <= l && r <= pr) return tree[rt].val;int res = INF;int mid = (l + r) >> 1;if(pl <= mid)  res = min(res, query(tree[rt].l, l, mid, pl, pr));if(pr >= mid + 1) res = min(res, query(tree[rt].r, mid +1, r, pl, pr));return res; 
} 
string s[2];
int main() {s[0] = "yes";s[1] = "no";scanf("%d %d %d", &n, &m, &k);for(int i = 1; i <= k; i++) {scanf("%d %d %d", &a[i].l, &a[i].r, &a[i].id);b[i] = a[i].r;}sort(a + 1, a + 1 + k);sort(b + 1, b + 1 + k);for(int i = 1; i <= k; i++) {//	cout << a[i].id << " " << a[i].l <<endl;root[i] = update(root[i - 1], 1, n, a[i].id, a[i].l);}len = k;int pos;int l, r, x, y;while(m--) {scanf("%d %d %d %d", &l, &r, &x, &y);pos = upper_bound(b + 1, b + 1 + len, y) - b;pos--;//	cout << pos << endl; if(query(root[pos], 1, n, l, r) >= x) cout << "yes" << endl;;else cout << "no" << endl;;}return 0;
}

 

相关文章：

1080 F. Katya and Segments Sets 主席树

题目链接&#xff1a;https://codeforces.com/contest/1080/problem/F 题意&#xff1a;有k个线段所属在n个集合中&#xff0c;每次询问a b x y&#xff0c;问是否[a, b]的每个集合中都存在一个线段在[x, y]的范围内 题解&#xff1a;按照每个线段的有区间排序&#xff0c;然…...

编程日记 2023/6/7 4:56:48

Kattis - largesttriangle Largest Triangle 平面最大三角形面积

题目链接&#xff1a;https://vjudge.net/problem/Kattis-largesttriangle 题意&#xff1a;任意三点的最大三角形面积 题解&#xff1a;首先想到最大的面积应该出现在凸包上&#xff0c;然后就是枚举任意两点&#xff0c;能想到第三点是满足线性的&#xff0c;所以第三点线性…...

编程日记 2023/4/28 19:51:00

数据挖掘-k平均算法

/* 题目内容&#xff1a;实现k平均算法的代码&#xff0c;并且通过样例 代码&#xff1a; */ #include <bits/stdc.h> using namespace std; #define eps 1e-8 #define INF 0x3f3f3f3f const int N 1e6 10; int n, k; pair<double, double> a[N], b[N]; vector&l…...

编程日记 2023/5/29 3:40:27

初识matlab

简单的数学运算&#xff1a; 极限运算&#xff1a; limit(f,x,x0): 计算x→x0时函数f的极限。 举例&#xff1a; syms x y1(1x2*sin(x))^(2/x); y2((1x)^0.5-2)/(x^2-2*x-3); y3x^2*sin(1/x)/sqrt(2*x^2-1); f1limit(y1,0) f2limit(y2,3) f3limit(y3,inf…...

编程日记 2023/5/23 13:32:01

MATLAB学习知识整理 从入门到放弃

简介&#xff1a; Matlab: 美国MathWorks公司出品的商业数学软件。是一种高级技术计算语言和交互式环境。 主要用于&#xff1a; 算法开发 数据可视化 数据分析 数值计算 一、初识matlab 二、matlab数组运算与…...

编程日记 2023/5/18 3:00:47

matlab数组运算与数组化编程

matlab中的运算和操作主要是以数组为对象的&#xff0c; 数组又包括&#xff1a;数值数组、字符数组、元胞数组等。 一、数值数组的建立&#xff1a; 1. 直接输入法&#xff1a; 逗号&#xff1a;用来分开数组中的行元素。&#xff08;可用空格代替&#xff09; 分号&#…...

编程日记 2023/6/1 12:10:01

matlab程序设计

一、自定义函数 格式&#xff1a;函数句柄 (自变量列表)函数表达式 例1 定义函数&#xff0c;并计算f(x)在点x-2,1,2.5,3,5.2的值。 f(x)x.^23*x5 x[-2,1,2.5,3,5.2] y1f(x) 二、 m-文件函数&#xff08;子程序&#xff09; 格式&#xff1a;function [y1,y2]ff(x1,x…...

编程日记 2023/5/22 3:05:26

matlab数值计算

第一节 多项式运算 一、多项式的表示、求值、求根 1. 表示&#xff1a; matlab中把多项式表达成一个行向量&#xff0c;该向量中的元素是按多项式降幂排列的。 p[2,3,-1,4,5]表示多项式&#xff1a; 显示多项式的数学形式&#xff1a; p1poly2str(p,x) 如&…...

编程日记 2023/6/4 1:36:40

matlab图形功能

//...

编程日记 2023/5/29 3:19:10

python实现键盘输入多个值

Python 2里面读取输入的函数是raw_input()&#xff0c; Python 3的是input()&#xff0c;读入一个值后回车读取输入就退出了&#xff0c;想要一次读取多个输入&#xff0c;可以像下面这样&#xff1a; a, b raw_input().split()1 2a Out[224]: 1b Out[225]: 2 上面保存的是字…...

编程日记 2023/6/6 22:17:50

VS2019在win10下配置boost库

第一步&#xff1a;官网下下载&#xff1a;https://www.boost.org/users/history/version_1_73_0.html win10选择boost_1_73_0.zip 第二步&#xff1a;解压 第三步&#xff1a;编译 打开VS命令行 选择 已压缩好的boost_1_73_0文件夹 运行 bootstrap.bat 成功之后运行 刚…...

编程日记 2023/6/5 15:30:24

pthread_cond_wait()

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); 该函数第一个参数为条件变量指针&#xff0c;第二个为互斥量指针。该函数调用前&#xff0c;需本线程加锁互斥量&#xff0c;加锁状态的时间内函数完成线程加入等待队列操作 &#xff0c;线程进入等待前…...

编程日记 2023/5/24 23:50:29

pthread多线程学习

基于pthread学习 多线程编程...

编程日记 2023/6/7 4:14:41

线程私有数据

线程私有数据实现的主要思想是&#xff1a;在分配线程私有数据之前&#xff0c;创建与该数据相关联的健&#xff0c;这个键可以被进程中的所有线程使用&#xff0c;但每个线程把这个键与不同的线程私有数据地址进行关联&#xff0c;需要说明的是每个系统支持有限数量的线程特定…...

编程日记 2023/6/5 16:22:33

创建线程的几种方式

class A {int x; public:void f(int x, char c) { };int operator()(int N) { return 0; } }; void foo(int x){} int main() {A a;thread t1(a, 6); // 传递a的拷贝给子线程thread t2(ref(a), 6); //传递a的引用给子线程thread t3(move(a), 6); //a在主线程中将不再有效threa…...

编程日记 2023/5/19 17:27:20

c++11多线程学习

一.join和detach C中的thread对象通常来说表达了执行的线程&#xff08;thread of execution&#xff09;&#xff0c;这是一个操作系统或者平台的概念。 当thread::join()函数被调用后&#xff0c;调用它的线程会被block&#xff0c;直到线程的执行被完成。基本上&#xff0…...

编程日记 2023/6/7 4:11:32

Socket编程

C Socket 编程&#xff1a;https://blog.csdn.net/sinat_35866463/article/details/81019778 windows环境下用c实现socket编程&#xff1a;https://blog.csdn.net/xiaoquantouer/article/details/58001960 win7系统两台电脑之间利用Socket实现文件传输---C实现&#xff1a;ht…...

编程日记 2023/5/31 12:06:49

inet_pton()和inet_ntop()函数

https://blog.csdn.net/zyy617532750/article/details/58595700 1.把ip地址转化为用于网络传输的二进制数值 int inet_aton(const char *cp, struct in_addr *inp); inet_aton() 转换网络主机地址ip(如192.168.1.10)为二进制数值&#xff0c;并存储在struct in_addr结构中&a…...

编程日记 2023/5/5 16:40:02

C/C++内存泄漏及检测

“该死系统存在内存泄漏问题”&#xff0c;项目中由于各方面因素&#xff0c;总是有人抱怨存在内存泄漏&#xff0c;系统长时间运行之后&#xff0c;可用内存越来越少&#xff0c;甚至导致了某些服务失败。内存泄漏是最难发现的常见错误之一&#xff0c;因为除非用完内存或调用…...

编程日记 2023/5/22 1:29:22

八大设计模式原则

1.依赖倒置原则 高层模块不依赖底层模块&#xff0c;二者都应该依赖抽象 抽象不依赖实现细节&#xff0c;实现细节应该依赖于抽象 这一原则与下面的针对接口编程而不是针对实现编程是一个道理&#xff0c;我们设计一个程序&#xff0c;我们应该先想好我们想要抽象什么&#x…...

编程日记 2023/6/2 18:50:35

C++设计模式

管理变化&#xff0c; 提高复用 两种手段&#xff1a;分解 抽象 八大原则&#xff1a;https://blog.csdn.net/mmk27_word/article/details/108521903 重构技法&#xff1a; 静态 -> 动态 早绑定 -> 晚绑定 继承 -> 组合 编译时依赖 -> 运行时依赖 紧耦合 ->…...

编程日记 2023/5/31 19:22:45

LRU算法

#include <iostream> #include <list> #include <map> using namespace std; class LRU {struct node {int key, val;node(int k_ 0, int v_ 0) {key k_;val v_;}};public:int cap; // 大小map<int, list<node>::iterator> mp;list<node&…...

编程日记 2023/5/30 23:37:41

数据库事务四个特性

ACID特性 数据库管理系统中事务(transaction)的四个特性&#xff08;分析时根据首字母缩写依次解释&#xff09;&#xff1a;原子性&#xff08;Atomicity&#xff09;、一致性&#xff08;Consistency&#xff09;、隔离性&#xff08;Isolation&#xff09;、持久性&#xf…...

编程日记 2023/6/2 19:35:22

Git入门简介

本文简单介绍一下Git的使用&#xff0c;主要内容有下&#xff1a; Git基本介绍Git相较于SVN的优势Git使用流程及常用命令 Git基本介绍 Git是一款免费、开源的分布式版本控制系统&#xff0c;用于敏捷高效地处理任何或小或大的项目 —— [ 百度百科 ] GitHub&#xff1a;https…...

编程日记 2023/6/7 2:51:34

《移动App测试实战》读书笔记

总的来讲&#xff0c;这本书基本涵盖了移动App测试的方方面面&#xff0c;并结合各个专题做了简单讲解&#xff0c;对于扩展无线端测试的知识面有极大的好处&#xff0c;缺点是知识点点到为止&#xff0c;毕竟全书300多页的篇幅也不可能对知识点进行专题讲解。书中作者提到的一…...

编程日记 2023/6/6 20:00:23

http load介绍

前几天工作中要对项目的接口做简单压测&#xff0c;就使用了http load做了简单测试&#xff0c;下面介绍一下这款工具的使用说明。简介&#xff1a;http_load是基于linux平台的性能测试工具&#xff0c;它体积非常小&#xff0c;仅100KB。它以并行复用的方式运行&#xff0c;可…...

编程日记 2023/6/6 0:44:36

工具介绍：ITerm 2

今天介绍一款终端工具ITerm2&#xff0c;有了它&#xff0c;大大提供了我们的工作效率&#xff1b;官方地址&#xff1a;http://www.iterm2.com/ 颜控首选&#xff0c;不多说&#xff0c;上图&#xff1a; bg图片、字体、颜色等都可以在Preferences里设置&#xff0c;强大&…...

编程日记 2023/6/6 23:42:54

shell编写图片抓取器

最近在看《Linux Shell脚本攻略》一书&#xff0c;书中有个图片抓取器的script&#xff0c;抓取出来记录一下。适用范围&#xff1a;适合抓取html里符合img标签正则规则的图片。 #!/bin/bash if [ $# -ne 3 ] thenecho "Usage: $0 URL -d DIRECTORY"exit -1 fi for …...

编程日记 2023/6/6 15:22:17

SSH免密码登录

公司服务器很多的话&#xff0c;如果每次连接都需要输入密码&#xff0c;那就太麻烦了。So&#xff0c;免密登录就可以大大提高我们的工作效率了。 下面介绍ssh免密登录的方法&#xff1a; 实现步骤&#xff1a; 1.在你的自己的机器下面使用ssh-keygen命令来实现创建公钥 使…...

编程日记 2023/5/28 13:34:04

Jmeter访问HTTPS请求

公司最近在搞全站HTTPS改造&#xff0c;进一步提高网站的安全性&#xff0c;防止运营商劫持。那么&#xff0c;改造完成后&#xff0c;所有前后端的URL将全部为https。 So &#xff0c;研究下怎么用Jmeter访问https请求呢。 其实很简单&#xff0c; 第一步在jmeter中创建HTT…...

编程日记 2023/6/3 16:58:29

《Maven实战》读书笔记

之前对Maven有些认识&#xff0c;通过这本书《Maven实战》一起系统的回顾一下&#xff0c;总结的东西不会很全面&#xff0c;但都是日常工作中最常用的。 简介&#xff1a; maven翻译为“知识的积累”&#xff0c;基于项目对象模型&#xff08;Project Object Model&#xff0…...

编程日记 2023/6/6 17:05:23

github/gitlab 管理多个ssh key

以前只使用一个 ssh key 在github上提交代码&#xff0c;由于工作原因&#xff0c;需要再添加一个ssh key在公司的 gitlab上提交代码&#xff0c;下面记录下配置过程&#xff0c;防止遗忘。 生成并添加第一个ssh key 第一次使用ssh生成key&#xff0c;默认会在用户~&#xff…...

编程日记 2023/6/7 4:10:54

解决部分国产机连不上adb shell的办法

手里头认领了公司的部分测试机&#xff0c;但是工作中发现部分手机连上usb后&#xff0c;adb devices识别不出设备。下面总结一下解决办法&#xff1a; 魅蓝Note2&#xff1a; 1.在命令行输入 system_profiler SPUSBDataType,查看连接的usb设备的信息&#xff0c;如下图&…...

编程日记 2023/6/1 22:22:57

流式断言器AssertJ入门介绍

之前一直使用Junit自带的Assert类进行断言&#xff0c;尽管这能满足一些我们最基础的需要&#xff0c;但从功能上来讲还是不够强大的。 今天介绍一款功能强大的流式断言器AssertJ&#xff0c;所谓的流式断言就是相较于Assert的单个校验点断言&#xff0c;支持一条断言语句对实…...

编程日记 2023/6/6 3:46:15

单元测试框架-Junit介绍

在工作中编写接口脚本中经常用到junit作为测试框架&#xff0c;下面总结一下junit的用法和编写规范&#xff0c;供大家参考。 junit简介&#xff1a; 基于Java语言的单元测试框架&#xff0c;在日常工作中被广泛运用于单元测试和接口测试。 junit官网&#xff1a;http://jun…...

编程日记 2023/6/5 7:57:19

TestNG使用总结

TestNG简介&#xff1a; TestNG是一个测试框架&#xff0c;其灵感来自JUnit和NUnit&#xff0c;但同时引入了一些新的功能&#xff0c;使其功能更强大&#xff0c;使用更方便。 TestNG相较于Junit的优点&#xff1a; 可指定执行顺序&#xff0c; dependsOnMethods 属性来应对…...

编程日记 2023/6/3 23:40:28

基于数据驱动的接口自动化测试解决方案

总结一下我么项目中使用的基于数据驱动的接口自动化测试解决方案&#xff0c;仅供大家参考。1.接口框架设计结构 2.接口测试脚本设计原则 3.持续集成 这块用jenkins就可以了&#xff0c;就不介绍了&#xff0c;目前我们项目的集成规则介绍一下&#xff1a; 1.脚本job与应用对…...

编程日记 2023/6/6 21:00:42

python数据类型

重温python数据类型&#xff0c;重点掌握str&#xff0c;list&#xff0c;tuple及dict类型。...

编程日记 2023/5/31 23:28:55

Python高级特性

Python高级特性 切片迭代及迭代器列表生成式生成器 这些高级特性的作用都是一样的&#xff0c;为了代码的简洁、高效运行。 切片 切片让取一个list或tuple的部分元素变得相当简单&#xff0c; e.g: L[‘jack’,’mike’,’jerry’] 那么第一个位置&#xff0c;索引为0&a…...

编程日记 2023/6/7 2:52:28

ADB学习笔记

简介&#xff1a; ADB的全称为Android Debug Bridge&#xff08;调试桥&#xff09;&#xff0c; 它是一个客户端-服务器端程序&#xff0c;其中客户端是你用来操作的电脑, 服务器端是android设备。作用显而易见&#xff0c;能方便我们在PC上对手机进行调试的一些工作。 原理…...

编程日记 2023/6/7 2:50:46

Appium简介

Appium简介 Appium is an open source, cross-platform test automation tool for native, hybrid and mobile web apps, tested on simulators (iOS), emulators (Android), and real devices (iOS, Android, Windows). 优缺点 优点显而易见&#xff0c;支持webview、hybri…...

编程日记 2023/6/7 2:49:43

Appium-java API详解

目前appium-java最新版本是5.0.0-BETA3&#xff0c;因此就拿最新的说明&#xff0c;以Java为例&#xff0c;首先引入java client的依赖&#xff1a;<dependency><groupId>io.appium</groupId><artifactId>java-client</artifactId><version&g…...

编程日记 2023/6/5 2:18:50

Appium学习遇到的坑

安装篇 Q1&#xff1a;安装时要求java运行环境为最低1.8&#xff0c;我原先的jdk1.7无法运行。 A1&#xff1a;升级jdk后解决。附appium安装教程 配置篇 Q2&#xff1a;运行提示error&#xff1a;Error: Android bootstrap socket crashed: Error: getaddrinfo ENOTFOUND lo…...

编程日记 2023/6/2 12:59:15

每天一个adb命令：pm 命令详解

介绍adb shell中一个很重要的命令——pm&#xff08;Package Manager&#xff09;&#xff0c;这个命令主要用于获取和安装在 Android 设备上的应用信息。 关于pm命令的用法解析。命令行下输入adb shell pm即可获得关于pm的用法帮助&#xff0c;如下所示&#xff1a; usage: …...

编程日记 2023/6/7 0:32:38

每天一个adb命令：am 命令详解

am 这个命令可以帮助我们直接启动activity、service及广播。 adb shell am 可以查看命令的详细说明。 usage: am [subcommand] [options] usage: am start [-D] [-W] [-P <FILE>] [--start-profiler <FILE>][--sampling INTERVAL] [-R COUNT] [-S] [--opengl-tra…...

编程日记 2023/6/6 9:23:56

每天一个adb命令：input 命令详解

input命令可以用于向键盘发送一些指令&#xff0c;先看看input的官方说明&#xff1a; Usage: input [<source>] <command> [<arg>...]The sources are:mousekeyboardjoysticktouchnavigationtouchpadtrackballstylusdpadtouchscreengamepadThe commands an…...

编程日记 2023/6/6 21:36:06

每天一个adb命令：screen 命令详解

screen命令分为截屏screencap命令及录制视频screenrecord命令。 screencap命令&#xff1a; sage: screencap [-hp] [-d display-id] [FILENAME]-h: this message-p: save the file as a png.-d: specify the display id to capture, default 0. If FILENAME ends with .png …...

编程日记 2023/6/3 9:35:53

每天一个adb命令：wm命令详解

wm命令可以用于获取屏幕分辨率、像素密度等。 前提&#xff1a;Android4.3及以上 usage: wm [subcommand] [options]wm size [reset|WxH]wm density [reset|DENSITY]wm overscan [reset|LEFT,TOP,RIGHT,BOTTOM]wm size: return or override display size.wm density: overrid…...

编程日记 2023/6/4 16:26:04

每天一个adb命令：dumpsys命令详解

dumpsys是一个能帮助我们对手机进行性能分析的命令&#xff0c;它可以帮助我们获取电池、内存、cpu、磁盘、wifi等等信息&#xff0c;具体能查询的信息可以通过命令&#xff1a; adb shell dumpsys | grep DUMP OF SERVICE DUMP OF SERVICE DockObserver: DUMP OF SERVICE Sm…...

编程日记 2023/6/7 4:09:18

每天一个adb命令：monkey命令详解

国际惯例&#xff0c;先用adb shell monkey 看看具体用法。 具体用法 usage: monkey [-p ALLOWED_PACKAGE [-p ALLOWED_PACKAGE] ...][-c MAIN_CATEGORY [-c MAIN_CATEGORY] ...][--ignore-crashes] [--ignore-timeouts][--ignore-security-exceptions][--monitor-native-cra…...

编程日记 2023/6/5 12:11:51