首页 > 其他 > 详细

莫队+离散化

时间:2021-09-02 15:40:42      阅读:16      评论:0      收藏:0      [点我收藏+]
#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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!