AT_abc262_h [ABC262Ex] Max Limited Sequence 题解

首先容易确定每个位置的上界，接下来考虑对每种上界分别求方案数，再乘起来。

对每一种上界将其对应的位置提出来，由于是区间 \(\max\)，只需要关注每个位置的值是否到达这个上界 \(x\)。枚举一个前缀，考虑维护 \(f_i\) 表示最后一个达到上界位置为 \(i\)，确定完这个前缀中所有数的方案数。考虑确定当前枚举到的数 \(p\)：

1. \(<x\)，则将所有 \(f_i\leftarrow f_i\cdot (x-1)\)。
2. \(=x\)，则将 \(f_p\leftarrow f_p+\sum f_i\)

接下来只需要处理掉区间的限制，对于一个右端点为 \(p\) 的区间 \([l,p]\)，此时 \(\forall i<l,f_i\leftarrow 0\) 即可，时间复杂度 \(\mathcal O(n\log n)\)，线段树或者双指针都可以实现。

参考代码：

#include<bits/stdc++.h>
#define ll long long
#define mxn 200003
#define md 998244353
#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define rept(i,a,b) for(int i=(a);i<(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
struct node{
	int l,r,x;
}d[mxn];
int n,m,q,a[mxn],c[mxn];
vector<int>p[mxn],s1[mxn],s2[mxn];
vector<node>as[mxn];
multiset<int>s;
ll ans=1,t[mxn<<2],f[mxn<<2];
void build(int p,int l,int r){
	t[p]=!l,f[p]=1;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
inline void tag(int p,ll x){
	t[p]=t[p]*x%md,f[p]=f[p]*x%md;
}
inline void push_down(int p){
	if(f[p]!=1){
		tag(p<<1,f[p]),tag(p<<1|1,f[p]);
		f[p]=1;
	}
}
void add(int p,int x,int y,int l,int r){
	t[p]=(t[p]+y)%md;
	if(l==r)return;
	int mid=(l+r)>>1;
	push_down(p);
	if(x<=mid)add(p<<1,x,y,l,mid);
	else add(p<<1|1,x,y,mid+1,r);
}
void upd(int p,int l,int r,int L,int R){
	if(l<=L&&R<=r){t[p]=f[p]=0;return;}
	int mid=(L+R)>>1;
	push_down(p);
	if(l<=mid)upd(p<<1,l,r,L,mid);
	if(r>mid)upd(p<<1|1,l,r,mid+1,R);
	t[p]=(t[p<<1]+t[p<<1|1])%md;
}
void solve(int x){
	rept(i,0,p[x].size())c[i]=-1;
	for(node i:as[x]){
		int l=lower_bound(p[x].begin(),p[x].end(),i.l)-p[x].begin(),r=upper_bound(p[x].begin(),p[x].end(),i.r)-p[x].begin()-1;
		if(l>r){
			puts("0");
			exit(0);
		}
		c[r]=max(c[r],l);
	}
	build(1,0,p[x].size());
	rept(i,0,p[x].size()){
		ll s=t[1];tag(1,a[x]);
		add(1,i+1,s,0,p[x].size());
		if(c[i]>=0)upd(1,0,c[i],0,p[x].size());
	}
	ans=ans*t[1]%md;
}
signed main(){
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0,l,r,x;i<q;++i){
		scanf("%d%d%d",&l,&r,&x);
		s1[l].pb(x),s2[r+1].pb(x);
		d[i]={l,r,x};
		a[i]=x;
	}
	a[q]=m;sort(a,a+q+1);
	rep(i,1,n){
		for(int j:s1[i])s.insert(j);
		for(int j:s2[i])s.erase(s.find(j));
		int mx=s.size()?*s.begin():m;
		p[lower_bound(a,a+q+1,mx)-a].pb(i);
	}
	rept(i,0,q)as[lower_bound(a,a+q+1,d[i].x)-a].pb(d[i]);
	rep(i,0,q)if(as[i].size()||p[i].size())solve(i);
	cout<<ans;
	return 0;
}