AtCoder ABC #342 (HUAWEI Programming Contest 2024) : G - Retroactive Range Chmax

珍しく快調。
https://atcoder.jp/contests/abc342/tasks/abc342_g

問題

N要素の整数列Aが与えられる。
以下のクエリを順次処理せよ。

• 部分列A[L,R]の各要素A[i]について、A[i]がX未満ならXに置き換える。
• 過去のクエリを1つなかったことにする
• A[i]の現在値を答える

解法

区間最大値更新、1点参照可能なSegTreeを考える。
巻き戻しなしなら、各ノードに最大値候補だけを置けばよいが、今回は巻き戻しがあり得るので各ノードにmultisetを配置し、各クエリの値を全部入れておく。

1点参照の場合は、その点の祖先にある各ノードのmultisetの最大値を取ればよい。

template<class V,int NV> class SegTree_2 {
public:
	multiset<V> val[2*NV];
	SegTree_2(){
		int i;
		FOR(i,2*NV) val[i].insert(0);
	};
	
	V getval(int entry) {
		entry += NV;
		ll ret=*val[entry].rbegin();
		while(entry>1) {
			entry>>=1;
			ret=max(ret,*val[entry].rbegin());
		}
		return ret;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k].insert(v);
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
	void del(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) val[k].erase(val[k].find(v));
		else if(l < y && x < r) {
			del(x,y,v,l,(l+r)/2,k*2);
			del(x,y,v,(l+r)/2,r,k*2+1);
		}
	}
};

int N;
SegTree_2<ll,1<<20> st;
int Q;
int A[202020],B[202020],C[202020],D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x;
		st.update(i,i+1,x);
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>A[i]>>B[i];
		if(A[i]==1) {
			cin>>C[i]>>D[i];
			st.update(B[i]-1,C[i],D[i]);
		}
		if(A[i]==2) {
			x=B[i]-1;
			st.del(B[x]-1,C[x],D[x]);
			
		}
		if(A[i]==3) {
			cout<<st.getval(B[i]-1)<<endl;
		}
	}
	
}

まとめ

今回の賞金賞品対象は国内限定ではないのか…？