本文主要是介绍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的数对数目。
思路:
莫队算法就是双指针加排序,通过分块,按块排序,块内排右指针。
由此在块的内部相邻左端点变化最大为 n \sqrt n n,而右端点是单调的,可以不计。
那么m次询问均摊下来最大 m n m\sqrt n mn,观察n和m的范围,越为3e4,莫队可行!
我们用双指针维护到当前询问区间,区间变化对答案的影响可以用树状数组记录。
这类似与逆序对,你求与x差距不大于k的数,就是 s u m ( x + k ) − s u m ( x − k − 1 ) sum(x + k) - sum(x - k - 1) 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(莫队+树状数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!