题意
给你一个序列，多次询问，每次让你回答一个区间中差的绝对值不超过一个给定常数K的元素对数。
题解
首先分析下复杂度，
n
,
m
=
2.7
∗
1
0
4
n,m = 2.7*10^4
n,m=2.7∗104，莫队复杂度
n
3
2
n^{\frac{3}{2}}
n23，离散化复杂度
3
n
l
o
g
(
3
n
)
3nlog(3n)
3nlog(3n)，树状数组查询修改
l
o
g
(
3
n
)
∗
l
o
g
(
3
n
)
log(3n)*log(3n)
log(3n)∗log(3n)，大概在1e8，会TLE，所以需要预处理下查询的时候上下界的复杂度，省去一个
l
o
g
(
3
n
)
log(3n)
log(3n)。 对序列中所有元素+k，-k之后再一起离散化。然后使用莫队算法对询问进行分块。在移动的过程中，用树状数组维护答案。 对于add操作，应该先更新答案再维护树状数组。不然会包括自身。 对于del操作，应该先维护树状数组再更新答案。不然会多减去自身。 树状数组的维护就是简单的二维偏序问题。
代码
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std
;
#define FOR0(a,b) for(int i = a; i < b; ++i)
#define FORE(a,b) for(int i = a; i <= b; ++i)
typedef long long ll
;
typedef pair
<int,int> pii
;
const int maxn
= 2e5+5;
template <typename _Tp
> inline _Tp
read(_Tp
&x
){
char c11
=getchar(),ob
=0;x
=0;
while(c11
^'-'&&!isdigit(c11
))c11
=getchar();if(c11
=='-')c11
=getchar(),ob
=1;
while(isdigit(c11
))x
=x
*10+c11
-'0',c11
=getchar();if(ob
)x
=-x
;return x
;
}
int block
, ans
, cnt
[maxn
];
int n
,m
,a
[maxn
],Ans
[maxn
],k
, tot
, b
[maxn
],lt
[maxn
], rt
[maxn
];
int val
[maxn
];
struct node
{
int l
,r
,id
;
}q
[maxn
];
bool cmp(node a
, node b
) {
return (a
.l
/block
)^(b
.l
/block
)?a
.l
< b
.l
: (((a
.l
/block
)&1)?a
.r
<b
.r
:a
.r
>b
.r
);
}
int getid(int x
) {
return lower_bound(b
+1,b
+tot
+1,x
)-b
;
}
int lowbit(int x
) {
return x
&(-x
);
}
void update(int x
,int v
) {
while(x
<= tot
) {
val
[x
] += v
;
x
+= lowbit(x
);
}
}
int query(int x
) {
int ret
= 0;
while(x
) {
ret
+= val
[x
];
x
-= lowbit(x
);
}
return ret
;
}
void add(int x
) {
ans
+= query(rt
[x
])-query(lt
[x
]);
update(a
[x
],1);
}
void del(int x
) {
update(a
[x
],-1);
ans
-= query(rt
[x
])-query(lt
[x
]);
}
int main() {
read(n
); read(m
); read(k
);
for(int i
= 1; i
<= n
; ++i
) read(a
[i
]);
for(int i
= 1; i
<= m
; ++i
) {
read(q
[i
].l
); read(q
[i
].r
);
q
[i
].id
= i
;
}
block
= n
/sqrt(m
*2/3);
tot
= 1;
for(int i
= 1; i
<= n
; ++i
) {
b
[tot
] = a
[i
], b
[tot
+1] = a
[i
]+k
, b
[tot
+2] = a
[i
]-k
-1;
tot
+= 3;
}
sort(b
+1,b
+tot
);
tot
= unique(b
+1,b
+tot
)-b
-1;
sort(q
+1,q
+m
+1,cmp
);
for(int i
= 1; i
<= n
; ++i
) {
lt
[i
] = getid(a
[i
]-k
-1);
rt
[i
] = getid(a
[i
]+k
);
a
[i
] = getid(a
[i
]);
}
int l
= 1,r
= 0;
for(int i
= 1; i
<= m
; ++i
) {
int ql
= q
[i
].l
, qr
= q
[i
].r
;
while(r
< qr
) add(++r
);
while(r
> qr
) del(r
--);
while(l
< ql
) del(l
++);
while(l
> ql
) add(--l
);
Ans
[q
[i
].id
] = ans
;
}
for(int i
= 1; i
<= m
; ++i
)
printf("%d\n", Ans
[i
]);
return 0;
}
