题解 P4528 【[CTSC2008]图腾】

· · 题解

洛咕 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;
}