题解 CF1375H 【Set Merging】

· · 题解

题目大意

给出一个长度为 n 的序列 a.开始时有 n 个集合 \{a_1\},\{a_2\},\dots,\{a_{n-1}\},\{a_n\}.每次可以合并两个集合 S,T,其中 S,T 要满足 S 集合中的最大值小于 T 集合中的最小值.接下来给出 q 次查询,每次查询给出 l_i,r_i,需要在 2.2\times10^6 操作内制作出所有的集合 \{a_{l_i},a_{l_i+1},\dots,a_{r_i-1},a_{r_i}\}.需要给出操作以及每个查询的集合的编号.

分析

考虑合并两个集合条件为一集合的最大值小于另一集合的最小值.查询的是取药组合出开始给出的序列的一个子串.所以最简单粗暴的方法就是找到子串内的数排序后逐个合并,但这显然是不行的.但这也提示了单次查询的操作上限必然是 n.所以需要考虑如何利用一些以前利用过的集合.考虑开一个权值线段树来维护,对于每个节点上需要维护当前节点内的数在数列上所有出现的位置.

那么暴力查询的代码就如下:

int Query(int now_left,int now_right,int now=1)
{
    //num 中记录的是当前范围内的数的所有出现位置(单调递增)
    int left=lower_bound(sgt[now].num.begin(),sgt[now].num.end(),now_left)-sgt[now].num.begin();
    int right=upper_bound(sgt[now].num.begin(),sgt[now].num.end(),now_right)-sgt[now].num.begin()-1;
    //找到当前查询的区间中在这个范围内的数最左边和最右边的位置
    if(right<left)//如果 right<left 显然不存在这个范围内的数
    {
        return 0;
    }
    if(left==right)//如果只有一个数那么可以直接用开始给出的集合
    {
        return sgt[now].num[left];
    }
    int lson=Query(NOW,LSON),rson=Query(NOW,RSON);//查找子树
    if(!lson||!rson)//如果左子树或右子树为空那么当前层就可以不用合并
    {
        return lson|rson;
    }
    //use 表示操作
    use[++cnt]=Range(lson,rson);//否则需要合并
    return cnt;
}

这样就可以做到单次查询操作数小于 n 了.

考虑如何优化这个东西.

考虑对于每个线段树上的节点只会有 len^2(len 是所对应的值域的范围)种本质不同的查询(即上面代码中的 left,right 的不同种类).那么可以将 left,right 扔到 map 中,那么对于每个节点所产生的操作上限就是 len^2 级别了.

代码如下:

int Query(int now_left,int now_right,int now=1)
{
    int left=lower_bound(sgt[now].num.begin(),sgt[now].num.end(),now_left)-sgt[now].num.begin();
    int right=upper_bound(sgt[now].num.begin(),sgt[now].num.end(),now_right)-sgt[now].num.begin()-1;
    if(right<left)
    {
        return 0;
    }
    if(left==right)
    {
        return sgt[now].num[left];
    }
    int p=sgt[now].Hash[make_pair(left,right)];
    if(p)//如果存在过就直接返回
    {
        return p;
    }
    int lson=Query(NOW,LSON),rson=Query(NOW,RSON);
    if(!lson||!rson)
    {
        return sgt[now].Hash[make_pair(left,right)]=lson|rson;//每次查询完就扔到 map 里
    }
    use[++cnt]=Range(lson,rson);
    return sgt[now].Hash[make_pair(left,right)]=cnt;
}

然后就会惊讶的发现可以过了.

复杂度分析(感谢 \color{black}{\sf A}\color{red}{\sf{utumnKite}} 提供证明思路):

记 N=\lceil\log_2n\rceil,Q=\lceil\log_2q\rceil.

那么对于深度大于 \frac{Q}{2} 层的操作数上限为(对于每个节点的 len^2 种情况都跑满)

\sum_{i=1}^{\frac{Q}{2}}(2^{N-i}\cdot\frac{2^{i^2}}{2})=\sum_{i=1}^{\frac{Q}{2}}2^{N+i-1}\leq 2^{N+\frac{Q}{2}}

对于深度小于等于 \frac{Q}{2} 层的操作数上限为(每次操作都将所有节点跑到)

q\times2^{N-\frac{Q}{2}}\leq 2^{N+\frac{Q}{2}}

所以总操作数上限为 2^{N+\frac{Q}{2}+1} 与 n\sqrt{q} 同阶.

代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(int i=first;i<=last;++i)
#define DOW(i,first,last) for(int i=first;i>=last;--i)
using namespace std;
const int MAXN=1e5+5;
const int MAXQ=2e6+2e5+5;
int n,q;
int arr[MAXN];
int app[MAXN];
struct Range//记录操作
{
    int left,right;
    Range(int l=0,int r=0)
    {
        left=l;
        right=r;
    }
}use[MAXQ];
int answer[MAXN];//记录答案
int cnt=0;
struct SegmentTree
{
    vector<int>num;
    map<pair<int,int>,int>Hash;
}sgt[MAXN*4];
#define LSON (now<<1)
#define RSON (now<<1|1)
#define MIDDLE ((left+right)>>1)
#define LEFT LSON,left,MIDDLE
#define RIGHT RSON,MIDDLE+1,right
#define NOW now_left,now_right
void Build(int now=1,int left=1,int right=n)//建树部分
{
    REP(i,left,right)//将在当前范围内的数扔到节点里面
    {
        sgt[now].num.push_back(app[i]);
    }
    sort(sgt[now].num.begin(),sgt[now].num.end());//按出现位置排序
    if(left==right)
    {
        return;
    }
    Build(LEFT);
    Build(RIGHT);
}
int Query(int now_left,int now_right,int now=1)//同上的记忆化查询
{
    int left=lower_bound(sgt[now].num.begin(),sgt[now].num.end(),now_left)-sgt[now].num.begin();
    int right=upper_bound(sgt[now].num.begin(),sgt[now].num.end(),now_right)-sgt[now].num.begin()-1;
    if(right<left)
    {
        return 0;
    }
    if(left==right)
    {
        return sgt[now].num[left];
    }
    int p=sgt[now].Hash[make_pair(left,right)];
    if(p)
    {
        return p;
    }
    int lson=Query(NOW,LSON),rson=Query(NOW,RSON);
    if(!lson||!rson)
    {
        return sgt[now].Hash[make_pair(left,right)]=lson|rson;
    }
    use[++cnt]=Range(lson,rson);
    return sgt[now].Hash[make_pair(left,right)]=cnt;
}
#undef LSON
#undef RSON
#undef MIDDLE
#undef LEFT
#undef RIGHT
#undef NOW
int main()
{
    scanf("%d%d",&n,&q);
    cnt=n;
    REP(i,1,n)
    {
        scanf("%d",&arr[i]);
        app[arr[i]]=i;
    }
    Build();
    int left,right;
    REP(i,1,q)
    {
        scanf("%d%d",&left,&right);
        answer[i]=Query(left,right);
    }
    printf("%d\n",cnt);
    REP(i,n+1,cnt)
    {
        printf("%d %d\n",use[i].left,use[i].right);
    }
    REP(i,1,q)
    {
        printf("%d ",answer[i]);
    }
    return 0;
}