CDQ分治求调
查看原帖
CDQ分治求调
285617
黑影洞人楼主2022/8/19 23:06
#include<cstdio>
#include<algorithm>
#define N 414514
using namespace std;
int n,m,tot,res[N];
struct question{
	int t,l,r,typ,ans;
	bool operator<(const question &a)const{return t<a.t;}
}q[N],tmp[N];
struct bit{
	int t[N];
	int lowbit(int x){return x&-x;}
	void add(int x,int v){for(;x<=n;x+=lowbit(x))t[x]+=v;}
	int query(int x){
		int ans=0;
		for(;x;x-=lowbit(x))ans+=t[x];
		return ans;
	}
	void assign(int x,int v){for(;x<=n;x+=lowbit(x))t[x]=v;}
}b;
void cdq(int l,int r){
	//puts("xx");
	if(l==r)return;
	int mid=(l+r)/2;
	cdq(l,mid),cdq(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(q[i].l<=q[j].l){
			if(q[i].typ==1)b.add(q[i].r,1);
			tmp[k++]=q[i++];
		}else{
			if(q[j].typ==2)q[j].ans+=b.query(n)-b.query(q[j].r-1);
			tmp[k++]=q[j++];
		}
	}
	while(i<=mid){
		if(q[i].typ==1)b.add(q[i].r,1);
		tmp[k++]=q[i++];
	}
	while(j<=r){
		if(q[j].typ==2)q[j].ans+=b.query(n)-b.query(q[j].r-1);
		tmp[k++]=q[j++];
	}
	for(int i=l;i<=mid;i++)b.assign(q[i].r,0);
	for(int i=l;i<=r;i++)q[i]=tmp[i];
}
signed main(){
	//freopen("P2184_1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int op,l,r;
		scanf("%d%d%d",&op,&l,&r);
		q[i]={i,l,r,op};
	}
	cdq(1,m);sort(q+1,q+m+1);
	for(int i=1;i<=m;i++)if(q[i].typ==2)printf("%d\n",q[i].ans);
	return 0;
}



验证码war9祭

2022/8/19 23:06
加载中...