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

· · 题解

前置知识

这应该是 dmy 省选模拟赛最简单的一道题了吧。

首先给出结论：一个区间是否是绝妙区间，当且仅当询问区间中 [A_i,B_i) 的并集等于这个区间内 B_i 组成的集合。

考虑证明：假设对于一一个数 A_i，他想要升到 B_i，那么必然从 A_i 到 B_i-1 都要有个数。所以 [A_i,B_i) 的并集是这个区间内 B_i 组成的集合的子集，显然后者也是前者的子集，所以只要判是否集合相等即可。又因为后者一定是前者的子集，我们只需要判集合大小是不是相等即可。

现在题意转化成求区间线段并，区间本质不同的数的个数。这个看前置知识使用 ODT 和树状数组即可，复杂度 O(n \log n)，具体实现可以看代码。

#define pb push_back
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
const int N=5e5+20;
int n,q,m,lst[N];
struct BIT{
    int c[N];
    void add(int x,int y){if(!x)return;for(;x<N;x+=x&-x)c[x]+=y;}
    int qry(int x){int r=0;for(;x;x-=x&-x)r+=c[x];return r;}
    int sum(int l,int r){return qry(r)-qry(l-1);}
}T,T2;
struct node{
    int l,r,t,v;
    node(int ll,int rr,int tt,int vv):l(ll),r(rr),t(tt),v(vv){}
    bool operator<(node x)const{return l<x.l;}
};
set<node>s;
auto split(int x){
    auto it=s.lower_bound(node(x,0,0,0));
    if(it!=s.end()&&it->l==x)return it;
    --it;
    int l=it->l,r=it->r,t=it->t,v=it->v;
    s.erase(it);
    s.insert(node(l,x-1,t,v));
    return s.insert(node(x,r,t,v)).first;
}
void assign(int l,int r,int t,int v){
    auto itr=split(r+1),itl=split(l);
    for(auto it=itl;it!=itr;++it)T.add(it->t,-(it->r-it->l+1)*it->v);
    s.erase(itl,itr);
    T.add(t,(r-l+1)*v);
    s.insert(node(l,r,t,v));
}
vector<pair<int,int>>vec[N];
vector<int> array_operation(vector<int>A,vector<int>B,vector<int>L,vector<int>R){
    n=A.size(),q=L.size();
    vector<int>a=A,b=B,l=L,r=R,ans(q),tmp;
    m=0;
    rep(i,0,n-1)tmp.pb(b[i]),m=max(m,b[i]);
    rep(i,0,n+5)vec[i].clear();
    rep(i,0,q-1)l[i]++,r[i]++,vec[r[i]].pb({l[i],i});
    s.clear(),s.insert(node(1,m+1,0,0));
    rep(i,1,n){
        assign(a[i-1],b[i-1],i,1);
        for(auto[ql,id]:vec[i])ans[id]=T.sum(ql,i);
    }
    sort(tmp.begin(),tmp.end()),tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    rep(i,0,n-1)b[i]=lower_bound(tmp.begin(),tmp.end(),b[i])-tmp.begin()+1;
    rep(i,1,n){
        if(lst[b[i-1]])T2.add(lst[b[i-1]],-1);
        T2.add(i,1),lst[b[i-1]]=i;
        for(auto[ql,id]:vec[i])ans[id]=(ans[id]==T2.sum(ql,i));
    }
    return ans;
}