1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| ll n,k,qe;
ll ans[maxn];
ll num[maxn];
int lowbit(int x)
{
return x&(-x);
}
ll getsum(ll x)
{
ll ans = 0;
while(x>0)
{
ans+=num[x];
x-=lowbit(x);
}
return ans;
}
ll add(int x,int v)
{
int up=n;
while(x<=up)
{
num[x]+=v;
x+=lowbit(x);
}
return x;
}
struct Q{
int le;
int ri;
int id;
}q[maxn];
int pos[maxn];
bool cmp(Q & a, Q & b) {
return pos[a.le]<pos[b.le] || (pos[a.le]==pos[b.le] && a.ri<b.ri);
}
ll v[maxn],vle[maxn],vri[maxn],vit[maxn];
map<ll,ll>hax;
set<ll>t;
void solve() {
slla(n),slla(k),slla(qe);
repp(i,1,n) {
slla(v[i]);
t.insert(v[i]);
t.insert(v[i]+k);
t.insert(v[i]-k);
}
int cnt = 0;
for(auto it:t){
cnt++;
hax[it]=cnt;
}
repp(i,1,n) {
vit[i] = hax[v[i]];
vle[i] = hax[v[i]-k];
vri[i] = hax[v[i]+k];
}
repp(i,1,qe) {
sa(q[i].le);
sa(q[i].ri);
q[i].le++;
q[i].ri++;
q[i].id=i;
}
int bk = ceil(sqrt(1.0*n));
for (int i = 1; i <= n; i++)
{
pos[i] = (i - 1) / bk + 1;
}
sort(q+1,q+qe+1,cmp);
int pl = 1;
int pr = 0;
ll cur = 0;
repp(i,1,qe) {
while(pl<q[i].le) {
int val = vit[pl];
add(val,-1);
cur-=(getsum(vri[pl]) - getsum(vle[pl]-1));
pl++;
}
while(pl>q[i].le) {
pl--;
int val = vit[pl];
cur += (getsum(vri[pl]) - getsum(vle[pl]-1));
add(val,1);
}
while(pr < q[i].ri) {
pr++;
int val = vit[pr];
cur += (getsum(vri[pr]) - getsum(vle[pr]-1));
add(val,1);
}
while(pr>q[i].ri) {
int val = vit[pr];
add(val,-1);
cur -= (getsum(vri[pr]) - getsum(vle[pr]-1));
pr--;
}
ans[q[i].id] = cur;
}
repp(i,1,qe) {
printf("%lld\n",ans[i]);
}
}
|