hdu2492 数状数组或者线段树

题意:

     给你一些人,每个人有自己的攻击力,输入的顺序就是每个人的顺序,他们之间互相比赛,两个人比赛的条件是必须在他们两个位置之间找到一个人当裁判,这个裁判的攻击力必须在他们两个人之间,问你最多能矩形多少场比赛。

思路:

      枚举每一个点当裁判,线段树或者树状数组正着跑一遍记录大于等于当前点和小于等于当前点的个数,然后倒着跑一边,做同样处理,最后乘一下就行了。


#include<stdio.h>
#include<string.h>

__int64
num[110000] ,G[110000];
__int64
L1[110000] ,R1[110000] ,L2[110000] ,R2[110000]; int lowbit(int x)
{
return
x & -x;
} void
update(int x ,__int64 a)
{
for(int
i = x ;i <= 100050 ;i += lowbit(i))
num[i] += a;
} __int64
get_sum(int x)
{
__int64
sum = 0;
for(int
i = x ;i > 0 ;i -= lowbit(i))
sum += num[i];
return
sum;
} int main ()
{
int
i ,t ,n;
scanf("%d" ,&t);
while(
t--)
{

scanf("%d" ,&n);
for(
i = 1 ;i <= n ;i ++)
scanf("%I64d" ,&G[i]);
memset(num ,0 ,sizeof(num));
for(
i = 1 ;i <= n ;i ++)
{

L1[i] = get_sum(G[i]);
R1[i] = get_sum(100005) - get_sum(G[i] - 1);
update(G[i] ,1);
}

memset(num ,0 ,sizeof(num));
for(
i = n ;i >= 1 ;i --)
{

L2[i] = get_sum(G[i]);
R2[i] = get_sum(100005) - get_sum(G[i] - 1);
update(G[i] ,1);
} __int64
sum = 0;
for(
i = 1 ;i <= n ;i ++)
sum += L1[i] * R2[i] + L2[i] * R1[i];
printf("%I64d\n" ,sum);
}
return
0;
}
上一篇:原生javascript难点总结(1)---面向对象分析以及带来的思考


下一篇:poj 3281 最大流建图