程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> cf 61E. Enemy is weak 樹狀數組求逆序數

cf 61E. Enemy is weak 樹狀數組求逆序數

編輯:C++入門知識

求出每個位置左邊有幾個比它大,右邊有幾個比它小,然後乘法原理加起來就夠了。

大於小於什麼的用樹狀數組YY一下就出來了。

#include
#include
#include
#include
#include
#include
using namespace std;
int n;
int c[2000000];
struct node
{
    int x;
    int id;
}a[2000000];
bool cmp(node x,node y)
{
    return x.x0)
    {
         sum+=c[n];
         n=n-lowbit(n);
    }
    return sum;
}
void change(int i,int x)
{
     while(i<=n)
     {
          c[i]=c[i]+x;
          i=i+lowbit(i);
     }
}
int main()
{
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].x);
            a[i].id=i;
        }
        sort(a+1,a+1+n,cmp);
        for(int i=1;i<=n;i++) mp[a[i].id]=i;

        for(int i=1;i<=n;i++)
        {
            change(mp[i],1);
            ls[mp[i]]=Sum(mp[i])-1;
            lb[mp[i]]=i-ls[mp[i]]-1;
        }
        long long ans=0;
//        for(int i=1;i<=n;i++)
//        {
//            printf("%d ",lb[mp[i]]);
//        }
//        puts("");
//        for(int i=1;i<=n;i++)
//        {
//            printf("%d ",ls[mp[i]]);
//        }
        for(int i=1;i<=n;i++)
        {
            rs[mp[i]]=(mp[i]-1-ls[mp[i]]);
            ans+=rs[mp[i]]*lb[mp[i]];
        }
        cout<

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved