原題鏈接

解析

注意到對于一個起點站 \(x\)，必定有另一個站 \(y > x\) 使得所有以 \(x\) 為起點站，終點站編號小于 \(y\) 的路線均處于停開狀態(tài)，而所有終點站編號大于等于 \(y\) 的路線均不處于停開狀態(tài)。

故考慮對于每個站 \(i\)，維護 \(a_i\) 表示以 \(i\) 為起點站的非停開線路的最小終點站編號。這樣，我們就得到了一個查詢和修改均為 \(O(nm)\) 的做法。

考慮優(yōu)化。對于一次修改操作 \((l,r)\)，實際上是讓 \(a[l,r]\) 對 \(r + 1\) 取 \(\max\)。觀察到 \(a\) 單調(diào)不減，故可以上線段樹，先線段樹上二分找到滿足 \(a_i \le r + 1\) 的最小 \(i\)，然后對 \(a[l,i]\) 進行區(qū)間賦值。

對于一次查詢操作，仍然利用單調(diào)性，線段樹上二分找到使得 \(a_i \le r,i\le l\) 的最大 \(i\)，此時最優(yōu)解為 \(p_r - p_i\)。對于 \([i+1,l]\) 這段區(qū)間，最優(yōu)解為 \(\min(a_j-p_j)\)，這個怎么維護呢？ push_up 顯然；區(qū)間推平時，\(a\) 都相等，\(p\) 必定取最大的 \(p\)，也就是最右的 \(p\)。

時間復雜度 \(O(m \log n)\)

代碼

#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
#define mid ((l + r) >> 1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 5,M = 100 + 5,mod = 998244353;
int pos[N];
int mn[N << 2],mx[N << 2],tag[N << 2];
int n,m;
void push_up(int p){
	mn[p] = min(mn[ls(p)],mn[rs(p)]);
	mx[p] = max(mx[ls(p)],mx[rs(p)]);
}
void add_tag(int p,int l,int r,int k){
	tag[p] = k;
	mx[p] = k;
	mn[p] = pos[k] - pos[r];
}
void push_down(int p,int l,int r){
	if(tag[p]){
		add_tag(ls(p),l,mid,tag[p]);
		add_tag(rs(p),mid + 1,r,tag[p]);
		tag[p] = 0;
	}
}
void build(int p,int l,int r){
	tag[p] = 0;
	if(l == r){
		mx[p] = l + 1;
		mn[p] = pos[l + 1] - pos[l];
		return;
	}
	build(ls(p),l,mid),build(rs(p),mid + 1,r);
	push_up(p);
}
int query(int p,int l,int r,int L,int R,int k){
	if(l == r) return mx[p] >= k ? l : 2e9;
	push_down(p,l,r);
	if(mx[ls(p)] >= k){
		return query(ls(p),l,mid,L,R,k);
	}else{
		return query(rs(p),mid + 1,r,L,R,k);
	}
}

void modi(int p,int l,int r,int L,int R,int k){
	if(l > R || r < L) return;
	if(l >= L && r <= R){
		add_tag(p,l,r,k);
		return;
	}
	push_down(p,l,r);
	modi(ls(p),l,mid,L,R,k),modi(rs(p),mid + 1,r,L,R,k);
	push_up(p);
}
int ask(int p,int l,int r,int L,int R){
	if(l > R || r < L) return 2e9;
	if(l >= L && r <= R){
		return mn[p];
	}
	push_down(p,l,r);
	return min(ask(ls(p),l,mid,L,R),ask(rs(p),mid + 1,r,L,R));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T;
	cin>>T;
	while(T--){
		
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			cin>>pos[i];
		}
		pos[n + 1] = 2.1e9;
		build(1,1,n);
		while(m--){
			int o;
			cin>>o;
			if(o == 1){
				int l,r;
				cin>>l>>r;
				int k = query(1,1,n,l,r,r + 1) - 1;
				if(k >= l){
					modi(1,1,n,l,min(k,r),r + 1);
				}
			}else{
				int l,r;
				cin>>l>>r;
				int k = query(1,1,n,l,r,r) - 1;
				k = min(k,n);
				int res = 2e9;
				if(k){
					res = pos[r] - pos[min(l,k)];
				}
				res = min(res,ask(1,1,n,k + 1,l));
				cout<<(res > 1e9 ? -1 : res)<<'\n';
			}
		}
	}
	return 0;
}