P15585 [KTSC 2026] 绝妙区间 2 / Wonderful Interval 2 题解

· · 题解

首先考察合法要求，考虑把 [a_i,b_i] 看成区间，对值域进行扫描线，维护一个下标集合 S，在左侧加入 i，在右侧放下 i，如果中间某一个时刻所有 S 中的下标都要加一，那么就无解。

也就是说对于每一个 i，在扫过 [a_i,b_i] 的每一个时刻都要放下一个下标，形式化的说 \forall l\le i\le r,[a_i,b_i]\sube\{b_l,b_{l+1},\dots,b_r\}，可以发现这个条件是充要的。

发现上述条件可以写成 \bigcup_{i=l}^r[a_i,b_i]\sube\{b_l,b_{l+1},\dots,b_r\}，也就可以写成 \bigcup_{i=l}^r[a_i,b_i]\sube\bigcup_{i=l}^r[b_i,b_i]。

发现右侧一定是左侧的子集，所以只需求出两者的集合大小看看是否相等即可。

求右侧的集合大小显然弱于求左侧的集合大小，所以考虑求左侧。

考虑扫描右端点，用 ODT 维护每一个数值的最晚出现时间，查询时只需查询有多少个数值最晚出现时间大于 l 即可，使用 BIT 维护。

时间复杂度 O(n\log n+q\log n)。

#include<bits/stdc++.h>
#define cint const int
#define uint unsigned int
#define cuint const unsigned int
#define ll long long
#define cll const long long
#define ull unsigned long long
#define cull const unsigned long long
using namespace std;
cint N=2.5e5,Q=2.5e5;
int n,q;
int a[N+1],b[N+1],ql[Q+1],qr[Q+1];
int ans[Q+1],ansa[Q+1];
vector<int>qry[N+1];
struct Binary_Index_Tree{
    int a[N+1];
    inline void add(cint p,cint x)
    {
        for(int i=p;i<=n;i+=(i&-i))a[i]+=x;
    }
    inline int ask(cint p)
    {
        int s=0;
        for(int i=p;i;i-=(i&-i))s+=a[i];
        return s;
    }
    inline int ask(cint l,cint r)
    {
        return ask(r)-ask(l-1);
    }
}S;
struct seg{
    int l,r,x;
};
bool operator<(seg p,seg q)
{
    return (p.r<q.r);
}
struct Old_Driver_Tree{
    set<seg>S;
    void update(cint l,cint r,cint x)
    {
        set<seg>::iterator it;
        while(1)
        {
            it=S.upper_bound({l-1,l-1,x});
            if(it==S.end()||(*it).l>r)break;
            seg x=*it;
            S.erase(it);
            if(x.l<l)
            {
                if(x.r>r)
                {
                    ::S.add(x.x,-r+l-1);
                    S.insert({x.l,l-1,x.x});
                    S.insert({r+1,x.r,x.x});
                }
                else
                {
                    ::S.add(x.x,-x.r+l-1);
                    S.insert({x.l,l-1,x.x});
                }
            }
            else
            {
                if(x.r>r)
                {
                    ::S.add(x.x,-r+x.l-1);
                    S.insert({r+1,x.r,x.x});
                }
                else
                {
                    ::S.add(x.x,-x.r+x.l-1);
                }
            }
        }
        ::S.add(x,r-l+1);
        S.insert({l,r,x});
    }
    void clear()
    {
        while(!S.empty())
        {
            set<seg>::iterator it=S.begin();
            seg x=*it;
            S.erase(it);
            ::S.add(x.x,-x.r+x.l-1);
        }
    }
}T;
void solve()
{
    T.clear();
    for(int i=1;i<=n;++i)
    {
        T.update(a[i],b[i],i);
        for(int p:qry[i])
        {
            ans[p]=S.ask(ql[p],qr[p]);
        }
    }
}
vector<int> array_operation(vector<int>A,vector<int>B,vector<int>L,vector<int>R)
{
    n=A.size();
    for(int i=1;i<=n;++i)a[i]=A[i-1],b[i]=B[i-1];
    q=L.size();
    for(int i=1;i<=q;++i)ql[i]=L[i-1]+1,qr[i]=R[i-1]+1;
    for(int i=1;i<=q;++i)
    {
        qry[qr[i]].push_back(i);
    }
    solve();
    for(int i=1;i<=q;++i)ansa[i]=ans[i];
    for(int i=1;i<=n;++i)a[i]=b[i];
    solve();
    vector<int>res;
    for(int i=1;i<=q;++i)res.push_back(ans[i]==ansa[i]);
    return res;
}