icontofig | 发布于 2019-05-19 21:03:32 | 阅读量 414 | 莫队 树状数组

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e5+5;
map<int,int>usp;
int n,m,k;
int c[maxn];
struct qarea{
int l,r,id;
}q[maxn];
int sum[maxn];
int belong[maxn];
bool cmp(qarea a,qarea b){
return ((belong[a.l] == belong[b.l]) ? (a.r < b.r) : (a.l < b.l));
}
int a[maxn][3];
int lowbit(int x){
return (x & -x);
}
void update(int now,int d){
for(int i = now;i < maxn;i += lowbit(i)){
c[i] += d;
}
return;
}
int query(int now){
int ret = 0;
int x = now;
while(x > 0){
ret += c[x];
x -= lowbit(x);
}
return ret;
}
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
struct data{
int v,id,type;
}b[maxn];
bool cmp2(data x,data y){
return x.v < y.v;
}
const int INF = 2e9+5;
int main(){
n = get_num();
m = get_num();
k = get_num();
for(int i = 1;i <= n;++i){
a[i][1] = get_num();
b[i].v = a[i][1];b[i].id = i;b[i].type = 1;
b[i+n].v = b[i].v - k;b[i+n].id = i;b[i+n].type = 0;
b[i+2*n].v = b[i].v + k;b[i+2*n].id = i;b[i+2*n].type = 2;
}
sort(b+1,b+3*n+1,cmp2);
int cnt = 0;
int pre = -INF;
for(int i = 1;i <= 3*n;++i){
if(b[i].v != pre){
cnt++;
pre = b[i].v;
b[i].v = cnt;
}
else b[i].v = cnt;
}
for(int i = 1;i <= 3*n;++i){
a[b[i].id][b[i].type] = b[i].v;
}
int pp = sqrt(n);
for(int i = 1;i <= n;++i){
belong[i] = i / pp;
}
for(int i = 1;i <= m;++i){
q[i].l = get_num();
q[i].r = get_num();
q[i].id = i;
}
sort(q+1,q+m+1,cmp);
int l = 1;
int r = 0;
int ans = 0;
for(int i = 1;i <= m;++i){
while(q[i].l > l){
update(a[l][1],-1);
ans -= (query(a[l][2]) - query(a[l][0]-1));
l++;
}
while(q[i].l < l){
l--;
ans += query(a[l][2]) - query(a[l][0]-1);
update(a[l][1],1);
}
while(q[i].r > r){
r++;
ans += query(a[r][2]) - query(a[r][0]-1);
update(a[r][1],1);
}
while(q[i].r < r){
update(a[r][1],-1);
ans -= (query(a[r][2])-query(a[r][0]-1));
r--;
}
sum[q[i].id] = ans;
}
for(int i = 1;i <= m;++i){
printf("%d\n",sum[i]);
}
return 0;
}

414 人读过

0 条评论