2023NOIP A层联测22-差后队列

本文主要是介绍2023NOIP A层联测22-差后队列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

定义差后队列为一个数据结构，支持两种操作：

pop 随机删除一个不是最大值的的数。如果只有一个数则删除该数。
push 插入一个数（正常插入）。

给定操作序列，求每次删的数的期望，以及每个数期望被删的时间（如果到最后也没被删则删除时间为 $0$ ）。

$n\le10^6$

容易发现，一个数如果不是最大值，都是一样的。

对于一个数，如果它是当前的最大值，就要到后面第一个大于它的位置开始计算贡献。

先考虑操作为 $1$ 的情况，对于每个数，记当前队列大小为 $k$ ，每次删除成功的概率是前面几次都失败的概率乘上 $\dfrac{k-2}{k-1}$ ，可以从前往后递推，因为贡献的式子是相似的。

对于操作 $2$ ，其实差不多，只是要倒过来做。

时间复杂度 $O (n)$ 。我的代码中懒得求逆元，是 $O(n\log n)$ ，但能过。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll mod=998244353;
const int N=1e6+1;
int n,s[N],X[N];
ll ans[N],f[N],inv[N];
struct node
{int op,x;node(){}node(int a,int b){op=a,x=b;}
}q[N];
ll ksm(ll a,ll b)
{ll ans=1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int main()
{freopen("queue.in","r",stdin);freopen("queue.out","w",stdout);scanf("%d",&n);int lstmax=0;ll sum=0;for(int i=1;i<=n;i++){scanf("%d",&q[i].op);if(!q[i].op){scanf("%d",&q[i].x);if(!lstmax) lstmax=i;else if(q[i].x>q[lstmax].x) sum=(sum+q[lstmax].x)%mod,s[i]=lstmax,lstmax=i;else sum=(sum+q[i].x)%mod,s[i]=i;X[i]=X[i-1]+1;}else{X[i]=X[i-1]-1;if(X[i]){ans[i]=sum=sum*ksm(X[i],mod-2)%mod;(sum*=X[i]-1)%=mod;}else ans[lstmax]=i,ans[i]=q[lstmax].x,lstmax=0;}}int cnt=0;for(int i=n;i>=1;i--){if(!q[i].op) ans[s[i]]=cnt;else{if(X[i]){ll inv=ksm(X[i],mod-2);cnt=((i*inv+cnt*(1-inv))%mod+mod)%mod;}}}for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
}