题解：P16348 「MierOI R1」Eternal (Hard ver.)

· · 题解

我去我口胡出来了道啥？

约定集合 L_1,L_2,\dots,L_n 表示右端点为 i 的区间的左端点集合，R_1,R_2,\dots,R_n 表示左端点为 i 的区间的右端点集合。

首先题目的意大概是说叫你找出数量最多的区间使得不存在两个区间 [l_i,r_i],[l_j,r_j] 满足 l_i<l_j<r_i<r_j。

可以把 l_i=r_i 的区间扔了，后面再统计。

然后考虑若干个相交的区间（即建图后的连通块），一定是以下几种情况之一：

  1. 所有的区间共享一个左端点 j。将这样的一个块称之为左倾块。
  2. 所有的区间共享一个右端点 i。将这样的一个块称之为右倾块。
  3. 存在一个最大的区间 [j,i]，使得所有其他的区间都被包裹再这个区间内部，并且这些区间有一部分以 j 为左端点，一部分以 i 为右端点。同时为了防止两组区间出现相交的情况存在一个隔离点 k 使得不存在除了大区间的区间包含这个点。

定义 f_i 表示只考虑完全包含在坐标范围 [1,i] 内的区间时，最多能选取的合法的区间的数量。同时，为了方便书写，定义 C(X,Y) 表示左端点属于集合 X，且右端点属于集合 Y 的区间数量。即：

C(X,Y)=\big|\{[u,v]\mid u\in X\land v\in Y\}\big|

转移的时候对上面的三种情况分讨：

  1. 对于第一种情况，当前位置可以什么也不选，或者作为一个左倾块的结束。转移方程为： f_i=\max_{1\le j<i}\Big(f_j+C(\{j\},[j,i]) \Big)
  2. 对于第二种情况，可以选取若干个以 i 为右端点的区间。设选择的这些区间中，最靠左的左端点是 j。\ 那么可以在 j 之前形成一个独立的最优解 f_j，然后加上所有左端点 \ge j 且右端点为 i 的区间数量。\ 那么转移方程为： f_i=\max_{j\in L_i}f_j+\text{C}([j,i],\{i\})
  3. 对于第三种情况，假设我们已经选出了一个隔离点 k，那么转移方程就是
f_i=\max_{j\in L_i}\big(f_j+C(\{j\},\{i\})+\max_{j<k \le i}(C(\{j\},[j,k))+C([k,i],\{i\})\big)

最终的 f_i 就是这三个转移方程求出的答案的最大值。

第一个转移方程可以使用线段树维护，第二个转移方程可以直接用我们的 L_i 求出。所以我们接下来只需要找到这个 k 了。

观察 C(\{j\},[j,k)) 的值和 C([k,i],\{i\}) 的值在什么时候会发生变化。

显然最优的 k 一定在一个发生了变化的坐标上。

那么我们只需要在 L_i 和 R_j 中的点中寻找 k。

但是这样子的时间复杂度仍然是 O(n^2) 的，所以可以考虑知名乱搞，又称启发式。

可以只遍历 L_i 和 R_j 中更小的那个集合。可以证明均摊时间复杂度是 O(\sqrt m) 的。

然后再证明一下。 :::info[时间复杂度证明] 可以将每个区间 [j,i] 看作图上的一条有向边 j \to i。

那么 |R_j| 就是点 j 的出度 deg_{out}(j)，|L_i| 就是点 i 的入度 deg_{in}(i)。

所以我们启发式所产生的代价为 \min(deg_{out}(j), deg_{in}(i))。

然后有个结论就是对于一个有 m 条边的图满足：

\sum_{(u, v) \in E} \min(deg(u), deg(v)) \le O(m \sqrt{m})

然后这个我不会证。qaq。可以上网搜搜。 ::: :::info[启发式正确性证明] 假设 R_j 为更小的集合。

那么对于集合中两个相邻的点 r_1,r_2，(r_1,r_2] 这个区间范围内 C(\{j\},[j,k))+C([k,i],\{i\}) 显然是单调不增的。

那么，这个区间的最大值一定是在这个区间的最左端。

同理如果 L_i 为更小的集合那么一个区间的最大值一定在这个区间的最右端。

由于 k 的取值是一个区间，选择 R_j 和 L_i 一定会取到这个区间的左端和右端，不会影响。

所以取较小的就好了。 :::

最后按题解模拟即可。（什

:::success[Code]

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=(int)(b);a<=(int)(c);a++)
#define Fro(a,b,c) for(int a=(int)(b);a>=(int)(c);a--)
#define Fov(g) for(auto e:g)
#define ms(a) memset(a,0,sizeof (a))
#define int long long
#define ull unsigned long long
#define pb push_back
using namespace std;
constexpr int N=2e5+5,MOD=998244353;
int cnte[N],f[N],tr[N<<2],n,mxm,mxv;
vector<int> L[N],R[N];
void pushUp(int id){
    tr[id]=max(tr[id<<1],tr[id<<1|1]);
}
void build(int id,int l,int r){
    tr[id]=0;
    if(l==r) return;
    int mid=l+r>>1;
    build(id<<1,l,mid);
    build(id<<1|1,mid+1,r);
}
void upd(int id,int l,int r,int pos,int val){
    if(l==r){
        tr[id]+=val;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid) 
        upd(id<<1,l,mid,pos,val);
    else
        upd(id<<1|1,mid+1,r,pos,val);
    pushUp(id);
}
int query(int id,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return tr[id];
    int mid=l+r>>1,ans=0;
    if(ql<=mid) 
        ans=max(ans,query(id<<1,l,mid,ql,qr));
    if(qr>mid) 
        ans=max(ans,query(id<<1|1,mid+1,r,ql,qr));
    return ans;
}
void eval(int k,int j,int i){
    if(k<j+1||k>i) return;
    int pj=upper_bound(R[j].begin(),R[j].end(),min(k,i-1))-R[j].begin();
    int si=L[i].end()-lower_bound(L[i].begin(),L[i].end(),k);
    mxv=max(mxv,pj+si);
}
void solve(){
    mxm=0;
    cin>>n;
    For(i,1,n){
        int l,r;
        cin>>l>>r;
        if(l==r)
            cnte[l]++;
        else
            L[r].pb(l),R[l].pb(r);
        mxm=max(mxm,r);
    }
    For(i,1,mxm)
        sort(L[i].begin(),L[i].end()),sort(R[i].begin(),R[i].end());
    build(1,1,mxm);
    f[0]=0;
    For(i,1,mxm){
        Fov(L[i])
            upd(1,1,mxm,e,1);
        int nfi=f[i-1];
        if(i>1)
            nfi=max(nfi,query(1,1,mxm,1,i-1));
        For(m,0,(int)L[i].size()-1)
            nfi=max((ull)nfi,f[L[i][m]]+L[i].size()-m);
        For(m,0,(int)L[i].size()-1){
            int j=L[i][m];
            if(m>0&&j==L[i][m-1])
                continue;
            int cji=upper_bound(L[i].begin(),L[i].end(),j)-L[i].begin()-m;
            mxv=0;
            if(R[j].size()<L[i].size()){
                eval(j+1,j,i);
                Fov(R[j])
                    if(e>=j+1&&e<=i-1)
                        eval(e,j,i);
            }
            else{
                eval(i,j,i);
                Fov(L[i])
                    if(e>=j+1&&e<=i)
                        eval(e,j,i);
            }
            nfi=max(nfi,f[j]+cji+mxv);
        }
        f[i]=nfi+cnte[i];
        upd(1,1,mxm,i,f[i]);
    }
    cout<<f[mxm]<<"\n";
    For(i,0,mxm)
        cnte[i]=0,L[i].clear(),R[i].clear(),f[i]=0;
}
signed main(){
    int t;
    cin>>t;
    while(t--) 
        solve();
    return 0;
}

:::