首页 > 编程语言 > 详细

做题集——(莫队+离散+树状数组)Chika and Friendly Pairs

时间:2021-05-07 23:54:51      阅读:41      评论:0      收藏:0      [点我收藏+]

题目:http://acm.hdu.edu.cn/showproblem.php?pid=6534

题面:

技术分享图片

Sample Input

7 5 3
2 5 7 5 1 5 6
6 6
1 3
4 6
2 4
3 4

Output

0
2
1
3
1

题意:

  给定一个区间,询问区间内有多少对数字满足两数之差的绝对值小于给定的K

思路:

  看到该题的特点为区间操作,常见的区间操作有线段树及树状数组,首先思考线段树,根据结论可知,线段树的节点维护的数值应该是可以在父子节点之间进行传递的,虽然父子区间的信息可以进行维护,但是关系过于复杂,并且询问的过程中,当前节点与临近节点有着较大的关系,实际考虑书写过于复杂。考虑到题目是没有修改的区间询问,因此可以联想到莫队的方法,那么实际要考虑的就是两个临近区间的转换关系是什么。

  思考以下不难发现,当插入一个新数字(设为a)的时候,友对增加的数目一定都包含a,而包含的另一个数字(设为b)一定在a的附近,具体为[a-k, a+k](设为集合A)。剩下的就不难处理了,插入一个新数字时,查找原区间内在集合A内的数字有多少个,这个的计算可以交给树状数组处理(线段树也可以,但是代码量有点多,且维护的内容并不复杂,所以还是优先考虑树状数组)。另外由于数据太大,树状数组开不了这么多的空间,因此需要进行离散化。所以大致的处理方法为,读入数据,进行离散化,读入所有的区间询问,对其进行排序,排完序之后,按序询问,根据需求调用插入一个数字和弹出一个数字时对应的操作,每一个询问处理完成之后将答案存储,全部询问处理完之后将答案按序输出。

Code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e4;
typedef long long ll;
ll a[MAXN], up[MAXN], down[MAXN]; ll t[MAXN
<< 2]; vector<int> zh; struct Query { int id, l, r, bl; }q[MAXN]; void Update(ll node, ll val) { for (; node <= MAXN * 4; node += node & -node) t[node] += val; } ll Ask(ll node) { ll ans = 0; for (; node; node -= node & -node) ans += t[node]; return ans; } int Find(int x) { return lower_bound(zh.begin(), zh.end(), x) - zh.begin(); } bool cmp(Query a, Query b) { return a.bl ^ b.bl ? a.l < b.l : ((a.bl & 1) ? a.r < b.r : a.r > b.r); } int res[MAXN]; int main() { int n, m, k; cin >> n >> m >> k; zh.push_back(-0x3f3f3f3f); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); up[i] = a[i] + k; down[i] = a[i] - k - 1; zh.push_back(a[i]); zh.push_back(up[i]); zh.push_back(down[i]); } sort(zh.begin() + 1, zh.end()); zh.erase(unique(zh.begin() + 1, zh.end()), zh.end()); for (int i = 1; i <= n; i++) { //转化为离散化后的坐标 up[i] = Find(up[i]); down[i] = Find(down[i]); a[i] = Find(a[i]); } int BL = sqrt(n); for (int i = 1; i <= m; i++) { scanf("%d%d", &q[i].l, &q[i].r); q[i].id = i; q[i].bl = q[i].l / BL; } sort(q + 1, q + m + 1, cmp); int r = 0, l = 1, ans = 0; for (int i = 1; i <= m; i++) { while (r < q[i].r) { ans += Ask(up[r + 1]) - Ask(down[r + 1]); Update(a[r + 1], 1); r++; } while (r > q[i].r) { Update(a[r], -1); ans -= Ask(up[r]) - Ask(down[r]); r--; } while (l < q[i].l) { Update(a[l], -1); ans -= Ask(up[l]) - Ask(down[l]); l++; } while (l > q[i].l) { ans += Ask(up[l - 1]) - Ask(down[l - 1]); Update(a[l - 1], 1); l--; } res[q[i].id] = ans; } for (int i = 1; i <= m; i++) { printf("%d\n", res[i]); } return 0; }

 

做题集——(莫队+离散+树状数组)Chika and Friendly Pairs

原文:https://www.cnblogs.com/TanJI-life/p/14742649.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!