树状数组 POJ 2481 Cows

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 const int MAX_N = 100000 + 10;
  7 int cnt[MAX_N];
  8 int ans[MAX_N];
  9 int maxn = -1;
 10 struct node
 11 {
 12     int s, e;
 13     int id;
 14 }cow[MAX_N];
 15 
 16 inline int read(void)
 17 {
 18     int x = 0, f = 1;    char ch = getchar ();
 19     while (ch < ‘0‘ || ch > ‘9‘)    {if (ch == ‘-‘)    f = -1;    ch = getchar ();}
 20     while (ch >= ‘0‘ && ch <= ‘9‘)    {x = x * 10 + ch - ‘0‘;    ch = getchar ();}
 21     return x * f;
 22 }
 23 
 24 inline void print(int x)
 25 {
 26     if (x < 0)    {putchar (‘-‘);    x = -x;}
 27     if (x > 9)    print (x / 10);
 28     putchar (x % 10 + ‘0‘);
 29 }
 30 
 31 bool cmp(node x, node y)        //先对e从大到小排序
 32 {
 33     if (x.e == y.e)
 34         return x.s < y.s;        //如果如果相等，再按s从小到大排序
 35     else
 36         return x.e > y.e;
 37 }
 38 
 39 int lowbit(int t)        //求 2^t
 40 {
 41     //return t & (t ^ (t - 1));
 42     return t & (-t);
 43 }
 44 
 45 void plus(int x)
 46 {
 47     while (x <= maxn)
 48     {
 49         ans[x]++;                //记录强壮的牛数
 50         x += lowbit (x);
 51     }
 52 }
 53 
 54 int sum(int x)                    //统计前x项强壮的牛数
 55 {
 56     int sum = 0;
 57     while (x > 0)
 58     {
 59         sum += ans[x];
 60         x -= lowbit(x);
 61     }
 62     return sum;
 63 }
 64 
 65 int main(void)        //POJ 2481 Cows
 66 {
 67     //freopen ("inH.txt", "r", stdin);
 68     int n;
 69 
 70     while (scanf ("%d", &n) && n)
 71     {
 72         for (int i=1; i<=n; ++i)
 73         {
 74             cow[i].s = read ();    cow[i].e = read ();        //读入外挂优化
 75             //scanf ("%d%d", &cow[i].s, &cow[i].e);
 76             cow[i].id = i;
 77             maxn = max (maxn, cow[i].e);
 78         }
 79         memset (ans, 0, sizeof (ans));
 80         sort (cow+1, cow+n+1, cmp);
 81         for (int i=1; i<=n; ++i)
 82         {
 83             if (cow[i].e == cow[i-1].e && cow[i].s == cow[i-1].s)        //如果值相等，不加入统计
 84                 cnt[cow[i].id] = cnt[cow[i-1].id];
 85             else
 86             {
 87                 cnt[cow[i].id] = sum (cow[i].s + 1);                    //第id的牛有多少比它强壮
 88             }
 89             plus (cow[i].s + 1);
 90         }
 91         int j;
 92         for (j=1; j<n; ++j)
 93         {
 94             print (cnt[j]);    putchar (‘ ‘);        //输出外挂优化
 95             //printf ("%d ", cnt[j]); 
 96         }
 97         printf ("%d\n", cnt[j]);
 98     }
 99 
100     return 0;
101 }