Stars HDU - 1541

深碍√TFBOYSˉ_ 2022-01-06 12:47 355阅读 0赞

HDU - 1541

思路：二维偏序，一维排序，一维树状数组查询即可。

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define maxn 33333
  4. int ans[maxn],n,sum[maxn];
  5. int lowbit(int x)
  6. {
  7.     return x&(-x);
  8. }
  9. struct node
  10. {
  11.     int x,y;
  12.     bool operator < (const node &b)const
  13.     {
  14.         if(x==b.x)return y<b.y;
  15.         return x<b.x;
  16.     }
  17. } a[maxn];
  18. void add(int x,int d)
  19. {
  20.     while(x<=32001)
  21.     {
  22.         sum[x]+=d;
  23.         x+=lowbit(x);
  24.     }
  25. }
  26. int getsum(int x)
  27. {
  28.     int ret=0;
  29.     while(x>0)
  30.     {
  31.         ret+=sum[x];
  32.         x-=lowbit(x);
  33.     }
  34.     return ret;
  35. }
  36. int main()
  37. {
  38.     while(scanf("%d",&n)!=EOF)
  39.     {
  40.         memset(sum,0,sizeof(sum));
  41.         memset(ans,0,sizeof(ans));
  42.         for(int i=1; i<=n; i++)
  43.             scanf("%d%d",&a[i].x,&a[i].y);
  44.         sort(a+1,a+1+n);
  45.         for(int i=1; i<=n; i++)
  46.         {
  47.             ans[getsum(a[i].y+1)]++;
  48.             add(a[i].y+1,1);
  49.         }
  50.         for(int i=0; i<n; i++)printf("%d\n",ans[i]);
  51.     }
  52.     return 0;
  53. }

　　

转载于:https://www.cnblogs.com/SDUTNING/p/10263960.html

发表评论

表情：
评论列表 （有 0 条评论，355人围观）

还没有评论，来说两句吧...

相关阅读

    相关 洛谷P1541 乌龟棋

    题目背景 小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。 题目描述 乌龟棋的棋盘是一行N个格子，每个格子上一个分数（非负整数）。棋盘第1格是唯一的起点，第N格是

    偏执的太偏执、偏执的太偏执、/ 0 赞/ 233 阅读