Codeforces #958 : Div2 E. Range Minimum Sum

なんかすごい長いコード書いたな。
https://codeforces.com/contest/1988/problem/E

問題

整数列aに対しf(a)は、aの各連続部分列における最小値の総和とする。

今1～NのPermutation 列Aが与えられる。
AからA[i]を取り除いた残りの数列Bに対するf(B)を値を、各iに対し求めよ。

解法

Cartesian Treeを作り、値の小さい点が祖先になるようにしていく。
各頂点について、その頂点のSubtreeに対応する区間に対し、左右から最小値を更新するindexを覚えておく。

各点を取り除くと、その点の左側の子と右側の子を両端とするケースで、f(A)の値がどの程度変化するか、前述のindexをマージソートの要領でマージしながら差分を計算していく。

int T;
int N;
int A[505050];
int re[505050];
int L[505050];
int R[505050];
int LP[505050];
int RP[505050];

ll sum[505050];
vector<int> Ls[505050],Rs[505050];
ll dif[505050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		set<int> S={0,N+1};
		FOR(i,N) {
			S.insert(i+1);
			cin>>A[i+1];
			re[A[i+1]]=i+1;
		}
		A[0]=A[N+1]=N+1;
		FOR(i,N+3) dif[i]=0;
		
		ll TS=0;
		for(i=N;i>=1;i--) {
			x=re[i];
			auto it=S.find(x);
			sum[x]=0;
			Ls[x].clear();
			Rs[x].clear();
			
			
			vector<int> RL,LR;
			if(*prev(it)==0||A[*prev(it)]<i) {
				LP[x]=0;
				L[x]=x;
			}
			else {
				LP[x]=*prev(it);
				L[x]=L[LP[x]];
				swap(Ls[x],Ls[LP[x]]);
				swap(RL,Rs[LP[x]]);
			}
			if(*next(it)==N+1||A[*next(it)]<i) {
				RP[x]=N+1;
				R[x]=x;
			}
			else {
				RP[x]=*next(it);
				R[x]=R[RP[x]];
				swap(Rs[x],Rs[RP[x]]);
				swap(LR,Ls[RP[x]]);
			}
			
			dif[x+1]-=1LL*(x-L[x]+1)*A[x];
			dif[R[x]+1]+=1LL*(x-L[x]+1)*A[x];
			dif[L[x]]-=1LL*(R[x]-x+1)*A[x];
			dif[x]+=1LL*(R[x]-x+1)*A[x];
			
			sum[x]=-1LL*i*(x+1-L[x])*(R[x]+1-x);
			TS+=1LL*i*(x+1-L[x])*(R[x]+1-x);
			
			int CL=L[x];
			int CR=R[x];
			while(RL.size()||LR.size()) {
				if(RL.empty()) {
					pat1:
					y=LR.back();
					sum[x]+=1LL*A[y]*(x-CL)*(CR-y+1);
					CR=y-1;
					LR.pop_back();
				}
				else if(LR.empty()) {
					pat2:
					y=RL.back();
					sum[x]+=1LL*A[y]*(y-CL+1)*(CR-x);
					CL=y+1;
					RL.pop_back();
				}
				else if(A[LR.back()]<A[RL.back()]) {
					goto pat1;
				}
				else {
					goto pat2;
				}
			}
			
			if(LP[x]!=0) S.erase(LP[x]);
			if(RP[x]!=N+1) S.erase(RP[x]);
			
			
			Ls[x].push_back(x);
			Rs[x].push_back(x);
		}
		
		
		FOR(i,N) {
			dif[i+1]+=dif[i];
			cout<<TS+sum[i+1]+dif[i+1]<<" ";
		}
		cout<<endl;
		
	}
	
}

まとめ

もっと短く書けないかな。