求助
查看原帖
求助
285617
黑影洞人楼主2024/12/8 15:09

这种写法为什么不对

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 414514
using namespace std;
int n,ans[N];
int a[N],bb[N],tot,kk;
void lsh(int *a,int n){
	for(int i=1;i<=n;i++)bb[i]=a[i];
	sort(bb+1,bb+n+1);kk=unique(bb+1,bb+n+1)-bb-1;
}
int query(int v){
	return lower_bound(bb+1,bb+kk+1,v)-bb;
}
struct bit{
	int t[N];
	void clear(){memset(t,0,sizeof(t));}
	int lowbit(int x){return x&-x;}
	void add(int x,int v){for(;x<=kk;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<=kk;x+=lowbit(x))t[x]=v;}
}b; 
struct Q{
	int l,r,k;
	int lk,rk;//l+k,r-k
	int id;
	bool operator<(const Q &a)const{return k==a.k?id<a.id:k<a.k;}
}q[N],tmp[N]; 
void cdq(int l,int r){
	if(l==r)return;
	int mid=(l+r)/2;
	int i=l,j=mid+1,k=l;
	cdq(l,mid);cdq(mid+1,r);
	while(i<=mid&&j<=r){
		if(q[j].r>=q[i].lk){
			if(q[j].id>n)b.add(q[j].l,1);
			tmp[k++]=q[j++];
		}else{
			if(q[i].id<=n)ans[q[i].id]+=b.query(q[i].rk);
			tmp[k++]=q[i++];
		}
	}
	while(j<=r){
		if(q[j].id>n)b.add(q[j].l,1);
		tmp[k++]=q[j++];
	}
	while(i<=mid){
		if(q[i].id<=n)ans[q[i].id]+=b.query(q[i].rk);
		tmp[k++]=q[i++];
	}
	for(int i=mid+1;i<=r;i++)if(q[i].id>n)b.assign(q[i].l,0);
	for(int i=l;i<=r;i++)q[i]=tmp[i];
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		q[i]=(Q){l,r,k,l+k,r-k,i};
		a[++tot]=l;
		a[++tot]=r-k;
	}
	lsh(a,tot); 
	for(int i=1;i<=n;i++){
		q[i].l=query(q[i].l);
		q[i].rk=query(q[i].rk);
		q[n+i]=q[i];
		q[n+i].k=q[i].r-q[i].l;
		q[n+i].id=n+i;
	}
	sort(q+1,q+n+n+1);
	cdq(1,2*n);
	for(int i=1;i<=n;i++)printf("%d\n",ans[i]-1);
	return 0;
}



2024/12/8 15:09
加载中...