Wannafly Winter Camp 2020 Day 7A 序列

给定一个全排列，对于它的每一个子序列 \(s[1..p]\)，对于每一个 \(i \in [1,p-1]\)，给 \(s[i],s[i+1]\) 间的每一个值对应的桶 \(+1\)，求最终每个桶的值。

Solution

对于一对 \((i,j), i<j, p[i]<p[j]\)，其对 \(k \in (p[i],p[j])\) 有 \(2^{(i-1)+(n-j)}\) 的贡献

于是我们得到了 \(O(n^2 \log n)\) 暴力

考虑枚举左侧的 \(i\)，它会与右侧 \(p[j]>p[i]\) 的 \(j\) 对 \([p[i]+1,p[j]-1]\) 之间的 \(k\) 产生相同的贡献 \(2^{i-1}2^{n-j}\)，

考虑枚举右侧的 \(j\)，它会与左侧 \(p[i]<p[j]\) 的 \(i\) 对 \([p[i]+1,p[j]-1]\) 之间的 \(k\) 产生相同的贡献 \(2^{i-1}2^{n-j}\)，

考虑 \(k+1\) 的分与 \(k\) 的分的差值，设为 \(\Delta_k=A_k-A_{k-1}\)

需要减去 \((i,k+1), i<k\)
需要加上 \((k,i), i>k+1\)

从前往后扫描序列，只考虑与当前点位置左边的点成对产生的贡献，（逆向的可以反过来再扫一次），让当前位置作为位置对的右端点 \(j\)，贡献为 \(2^{n-j}\)

这个点作为值对中的大者，则 \(j\) 位置前所有小于 \(p[j]\) 的数 \(p[i]\) 会产生 \(-2^{i-1}\) 的贡献
这个点作为值对中的小者，则 \(j\) 位置前所有大于 \(p[j]\) 的数 \(p[i]\) 会产生 \(2^{i-1}\) 的贡献

这个过程显然可以用树状数组维护

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int mod=1e9+7;

const int N=1e5+5;

int n,a[N],d[N],m[N],b[N];

int lowbit(int x) {return x&(-x);}

void modify(int x,int v) {

    for(;x<=n;x+=lowbit(x)) (b[x]+=v)%=mod;

}

int query(int x) {

    int ans=0;

    for(;x;x-=lowbit(x)) (ans+=b[x])%=mod;

    return ans;

}

signed main() {

    ios::sync_with_stdio(false);

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    m[0]=1;

    for(int i=1;i<=n;i++) m[i]=(m[i-1]*2)%mod;

    for(int i=1;i<=n;i++) {

        int v=query(a[i]-1)*m[n-i]%mod;

        ((d[a[i]]-=v)+=mod)%=mod;

        v=(query(n)-query(a[i])+mod)%mod*m[n-i]%mod;

        (d[a[i]+1]+=v)%=mod;

        modify(a[i],m[i-1]);

    }

    memset(b,0,sizeof b);

    for(int i=n;i>=1;--i) {

        int v=(query(n)-query(a[i])+mod)%mod*m[i-1]%mod;

        (d[a[i]+1]+=v)%=mod;

        v=query(a[i]-1)*m[i-1]%mod;

        ((d[a[i]]-=v)+=mod)%=mod;

        modify(a[i],m[n-i]);

    }

    for(int i=1;i<=n;i++) {

        (d[i]+=d[i-1])%=mod;

        cout<<(d[i]+mod)%mod<<endl;

    }

}

巴特西

Wannafly Winter Camp 2020 Day 7A 序列 - 树状数组

Solution

最新文章

热门文章