526互联

2023NOIP A层联测22 差后队列

发布时间 2023-11-01 22:48:34作者: 彬彬冰激凌

2023NOIP A层联测22 差后队列

挺有意思的期望题，题解做法应该是 DP，但是我又双叒写出奇怪的做法……

思路

除去最大值外的元素个数的倒数就是这一轮取到某个数的概率，而最大值是特殊的情况，在被替代之前或作为最后一个数被弹出之前，不参与计算。

对于操作 0 的输出和操作 1 的输出分开处理。

操作 1

设 \(f[i]\) 表示在执行第 \(i\) 个操作时可弹出数的期望大小。

1.加入操作

加入后不成为最大值，\(f[i]=f[i-1]+val[i]\)。

加入后成为最大值，\(f[i]=f[i-1]+mx\)，然后更新 \(mx=val[i]\)。（\(mx\) 为最大值）

2.删除操作

设此时队列中除去最大值外元素个数为 \(has\)。

除最大值外每个元素被取到的概率 \(p=\frac{1}{has}\)。

此时期望取到的值 \(ans=p*f[i]\)。

更新 \(f[i]=f[i-1]-ans\)。

\(ans\) 为这一次操作的答案。

操作 0

不难发现，每个元素都有一个开始会被弹出的操作 1，和一定被弹出队列的操作 1。

设第 \(i\) 个弹出操作弹出每个树的概率是 \(p[i]\)。（除最大值外每一个数被等概率弹出，所以 \(p[i]\) 容易得到）

设第 \(i\) 个弹出操作是总操作中第 \(a[i]\) 个操作。

设第 \(u\) 个插入队列的数，可以被弹出的第一个操作 1 是总弹出操作第 \(st_u\) 个，一定会被弹出的操作 1 是总弹出操作的第 \(ed_u\) 个。

那么对于第 \(u\) 个插入的数。如果不是最大值，那么它在第 \(k\ (st_u \leq k \leq ed_u)\) 次操作被弹出的概率是 \(p_k\prod_{j=st_u}^{k-1}(1-p_j)\)。

给期望删除时间的贡献为 \(a_kp_k\prod_{j=st_i}^{k-1}(1-p_j)\)。

第 \(u\) 个插入的数被删除时间的期望为 \(ans_u=\sum_{i=st_u}^{ed_u} a_ip_i \prod_{j=st_u}^{i-1} (1-p_j)\)。

接下来要考虑如何 \(O(1)\) 的求这个式子。

设 \(s_i=a_ip_i\prod_{j=1}^{i-1}(1-p_j)\)。

又有 \(g_1=\frac{1}{1-p_1}\)，\(g_i=g_{i-1}\frac{1}{1-p_i}\)。

所以 \(ans_u=\sum_{i=st_u}^{ed_u} s_ig_{st_u-1}=g_{st_u-1}\sum_{i=st_u}^{ed_u} s_i\)。

后面的 \(s_i\) 可以用前缀和 \(O(1)\) 求出。

而上面的数预处理都是 \(O(n)\) 或 \(O(n\log_2n)\)。

总时间复杂度 \(O(n\log_2n)\)。

可能会有点小常数。

CODE

#include<bits/stdc++.h>
using namespace std;

#define mod 998244353
#define int long long

const int maxn=1e6+5;

struct node
{
    int st,ed;
}point[maxn];

int cnt,n,has=-1,mx,smx;
int a[maxn],val[maxn],p[maxn],s[maxn],f[maxn],g[maxn],ans[maxn],sp[maxn],t[maxn],st[maxn],ed[maxn];

queue<int>que;

int ksm(int x,int y)
{
    int sum=1;
    for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;
    return sum;
}

signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        int op;
        scanf("%lld",&op);
        if(op==0)
        {
            scanf("%lld",&val[i]);
            has++;
            if(val[i]>mx)
            {
                f[i]=(f[i-1]+mx)%mod,mx=val[i],st[smx]=cnt+1;
                if(smx) que.push(smx);
                smx=i;
            }
            else f[i]=(f[i-1]+val[i])%mod,st[i]=cnt+1,que.push(i);
        }
        else
        {
            cnt++;
            if(has)
            {
                p[cnt]=ksm(has,mod-2);
                a[cnt]=i;
                ans[i]=f[i-1]*p[cnt]%mod;
                f[i]=(f[i-1]-ans[i]+mod)%mod;
            }
            else
            {
                p[cnt]=1;
                a[cnt]=i;
                ans[i]=mx;
                ans[smx]=i;
                mx=smx=0;
                f[i]=0;
            }
            has--;
            if(has==0) while(!que.empty()) ed[que.front()]=cnt,que.pop();
        }
    }
    while(!que.empty()) ed[que.front()]=cnt,que.pop();

    sp[0]=1;
    for(int i=1;i<=cnt;i++) sp[i]=max(sp[i-1]*((1-p[i]+mod)%mod)%mod,1ll);
    for(int i=1;i<=cnt;i++) s[i]=sp[i-1]*p[i]%mod*a[i]%mod,t[i]=(t[i-1]+s[i])%mod;
    g[0]=1;
    for(int i=1;i<=cnt;i++)
    {
        if(p[i]==1) g[i]=1;
        else g[i]=g[i-1]*ksm((1-p[i]+mod)%mod,mod-2)%mod;
    }
    for(int i=1;i<=n;i++)
    {
        if(ans[i]||val[i]==0||ed[i]==0||st[i]==0||ed[i]<st[i]||ed[i]>cnt) continue;
        ans[i]=(t[ed[i]]-t[st[i]-1]+mod)*g[st[i]-1]%mod;
    }
    for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}

还是挺浅显易懂的吧。