EducationalCodeforcesRound10D.NestedSegments(树状数组)

作者：暖倪2502938803 | 来源：互联网 | 2023-05-17 12:28

题目链接：http:codeforces.comproblemsetproblem652D给你n个不同的区间，L或者R不会出现相同的数字，问你每一个区间包含多少个区间。我是先把每个

题目链接：http://codeforces.com/problemset/problem/652/D

给你n个不同的区间，L或者R不会出现相同的数字，问你每一个区间包含多少个区间。

我是先把每个区间看作整体，按照R从小到大排序。然后从最小的R开始枚举每个区间，要是枚举到这个区间L的时候，计算之前枚举的区间有多少个Li在L之后，那么这些Li大于L的区间的数量就是答案。那我每次枚举的时候用树状数组add(L , 1) 说明在L这个位置上出现了区间，之后枚举的时候计算L之前的和，然后i - 1 - sum(L)这个就是答案。（跟用树状数组计算逆序对有点类似，自己模拟一下就明白了）。

但是区间的L和R很大，区间的个数又不是很多。所以我用离散化，区间的大小包含1到2n这些数。我用map做的，也可以用二分。

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 using namespace std;
 7 const int MAXN = 4e5 + 10;
 8 struct data {
 9     int l , r , pos;
10 }a[MAXN];
11 int ans[MAXN] , n , bit[MAXN] , x[MAXN * 2];
12 map <int , int> mp;
13 bool cmp(data x , data y) {
14     return x.r < y.r;
15 }
16 int sum(int i) {
17     int s = 0;
18     while(i > 0) {
19         s += bit[i];
20         i -= (i&-i);
21     }
22     return s;
23 }
24 
25 void add(int i , int x) {
26     while(i <= n*2) {
27         bit[i] += x;
28         i += (i&-i);
29     }
30 }
31 
32 int main()
33 {
34     scanf("%d" , &n);
35     int cOnt= 0;
36     for(int i = 1 ; i <= n ; i++) {
37         scanf("%d %d" , &a[i].l , &a[i].r);
38         x[++cont] = a[i].l;
39         x[++cont] = a[i].r;
40         a[i].pos = i;
41     }
42     sort(x + 1 , x + cont + 1);
43     for(int i = 1 ; i <= cont ; i++) {
44         mp[x[i]] = i;
45     }
46     sort(a + 1 , a + n + 1 , cmp);
47     for(int i = 1 ; i <= n ; i++) {
48         a[i].l = mp[a[i].l];
49         a[i].r = mp[a[i].r];
50     }
51     for(int i = 1 ; i <= n ; i++) {
52         ans[a[i].pos] = i - 1 - sum(a[i].l);
53         //cout <
54         add(a[i].l , 1);
55     }
56     for(int i = 1 ; i <= n ; i++) {
57         printf("%d\n" , ans[i]);
58     }
59 }

Educational Codeforces Round 10 D. Nested Segments (树状数组)

推荐阅读

html
HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]

蜡笔小新 2023-12-14 15:08:18
uri
lua语言闭包、模式匹配、日期、编译、模块的特性及应用

本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]

蜡笔小新 2023-12-14 18:18:21
text
C#之数据集：DataSet对象的使用及相关方法详解

本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]

蜡笔小新 2023-12-14 12:09:13
text
OC学习笔记之@property和@synthesize

本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]

蜡笔小新 2023-12-14 12:05:06
text
SpringBoot集成前端模版（thymeleaf）的配置步骤

本文介绍了在SpringBoot中集成thymeleaf前端模版的配置步骤，包括在application.properties配置文件中添加thymeleaf的配置信息，引入thymeleaf的jar包，以及创建PageController并添加index方法。 ... [详细]

蜡笔小新 2023-12-14 10:11:46
uri
知识图谱——机器大脑中的知识库

本文介绍了知识图谱在机器大脑中的应用，以及搜索引擎在知识图谱方面的发展。以谷歌知识图谱为例，说明了知识图谱的智能化特点。通过搜索引擎用户可以获取更加智能化的答案，如搜索关键词"Marie Curie"，会得到居里夫人的详细信息以及与之相关的历史人物。知识图谱的出现引起了搜索引擎行业的变革，不仅美国的微软必应，中国的百度、搜狗等搜索引擎公司也纷纷推出了自己的知识图谱。 ... [详细]

蜡笔小新 2023-12-14 10:06:19
uri
Linux进程控制块PCBtask_struct结构体结构及作用详解

本文详细介绍了Linux中进程控制块PCBtask_struct结构体的结构和作用，包括进程状态、进程号、待处理信号、进程地址空间、调度标志、锁深度、基本时间片、调度策略以及内存管理信息等方面的内容。阅读本文可以更加深入地了解Linux进程管理的原理和机制。 ... [详细]

蜡笔小新 2023-12-13 21:31:18
text
后台获取视图对应的字符串

1.帮助类后台获取视图对应的字符串publicclassViewHelper{将View输出为字符串(注：不会执行对应的ac ... [详细]

蜡笔小新 2023-12-13 18:03:01
text
《数据结构》学习笔记3——串匹配算法性能评估

本文主要讨论串匹配算法的性能评估，包括模式匹配、字符种类数量、算法复杂度等内容。通过借助C++中的头文件和库，可以实现对串的匹配操作。其中蛮力算法的复杂度为O(m*n)，通过随机取出长度为m的子串作为模式P，在文本T中进行匹配，统计平均复杂度。对于成功和失败的匹配分别进行测试，分析其平均复杂度。详情请参考相关学习资源。 ... [详细]

蜡笔小新 2023-12-13 16:16:05
text
求解hdu 1003 java题目的动态规划优化方法

本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]

蜡笔小新 2023-12-14 13:11:00
text
Mac OS 升级到11.2.2 Eclipse打不开了，报错Failed to create the Java Virtual Machine

本文介绍了在Mac OS升级到11.2.2版本后，使用Eclipse打开时出现报错Failed to create the Java Virtual Machine的问题，并提供了解决方法。 ... [详细]

蜡笔小新 2023-12-14 12:01:13
const
Hibernate基础映射

在说Hibernate映射前，我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象，以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]

蜡笔小新 2023-12-14 10:57:47
const
测试人的性格，点火让他着急，考验婚姻问题的善意玩人

本文讲述了作者通过点火测试男友的性格和承受能力，以考验婚姻问题。作者故意不安慰男友并再次点火，观察他的反应。这个行为是善意的玩人，旨在了解男友的性格和避免婚姻问题。 ... [详细]

蜡笔小新 2023-12-14 09:10:09
text
java 线程死锁模拟

1，关于死锁的理解死锁，我们可以简单的理解为是两个线程同时使用同一资源，两个线程又得不到相应的资源而造成永无相互等待的情况。 2，模拟死锁背景介绍：我们创建一个朋友 ... [详细]

蜡笔小新 2023-12-13 19:12:25
text
ABAP开发发送邮件程序的配置和代码整理

本文介绍了通过ABAP开发往外网发邮件的需求，并提供了配置和代码整理的资料。其中包括了配置SAP邮件服务器的步骤和ABAP写发送邮件代码的过程。通过RZ10配置参数和icm/server_port_1的设定，可以实现向Sap User和外部邮件发送邮件的功能。希望对需要的开发人员有帮助。摘要长度：184字。 ... [详细]

蜡笔小新 2023-12-13 15:50:17

暖倪2502938803

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章