莫队+树状数组+离散化

2019CCPC湖南全国邀请赛（广东省赛、江苏省赛）C题

C Chika and Friendly Pairs

这题是江苏省赛的题目，当时我和对友做出了4个题之后，我一个人就一直在看这题，然后就一直看到了比赛结束也不会做，正好昨天学了莫队，就把这题补一下。

首先这题题意很明确，题目所求答案需要满足的条件是 $i<j, |a_i - a_j|<=k$ ，化简一下变成 $i<j, a_i-k=<a_j<=a_i+k$ , 给出 $m$ 个询问，对于这些询问我们可以用莫队来处理。关键在于我们怎么实现快速的转移呢？
加入我们当前区间为$[l,r]$，也就是已知区间。我们需要转移到$[q[i].l,q[i].r]$ ，可以发现我们每次转移$l,r$ 的时侯，已知区间都在我们的一侧，也就是说满足了 $i<j$ 这个关系，我们只需要统计 转移当前位置对答案带来的影响即可。 由刚刚推的关系式可得，当我们每转移一次时，我们只需要统计我们的已知区间$[l,r]$内有多个数满足 $a_i-k=<a_j<=a_i+k$ ,这个可以用树状数组来解决。这样我们实现了$O(log_n)$ 转移。
另外数比较大，先离散化。另外一些细节在代码中说明。
总复杂度$O(n^{3/2} log_n)$

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
using namespace std; 
#define lowbit(x) (x&(-x))
const int N = 27000+10;
int b[N],Ans[N];
int c[N];
int  a[N], g[N];
int up[N], low[N];
int n, m,block,tot, ans;
int  k;
int l, r;
struct query{
	int id, l, r,t;
}q[N];
bool cmp1(query o1, query o2)
{
	if (b[o1.l] == b[o2.l]) 
		return o1.r < o2.r; 
	return o1.l < o2.l;
}
void update(int pos,int val)
{
	for (; pos <= tot; pos += lowbit(pos))
		c[pos] += val;
}
int ask(int pos)
{
	int res=0;
	for (; pos; pos -= lowbit(pos))
		res += c[pos];
	return res;
}
void add(int pos)
{
	int s = ask(up[pos]) - ask(low[pos] - 1);
	ans += s;
	update(a[pos], 1);//这个最后加，如果刚开始就加的话就会把本身也算进去了
}
void del(int pos)
{
	update(a[pos], -1);//这个必须刚开始就减去，也是防止把自身算进去
	int s = ask(up[pos]) - ask(low[pos] - 1);
	ans -= s;
}
void Mo()
{
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		while (l < q[i].l) del(l++);
		while (l>q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (r> q[i].r)  del(r--);
		Ans[q[i].id] = ans;
	}
	for (int i = 1; i <= m; i++)
		printf("%d\n", Ans[i]);
}
int main()
{
	scanf("%d%d%d", &n, &m,&k);
	block = sqrt(n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		g[i] = a[i];
		b[i] = (i - 1) / block + 1;
	}
	sort(g + 1, g + n + 1);
	tot = unique(g + 1, g + n + 1) - g - 1;
	for (int i = 1; i <= n; i++)
	{
		up[i] = upper_bound(g + 1, g + tot + 1, a[i] + k) - g -1 ;//因为需要找到<=a[i]+k,所以减1
		low[i] = lower_bound(g + 1, g + tot + 1, a[i] - k) - g;//这两个上下区间必须预处理，每次转移的时候再求这个上下界就会超时。
		a[i] = lower_bound(g + 1, g + tot + 1, a[i]) - g;
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &q[i].l,&q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp1);
	Mo();
	return 0;
}