题解：P11800 【MX-X9-T4】『GROI-R3』区间

· · 题解

这个题还是比较有趣的。

首先分析一下题目，题目中给出了一个比较奇怪的限制，区间长度不同。一般来说，这种限制要么是为了保证题目有解，要么是保证复杂度。这题中显然不是前者，但具体是如何保证复杂度的，我们先继续思考。

另外，发现除了 a_i 之外，其他的值域都是 10^{18} 级别，说明最后的复杂度大概率与 a_i 有关。

题目给出的条件其实是说对于给定的 m 个区间，将每个区间向左平移 a_i 个单位，被区间覆盖的位置是被 ban 掉的，求没被 ban 掉的数的个数。由于 a_i 非常小，我们对这个题目有一个大体的感受，那就是区间之间会有许多交集。

具体分析一下，若有一个区间 [l,r]，分别有两个平移的距离 a_i<a_j，最后形成的区间 [l-a_i,r-a_i] 和 [l-a_j,r-a_j] 有交的条件为 l-a_j\le r-a_i，即 a_i-a_j\le r-l。考虑将每 r-l 分为一段，一段中的 a_i 都是可以合并的，也就是说，每段会合并出一个区间。这样，形成的区间个数是 \frac{a_i}{r-l} 的。在复杂度的分析中，默认 O(a_i)=O(n)。由于区间长度不同，根据调和级数，区间的个数是 O(n\log n) 的。这也印证了我们一开始的关于区间长度不同保证复杂度的猜想。

令 S=n\log n，这样总的时间复杂度为 O(S\log S)，可能无法通过这题。但是，我们只要对每个区间处理的时候先按上面的步骤合并一次，再将合并出的区间合并第二次，就会大大减少区间的个数。经过实测，两次合并后的区间个数小于 10^6 个，可以非常轻松地通过。不过我也不太清楚这里的复杂度是否有所改变，因为这里合并后的区间个数居然是 O(n) 级别的，希望大家可以一起分析一下。下面给出代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5,M=1e6,inf=2e18;
struct node{
    int l,r;
}b[M],c[N];
bool cmp(node a,node b){
    return a.l<b.l;
}
int n,m,v,a,l,r,L[N+10],R[N+10],cnt;
signed main(){
    scanf("%lld%lld%lld",&n,&m,&v);
    memset(R,127,sizeof R);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a);
        L[a]=R[a]=a;
    }
    for(int i=1;i<=N;i++){
        L[i]=max(L[i],L[i-1]);
    }
    for(int i=N;i>=1;i--){
        R[i]=min(R[i],R[i+1]);
    }
    c[0]={inf,inf};
    for(int i=1;i<=m;i++){
        scanf("%lld%lld",&l,&r);
        int len=r-l,cnt0=0;
        for(int ll=1;ll<=N;ll+=len+1){
            int rr=ll+len;
            if(rr>N)rr=N;
            int a1=R[ll],a2=L[rr];
            if(a1>rr||a2<ll)continue;
            int LL=l-a2,RR=r-a1;
            if(RR<1)continue;
            if(LL<1)LL=1;
            if(LL>v)continue;
            if(RR>v)RR=v;
            c[++cnt0]={LL,RR};
        }
        int lll=c[cnt0].l,rrr=c[cnt0].r;
        for(int j=cnt0-1;j>=0;j--){
            if(c[j].r<=rrr)continue;
            if(c[j].l<=rrr)rrr=c[j].r;
            else{
                b[++cnt]={lll,rrr};
                lll=c[j].l,rrr=c[j].r;
            }
        }
    }
    sort(b+1,b+1+cnt,cmp);
    int ans=v,mx=0;
    for(int i=1;i<=cnt;i++){
        if(b[i].r<=mx)continue;
        if(b[i].l<=mx)ans-=(b[i].r-mx);
        else ans-=(b[i].r-b[i].l+1);
        mx=b[i].r;
    }
    cout<<ans;
    return 0;
}