题解——[ABC282F] Union of Two Sets

yuyc · 2024-06-12 15:05:58 · 题解

前言

在这里提供运用 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;
}