【ZJOI2016】线段树

ZJOI的题神啊。

我们考虑计算每个位置\(p\)，它在操作过后变成第\(x\)个数的操作序列数。

我们枚举\(x\)。我们先得到了\(L_x,R_x\)表示最左边比\(x\)小的数以及最右边比\(x\)小的数（权值相同编号小的更小）。设\(f_{i,l,r}\)表示前\(i\)个操作结束后，恰好\([l,r]\)的权值\(\leq a_x\)，\([L_x,l-1],[r+1,R_x]\)的权值\(> a_x\)的方案数。初始\(f_{0,L_x,R_x}=1\)。

考虑转移。我们新的状态\(l',r'\)一定是有\(l',t\)或者\(t,r'\)转移过来的。

以第一种为例：

\[ \displaystyle f_{i,l',r'}=\sum_{t=r'+1}^{R_x}f_{i-1,l',t*(n-t)} \]

然后这个可以前缀和优化。

还有就是第\(i\)个操作区间为\([1,l-1],[l,r],[r+1,n]\)的子区间，这样的话\(l'=l,r'=r\)。

开始想的状态是\(f_{i,l,r}\)表示\([l,r]\)的权值\(>a_x\)的，怎么都转移不了。

代码：

#include
    
     #define ll long long#define N 405#define int llusing namespace std;inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}const ll mod=1e9+7;int f[2][N][N];int n,q;int w[N];int L[N],R[N];int sum[N];int g[N][N];void solve(int L,int R,int id) {    for(int i=L;i<=R;i++)        for(int j=i;j<=R;j++)            f[0][i][j]=0;    f[0][L][R]=1;    int now=0;    for(int i=0;i
     
      =l;r--) {                (f[now^1][l][r]=tem);                (tem+=1ll*f[now][l][r]*(n-r))%=mod;            }        }        for(int r=L;r<=R;r++) {            ll tem=0;            for(int l=L;l<=r;l++) {                (f[now^1][l][r]+=tem)%=mod;                (tem+=1ll*f[now][l][r]*(l-1))%=mod;            }        }        for(int l=L;l<=R;l++) {            for(int r=l;r<=R;r++) {                (f[now^1][l][r]+=1ll*f[now][l][r]*(sum[r-l+1]+sum[l-1]+sum[n-r]))%=mod;            }        }        now^=1;    }    for(int i=L;i<=R;i++) {        int tem=0;        for(int j=R;j>=i;j--) {            (tem+=f[now][i][j])%=mod;            (g[j][id]+=tem)%=mod;        }    }}bool cmp(int a,int b) {    if(w[a]!=w[b]) return w[a]
      
       =1&&w[j]