Codeforces 1264 C Beautiful Mirrors with queries —— 线段树+期望

本文主要是介绍Codeforces 1264 C Beautiful Mirrors with queries —— 线段树+期望，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

有n张镜子，每个镜子有pi/100的概率说你好看。
现在第一个镜子是检查点
你从第一个镜子问到第n个镜子，如果第i个镜子说你好看，你就问第i+1个镜子，否则就找到小于等于i的检查点，从那开始继续。
每次都会告诉你一个值，如果那里没有检查点就将那里设为检查点，否则就将那里的检查点取消。
问你从1到n问的次数的期望是多少。

题解：

期望的题目一看就不想做。。
我们考虑第i个点，如果不管之后的点，那么这个点访问次数为1+(1-p)+(1-p)*(1-p)+…
用等比数列求和得出为$\frac{100}{pi}$
如果不管增删检查点，那么可以列出一个式子：第i个点的访问次数是$f[i]=\frac{100}{pi}\ast f[i+1]$
然后我们可以发现，其实加一个检查点，也就是将一块连续的区域分成了两个。每个都当做独立的即可。
那么我们只需要记录每个检查点所管的区域的值即可，以及我们需要查找每个点的上一个检查点和下一个检查点的位置，更新当前点以及上一个检查点。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const int N=2e5+5;
ll qpow(ll a,ll b){ll ans=1;for(;b;b>>=1,a=a*a%mod)if(b&1)ans=ans*a%mod;return ans;}
ll p[N],f[N],suf[N],sum[N*4];
int num[N*4];
void update(int l,int r,int root,int p,ll v1,int v2){if(l==r){num[root]=v2;sum[root]=v1;return ;}int mid=l+r>>1;if(mid>=p)update(l,mid,root<<1,p,v1,v2);elseupdate(mid+1,r,root<<1|1,p,v1,v2);num[root]=num[root<<1]+num[root<<1|1];sum[root]=(sum[root<<1]+sum[root<<1|1])%mod;
}
int q_num(int l,int r,int root,int ql,int qr){if(l>=ql&&r<=qr)return num[root];int mid=l+r>>1;int ans=0;if(mid>=ql)ans=q_num(l,mid,root<<1,ql,qr);if(mid<qr)ans+=q_num(mid+1,r,root<<1|1,ql,qr);return ans;
}
int q_pos(int l,int r,int root,int v){if(l==r)return l;int mid=l+r>>1;if(num[root<<1]<v)return q_pos(mid+1,r,root<<1|1,v-num[root<<1]);return q_pos(l,mid,root<<1,v);
}
bool chk[N];
int main()
{int n,q;ll inv_=qpow(100,mod-2);scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%lld",&p[i]),p[i]=100ll*qpow(p[i],mod-2)%mod;f[n+1]=1;for(int i=n;i;i--){f[i]=f[i+1]*p[i]%mod;suf[i]=(suf[i+1]+f[i])%mod;}update(1,n,1,1,suf[1],1);chk[1]=1;while(q--){int pos;scanf("%d",&pos);chk[pos]^=1;if(chk[pos]){int s=q_num(1,n,1,1,pos);int l=q_pos(1,n,1,s),r;if(s==num[1])r=n+1;else r=q_pos(1,n,1,s+1);ll v=(suf[l]-suf[pos]+mod)%mod*qpow(f[pos],mod-2)%mod;update(1,n,1,l,v,1);v=(suf[pos]-suf[r]+mod)%mod*qpow(f[r],mod-2)%mod;update(1,n,1,pos,v,1);}else{int s=q_num(1,n,1,1,pos);int l=q_pos(1,n,1,s-1),r;if(s==num[1])r=n+1;else r=q_pos(1,n,1,s+1);update(1,n,1,pos,0,0);ll v=(suf[l]-suf[r]+mod)%mod*qpow(f[r],mod-2)%mod;update(1,n,1,l,v,1);}printf("%lld\n",sum[1]);}return 0;
}

这篇关于Codeforces 1264 C Beautiful Mirrors with queries —— 线段树+期望的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---