前言

在這里提供運用 ST 表思想但又略不同于 ST 表的構造方法，能夠在 \(n=4000\) 時相比 ST 表少構造將近 \(4000\) 個區間。

解析

構造的思路是這樣的：

設 \(len\) 為詢問的區間的長度，從小到大考慮。

當 \(len=1\) 時，詢問區間必定只能是相同的長度為一的區間的并，故對于所有 \(1 \le i\le n\)，必定需要構造一個 \([i,i]\) 的區間。

當 \(len=2\) 時，詢問區間可以通過先前構造的長度為 \(1\) 的相鄰兩個區間取并得到。

當 \(len=3\) 時，無法通過現有的區間得到詢問區間，故對于所有 \(1 \le i \le n-2\)，構造一個 \([i,i+2]\) 的區間。

當 \(4 \le len \le 6\) 時，可以發現詢問區間可以通過兩個長度為 \(3\) 的區間取并得到。

事實上，如果我們構造了一連串的一個長度為 \(i\) 的區間，那么對于所有 \(i \le len \le i \times2\)，詢問區間都可以由兩個長度為 \(i\) 的區間取并得到。

具體地，對于滿足 \(i \le len \le i \times2\) 的一次詢問 \(L,R\)，可以先選取一個以 \(L\) 為左端點，長度為 \(i\) 的區間，再選取一個以 \(R\) 為右端點（即以 \(L+len-i\) 為左端點），長度為 \(i\) 的區間，取并得到詢問區間。

這樣，我們就只需要從長度為 \(1\) 的區間開始構造，每次將長度乘 \(2\) 再加 \(1\)。

通過這種方法構造出來的區間，第 \(k\) 短的區間長度為 \(2^k-1\)，ST 表則是 \(2^{k-1}\)，并且，如果 \(n\) 不等于 \(2\) 的冪減 \(1\)，這種方法構造出來的不同區間長度的數量比 ST 表少 \(1\)，其余情況相等。

由此可見，當 \(n \not = 1\) 時，此方法構造出來的區間的數量總是比 ST 表少。

代碼

#include <bits/stdc++.h>
using namespace std;
const int N = 4e3 + 5;
vector<int> v[N];//v[i][j]表示是否構造出長度第 i 短，左端點位于 j 的區間，
int s[N],lth[N];//s[i]表示構造出來的第 1 至第 i 短的區間個數
			//lth[i]表示第 i 短的區間的長度
int main(){
	int n,cnt = 0;
	cin>>n;
	for(int len = 1;len <= n;len = len * 2 + 1){
		cnt++;
		lth[cnt] = len;
		for(int l = 1;l + len - 1 <= n;l++){
			v[cnt].push_back(l);//存的東西不重要，能判斷有沒有構造出這個區間即可
		}
		s[cnt] = s[cnt - 1] + v[cnt].size();
	}
	cout<<s[cnt]<<endl;
	for(int i=1;i<=cnt;i++){
		for(int j : v[i]){
			cout<<j<<' '<<j + lth[i] - 1<<endl;
		}
	}
	int q;
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		int len = r - l + 1;
		int t = upper_bound(lth,lth + cnt + 1,len) - lth - 1;
		cout<<s[t - 1] + l<<" "<<s[t - 1] + l + len - lth[t]<<endl;
	}
	return 0;
}