[LuoguP1637] 三元上升子序列

题解

对于 ,考虑在它前面比它小的数的个数记为 ,在它后面比它打的数的个数记为 ,相乘累加到答案。

显然,离散化一下后可以用树状数组统计。

具体方法是离散化后,遍历数组时把当前元素的值当作下标,在该下标的位置上 +1, 表示值为 的数目前出现的次数,则比 小的数即为 ,树状数组维护前缀和即可。

需要注意的是,在统计比 大的数的个数的时候,可以将数组倒序,再把每个 取相反数,转化为统计比 小的数。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;a++)
#define pii pair<int,int>
#define mk make_pair
#define x first
#define y second
using namespace std;
const int N=30004;
int n;
long long ans;
pii a[N];
bool cmp(pii p1,pii p2){return p1.y<p2.y;}

int ps[N],p1[N],p2[N];
void upd(int p,int v){for(int i=p;i<=n;i+=(i&-i))ps[i]+=v;
}
int sum(int p){
    int res=0;
    for(int i=p;i>0;i-=(i&-i))res+=ps[i];
    return res;
}

int main(){scanf("%d",&n);
    FOR(i,1,n)scanf("%d",&a[i].x),a[i].y=i;
    // 离散化
    sort(a+1,a+n+1);
    int cur=0;
    FOR(i,1,n){
        cur++;
        while(a[i+1].x==a[i].x)a[i].x=cur,i++;
        a[i].x=cur;
    }
    sort(a+1,a+n+1,cmp);
    // 统计在 a[1..i-1] 中比 a[i] 小的数
    FOR(i,1,n){upd(a[i].x,1);
        p1[i]=sum(a[i].x-1);
    }
    // 倒序取相反
    memset(ps,0,sizeof(ps));
    reverse(a+1,a+n+1);
    FOR(i,1,n)a[i].x=cur+1-a[i].x;
    // 统计在 a[i+1..n] 中比 a[i] 大的数
    FOR(i,1,n){upd(a[i].x,1);
        p2[n-i+1]=sum(a[i].x-1);
    }
    // 累加答案
    FOR(i,1,n)ans+=(long long)p1[i]*p2[i];
    printf("%lld",ans);
    return 0;
}

  目录