专栏首页小樱的经验随笔UESTC 1584 Washi与Sonochi的约定【树状数组裸题+排序】

UESTC 1584 Washi与Sonochi的约定【树状数组裸题+排序】

题目链接:UESTC 1584 Washi与Sonochi的约定

题意:在二维平面上,某个点的ranked被定义为x坐标不大于其x坐标,且y坐标不大于其y坐标的怪物的数量。(不含其自身),要求输出n行,每行一个整数,分别代表rank为0~n^1的怪物数量。

分析:树状数组+排序,其实就是道树状数组的裸题,和poj2352是同题,套个板子就可以过 思路就是把所有的坐标读入之后,按照x为第优先级,y为第二优先级,都是从小到大排序,只从从0~n-1扫一遍,此时(i时)树状数组里的点的x值,

都不比val[i].x大,//这题所有坐标都不同。所以get(val[i].y)即可得到,所有x坐标不大于vali,且y坐标小于vali的坐标(点)的个数, 然后把val[i].y插入到树状数组里。扫一遍即可得到所有答案,复杂度 O(nlogn)!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int MAXN=100010;
 5 struct p
 6 {
 7     int x, y;
 8 }val[MAXN];
 9 inline int read()
10 {
11     int x=0,f=1;
12     char ch=getchar();
13     while(ch<'0'||ch>'9')
14     {
15         if(ch=='-')
16             f=-1;
17         ch=getchar();
18     }
19     while(ch>='0'&&ch<='9')
20     {
21         x=x*10+ch-'0';
22         ch=getchar();
23     }
24     return x*f;
25 }
26 inline void write(int x)
27 {
28     if(x<0)
29     {
30         putchar('-');
31         x=-x;
32     }
33     if(x>9)
34     {
35         write(x/10);
36     }
37     putchar(x%10+'0');
38 }
39 inline bool cmp(const p &a,const p &b)
40 {
41     if(a.x!=b.x) return a.x<b.x;
42     else return a.y<b.y;
43 }
44 int ranked[MAXN<<1];
45 int Tree[MAXN<<1];
46 inline int lowbit(int x)
47 {
48     return (x&-x);
49 }
50 inline void add(int x,int value)
51 {
52     for(int i=x;i<MAXN;i+=lowbit(i))
53         Tree[i]+=value;
54 }
55 inline int get(int x)
56 {
57     int res=0;
58     for(int i=x;i;i-=lowbit(i))
59     {
60         res+=Tree[i];
61     }
62     return res;
63 }
64 int main()
65 {
66     int n;
67     n=read();
68     for(int i=0;i<n;i++)
69     {
70         scanf("%d%d",&val[i].x,&val[i].y);
71     }
72     sort(val,val+n,cmp);
73     for(int i=0;i<n;i++)
74     {
75         ranked[get(val[i].y)]++;
76         add(val[i].y, 1);
77     }
78     for(int i=0;i<n;i++)
79         printf("%d\n", ranked[i]);
80     cout<<endl;
81     return 0;
82 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 并查集(个人模版)

    并查集: 1 int find(int a) 2 { 3 int r=a; 4 while(f[r]!=r) 5 ...

    Angel_Kitty
  • 2017广东工业大学程序设计竞赛决赛 题解&源码(A,数学解方程,B,贪心博弈,C,递归,D,水,E,贪心,面试题,F,贪心,枚举,LCA,G,dp,记忆化搜索,H,思维题)

    心得: 这比赛真的是不要不要的,pending了一下午,也不知道对错,直接做过去就是了,也没有管太多! Problem A: 两只老虎 Description ...

    Angel_Kitty
  • Kruscal(最小生成树)算法模版

    1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m...

    Angel_Kitty
  • 01:数制转换

    01:数制转换 总时间限制: 1000ms 内存限制: 65536kB描述 求任意两个不同进制非负整数的转换(2进制~16进制),所给整数在long所能表达...

    attack
  • C语言中一些不被熟知的特性

    限定词restricted用于限定一个指针(如名,告诉编译器该指针的内存访问在任何情况下都只能通过该指针进行,其余指向无效.如

    racaljk
  • 浙大版《C语言程序设计(第3版)》题目集 习题5-2 使用函数求奇数和

    其中函数even将根据用户传入的参数n的奇偶性返回相应值:当n为偶数时返回1,否则返回0。函数OddSum负责计算并返回传入的N个整数List[]中所有奇数的和...

    C you again 的博客
  • Java经典编程50题(面试笔试机试)

    https://blog.csdn.net/alias_fa/article/details/52985112

    林万程
  • 洛谷P4725 【模板】多项式对数函数(多项式ln)

    可以直接对两边求导\(G'(A(x)) = F'(A(x))A'(x) = \frac{A(x)}{A'(x)}\)

    attack
  • 浙大版《C语言程序设计(第3版)》题目集 习题4-6 水仙花数

    水仙花数是指一个N位正整数(N≥3),它的每个位上的数字的N次幂之和等于它本身。例如:153=13+53+33。 本题要求编写程序,计算所有N位水仙花数。

    C you again 的博客
  • 排序算法——一篇文章搞懂常用的排序算法

    排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记...

    海盗船长

扫码关注云+社区

领取腾讯云代金券