题解 | #[NOIP2004]合唱队形#

题目中的坐标给出序列是一个很好的序列。因为我们只需要找该点左下角的星星，那么后面给出的点必然不符合左下角的设定，所以只需要判断给出该点之前有多少个星星在其左下角。更准确的说，只需要判断多少个星星的x坐标<=当前星星的x坐标即可。

不会树状数组，还没学。用线段树写了一遍，还是比较基础的。

主要思路就是对于每一个读入的点，搜索一遍x坐标组成的线段树中有多少个区间在他之前即可。比如读入的x坐标为7，假设之前读入的x坐标区间[1,10]，那么第一个点的区间就是[1,10]，然后依次往下二分成左右子树区间，显然[1,5],[6,7]为最终找到的组成答案的区间。加起来即可。

具体看代码，代码中有注释吧。

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e4 + 5e3 + 7,rr=3e4+2e3+7;//rr表示的是x的最大坐标，也就是所构建的线段树的最大区间的端点值。
int ans[N],n,x,y,cnt=0,tmp=0,val[rr<<2];//val表示区间的值，应该开rr*4的大小，因为区间最大的端点值就是x的最大坐标值。
void serch(int p,int l,int r,int x)
{
    if (r <= x)//判断条件应当是r<=x的时候，l不用判，因为只考虑某个区间在x的左边即可。
    {
        tmp += val[p]; return;
    }
    int mid = l + r >> 1;
    serch(p << 1,l,mid,x);//左边区间必搜
    if (x >= mid + 1)serch(p<<1|1,mid+1,r,x);//右边区间需要判断x是否在这个区间
}
void build(int p,int l,int r,int x)
{
    if (l==r)//代表找到了x这个点
    {
        val[p]++;
        return;
    }
    int mid = l + r >> 1;
    if (x <= mid)build(p << 1, l, mid, x);
    else build(p << 1 | 1, mid + 1, r, x);
    val[p] = val[p << 1] + val[p << 1 | 1];//回溯赋值
}
int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        tmp = 0;//这是不考虑0的等级。每次要清零。
        scanf("%d%d",&x,&y);
        if (x == 0) { ans[cnt++]++; continue;}//此处用于特判x=0的情况，cnt表示x=0的星星的个数
        serch(1,1,rr,x);
        ans[tmp + cnt]++;//要额外考虑cnt，所以这里是tmp+cnt
        build(1,1,rr,x);
    }
    for (int i = 0; i < n; i++)printf("%d\n",ans[i]);
    return 0;
}

那么就让我们一起愉快地AC吧~