Codeforces #852 : Div2 F. Rebrending

3250ptの問題なのに、Fの方がupsolve数多いな。
https://codeforces.com/contest/1793/problem/F

問題

1～Nの順列である整数列Aが与えられる。
以下のクエリに答えよ。

• 区間[L,R]が指定される。A[L...R]の値のうち、2値の差の最小値を求めよ。

解法

Mo's Algorithmを回すだけでも間に合う。

int N,Q;
int A[303030],pos[303030];
int PL[303030],PR[303030];

int L[1303030],R[1303030];
int ret[1303030];
const int DI=550;

int S[303030];
int B[303030];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&Q);
	FOR(i,303030) S[i]=B[i]=1<<20;
	FOR(i,N) {
		scanf("%d",&A[i]);
		A[i]--;
		pos[A[i]]=i;
	}
	vector<pair<int,int>> Qs;
	FOR(i,Q) {
		scanf("%d%d",&L[i],&R[i]);
		L[i]--;
		Qs.push_back({L[i],i});
	}
	sort(ALL(Qs));
	
	for(i=N-2;i>=0;i--) {
		for(j=i+1;j<N&&j-i<DI;j++) {
			chmin(S[j],abs(A[j]-A[i]));
			chmin(B[j/DI],abs(A[j]-A[i]));
		}
		for(j=max(0,A[i]-DI);j<min(N,A[i]+DI);j++) if(pos[j]>i) {
			x=pos[j];
			chmin(S[x],abs(A[x]-A[i]));
			chmin(B[x/DI],abs(A[x]-A[i]));
		}
		while(Qs.size()&&Qs.back().first==i) {
			x=Qs.back().second;
			Qs.pop_back();
			ret[x]=1<<20;
			for(y=L[x]/DI;y<R[x]/DI;y++) chmin(ret[x],B[y]);
			for(y=R[x]/DI*DI;y<R[x];y++) chmin(ret[x],S[y]);
		}
	}
	
	FOR(i,Q) _P("%d\n",ret[i]);
		
	
	
}

まとめ

なんでこれFなんだろ。