区间和 Namomo 每日一题div1 03-27

题目链接

题意

有一个长度为$n$的数组$A$，另外给出$Q$段区间， 你知道这$Q$段区间内的所有元素的和， 给出区间的描述为$[L_i,R_i]$，保证所有的区间都合法， 并且对任何$i\ne j,[L_i,R_i]\ne [L_j,R_j]$

问给出的这些区间能不能确定这$n$个元素的和

数据范围

$1\le n\le 2\times {10}^5,1\le Q\le min(n,\frac{n\times (n+1)}{2})$

题解

显然我们可以用这些区间对整个数组进行覆盖， 看是否可以每个位置都只被覆盖一次

覆盖操作分为三种

1. 将区间内所有数的覆盖次数加1
2. 将区间内所有数的覆盖次数减1
3. 什么也不做， 相当于这个区间没有用

思路

那么我们就可以对于每个位置， 找到所有可以覆盖到这个位置的区间， 然后决定用哪些区间覆盖使得这个位置只被覆盖1次

这显然是无法实现的， 因为你不能确定对每个位置用那些区间怎么覆盖， 不同位置如果被同一个区间包含那也不好处理

优化

如果我们将区间按左端点为关键字从小到大排序， 这样的话我们就可以从$1$到$n$顺序枚举每个位置， 如果这个位置目前被覆盖的次数需要被修改， 那我们就看看有没有对应左端点为这个位置的区间并尝试更改

但是这还是有问题的， 因为可能出现一个位置对应了多个区间的左端点的情况， 这样我们还是不能确定怎么覆盖

继续优化

既然可能出现一个位置对应了多个区间左端点的情况， 那我们就通过分割把他们分成左端点不同的两段区间

假设存在$i,j$, $L_i=L_j,R_i<R_j$， 那么我们可以把他们分成两段左端点不同的等效区间$[L_i,R_i],[R_i+1,R_j]$

这样就不存在左端点相同的情况了， 然后顺序枚举每个位置即可

代码

实现思路

在实际写代码的过程中， 我们将区间的左端点作为第一关键字， 右端点作为第二关键字从小到大排序， 然后将左端点相同的区间分割， 为实现这个操作， 我们只需要在排好序的区间序列中把当前区间的左端点与前一个区间的左端点比较就好了

但是可能会存在如下情况：

$L_i=L_j,R_i<R_j$， 我们将其分割成$[L_i,R_i],[R_i+1,R_j]$后， 又出现了存在$R_i+1$为左端点重复的情况，那我们就需要用$[R_i+1,R_j]$来更新其他区间， 所以我们的区间序列实际上应该是动态维护的， 鉴于完全相同的两个区间显然有一个就行， 我们使用stl set来维护这个序列

如果原始区间存在多个区间共享一个左端点的情况， 这个方法也是可以处理的， 精髓就在于将分割出的区间塞回set

#include <iostream>
#include <cstdio>
#include <set>

int n, q;
int s[200005]; // 差分数组， 用于计算每个位置被覆盖的次数
int mxr[200005]; // 最大右端点位置
struct Seg
{
    int a, b;

    bool operator < (Seg tmp) const
    {
        if(a < tmp.a)
            return true;
        else if(a > tmp.a)
            return false;
        else
            return b < tmp.b;
    }
};
std:: set<Seg> st;
int l[200005], r[200005], cnt; // 最终更新区间的左端点， 右端点和区间个数

int main()
{
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= q; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        st.insert((Seg){a, b});
    }

    while(! st.empty())
    {
        int a = st.begin()->a, b = st.begin()->b;
        st.erase(st.begin()); 

        if(mxr[a]) // 存在左端点相同的区间， 需要分隔
            st.insert((Seg){mxr[a] + 1, b});
        else // 不存在左端点相同的区间， 放到更新区间里
            cnt ++, l[cnt] = a, r[cnt] = b;
      
        mxr[a] = b;
    }

    bool judge = true;

    int now = 0;
    for(int i = 1; i <= n; i ++)
    {
        s[i] += s[i - 1]; // 计算覆盖次数

        if(i == l[now + 1]) now ++;

        if(s[i] == 1)
            continue;
        else if(s[i] == 2)
        {
            if(i == l[now])
                s[i] --, s[r[now] + 1] ++; // 差分
            else
                judge = false;
        }
        else if(s[i] == 0)
        {
            if(i == l[now])
                s[i] ++, s[r[now] + 1] --; // 差分
            else
                judge = false;
        }
        else
            judge = false;
    }

    if(judge)
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

$mxr[i]$表示以$i$为左端点的区间中(不论这个区间是原始区间还是最终区间， 都要参与数组的更新)， 最大的右端点， 保证了分割出的区间不会有冗余

问题

我们分割出了一段新的区间$[R_i+1,R_j]$， 会不会存在区间$[R_i+1,R_k],R_k>R_j$且$[R_i+1,R_k]$已经被记录到最终更新区间了？

如果存在， 那么我们这个做了显然就是错误的， 但是事实是不会存在， 因为分割出$[R_i+1,R_j]$说明我们当前处理到的$L$才到$L_i$， 显然$L_i<R_i+1$， 所以不会出现这种情况