题解：P16698 [CSPro 29] 施肥

lailai0916 · 2026-08-31 04:59:39 · 题解

题意简述

给定 m 个区间，每次可以选择若干个区间。求有多少个区间 [L,R]，能够恰好表示成所选区间的并集。

解题思路

两个被覆盖区间首尾相邻时，中间也没有未施肥的田地。因此，已经覆盖到 x 时，下一个区间的左端点至多为 x+1。

考虑固定的 [L,R]。被选择的区间必须包含于 [L,R]。若所有这类区间已经覆盖整个 [L,R]，直接选择它们即可。因此，只需判断能否用若干个相接或相交的区间，从 L 连续覆盖到 R。

使用分治统计答案。对于当前区间 [l,r]，令 mid=\lfloor(l+r)/2\rfloor。递归处理完全位于两侧的答案，当前只统计满足 L\le mid<R 的答案。

先处理左半部分。对每个 x\in[l,mid]，定义 a_x。它表示仅使用左半部分内部区间时，从 x 开始能够覆盖到的最远位置。若没有以 x 为左端点的可用区间，则 a_x 不存在。

按照 x 递减计算。先求满足 y\le mid 的区间 [x,y] 中，最大的 y。设当前能够直接到达 d。下一段可以从 [x,d+1] 中任意位置开始，而这些位置的答案均已求出。因此转移为：

用线段树维护单点加入和区间最大值。右半部分完全对称。按照 y 递增计算 a_y。它表示仅使用右半部分内部区间时，覆盖到 y 所能到达的最左位置。此时在线段树上查询区间最小值。

接下来计算跨过分界线的信息。对左端点 x，定义 b_x。从 x 出发，先经过左半部分，再使用一个跨界或相邻区间。b_x 表示此时能到达的最小右端点。这个区间的左端点必须位于 [x,a_x+1]。从 x 开始的跨界区间也应计入。用另一棵线段树按照左端点维护右端点最小值，即可求出 b_x。

对右端点 y 对称处理。先使用一个跨界或相邻区间，再经过右半部分到达 y。此时 b_y 表示能取得的最大左端点。

于是跨越分界线的 [L,R] 合法，当且仅当：

任何合法覆盖都必须从两侧到达分界线，故两个不等式必要。再证充分性。[L,b_L] 和 [b_R,R] 均可被连续覆盖。两段都跨过或紧邻分界线，因此必然相交或首尾相邻。两个不等式还保证它们均包含于 [L,R]，故并集恰为 [L,R]。

现在得到两类点 (L,b_L) 和 (b_R,R)。按照第一维排序。扫描到 (b_R,R) 时，将满足 L\le b_R 的左侧点加入树状数组。树状数组按照 b_L 统计前缀和。查询不超过 R 的数量，便得到满足两个不等式的点对数。同一坐标下先加入再查询。

每个合法区间会在两个端点第一次落入分治两侧时被统计，因而不会遗漏或重复。每层分治扫描当前区间和相关输入区间，并进行对数复杂度的数据结构操作。总时间复杂度为 O((n+m)\log^2 n)，空间复杂度为 O(n+m)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const int inf=0x3f3f3f3f;
struct Tree
{
    int mn[N*4],mx[N*4];
    bool tag[N*4];
    void reset(int p)
    {
        mn[p]=inf;
        mx[p]=-inf;
        tag[p]=1;
    }
    void init()
    {
        reset(1);
    }
    void down(int p)
    {
        if(!tag[p])return;
        reset(p*2);
        reset(p*2+1);
        tag[p]=0;
    }
    void add(int p,int l,int r,int x,int y)
    {
        if(l==r)
        {
            mn[p]=min(mn[p],y);
            mx[p]=max(mx[p],y);
            return;
        }
        down(p);
        int mid=(l+r)/2;
        if(x<=mid)add(p*2,l,mid,x,y);
        else add(p*2+1,mid+1,r,x,y);
        mn[p]=min(mn[p*2],mn[p*2+1]);
        mx[p]=max(mx[p*2],mx[p*2+1]);
    }
    int ask_min(int p,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)return mn[p];
        down(p);
        int mid=(l+r)/2,res=inf;
        if(x<=mid)res=min(res,ask_min(p*2,l,mid,x,y));
        if(y>mid)res=min(res,ask_min(p*2+1,mid+1,r,x,y));
        return res;
    }
    int ask_max(int p,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)return mx[p];
        down(p);
        int mid=(l+r)/2,res=-inf;
        if(x<=mid)res=max(res,ask_max(p*2,l,mid,x,y));
        if(y>mid)res=max(res,ask_max(p*2+1,mid+1,r,x,y));
        return res;
    }
    void clear(int p,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)
        {
            reset(p);
            return;
        }
        down(p);
        int mid=(l+r)/2;
        if(x<=mid)clear(p*2,l,mid,x,y);
        if(y>mid)clear(p*2+1,mid+1,r,x,y);
        mn[p]=min(mn[p*2],mn[p*2+1]);
        mx[p]=max(mx[p*2],mx[p*2+1]);
    }
}reach_tree,left_tree,right_tree;
int n;
int a[N],b[N],tr[N];
vector<int> ls[N],rs[N];
void add(int x,int y)
{
    for(int i=x;i<=n;i+=i&-i)tr[i]+=y;
}
int ask(int x)
{
    int res=0;
    for(int i=x;i;i-=i&-i)res+=tr[i];
    return res;
}
ll solve(int l,int r)
{
    if(l==r)return 0;
    int mid=(l+r)/2;
    ll ans=solve(l,mid)+solve(mid+1,r);
    for(int i=mid;i>=l;i--)
    {
        a[i]=-inf;
        b[i]=inf;
        for(auto x:ls[i])
        {
            if(x>r)continue;
            if(x<=mid)a[i]=max(a[i],x);
            else b[i]=min(b[i],x);
            if(x>=mid)right_tree.add(1,1,n,x,i);
        }
        if(a[i]>-inf)
        {
            int x=reach_tree.ask_max(1,1,n,i,min(mid,a[i]+1));
            a[i]=max(a[i],x);
            reach_tree.add(1,1,n,i,a[i]);
        }
    }
    for(int i=mid+1;i<=r;i++)
    {
        a[i]=inf;
        b[i]=-inf;
        for(auto x:rs[i])
        {
            if(x<l)continue;
            if(x>mid)a[i]=min(a[i],x);
            else b[i]=max(b[i],x);
            if(x<=mid+1)left_tree.add(1,1,n,x,i);
        }
        if(a[i]<inf)
        {
            int x=reach_tree.ask_min(1,1,n,max(mid+1,a[i]-1),i);
            a[i]=min(a[i],x);
            reach_tree.add(1,1,n,i,a[i]);
        }
    }
    vector<array<int,3>> event;
    for(int i=mid;i>=l;i--)
    {
        if(a[i]>-inf)
        {
            int x=left_tree.ask_min(1,1,n,i,a[i]+1);
            b[i]=min(b[i],x);
        }
        if(b[i]<=r)event.push_back({i,0,b[i]});
    }
    for(int i=mid+1;i<=r;i++)
    {
        if(a[i]<inf)
        {
            int x=right_tree.ask_max(1,1,n,a[i]-1,i);
            b[i]=max(b[i],x);
        }
        if(b[i]>=l)event.push_back({b[i],1,i});
    }
    sort(event.begin(),event.end());
    for(auto [x,t,y]:event)
    {
        if(t==0)add(y,1);
        else ans+=ask(y);
    }
    for(auto [x,t,y]:event)if(t==0)add(y,-1);
    reach_tree.clear(1,1,n,l,r);
    left_tree.clear(1,1,n,l,r);
    right_tree.clear(1,1,n,l,r);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        ls[l].push_back(r);
        rs[r].push_back(l);
    }
    reach_tree.init();
    left_tree.init();
    right_tree.init();
    cout<<solve(1,n)<<'\n';
    return 0;
}