[fjwc2015]Screen [从hzw神犇那里扒来的题]

【题目描述】

码农有一块超新星屏幕，它有N个像素点，每个像素点有亮度和灰度两个参数，记为I和H, 范围都是0~32000.

一天，码农突发奇想，想知道哪个点比较容易亮瞎眼睛。为此，他定义了一个瞎眼指数: 瞎眼指数就是灰度和亮度均不大于该像素点的像素个数。

现在，码农希望知道，瞎眼指数为0~N-1的像素点分别有多少个

【输入格式】

第一行一个数字N，代表有N个像素点。接下来N行，每行两个数字,代表该像素点的亮度和灰度。

N个像素的亮度和灰度。像素按照灰度从小到大的顺序给出，（0 <= I, H <= 32000, N < 20000）

【输出格式】

输出：瞎眼指数从0到H-1之间各等级的像素个数。

【样例输入】

1 1

5 1

7 1

3 3

5 5

【样例输出】

排序树状数组。

先按亮度从小到大排好序，这样扫到一个点的时候，之前处理过的点亮度都不大于它。

然后用树状数组标记灰度，然后统计……

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 using namespace std;

 const int mxn=;

 struct point{

     int l,h;

 }d[mxn];

 int a[mxn];

 int ans[mxn];

 int n;

 int cmp(point a,point b){

     if(a.l==b.l)return a.h<b.h;

     return a.l<b.l;

 }

  inline int lowbit(int x){

     return x&-x;

 }

 void add(int p,int x){

     while(p<=n){

         a[p]+=x;

         p+=lowbit(p);

     }

 }

 int ask(int x){

     int res=;

     while(x){

         res+=a[x];

         x-=lowbit(x);

     }

     return res;

 }

 int main(){

     scanf("%d",&n);

     int i,j;

     for(i=;i<=n;i++)scanf("%d%d",&d[i].l,&d[i].h);

     sort(d+,d+n+,cmp);

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

         int tmp=ask(d[i].h);

         add(d[i].h,);

         ans[tmp]++;

     }

     for(i=;i<n;i++)printf("%d\n",ans[i]);

 }

巴特西

[fjwc2015]Screen [从hzw神犇那里扒来的题]

最新文章

热门文章