Dses
如题。
[ABC332F] Random Update Query
算是一种期望与概率线段树。
考虑 $X $ 有 \(\dfrac{1}{d}\) 的概率变成 \(Y\) 的 \(E(X).\)
古典概型，得到 \(E(x)=\dfrac{d-1}{d} X +\dfrac{Y}{d}.\)
分作两步：
-
\(x \rightarrow \dfrac{d-1}{d}x\)
-
\(x\rightarrow x+\dfrac{1}{d}Y\)
线段树维护就好了。
居然可以一发 \(AC.\) 看来我又变强了。
程式
#include <bits/stdc++.h>
#define int long long
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define lson ls,l,mid
#define rson rs,mid+1,r
const int p=998244353;
const int N=2e5+10;
int w[N],tree[N<<2],tag[N<<2],tag2[N<<2];
int n,m;
void push_down(int rt,int l,int r){
tree[rt]*=tag2[rt], tree[rt]+=(r-l+1)*tag[rt], tree[rt]%=p;
if(l!=r){
tag[ls]*=tag2[rt], tag[rs]*=tag2[rt];
tag2[ls]*=tag2[rt], tag2[rs]*=tag2[rt];
tag[ls]%=p, tag2[ls]%=p, tag[rs]%=p;tag2[rs]%=p;
}
if(l!=r)tag[ls]+=tag[rt],tag[rs]+=tag[rt],tag[ls]%=p,tag[rs]%=p;
tag[rt]=0;
tag2[rt]=1;
}
void push_up(int rt,int l,int r){
if(l!=r)push_down(lson),push_down(rson);
tree[rt]=tree[ls]+tree[rs];
}
void update(int rt,int l,int r,int L,int R,int k){
push_down(rt,l,r);
if(L<=l && r<=R){
tag[rt]+=k;
tag[rt]%=p;
return;
}
if(L<=mid)update(lson,L,R,k);
if(R>mid) update(rson,L,R,k);
push_up(rt,l,r);
}
void update2(int rt,int l,int r,int L,int R,int k){
push_down(rt,l,r);
if(L<=l && r<=R){
tag2[rt]*=k, tag[rt]*=k, tag[rt]%=p, tag2[rt]%=p;
return;
}
if(L<=mid)update2(lson,L,R,k);
if(R>mid) update2(rson,L,R,k);
push_up(rt,l,r);
}
int query(int rt,int l,int r,int L,int R){
push_down(rt,l,r);
if(L<=l&&r<=R)return tree[rt]%p;
int res=0;
if(L<=mid) res+=query(lson,L,R),res%=p;
if(R>mid) res+=query(rson,L,R),res%=p;
return res%p;
}
int qpow(int a,int b){
int res=1;
while(b){
if(b&1) res=res*a%p;
a=a*a%p, b>>=1;
}
return res;
}
int inv(int x){ return qpow(x,p-2); }
signed main(){
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i){
int x; scanf("%lld",&x);
update(1,1,n,i,i,x);
}
while(m--){
int l,r,x;
scanf("%lld%lld%lld",&l,&r,&x);
int d=(r-l+1),iv=inv(d);
update2(1,1,n,l,r,(d-1)*iv);
update(1,1,n,l,r,iv*x);
}
for(int i=1;i<=n;++i) printf("%lld ",query(1,1,n,i,i));
return 0;
}
P10077 [GDKOI2024 普及组] 读书
考虑用线段树去掉最小数，直到没有小于 \(0\) 的数。
在删除一个数的时候，把那个数改成 \(+\infty\)，然后后面的数集体 \(-1.\)
以此类推。在第二轮的时候，还原线段树。
用栈记录每轮修改的数。
清栈显然是 \(\mathcal{O(1)}\) 的。
程式
#include <bits/stdc++.h>
#define ll long long
#define ls (u<<1)
#define rs (u<<1|1)
#define lson ls,l,mid
#define rson rs,mid+1,r
#define mid ((l+r)>>1)
#define file "book"
using namespace std;
const int N=5e5+10,inf=0x3f3f3f3f;
int n,d,cnt,a[N],st[N];
struct sgt{
int mn[N],ps[N],tg[N];
inline void pu(int u){if(mn[ls]>mn[rs])mn[u]=mn[rs],ps[u]=ps[rs];else mn[u]=mn[ls],ps[u]=ps[ls];}
inline void p(int u,int x){mn[u]+=x,tg[u]+=x;}
inline void pd(int u){if(tg[u])p(ls,tg[u]),p(rs,tg[u]),tg[u]=0;}
inline void upd(int u,int l,int r,int L,int R,int k){
if(R<L)return;
if(L<=l&&r<=R)return p(u,k);pd(u);
if(L<=mid)upd(lson,L,R,k);
if(R> mid)upd(rson,L,R,k);pu(u);
}
inline void bd(int u,int l,int r){
if(l==r)return ps[u]=l,mn[u]=a[l],void();
bd(lson),bd(rson),pu(u);
}
}t;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>d>>n;
for(int i=1;i<=n;++i)cin>>a[i];
t.bd(1,1,n);
for(int i=1;i<=n+1;++i){
int top=0;
if(i==n+1)return cout<<-1<<"\n",0;
for(;t.mn[1]<=0;){
int p=t.ps[1];
t.upd(1,1,n,p+1,n,-1),t.upd(1,1,n,p,p,inf),st[++top]=p,++cnt;
}
if(cnt==n)return cout<<i<<"\n",0;
for(int j=1;j<=top;++j)t.upd(1,1,n,st[j]+1,n,1);
t.upd(1,1,n,1,n,-top);
}
return 0;
}