小A的排列 题解

一个暴力是枚举左右端点，用 set 求中位数，然而是 的。

但是我们注意到，在加入一个数后，中位数至多只会移动 个位置，即不变或者变成前驱或后继。

于是我们需要支持一个 插入、 求前驱后继的数据结构，发现并找不到。

但是我们可以倒过来变成删除，这样子就可以用链表维护了。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

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*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10;
const int mod=1e9+7;

int n,p[N],seed,pw1[N],pw2[N];

struct H {
    int L[N],R[N];
    int pre(int x) { return L[x]; }
    int nxt(int x) { return R[x]; }
    void del(int x) { R[L[x]]=R[x],L[R[x]]=L[x]; }
} A,B;

int main() {
    n=read(),seed=read();
    for (int i=1;i<=n;++i) p[i]=read();
    pw1[0]=1;
    for (int i=1;i<=n;++i) pw1[i]=1ll*pw1[i-1]*seed%mod;
    pw2[0]=1;
    for (int i=1;i<=n;++i) pw2[i]=1ll*pw2[i-1]*pw1[n]%mod;
    for (int i=1;i<=n+1;++i) B.L[i]=i-1,B.R[i-1]=i;
    int ans=0;
    for (int r=n,M1=(n+1)>>1,M2=(n+2)>>1;r;--r) {
        int m1=M1,m2=M2; A=B;
        for (int l=1;l<=r;++l) {
            ans=(ans+1ll*pw2[l-1]*pw1[r]%mod*(m1+m2))%mod;
            if (m1==m2) {
                if (p[l]<=m2) m2=A.nxt(m2);
                if (p[l]>=m1) m1=A.pre(m1);
            } else {
                if (p[l]<=m1) m1=A.nxt(m1);
                if (p[l]>=m2) m2=A.pre(m2);
            }
            A.del(p[l]);
        }
        if (M1==M2) {
            if (p[r]<=M2) M2=B.nxt(M2);
            if (p[r]>=M1) M1=B.pre(M1);
        } else {
            if (p[r]<=M1) M1=B.nxt(M1);
            if (p[r]>=M2) M2=B.pre(M2);
        }
        B.del(p[r]);
    }
    printf("%d\n",ans);
    return 0;
}