自动搬运

查看原文

来自洛谷，原作者为

	λᴉʍ 大家好，我是刚学OI的萌新

搬运于2025-08-24 22:01:04，当前版本为作者最后更新于2018-11-29 17:39:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛咕 P4528 [CTSC2008]图腾

神题orz。

先约定abcd表示$1\leq A<B<C<D\leq n$，而且$y_a,y_b,y_c,y_d$的排名正好是$a,b,c,d$的方案数

那么所求就是

1324-1243-1432

=(1x2x-1423)-(14xx-1423)-(12xx-1234)

（其中有x的表示排名任意，但是不能重复)

=1x2x-14xx-12xx+1234

=1x2x-1xxx+13xx+1234

预处理$L,R$，$L_i=\sum_{j<i}[y_j<y_i],R_i=\sum_{j>i}[y_j<y_i]$，可以用树状数组处理

（可以看出，$L_i+R_i=y_i-1$，可以只求$L_i$就行了；$n-i-R_i=\sum_{j>i}[y_j>y_i]$，这是等一下要用到的性质）

分别看怎么求：

1x2x：枚举2的位置$i$，那么右边有$n-i-R_i$中选法，左边要满足$j<k<i,y_j<y_i,y_k>y_i$，1放在j，x放在k的位置

若只考虑$y_j<y_i$，有$L_i*(i-1)$种选法；那么多算了$j<k,y_k<y_i$的和$j\geq k$的

$j<k,y_k<y_i$的方案数是$C_{L_i}^2$

$j>k$的方案数，因为此时对$k$的限制只有$k\leq j$，所以对每个$j$都可以取$[1,j]$，所以就是$\sum_{p<i,y_p<y_i}p$

1xxx：很容易，就是$\sum C_{n-i-R_i}^3$

13xx：枚举3，那么4有$n-i-R_i$种选法，1和2要满足$j<i<k,y_j<y_k<y_i$

只考虑$y_j<y_i,y_k<y_i,j<i$，有$L_i(y_i-1)$种选法，需要减去的是$k\leq i$的和$y_j\geq y_k$的

$k\leq i$的就是$C_{L_i}^2$

$y_j>y_k$的，此时对$k$的限制只有$y_k\leq y_j$，所以对每个$j$都可以取所有$y<y_j$的位置，就是$\sum_{p<i,y_p<y_i}y_p$

1234:枚举3，后面的就是$n-i-R_i$，前面如果2确定了放在$j$位置,1的放法就是$L_j$，答案是$\sum_{i} (n-i-R_i)(\sum_{j<i,y_j<y_i}L_j)$，树状数组直接做

完结撒FA（逃

#include<bits/stdc++.h>
#define il inline
#define vd void
#define mod 16777216
typedef long long ll;
il int gi(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
ll n,p[200010],L[200010],R[200010];
int t[200010];
il vd inc(int&x,int y){x+=y;x%=mod;}
il vd upd(int p,int d){while(p<=n)inc(t[p],d),p+=p&-p;}
il int query(int p){int ret=0;while(p)inc(ret,t[p]),p-=p&-p;return ret;}
int main(){
    n=gi();
    for(int i=1;i<=n;++i)p[i]=gi();
    for(int i=1;i<=n;++i)L[i]=query(p[i]),R[i]=p[i]-1-L[i],upd(p[i],1);
    memset(t,0,sizeof t);
    int ans=0;
    for(int i=1;i<=n;++i){
        int x=n-i-R[i];
        ans=(ans-(1ll*x*(x-1)*(x-2)/6)%mod+mod)%mod;//1xxx
    }
    for(int i=1;i<=n;++i)ans=(ans+(n-i-R[i])*query(p[i]))%mod,upd(p[i],L[i]);//1234
    memset(t,0,sizeof t);
    for(int i=1;i<=n;++i)ans=(ans+(L[i]*(i-1)-query(p[i])-L[i]*(L[i]-1)/2)*(n-i-R[i])%mod+mod)%mod,upd(p[i],i);//1x2x
    memset(t,0,sizeof t);
    for(int i=n;i;--i)ans=(ans+(query(p[i])-R[i]*(R[i]+1)/2)*(n-i-R[i])%mod+mod)%mod,upd(p[i],p[i]);//13xx
    printf("%d\n",ans);
    return 0;
}