UVA1428

~~看 weistars 小朋友正在学所以来做一下。~~

思路

考虑树状数组。

先从前往后扫一遍，再在从前往后的同时更新从后往前的答案，在计算即可。

具体的，先离散化，建立阈值树状数组，记录每个技能值的人数。

则对于每一项，答案应当增加前面的比他技能值小的数的个数乘上后面的比他大的数的个数再加上后面的比他小的数的个数和前面的比他大的数的个数。

用两个树状数组分别记录前面的、和后面的数的个数。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N],c[N],d[N];
void add1(int x,int k)//前面的
{
    for(;x<N;x+=x&(-x))
        c[x]+=k;
}
void add2(int x,int k)//后面的
{
    for(;x<N;x+=x&(-x))
        d[x]+=k;
}
int get1(int x)//前面的
{
    int sum=0;
    for(;x;x-=x&(-x))
        sum+=c[x];
    return sum;
}
int get2(int x)//后面的
{
    int sum=0;
    for(;x;x-=x&(-x))
        sum+=d[x];
    return sum;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T,n;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)add2(a[i],1);
        long long ans=0;
        for(int i=1;i<=n;i++)
        {
            add2(a[i],-1);
            ans+=get1(a[i]-1)*(get2(N-1)-get2(a[i]));//计算a[i]<a[j]<a[k]的个数
            ans+=get2(a[i]-1)*(get1(N-1)-get1(a[i]));//计算a[i]>a[j]>a[k]的个数
            add1(a[i],1);
        }
        cout<<ans<<'\n';
    }
    return 0;
}

文章操作

思路

代码

相关推荐

评论

UVA1428