POJ 2352 Stars 【线段树】

题目来源：http://poj.org/problem?id=2352

★这题我一开始题目都理解不了awa 后来经过同学指点才知道意思 但是知道也没用 还是不会写~

感觉就是线段树没学进骨子里，看不出这题是线段树awa 加油~

题意：

大概就是输出 0 到 n-1 level层所有的点数,一个点的左下方（包括左下的线上）有多少个点就是多少层

思路：

题目已经以y从小到大排好序了，我们想象一个原点（0,0）出来，把每个星星与原点作为矩形的对顶点形成一个矩形，只要数矩形里面有多少星星就好了，把这想象成 线段树 就是：

以x轴为线 建树（不知道说的规范不）,然后要一边输入 一边更新点 更新一个点询问一次 (因为如果你一次性的把点更新完了再查询 会出现level 比实际大 的情况, 举个例子：有个点（1,1） 和 （1,2） 这两个点横坐标都是x，你更新完就直接加2了，到时候查询（1,1）点时 直接把（1,2）也算进去了 算多了）

注意：

在update函数里面 l==r时的特判（看代码部分）不能让sum[k]=1 ,别忘了这 不是一层

例子：（1,1）点 和 （1,2）点 开始查询（1,1）点可能没问题 但是 后面更新（1,2）点时 sum[k]还是等于 1 （实际应该等于2），所以后面就错了，关键就是y不是相同的 后面会增大

然后查询的时候别忘了把自己一个减掉~

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<string>
#include<map>
using namespace std;
const int maxn=4e4+5;
const int mod=1e9+7;
typedef long long ll;
int n,m,maxx,y;
int sum[maxn<<2];
int level[maxn],x[maxn];
inline void read(int &x)   //读入优化
{
    char c;x=1;
    while((c=getchar())<'0'||c>'9') if(c=='-') x=-1;
    int res=c-'0';
    while((c=getchar())>='0'&&c<='9') res=res*10+c-'0';
    x*=res;
}
void update(int k,int l,int r,int x)
{
     if(l==r) {sum[k]++;return ;}  //这里不是sum[k]=1;
     int mid=l+r>>1;
     if(mid>=x) update(k<<1,l,mid,x);
     else update(k<<1|1,mid+1,r,x);
     sum[k]=sum[k<<1]+sum[k<<1|1];
}
int query(int k,int l,int r,int x,int y)
{
    if(x<=l&&r<=y) return sum[k];
    int mid=l+r>>1;
    int ans=0;
    if(mid>=x) ans+=query(k<<1,l,mid,x,y);
    if(mid<y) ans+=query(k<<1|1,mid+1,r,x,y);
    return ans;
}
int main()
{
    while(~scanf("%d",&n)){
    maxx=0;
    memset(level,0,sizeof level);
    memset(sum,0,sizeof sum);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x[i],&y);
        if(maxx<x[i]) maxx=x[i];             //找x坐标最大值建树
    }
    for(int i=1;i<=n;i++){
        update(1,0,maxx,x[i]);                   //边更新边查询
//        for(int i=1;i<=maxx<<1;i++) cout<<sum[i]<<' ';
//        cout<<query(1,0,maxx,0,x[i])<<endl;
            level[query(1,0,maxx,0,x[i])-1]++;   //减掉自己的一个
        }
        for(int i=0;i<n;i++) cout<<level[i]<<endl;
    }
    return 0;
}