AtCoder ABC #427 (パナソニックグループ プログラミングコンテスト2025) : G - Takahashi's Expectation 2

これは方針すら思いつかなかった…。
https://atcoder.jp/contests/abc427/tasks/abc427_g

問題

整数列Pと、正整数A,Bが与えられる。
以下のクエリに順次答えよ。

• Pの末尾に要素を加える。
• 整数Xが与えられる。Pの要素pに対し、以下の処理を順次加えたときの最終的な値を答えよ。
  • X≦pの時、XにAを加える
  • X＞pの時、XからBを引く

解法

Pに対し、Xに対し処理を行った結果が変化しない状態で、隣接要素の差がA以上に保つことができる。
具体的には、P=(p,q)としたとき、P'=(q-A, max(q, p-B))を用いてもよい。
さらにこれを応用すると、隣接要素の差がA以上である2つの数列を連結することもできる。

この状態だと何が良いかというと、隣接要素の差がA以上の場合、Xに対し処理を行うと何度かB減算したあと、A増加を繰り返すという単純な変化で表現できる。
あとは二分探索でBの減算回数を求めれば、長いPに対しても処理後の結果をO(log|P|)で求められる。

Pは愚直に1つの数列ではなく、2の累乗の長さの数列をO(log|P|)個持たせるように使用。
末尾に要素を追加していき、同じ長さの数列が2個並んだら、それらを連結する。
そうすれば、後者のクエリに対し、数列数がO(log|P|)、それぞれ処理後の値をO(log|P|)で求められる。

int N,A,B,Q;
ll P[404040];

vector<vector<ll>> S;

vector<ll> merge(vector<ll> L,vector<ll> R) {
	int NL=L.size(),NR=R.size();
	vector<ll> X={-1LL<<60};
	
	int CL=0,CR=0;
	while(CL<NL||CR<NR) {
		if(CL==NL) {
			addr:
			X.push_back(R[CR]-1LL*(NL-CL)*A);
			CR++;
		}
		else if(CR==NR) {
			addl:
			X.push_back(max(X.back()+A, L[CL]-1LL*CR*B));
			CL++;
		}
		else {
			ll vl=L[CL]-1LL*CR*B;
			ll vr=R[CR]-1LL*(NL-CL)*A;
			if(vl<vr) goto addl;
			else goto addr;
		}
	}
	X.erase(X.begin());
	return X;
}

void add(vector<ll> p) {
	if(S.empty()||S.back().size()!=p.size()) {
		S.push_back(p);
	}
	else {
		p=merge(S.back(),p);
		S.pop_back();
		add(p);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	FOR(i,N) {
		cin>>x;
		vector<ll> P={x};
		add(P);
		
	}
	
	
	cin>>Q;
	int NQ=0;
	while(Q--) {
		cin>>x;
		if(x==1) {
			cin>>x;
			vector<ll> P={x};
			add(P);
		}
		else {
			ll X;
			cin>>X;
			FORR(s,S) {
				if(s[0]>=X) {
					X+=s.size()*A;
				}
				else if(X-((ll)s.size()-1)*B>s.back()) {
					X-=1LL*s.size()*B;
				}
				else {
					int L=0;
					for(i=20;i>=0;i--) if(L+(1<<i)<=s.size()&&X-((1LL<<i)-1)*B>s[L+((1LL<<i)-1)]) {
						L+=1<<i;
						X-=(1LL<<i)*B;
					}
					X+=1LL*(s.size()-L)*A;
				}
			}
			cout<<X<<endl;
		}
	}
	
	
}

まとめ

数列を置き換えるところに考えが至らなかった。