HDU 6534（XTCPC2019）C - Chika and Friendly Pairs (莫隊 + 權值樹狀數組)

題意：

思路：

再想過了一些主席樹等大資料結構如何維護後，毫無頭緒，此時根據資料範圍找算法可能，注意到 3 e 4 3e4 3e4的資料那麼 O ( n n ) O(n\sqrt n) O(nn

​)也可過，再加上題目裡并沒有要求我們強制線上處理，再加上這道題目答案的更新在單點添加和删除的是保證正确性的，是以可以用莫隊來解決。

下一步就是找一種方法來快速的獲得，目前周遊的 [ l , r ] [l , r] [l,r]區間間内值域處于 [ a i − k , a i + k ] [a_i -k,a_i + k] [ai​−k,ai​+k]的數有多少，一開始看到這個無腦想到主席樹 l o g n logn logn的查詢，就沖了，結果一直 t l e tle tle，後來得知可能是常數太大，無法優化，遞歸類算法都自帶比較大的常數，但一般無人卡。

繼續想，莫隊處理區間的時候，是一個個位置單點滑動的，是以我們每個位置都更新的話，目前區間其實就跟查整棵數是一緻的，因為加的我及時加，不要的我及時消除，到此隻需要一個樹狀數組來維護對應值域内的數有多少個即可。

再就是最好提前将 a i − k a_i - k ai​−k和 a i + k a_i + k ai​+k放入離散化數組，不然的話，對于上界的有些情況需要特殊處理一下，要不然不對，當然細節也不難，很好了解。

#include <bits/stdc++.h>

using namespace std;

#define pb emplace_back
#define MP make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define lson rt<<1
#define rson rt<<1|1
#define CLOSE std::ios::sync_with_stdio(false)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-6;
const int N = 27010;
int n,m,a[N],up[N],down[N],c[N],b[N],cnt,k;
int lowbit(int x) {
	return x & (-x);
}
void add(int pos,int v) {
	while(pos <= n) {
		c[pos] += v;
		pos += lowbit(pos);
	}
}
int query(int pos) {
	int res = 0;
	while(pos) { res += c[pos]; pos -= lowbit(pos); }
	return res;
}
int posq[N],posa[N],ans[N];
struct Q {
	int l,r,id;
}q[N];
bool cmp(Q a,Q b) {
	return posq[a.l] == posq[b.l] ? a.r < b.r : posq[a.l] < posq[b.l];
}
int getid(int x) { return lower_bound(b + 1,b + 1 + cnt,x) - b; }

int main() {
	scanf("%d%d%d",&n,&m,&k);
	int siz = sqrt(n);
	for(int i = 1;i <= n;i ++) {
		scanf("%d",&a[i]);
		posq[i] = (i + siz - 1) / siz;
		b[i] = a[i];
	}
	sort(b + 1,b + 1 + n);
	cnt = unique(b + 1,b + 1 + n) - b - 1;
	for(int i = 1;i <= m;i ++) {
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id = i;
	}
	b[cnt+1] = INF;
	sort(q + 1,q + 1 + m,cmp);
	for(int i = 1;i <= n;i ++) {
		posa[a[i]] = getid(a[i]);
		down[a[i]] = getid(a[i] - k);
		int tmp = getid(a[i] + k); 
		up[a[i]] = (b[tmp] > a[i] + k) ? tmp-1 : tmp;//邊界的細節情況
	}
	int l = 1,r = 0,sum = 0;
	for(int i = 1;i <= m;i ++) {
			while(q[i].l < l) {
			int tmp = l - 1;
			sum += query(up[a[tmp]]) - query(down[a[tmp]]-1);
			add(posa[a[tmp]],1);
			l--;
		}
		while(q[i].r > r) {
			int tmp = r + 1;
			sum += query(up[a[tmp]]) - query(down[a[tmp]]-1);
			add(posa[a[tmp]],1);
			r++;
		}
		while(q[i].l > l) {
			add(posa[a[l]],-1);
			sum -= query(up[a[l]]) - query(down[a[l]]-1);
			l++;
		}
		while(q[i].r < r) {
			add(posa[a[r]],-1);
			sum -= query(up[a[r]]) - query(down[a[r]]-1);
			r--;
		}
		ans[q[i].id] = sum;
	}
	for(int i = 1;i <= m;i ++) printf("%d\n",ans[i]);
	return 0;
}
/*
7 5 3
2 5 7 5 1 5 6
6 6
1 3
4 6
2 4
3 4
*/