自力で通せたものの、時間内には間に合わず。
https://atcoder.jp/contests/abc262/tasks/abc262_h
問題
N要素の整数列Aを考える。
また、Q個の条件(L[i],R[i],X[i])が与えられる。
以下を満たす数列Aは何通りか。
- Aの各要素は、0以上M以下の整数である。
- Aの部分列A[L[i]...R[i]]の最大値はX[i]である。
解法
まず、各条件より各A[n]の最大値を求めよう。
次に「Aの部分列A[L[i]...R[i]]の最大値はX[i]である。」の条件より、A[L[i]...R[i]]中にに1つはX[i]を持たなければならない。
最大値Xが一致する一連のクエリと、最大値をXとするA[n]をまとめて考える。
dp(n,m) := Aのうち最大値がXとなるような添え字のうち、Aのprefix n個目まで考えたときにA[l]=Xとなる最大のlがmであるような組み合わせ
nを増やしながらdp(n,m)を更新していくが、この手順は
- A[n]をXとする場合、dp(n,n)=sum(dp(n-1,*))
- A[n]をX未満とする場合、dp(n,m)=dp(n-1,m)*X
と置ける。
ただし、R[i]=nとするクエリがある場合、m<L[i]であってはならないので、dp(n,l)=0 (l<m)としなければならない。
上記処理は、区間乗算、区間加算、区間総和を取れるSegTreeを用いれば処理できる。
int N,M,Q; ll A[202020]; vector<int> add[202020],del[202020]; int L[202020],R[202020],X[202020]; const ll mo=998244353; int rev2=(mo+1)/2; template<class V,int NV> class SegTree_MulAdd { public: vector<V> sum,mul,add; // sum stores val after muladd SegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);}; V getval(int x,int y,int l=0,int r=NV,int k=1) { if(r<=x || y<=l) return 0; if(x<=l && r<=y) return sum[k]; x=max(x,l); y=min(y,r); V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1); return (ret*mul[k]+add[k]*(y-x))%mo; } void propagate(int k,int s) { (mul[k*2]*=mul[k])%=mo; add[k*2]*=mul[k]; sum[k*2]*=mul[k]; (add[k*2]+=add[k])%=mo; (sum[k*2]+=add[k]*s%mo*rev2)%=mo; (mul[k*2+1]*=mul[k])%=mo; add[k*2+1]*=mul[k]; sum[k*2+1]*=mul[k]; (add[k*2+1]+=add[k])%=mo; (sum[k*2+1]+=add[k]*s%mo*rev2)%=mo; mul[k]=1; add[k]=0; } void domul(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { (mul[k]*=v)%=mo; (add[k]*=v)%=mo; (sum[k]*=v)%=mo; } else if(l < y && x < r) { propagate(k,r-l); domul(x,y,v,l,(l+r)/2,k*2); domul(x,y,v,(l+r)/2,r,k*2+1); sum[k]=(sum[k*2]+sum[k*2+1])%mo; } } void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { (add[k]+=v)%=mo; (sum[k]+=(r-l)*v)%=mo; } else if(l < y && x < r) { propagate(k,r-l); doadd(x,y,v/mul[k],l,(l+r)/2,k*2); doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1); (sum[k]=sum[k*2]+sum[k*2+1])%=mo; } } }; SegTree_MulAdd<ll,1<<18> st; map<int,vector<int>> cand; map<int,vector<int>> query; int vis[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>Q; multiset<int> C={M}; FOR(i,Q) { cin>>L[i]>>R[i]>>X[i]; add[L[i]].push_back(X[i]); del[R[i]].push_back(X[i]); query[X[i]].push_back(i); } for(i=1;i<=N;i++) { FORR(a,add[i]) C.insert(a); A[i]=*C.begin(); cand[A[i]].push_back(i); FORR(a,del[i]) C.erase(C.find(a)); } ll ret=1; FORR2(a,b,query) { st.domul(0,N+1,0); st.doadd(0,1,1); set<int> T; map<int,int> M; FORR(c,cand[a]) T.insert(c); FORR(i,b) { T.insert(R[i]); M[R[i]]=max(M[R[i]],L[i]); } FORR(t,T) { if(A[t]==a) { vis[t]=1; ll v=st.getval(0,t); st.domul(0,t,a); st.doadd(t,t+1,v); } st.domul(0,M[t],0); } ret=ret*st.getval(0,N+1)%mo; } for(i=1;i<=N;i++) if(vis[i]==0) ret=ret*(M+1)%mo; cout<<ret<<endl; }
まとめ
方針は本番中に立ったけど、実装が間に合わず…。