2019CCPC湘潭邀请赛 Chika and Friendly Pairs（莫队+树状数组）

本文主要是介绍2019CCPC湘潭邀请赛 Chika and Friendly Pairs（莫队+树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem Description
Chika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of “friendly pairs” in a given interval.

friendly pair: for two integers ai and aj, if i<j and the absolute value of ai−aj is no more than a given constant integer K, then (i,j) is called a “friendly pair”.A friendly pair (i,j) in a interval [L,R] should satisfy L≤i<j≤R.

Input
The first line contains 3 integers n (1≤n≤27000), m (1≤m≤27000) and K (1≤K≤109), representing the number of integers in the sequence a, the number of tasks and the given constant integer.
The second line contains n non-negative integers, representing the integers in the sequence a. Every integer of sequence a is no more than 109.
Then m lines follow, each of which contains two integers L, R (1≤L≤R≤n). The meaning is to ask the number of “friendly pairs” in the interval [L,R]。

Output
For each task, you need to print one line, including only one integer, representing the number of “friendly pairs” in the query interval.

Sample Input
7 5 3
2 5 7 5 1 5 6
6 6
1 3
4 6
2 4
3 4

Sample Output
0
2
1
3
1

Source
2019CCPC湖南全国邀请赛（广东省赛、江苏省赛）重现赛

题意： 询问某个区间内差值不大于k的数对数目。
思路：
莫队算法就是双指针加排序，通过分块，按块排序，块内排右指针。
由此在块的内部相邻左端点变化最大为 $\sqrt{n}$，而右端点是单调的，可以不计。
那么m次询问均摊下来最大$m\sqrt{n}$，观察n和m的范围，越为3e4，莫队可行！

我们用双指针维护到当前询问区间，区间变化对答案的影响可以用树状数组记录。
这类似与逆序对，你求与x差距不大于k的数，就是$sum(x+k)-sum(x-k-1)$
当然，数字很大，再离散化一遍就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>using namespace std;const int maxn = 1e5 + 7;struct Query {int l,r,id;
}q[maxn];int a[maxn];
int t[maxn],tot,cnt,sqr;
int L,R,num,ans[maxn];
int mp[maxn][2];
int c[maxn];void init() {sort(t + 1,t + 1 + tot);cnt = unique(t + 1,t + 1 + tot) - t - 1;
}int Find(int x) {return lower_bound(t + 1,t + 1 + cnt,x) - t;
}int cmp(Query a,Query b) {return a.l / sqr == b.l / sqr ? a.r < b.r : a.l < b.l;
}void add(int x,int v) {while(x < maxn) {c[x] += v;x += x & (-x);}
}int sum(int x) {int res = 0;while(x) {res += c[x];x -= x & (-x);}return res;
}void Add(int x) {num += sum(mp[a[x]][1]) - sum(mp[a[x]][0]);add(a[x],1);
}void Del(int x) {add(a[x],-1);num -= sum(mp[a[x]][1]) - sum(mp[a[x]][0]);
}int main() {int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i = 1;i <= n;i++) {scanf("%d",&a[i]);t[++tot] = a[i];t[++tot] = a[i] - k - 1;t[++tot] = a[i] + k;}init();for(int i = 1;i <= m;i++) {scanf("%d%d",&q[i].l,&q[i].r);q[i].id = i;}for(int i = 1;i <= n;i++) {int now = Find(a[i]);mp[now][0] = Find(a[i] - k - 1);mp[now][1] = Find(a[i] + k);a[i] = now;}sqr = sqrt(n);sort(q + 1,q + 1 + m,cmp);L = 1,R = 0;for(int i = 1;i <= m;i++) {int l = q[i].l,r = q[i].r;int id = q[i].id;while(L < l) {Del(L++);}while(L > l) {Add(--L);}while(R < r) {Add(++R);}while(R > r) {Del(R--);}ans[id] = num;}for(int i = 1;i <= m;i++) {printf("%d\n",ans[i]);}return 0;
}

这篇关于2019CCPC湘潭邀请赛 Chika and Friendly Pairs（莫队+树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---