P10589 楼兰图腾

yiweixxs / 2024-10-12 / 原文

Problem

有n个记号在一面墙上从左往右排列，其离地面高度$h_i$不同，保证是1~n的一个排列，试求出有多少种如下两种情况

\[①i<j<k \]

\[②h_i>h_j<h_k或h_i<h_j>h_k \]

其中在满足①②的情况下②分左右两种，$n\le2\times10^5$且$Ans\le2^{64}-1$

Solve

可以枚举每个$i,j,k$计算满足哪些情况，时间复杂度$O(n^3)$
但其实我们可以维护两个值域线段树，分别计算在i的前面与后面大于或小于$h_j$的个数
以V字(第一种)情况举例，设在p节点，在它前面有u个数比他大，在后面有v个数比它大，那么不难得出当$j=p$时，会为答案产生$u\times v$的贡献，这样时间复杂度就变成了$O(n\log n)$

Code

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdlib>
#include<list>
#include<map>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
long long n,a[200005],s[800005],ans[5][200005];
void upd(int p,int l,int r,int x,long long v){
    if(l>x||r<x)return ;
    if(l==r){
        s[p]++;
        return ;
    }
    upd(2*p,l,(l+r)/2,x,v);
    upd(2*p+1,(l+r)/2+1,r,x,v);
    s[p]++;
}
long long qsum(int p,int l,int r,int x,int y){
    if(x>r||y<l)return 0;
    if(l>=x&&r<=y)return s[p];
    long long ans=0;
    ans+=qsum(2*p,l,(l+r)/2,x,y);
    ans+=qsum(2*p+1,(l+r)/2+1,r,x,y);
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        upd(1,1,n,a[i],1);
        ans[1][i]+=qsum(1,1,n,a[i]+1,n);
        ans[2][i]+=qsum(1,1,n,1,a[i]-1);
    }
    memset(s,0,sizeof(s));
    for(int i=n;i>=1;i--){
        upd(1,1,n,a[i],1);
        ans[3][i]+=qsum(1,1,n,a[i]+1,n);
        ans[4][i]+=qsum(1,1,n,1,a[i]-1);
    }
    long long res=0,res1=0;
    for(int i=1;i<=n;i++){
        res+=ans[1][i]*ans[3][i];
        res1+=ans[2][i]*ans[4][i];
    }
    cout<<res<<" "<<res1;
    return 0;
}