URAL1028[Stars]

线段树,不习惯啊,写着很累。多亏有WSC的CODE做参考。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-3-19


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


using std::find;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int oo=32000;


      int N;


      vector<pair<int,int> > point;


      void insert(vector<int>& st,int where,int l,int r,int in)


      {


           if (l<=in&&in<=r) st[where-1]++;


           if (l>=r) return;


           int mid=(l+r)/2;


           if (l<=in&&in<=mid) insert(st,where*2,l,mid,in);


           if (mid+1<=in&&in<=r) insert(st,where*2+1,mid+1,r,in);


      }


      int ask(vector<int>& st,int where,int l,int r,int as)


      {


          if (r<=as) return st[where-1];


          else


          {


              if (l>=r) return 0;


              int mid=(l+r)/2;


              int get=0;


              if (l<=as) get+=ask(st,where*2,l,mid,as);


              if (mid+1<=as) get+=ask(st,where*2+1,mid+1,r,as);


              return get;


          }


      }


      public:


      Application()


      {


                    cin>>N;


                    point.resize(N);


                    for (int i=0;i<N;i++)


                        cin>>point[i].first>>point[i].second;


      }


      int run()


      {


          vector<int> counter(N,0);


          vector<int> st(oo*4);


          for (int i=0;i<N;i++)


          {


              counter[ask(st,1,0,oo,point[i].first)]++;


              insert(st,1,0,oo,point[i].first);


          }


          for (int i=0;i<N;i++)


              cout<<counter[i]<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}