题目
D - Earthquakes
思路来源
官方题解
题解
对于不存在连锁反应的区间，每个区间独立处理，最后求个乘积
对于每个区间，相邻的两个杆子距离都小于H，
意味着没倒的区间是个连续的区间，假设要算i的概率
一定是第i次地震时，i从没倒变成倒了，并且i倒完之后，所有都倒了
那在i倒之前，i是这个连续的区间的左端点或右端点
举个例子，比如6 1 3 2 4 5，
如果3在第三轮倒，并且把其他所有的都带倒了，一定是以下两种情况之一：
①3朝左倒：3右边的比3小的都往右倒了，并且把比3大的都带倒了，也就意味着3右边第一个就是比3小的，并且右边每一个比3小的都向右倒了
②3朝右倒：同理，3左边第一个就比3小，并且左边每一个比3小的都向左倒了
统计同一个块内左侧右侧小的数个数，用单调栈解决
计两侧比3小的数量为cnt1，首先概率需要乘上cnt1
此外，考察与3相邻的两个数，
1. 左右都比3小，3就两侧都可以倒，
2. 否则，有一个比3小，就只能倒向另一侧
3. 如果都比3大就没有合法方案了
也就是，与3相邻的两个数比3小的个数为cnt，则概率还需要乘上(1/2)*cnt
算完i所在的块的之后，还需要乘上其他块在第i轮都倒了的概率
这个现算很难算，但是注意到，其他块能在第i轮都倒了，
一定是在[1,i-1]轮里的某一轮倒的，而之前的概率在对应块里算过，
所以，对于每个块，维护一下全倒了的概率和即可，
第i轮全倒的概率，是这若干个其他块已经倒了 和 i所在的块在第i轮倒的积
输出完之后，把新增概率加到当前块的概率和里
由于0不存在逆元，所以记录一下概率为0的块的个数，分别维护0的个数和概率乘积
代码
#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,mod=998244353,inv2=(mod+1)/2;
int modpow(int x,int n,int mod){
int res=1;
for(;n;n/=2,x=1ll*x*x%mod){
if(n&1)res=1ll*res*x%mod;
}
return res;
}
int n,h,x[N],id[N],par[N],ans[N],cnt[N],zero;
int stk[N],c,l[N],r[N];
int main(){
sci(n),sci(h);
rep(i,1,n){
sci(x[i]);
id[i]=i;
par[i]=i;
}
sort(id+1,id+n+1,[&](int a,int b){
return x[a]<x[b];
});
rep(i,1,n){
int p=id[i],pre=id[i-1];
if(i==1 || x[pre]<x[p]-h)par[p]=p,c=0,zero++;
else par[p]=par[pre];
if(stk[c]<=p)cnt[p]++;
while(c && stk[c]>p)c--;
l[p]=c;
stk[++c]=p;
}
//stk[c=0]=0;
c=0;
per(i,n,1){
int p=id[i];
if(c && x[stk[c]]>x[p]+h)c=0;
if(stk[c]<=p)cnt[p]++;
while(c && stk[c]>p)c--;
r[p]=c;
stk[++c]=p;
}
int prob=1,bs=1ll*modpow(2,n,mod);
rep(i,1,n){
//printf("i:%d par:%d cnt:%d l+r:%d ans:%d\n",i,par[i],cnt[i],l[i]+r[i],ans[par[i]]);
int &p=ans[par[i]];
if(p)prob=1ll*prob*modpow(p,mod-2,mod)%mod;
else zero--;
int add=1ll*cnt[i]*inv2%mod*modpow(inv2,l[i]+r[i],mod)%mod;
int ans=zero?0:1ll*prob*add%mod*bs%mod;
printf("%d%c",ans," \n"[i==n]);
p=(p+add)%mod;
if(p)prob=1ll*prob*p%mod;
else zero++;
}
return 0;
}
