[ABC282F] Union of Two Sets

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