莫队+离散化

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5,M=5e5;
int n,m,k,maxn;
int a[N],b[N],c[N];
ll num[N];
ll curn;
int pre[N],pre2[N];
ll tree[N];
int l,r;
void add(int x,int y){
	for(;x<=N;x+=x&-x)tree[x]+=y;
}
ll ask(int x){
	ll ans=0;
	for(;x;x-=x&-x)ans+=tree[x];
	return ans;
}
struct query{
	int l,r,id;
	bool operator<(const query& q){
		if(l/maxn!=q.l/maxn)return l<q.l;
		return (l/maxn&1)?r<q.r:r>q.r;
	}
}q[N];
void add(int x){
	int down=pre[x],up=pre2[x];
	curn+=ask(up)-ask(down-1);
	add(c[x],1);
	
}
void del(int x){
	add(c[x],-1);
	int down=pre[x],up=pre2[x];
	curn-=ask(up)-ask(down-1);
	
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
		b[i+n]=a[i]-k;
		b[i+2*n]=a[i]+k; 
	}
	sort(b+1,b+3*n+1);
	int cnt=unique(b+1,b+3*n+1)-b-1;
	for(int i=1;i<=n;i++){
		c[i]=lower_bound(b+1,b+cnt+1,a[i])-b;
		pre[i]=lower_bound(b+1,b+cnt+1,a[i]-k)-b;
		pre2[i]=lower_bound(b+1,b+cnt+1,a[i]+k)-b;
	}
	for(int i=1;i<=n;i++)cout<<c[i]<<" "<<pre[i]<<" "<<pre2[i]<<endl;
	for(int i=0;i<m;i++){
		cin>>q[i].l>>q[i].r;
		q[i].id=i;	
	}
	sort(q,q+m);
	l=1,r=0;
	for(int i=0;i<m;i++){
		int cl=q[i].l,cr=q[i].r,id=q[i].id;
		while(l>cl)add(a[--l]);
		while(r<cr)add(a[++r]);
		while(l<cl)del(a[l++]);
		while(r>cr)del(a[r--]);
		num[id]=curn;
	}
	for(int i=0;i<m;i++)cout<<num[i]<<endl;
} 

莫队+离散化

原文：https://www.cnblogs.com/codjjj/p/15213895.html