//值域线段树
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 32010;
ll int ans[N];
struct ty
{
int l,r;
int sum;
}t[4*N];
struct tyy
{
int x,y;
}a[N];
void build(int p,int l,int r)//建树
{
t[p].l=l;
t[p].r=r;
if(l==r)
{
t[p].sum=0;//只剩最后一个就把值
return; //return的意思是结束,直接退出
}
int mid=(l+r)>>1;
build(2*p,l,mid);//建立左子树
build(2*p+1,mid+1,r);//建立右子树
t[p].sum = t[p*2].sum + t[p*2+1].sum;//这个节点建完再维护线段树的值
}
void change(int p,int x)//,int y,int z)//区间修改
{
if(t[p].l==t[p].r)
{
t[p].sum++;//记数
return;
}
int mid=(t[p].l+t[p].r)>>1;
if(x<=mid) change(p*2,x);//,y,z);//区间的范围是一直不变的,直到有返回值为止
// if(y>mid) change(p*2+1,x,y,z);
else change(p*2+1,x);//,y,z);
t[p].sum = t[p*2].sum + t[p*2+1].sum;//更新数据
}
ll int query(int p,int x,int y) //区间查询
{
if(x<=t[p].l && y>=t[p].r)//直接增加懒标记
return t[p].sum;
int mid=(t[p].l+t[p].r)>>1;
ll int ans=0;//这里用的是递归的原理把这个返回去
if(x<=mid) ans += query(p*2,x,y);//区间的范围是一直不变的,直到有返回值为止
if(y>mid) ans += query(p*2+1,x,y);
return ans;
}
bool cmp(tyy a,tyy b)
{
if(a.y==b.y) return a.x<b.x;
return a.y<b.y;
}
int main()
{
int n;
cin>>n;
if(n==0)
{
cout<<0<<endl;
return 0;
}
build(1,1,32000);
for(int i=1;i<=n;i++)
{
int x,y;
scanf("%d%d",&a[i].x,&a[i].y);
// ans[query(1,1,a[i].x)]++;
// change(1,a[i].x);//单点添加
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
ans[query(1,1,a[i].x)]++;
change(1,a[i].x);//单点添加
}
for(int i=0;i<n;i++)
printf("%lld\n",ans[i]);
return 0;
}
全部评论
(2) 回帖