kmjp's blog

競技プログラミング参加記です

AtCoder ABC #262 (第三回日本最強プログラマー学生選手権-予選-) : Ex - Max Limited Sequence

自力で通せたものの、時間内には間に合わず。
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;
	
}

まとめ

方針は本番中に立ったけど、実装が間に合わず…。