poj 3928 树状数组

时间：2021-07-05 23:34:06

题目中只n个人，每个人有一个ID和一个技能值，一场比赛需要两个选手和一个裁判，只有当裁判的ID和技能值都在两个选手之间的时候才能进行一场比赛，现在问一共能组织多少场比赛。

由于排完序之后，先插入的一定是小的，所以左右两边的大于小于都能确定，用树状数组维护选手的id

Sample Input
1
3 1 2 3
Sample Output
1

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<queue>

 using namespace std;

 int n,m,t;

 const int maxn=;

 __int64 c[maxn];

 struct node

 {

     int x,id;

 }p[maxn+];

 bool cmp(node a,node b)

 {

     return a.x<=b.x;

 }

 int lowbit(int i)

 {

     return i&(-i);

 }

 void add(int i,__int64 d)

 {

     while(i<=maxn)

     {

         c[i]+=d;

         i+=lowbit(i);

     }

 }

 __int64 sum(int i)

 {

     __int64 ret=;

     while(i)

     {

         ret+=c[i];

         i-=lowbit(i);

     }

     return ret;

 }

 int main()

 {

     int i,j,k;

     __int64 lmin,lmax,rmin,rmax,ans=;

     //freopen("1.in","r",stdin);

     scanf("%d",&t);

     while(t--)

     {

         for(i=;i<=maxn;i++) c[i]=;

         scanf("%d",&n);

         for(i=;i<=n;i++)   scanf("%d",&p[i].x),p[i].id=i;

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

         add(p[].id,);

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

         {

             lmin=sum(p[i].id-);        //计数是从1到i-1，故要多减一个1

             lmax=p[i].id--lmin;

             //printf("%I64d %I64d ",lmin,lmax);

             rmin=sum(n)-sum(p[i].id);

             rmax=n-p[i].id-rmin;

             //printf("%I64d %I64d \n",rmin,rmax);

             ans+=(lmin*rmax+rmin*lmax);  add(p[i].id,);

             //printf("%I64d\n",ans);

         }

         printf("%I64d\n",ans);

         ans=;

     }

     return ;

 }

相关文章