Codeforces #1008 : Div1 E. Another Folding Strip

これは本番中に解き切れてよかった。
https://codeforces.com/contest/2077/problem/E

問題

m要素の整数列Bに対し、f(B)を以下のように定める。
初期状態で各セルに0が書かれた1*mの紙テープを考える。
この紙テープをセルの境界にそって任意回数折り畳み、1か所指定した箇所にインクを垂らす。
そうすると、その位置に折り重なっている各セルの色が1加算される。
その後、折り畳みを解除する。
この作業を繰り返し、各セルの色値がBになるまでの最小回数とする。

整数列Aが与えられる。Aの部分列A'におけるf(A')の総和を求めよ。

解法

1回で色を加算できる複数のセルは、隣の加算されるセルの距離が奇数でなければならない。
右端を1つずつ伸ばしていくとき、そこから奇数マスだけ左側にえるセルのうち、そのセルが塗られた右端であるような回数について、同時に色を塗ることができる。
あとはそれで足りない分は、その点を起点として追加で塗ろう。

int T;
int N,A[202020];
const ll mo=998244353;

ll dif[202020];
map<ll,int> num[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N+2) num[i].clear(),dif[i]=0;
		ll ret=0;
		for(x=0;x<N;x++) {
			//ここからスタート
			(ret+=1LL*(N-x)%mo*A[x])%=mo;
			num[x+2][0]++;
			///1つ前からスタート
			if(x) {
				if(A[x-1]<A[x]) {
					(ret+=1LL*(N-x)%mo*(A[x]-A[x-1]))%=mo;
					num[x+2][0]++;
				}
				else {
					num[x+2][A[x-1]-A[x]]++;
				}
			}
			//2つ前からスタート
			while(num[x].size()) {
				ll a=num[x].begin()->first+dif[x]+A[x-1];
				if(a>=A[x]) break;
				ll b=num[x].begin()->second;
				(ret+=b*(N-x)%mo*(A[x]-a))%=mo;
				num[x].erase(num[x].begin());
				num[x+2][0]+=b;
			}
			
			
			swap(num[x],num[x+2]);
			dif[x+2]=dif[x]+A[x-1]-A[x];
			FORR2(a,b,num[x]) num[x+2][a-dif[x+2]]+=b;
			
			
		}
		cout<<ret<<endl;
	}
}

まとめ

E解けて珍しいと思ったけど、2250ptだったか。