XDOJ-1613

最近一段时间 tsy 对排列非常感兴趣，每天都在研究排列的变化和性质。一天 tsy 正在看球，场上来回碰撞 的足球给了 tsy 灵感，他想知道对于一个排列 $P$ 有多少个 “锯齿序列” 。一个 “锯齿序列” 可以用一个四元组 $(a, b, c, d)$ 来表示，这个四元组同时满足以下两个条件：

（1）$a < b < c < d$

（2）$P_a < P_b，P_b > P_c，P_c < P_d$

tsy 很快就解决了这个问题，现在他想考考你，聪明的你能解决这个问题吗？ 大小为 $n$ 的排列指一个长度为 $n$ 的正整数序列，其中每个数属于 $[1, n]$ ，且每个数字只出现一次。 由于答案很大，请输出答案对 $35198030$ 取模后的结果。

思路

容易发现这样一个四元组是由两个顺序对 $(p_a,p_b)$ 与 $(p_c,p_d)$ 和一个逆序对 $(p_b,p_c)$ 构成的。

记录 $Fmin_i$ 表示在 $p_i$ 前面且比 $p_i$ 小的数的个数（即以 $p_i$ 为后的顺序对的个数）， $Bmax_i$ 表示在 $p_i$ 后面且比 $p_i$大的数的个数（即以 $p_i$ 为前的顺序对的个数）。

那么对于一个逆序对 $(p_b,p_c)$ ，其贡献的方案数为 $Fmin_b\times Bmax_c$ 。

那么对于 $p_i$ ，其作为 $c$ 时贡献的方案数即为 $Bmax_c\times \sum\limits_{b}Fmin_b$ 。

于是想到在用线段树求逆序对的过程中，令 $Fmin$ 为权值，这样就可以依次统计每个 $p_i$ 作为 $p_c$ 时的方案数。

至于 $Fmin$ 与 $Bmax$ ，同样也可以先用线段树求出来。

据此，只需要用维护两个权值线段树即可（一个权值为 $1$ ，一个权值为 $Fmin$ ）。

时间复杂度 $O(n\log n)$ 。

代码

#include<bits/stdc++.h>
#define ll long long 
#define N 300010
#define mod 35198030

using namespace std;

inline ll read() {
    ll w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,p[N];
ll Fmin[N],Bmax[N],ans=0;

class SegmentTree{
  private:
    int cnt[N<<2];
    ll sum[N<<2];
    #define c(x) cnt[x]
    #define s(x) sum[x]
    #define ls (p<<1)
    #define rs (ls|1)
    #define mid (l+r>>1)
    void update(int p) {
        c(p)=c(ls)+c(rs);
        (s(p)=s(ls)+s(rs))%=mod;
    }
  public:
    void build(int p,int l,int r) {
        c(p)=s(p)=0;
        if(l==r) return ;
        build(ls,l,mid),build(rs,mid+1,r);
        update(p);
    }
    void change_cnt(int p,int l,int r,int x) {
        if(l>x||r<x) return ;
        if(l==r) {
            c(p)++;
            return ;
        }
        change_cnt(ls,l,mid,x),change_cnt(rs,mid+1,r,x);
        update(p);
    }
    void change_sum(int p,int l,int r,int x,ll y) {
        if(l>x||r<x) return ;
        if(l==r) {
            (s(p)+=y)%=mod;
            return ;
        }
        change_sum(ls,l,mid,x,y),change_sum(rs,mid+1,r,x,y);
        update(p);
    }
    int ask_cnt(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return c(p);
        return ask_cnt(ls,l,mid,L,R)+ask_cnt(rs,mid+1,r,L,R);
    }
    ll ask_sum(int p,int l,int r,int L,int R) {
        if(l>R||r<L) return 0;
        if(l>=L&&r<=R) return s(p);
        return (ask_sum(ls,l,mid,L,R)+ask_sum(rs,mid+1,r,L,R))%mod;
    }
}SMT;

int main() {
    n=read();
    for(int i=1;i<=n;i++) p[i]=read();
    for(int i=1;i<=n;i++) {
        SMT.change_cnt(1,1,n,p[i]);
        Fmin[i]=SMT.ask_cnt(1,1,n,1,p[i]-1);
        Bmax[i]=n-p[i]-SMT.ask_cnt(1,1,n,p[i]+1,n);
        (ans+=Bmax[i]*SMT.ask_sum(1,1,n,p[i]+1,n)%mod)%=mod;
        SMT.change_sum(1,1,n,p[i],Fmin[i]);
    }
    printf("%lld\n",ans);
    system("pause");
    return 0;
}