http://acm.hdu.edu.cn/showproblem.php?pid=6534
题意:给你一个序列,多次询问,每次让你回答一个区间中差的绝对值不超过一个给定常数K的元素对数。
题解:对序列中的所有元素以及这些元素+K,-K后的值进行离散化。 然后使用莫队算法,在莫队算法的端点移动过程中,新加入一个元素x的过程中,将其插入树状数组,查询[x-K,x+K]范围的元素数即可。删除一个元素的过程与其类似。
C++版本一
题解:莫队+树状数组+离散化
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l[N],r[N],u,v;
int ans[N],cnt,flag,temp,tot;
int a[N],b[N],c[N],be[N];
char str;
struct node{
int l,r,id;
bool operator <(const node &S)const{
return (be[l] ^ be[S.l]) ? be[l] < be[S.l] : ((be[l] & 1) ? r < S.r : r > S.r);
}
}e[N];
int tree[N];
void add(int x,int C){
for(int i=x;i<=tot;i+=i&-i){
tree[i]+=C;
}
}
int sum(int x){
int res=0;
for(int i=x;i>0;i-=i&-i){
res+=tree[i];
}
return res;
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d%d%d",&n,&m,&k);
int sz = sqrt(n);
int bnum = ceil((double)n / sz);
for (int i = 1; i <= bnum; i++){
for (int j = (i - 1) * sz + 1; j <= i * sz; j++)
be[j] = i;
}
for(int i=1;i<=n;i++)scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
c[1]=b[1];
tot=1;
for(int i=2;i<=n;i++)if(b[i-1]!=b[i])c[++tot]=b[i];
for(int i=1;i<=m;i++){
scanf("%d%d",&e[i].l,&e[i].r);
e[i].id=i;
}
sort(e+1,e+m+1);
for (int i = 1; i <= n; i++){
l[i] = lower_bound(c+1,c+tot+1, a[i] - k) - c ;
r[i] = upper_bound(c+1,c+tot+1, a[i] + k) - c - 1;
a[i] = lower_bound(c+1,c+tot+1, a[i]) - c ;
}
int L = 1, R = 0, temp = 0;
for (int i = 1; i <= m; i++){
int ql = e[i].l, qr = e[i].r;
while(L < ql){
add(a[L], -1);
temp -= sum(r[L]) - sum(l[L] - 1);
L++;
}
while(L > ql){
L--;
temp += sum(r[L]) - sum(l[L] - 1);
add(a[L], 1);
}
while(R < qr){
R++;
temp += sum(r[R]) - sum(l[R] - 1);
add(a[R], 1);
}
while(R > qr){
add(a[R], -1);
temp -= sum(r[R]) - sum(l[R] - 1);
R--;
}
ans[e[i].id] = temp;
//cout<<L<<" "<<R<<endl;
//cout<<temp<<endl;
}
for(int i=1;i<=m;i++){
cout<<ans[i]<<endl;
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
/**/
/*
5 5 3
2 5 7 1 3
6 6
1 3
2 4
1 5
2 3
*/