现在的位置: 首页 > 综合 > 正文

poj 2481 Cows(树状数组)

2018年03月17日 ⁄ 综合 ⁄ 共 1164字 ⁄ 字号 评论关闭
题意:有N头牛 它个每个都有一个领域[S,E] 如果 Si <= Sj and Ej
<= Ei 的话,说明i牛比j牛strong 求对每头牛而言 有多少牛比它strong

思路:跟前一道2352 stars 想法差不多,给E降序排序,if
E相同,S升序,这样就转化到stars那道题了  不过这里要注意一个问题 Ei == Ej and
Si == Sj的情况,

//2120K  
 969MS
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define lowbit(x) (x&(-x))
#define M 100010
using namespace std;

int ar[M],Max,n;
struct data
{
    int
x,y,num;
}node[M];

int max (int a,int b)
{
    return a
> b? a:b;
}
bool cmp (const data &a,const data
&b)
{
    if (a.y
> b.y)
       
return true;
    if (a.y ==
b.y&&a.x <
b.x)
       
return true;
    return
false;
}

void add (int u)
{
    while (u
<=
Max)      
//发现加了Max这个优化没少几MS啊!!!
    {
       
ar[u] += 1;
       
u += lowbit(u);
    }
}

int sum (int u)
{
    int ans =
0;
    while (u
> 0)
    {
       
ans += ar[u];
       
u -= lowbit(u);
    }
    return
ans;
}
int main ()
{
    int
i,x,y,strong[M];
    while (scanf
("%d",&n)&&n)
    {
       
memset (ar,0,sizeof(ar));
       
Max = 0;
       
for (i = 0;i < n;i ++)
       
{
           
scanf ("%d%d",&x,&y);
           
node[i].x =
x+1;          
//加1处理 因为等于0时,0&(-0) 还是0
           
node[i].y = y+1;
           
node[i].num = i;
           
Max = max(Max,node[i].x);
       
}
       
sort (node,node + n,cmp);
       
int x0 = -1,y0 = -1;
       
int count = 0;
       
for (i = 0;i < n;i ++)
       
{
           
if (x0 == node[i].x&&y0 ==
node[i].y)  //相等的时候
  

抱歉!评论已关闭.