原题
题目描述
你需要生成M(M<=50000)个区间，选择其中的两个区间组成给定的区间。
解题思路
我们看到把两个区间合并成一个区间，就是 ST 表基本操作。我们利用倍增预处理出以 i 位置为左端点，包含个元素的区间。对于 [l,r] 区间的询问，我们选取适当的 k，把给定区间拆分为 [l,l+2k−1]，[r−2k+1,r] 两个区间，使得两个区间的并为原询问区间，输出两个区间分别的编号即可。
#include<bits/stdc++.h> using namespace std; int f[4010][20];//st表 int _log[4010]; vector<pii> v;//存储输出的区间 int main(){ int n,cnt=0; cin>>n; _log[1]=0; for(int i=2;i<=n;i++){ _log[i]=_log[i/2]+1; } //预处理一下log for(int j=0;(1<<j)<=n;j++){ for(int i=1;i+(1<<j)-1<=n;i++){ cnt++; f[i][j]=cnt; v.emplace_back(i,i+(1<<j)-1); } } //构建st表，同时记录区间及其编号 cout<<cnt<<endl; for(auto i:v){ cout<<i.first<<" "<<i.second<<endl; } int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int len=(r-l+1); cout<<f[l][_log[len]]<<" "<<f[r-(1<<_log[len])+1][_log[len]]<<endl; } return 0; }
