树状数组POJ2352星星

这道题的题意对于住学者应该比较难理解，但是如果弄明白他的意思的话，你就会发现这就是赤裸裸的树状数组，哎，欺负我不懂是吧，当时读题读啦好久，好啦，下面说一下他的意思吧。。

由于题目已经说明y的坐标是递增顺序，所以直接考虑x的坐标就可以啦。每次当有x输入时，都求出sum（x+1）的值（注意呦，在树状数组中，可是从1开始的，而题目中的输入是包含0的），并把result[sum（x+1)]++；再更新一下，就好啦啦啦啦。

还是要注意一点，用c++提交超时，还是用c吧！！！！！！！！！！！！！！！！

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<iostream>

 const int N=;

 using namespace std;

 int c[N+];

 int n;

 int lowbit(int i){

 return i&(-i);

 }

 void add(int i,int x)

 {

     while(i<=N){

         c[i]+=x;

         i+=lowbit(i);

     }

 }

 int sum(int i)

 {

     int s=;

     while(i>){

         s+=c[i];

         i-=lowbit(i);

     }

     return s;

 }

 int main(){

 int a,b;

 int result[N];

 scanf("%d",&n);

        //memset(result,0,sizeof(result));

         //memset(c,0,sizeof(c));

     for(int i=;i<n;i++){

         scanf("%d%d",&a,&b);

         int temp=sum(a+);

         result[temp]++;

          add(a+,);

     }

     for(int i=;i<n;i++){

         cout<<result[i]<<endl;

     }

 }

巴特西

树状数组POJ2352星星

最新文章

热门文章