题目描述

图片说明

题解：

题目又臭又长，我来简化一下
其实就是问有多少个山峰，有多少个山谷
山峰就是^
山谷就是v
线段树和树状数组都可以做
用到两个变量right_num和left_num
right_num[i]表示在i的右边比i小的数有多少
left_num[i]表示在i的左边比i小的数有多少
求出两个数组之后，我们要求山峰不就是要知道左右两边比他小的数量吗。所以直接left_num[i]right_num[i]
求山谷就正好反过来，(i-1-left_num[i])(n-i-right_num[i])即可

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 200006;
typedef long long ll;
ll n,a[maxn],c[maxn],left_num[maxn],right_num[maxn];
int lowbit(int x)
{
    return x=x&(-x);
}
void insert(int x,int y)
{
    while(y<=n)
    {
        c[y]+=x;
        y+=lowbit(y);
    }
}
int getsum(int x)
{
    int sum = 0;
    while(x>0)
    {
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}
int main(int argc, char const *argv[])
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=n;i;i--)
    {
        int k = getsum(a[i]);
        insert(1,a[i]);
        right_num[i]=k;
    }
    for(int i=1;i<=n;i++)c[i]=0;
    for(int i=1;i<=n;i++)
    {
        int k = getsum(a[i]);
        insert(1,a[i]);
        left_num[i]=k;
    }
    long long ans1 = 0;
    for(int i=1;i<=n;i++)
    {
        ans1+=left_num[i]*right_num[i];
    }
    long long ans2 = 0;
    for(int i=1;i<=n;i++)
    {
        ans2+=(i-1-left_num[i])*(n-i-right_num[i]);
    }
    cout<<ans2<<" "<<ans1<<endl;
    return 0;
}

线段树代码；

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <map>
#include <climits>
using namespace std;

#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r

typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+10;
int T,n,m,k;
int a[maxn];
int sum[maxn<<2];

void PushUp(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}

void Update(int rt,int l,int r,int pos){
    if(l==r){
        sum[rt]++;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) Update(lson,pos);
    else Update(rson,pos);
    PushUp(rt);
}

ll Query(int rt,int l,int r,int L,int R){
    if(L<=l&&r<=R) return sum[rt];
    int mid=(l+r)>>1;
    ll ans=0;
    if(L<=mid) ans+=Query(lson,L,R);
    if(R>mid) ans+=Query(rson,L,R);
    return ans;
}

int main(){
    scanf("%d",&n);
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        ll ans1=0,ans2=0;
        for(int i=1;i<=n;i++){
            ll tmp1=Query(1,1,n,1,a[i]);
            ll tmp2=Query(1,1,n,a[i],n);
            ans1+=tmp2*(n-a[i]-tmp2);
            ans2+=tmp1*(a[i]-1-tmp1);
            Update(1,1,n,a[i]);
        }
        printf("%lld %lld\n",ans1,ans2);
    }
    return 0;
}