关于树套树在代码中的疑问
查看原帖
关于树套树在代码中的疑问
943489
Ghtl楼主2025/6/24 21:09

以下是代码,问题处标出了

#include<bits/stdc++.h>
#define int long long
using namespace std;
int K;
struct abc
{
	int a,b,c;
	bool operator ==(const abc &x) const
	{
		return (a==x.a&&b==x.b&&c==x.c);
	}
}arr[100005];
struct node
{
	int l,r,num;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define n(x) tree[x].num
}tree[200005<<7];
int pos[200005];
int root[200005];
int idx;
int d[200005];
int nd=0;
void update(int &id,int l,int r,int x,int k)
{
	if(!id) id=++idx;
//	n(id)+=k;
	if(l==r) 
	{
		n(id)+=k;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(l(id),l,mid,x,k);
//		cout<<"fsef        "<<r(id)<<'\n';
	}
	else
	{
		update(r(id),mid+1,r,x,k);
	}
	n(id)=n(l(id))+n(r(id));
}
void upd(int x,int y,int k)
{
	for(int i =x;i<=K;i+=(i&-i))
	{
		update(root[i],1,K,y,k);
	}
}
int query_rank(int l,int r,int val)
{
	int mid=(l+r)>>1;
	int sum=0;
	if(l>=r)
	{
		return 0;
	}
	if(val<mid)
	{
		for(int i =1;i<=nd;i++) d[i]=l(d[i]);
		return query_rank(l,mid,val);
	}
	else if(val==mid)
	{
		for(int i =1;i<=nd;i++) sum+=n(l(d[i]));
		return sum;
	}
	else
	{
		for(int i =1;i<=nd;i++) sum+=n(l(d[i]));
		for(int i =1;i<=nd;i++) d[i]=r(d[i]);
		return sum+query_rank(mid+1,r,val);
	}
}
int que_rank(int r,int k)
{
	nd=0;
	for(int i =r;i>=1;i-=(i&-i))
	{
		d[++nd]=root[i];
	}
	return query_rank(1,K,k);
}
bool cmp(abc x,abc y)
{
	if(x.a==y.a)
	{
		if(x.b==y.b) return x.c<y.c;
		return x.b<y.b;
	}
	return x.a<y.a;
}
int n,ans[100005];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>K;
	for(int i =1;i<=n;i++)
	{
		cin>>arr[i].a>>arr[i].b>>arr[i].c;
	}
	sort(arr+1,arr+n+1,cmp);
	K++;//--------------在这里-----------------
	for(int i =1;i<=n;i++)
	{
		int sum=1;
		while(arr[i]==arr[i+1])
		{
			sum++;
			i++;
		}
		upd(arr[i].b,arr[i].c,sum);
		ans[que_rank(arr[i].b,arr[i].c)-1]+=sum;
//		cout<<que_rank(arr[i].b,arr[i].c)-1<<'\n';
	}
	for(int i =0;i<n;i++)
	{
		cout<<ans[i]<<'\n';
	}
	return 0;
}

本人调试时为了方便将K++,后来却发现改完后样例过了,并没有找到原因所在,求助大佬orz%%%

2025/6/24 21:09
加载中...