朗格拉日计数(counter)

题目描述

在平面上以圆周等分排列着n个带标号(标号为1～n）的点，你需要计算有多少个三元组(a,b,c)，满足a<b<c而且标号为a,b,c的点在圆上分布的顺序为顺时针顺序。

分布顺序为顺时针的意思是，从标号为a的点出发，顺时针在圆上遍历一圈，标号为b的点先遍历到，标号为c的点后遍历到(a<b<c）。

输入

第一行一个整数n表示点数。

第二行n个整数表示一个1～n的排列，按顺时针顺序描述圆上点的标号。

输出

仅一行一个整数表示答案

约定

20%的数据：n≤100n≤100

60%的数据：n≤5000n≤5000

100%的数据：3≤n≤2∗1053≤n≤2∗105

solution

好题，xiaoyao巨

显然点的大小关系应为123 231 312

123很好统计

231=**1-321 这两个也很好统计

312=3**-321 这也很好统计

就结束了

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#define maxn 200005

using namespace std;

int n,s[maxn],a1[maxn],a2[maxn],b1[maxn],b2[maxn];

int tr[maxn];

void add(int i){

    for(;i<=n;i+=i&-i)tr[i]++;

}

int ask(int i){

    int sum=0;for(;i;i-=i&-i)sum+=tr[i];

    return sum;

}

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)scanf("%d",&s[i]);

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

        add(s[i]);

        a1[i]=ask(s[i]-1);

        a2[i]=i-1-a1[i];

    }

    memset(tr,0,sizeof tr);

    for(int i=n;i>=1;i--){

        add(s[i]);

        b1[i]=ask(s[i]-1);

        b2[i]=n-i-b1[i];

    }

    long long ans=0,tmp;

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

        ans=ans+1LL*a1[i]*b2[i];

        tmp=1LL*a2[i]*b1[i];

        ans=ans+1LL*a2[i]*(a2[i]-1)/2+1LL*b1[i]*(b1[i]-1)/2-tmp-tmp;

    }

    cout<<ans<<endl;

    return 0;

}

巴特西

朗格拉日计数(counter)

朗格拉日计数(counter)

题目描述

输入

输出

最新文章

热门文章