热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

BZOJ2141排队:分块与树状数组详解

题目描述:孩子们围坐在一起,分享水果,场面温馨。然而,由于孩子们身高不同,排队时显得高低不齐。给定孩子们的身高序列,通过交换某些孩子的顺序,计算每次交换后的序列混乱度。
### 描述
孩子们围坐在一起,分享水果,场面温馨。然而,由于孩子们身高不同,排队时显得高低不齐。给定孩子们的身高序列,通过交换某些孩子的顺序,计算每次交换后的序列混乱度。

#### 输入
- 第一行是一个正整数n,表示孩子们的数量。
- 第二行包含n个由空格分隔的正整数h1, h2, ..., hn,依次表示初始队列中孩子们的身高。
- 第三行是一个正整数m,表示交换操作的次数。
- 以下m行每行包含两个正整数ai和bi,表示交换位置ai与位置bi的孩子。

#### 输出
- 输出文件共m行,第i行一个正整数表示交换操作i结束后,序列的混乱度。

#### 示例
**输入:**
```
3
130 150 140
2
2 3
1 3
```
**输出:**
```
1
0
3
```

**解释:**
- 初始时,(2,3)满足条件。
- 第一次交换后,序列为130 140 150,没有满足条件的对。
- 第二次交换后,序列为150 140 130,有(1,2),(1,3),(2,3)三对满足条件。

#### 数据范围
- 对于100%的数据,1≤m≤2*10^3,1≤n≤2*10^4,1≤hi≤10^9,ai≠bi,1≤ai, bi≤n。

### 解法
#### 逆序数
逆序数是指满足i a[j]的数对数量。直接暴力求解的时间复杂度为O(n^2),而使用树状数组可以在O(n log n)的时间内求解。

#### 算法步骤
1. **离散化**:由于数值较大,先进行离散化处理。
2. **分块**:将数组分成若干块,每块建立一个树状数组。
3. **查询与更新**:对于每次交换操作,根据块的位置分别处理。
- 如果交换的两个位置在同一个块内,直接暴力计算贡献。
- 如果不在同一个块内,中间的完整块使用树状数组快速查询,两端的不完整块则暴力计算。
4. **复杂度分析**:整体复杂度为O(√n * log n)。

#### 代码实现
```cpp
#include
using namespace std;

struct Node {
int h, id;
Node() {}
Node(int h, int id) : h(h), id(id) {}
};

Node a[20010];
int v[20010], top, tree[150][20010];
int n, m, block;

bool cmp1(Node a, Node b) { return a.h bool cmp2(Node a, Node b) { return a.id
void update(int p, int x, int a) {
for (int i = x; i <= top; i += i & -i) {
tree[p][i] += a;
}
}

int query(int p, int x) {
int ans = 0;
for (int i = x; i; i -= i & -i) {
ans += tree[p][i];
}
return ans;
}

int main() {
scanf("%d", &n);
block = sqrt(n);
for (int i = 0; i scanf("%d", &a[i].h);
a[i].id = i;
}

sort(a, a + n, cmp1);
for (int i = 0; i if (a[i].h != v[top]) v[++top] = a[i].h;
a[i].h = top;
}

sort(a, a + n, cmp2);
int ans = 0;
for (int i = 0; i for (int j = 0; j <= i / block; j++) {
ans -= query(j, a[i].h);
}
ans += i;
update(i / block, a[i].h, 1);
}

printf("%d\n", ans);
scanf("%d", &m);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
x--, y--;
if (x > y) swap(x, y);
if (x / block == y / block) {
for (int i = x + 1; i ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
} else {
for (int i = x / block + 1; i ans += (block - query(i, a[x].h)) + query(i, a[y].h - 1) - query(i, a[x].h - 1) - (block - query(i, a[y].h));
}
for (int i = x + 1; i <(x / block + 1) * block; i++) {
ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
for (int i = y / block * block; i ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
}
ans += (a[x].h a[y].h);
update(x / block, a[x].h, -1);
update(y / block, a[y].h, -1);
swap(a[x].h, a[y].h);
update(x / block, a[x].h, 1);
update(y / block, a[y].h, 1);
printf("%d\n", ans);
}
return 0;
}
```

推荐阅读
  • 基于KVM的SRIOV直通配置及性能测试
    SRIOV介绍、VF直通配置,以及包转发率性能测试小慢哥的原创文章,欢迎转载目录?1.SRIOV介绍?2.环境说明?3.开启SRIOV?4.生成VF?5.VF ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
  • 本题探讨了在一个有向图中,如何根据特定规则将城市划分为若干个区域,使得每个区域内的城市之间能够相互到达,并且划分的区域数量最少。题目提供了时间限制和内存限制,要求在给定的城市和道路信息下,计算出最少需要划分的区域数量。 ... [详细]
  • 配置多VLAN环境下的透明SQUID代理
    本文介绍如何在包含多个VLAN的网络环境中配置SQUID作为透明网关。网络拓扑包括Cisco 3750交换机、PANABIT防火墙和SQUID服务器,所有设备均部署在ESXi虚拟化平台上。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文将介绍如何编写一些有趣的VBScript脚本,这些脚本可以在朋友之间进行无害的恶作剧。通过简单的代码示例,帮助您了解VBScript的基本语法和功能。 ... [详细]
  • Explore how Matterverse is redefining the metaverse experience, creating immersive and meaningful virtual environments that foster genuine connections and economic opportunities. ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 本文探讨了如何优化和正确配置Kafka Streams应用程序以确保准确的状态存储查询。通过调整配置参数和代码逻辑,可以有效解决数据不一致的问题。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • PHP 5.5.0rc1 发布:深入解析 Zend OPcache
    2013年5月9日,PHP官方发布了PHP 5.5.0rc1和PHP 5.4.15正式版,这两个版本均支持64位环境。本文将详细介绍Zend OPcache的功能及其在Windows环境下的配置与测试。 ... [详细]
  • 本题通过将每个矩形视为一个节点,根据其相对位置构建拓扑图,并利用深度优先搜索(DFS)或状态压缩动态规划(DP)求解最小涂色次数。本文详细解析了该问题的建模思路与算法实现。 ... [详细]
  • 毕业设计:基于机器学习与深度学习的垃圾邮件(短信)分类算法实现
    本文详细介绍了如何使用机器学习和深度学习技术对垃圾邮件和短信进行分类。内容涵盖从数据集介绍、预处理、特征提取到模型训练与评估的完整流程,并提供了具体的代码示例和实验结果。 ... [详细]
  • 本文介绍如何使用布局文件在Android应用中排列多行TextView和Button,使其占据屏幕的特定比例,并提供示例代码以帮助理解和实现。 ... [详细]
  • 数据结构入门:栈的基本概念与操作
    本文详细介绍了栈这一重要的数据结构,包括其基本概念、顺序存储结构、栈的基本操作(如入栈、出栈、清空栈和销毁栈),以及如何利用栈实现二进制到十进制的转换。通过具体代码示例,帮助读者更好地理解和应用栈的相关知识。 ... [详细]
author-avatar
小梅LMY
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有