洛谷1637 三元上升子序列

Luogu

算法

考虑枚举中间的元素$j$。那么设前面有$s_i$个比它小的,后面有$s_k$个比它大的,那么显然有$s_i\cdot s_k$个以$j$为中心的"thair"。

考虑怎么得到$s_i$和$s_k$。我们记录一下每个元素出现的个数(记为$c[]$),那么比$j$小的个数就是$\sum\limits_{i=1}^{j-1}c[i]$。

这个可以用树状数组来维护。比$j$大的是类似的。

注意$n$很小但$a[i]$很大,所以要离散化。

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
#define lowbit(x) (x&-x)
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[30010],tmp[30010];
int c[30010];
int t1[30010],t2[30010];
int n;

inline void add(int x,int k) { while (x<=n) c[x]+=k,x+=lowbit(x); }
inline int sum(int x) { int rt=0; while (x) rt+=c[x],x-=lowbit(x); return rt; }

int main() {
    n=read();
    for (re int i=1;i<=n;++i) tmp[i]=a[i]=read();
    
    sort(tmp+1,tmp+n+1); int m=unique(tmp+1,tmp+n+1)-tmp-1;
    for (re int i=1;i<=n;++i) a[i]=lower_bound(tmp+1,tmp+m+1,a[i])-tmp;
    
    for (re int i=1;i<=n;++i) t1[i]=sum(a[i]-1),add(a[i],1);
    memset(c,0,sizeof(c));
    for (re int i=n;i>=1;i--) t2[i]=sum(n-a[i]),add(n-a[i]+1,1);
    
    long long ans=0;
    for (re int i=1;i<=n;i++) ans+=t1[i]*t2[i];
    printf("%lld\n",ans);
    
    return 0;
}
最后修改:2019 年 09 月 24 日 01 : 20 PM

发表评论