B_牛客博客

本文亦发表于笔者博客：https://www.codein.icu/nowcoderweekly19/

B

赛上看错题，导致一直不知道如何下手。
解说一下题意，给出若干个三元组 $(l,r,num)$ ，要求满足对于 $i \in [l,r]$ $\min{a_i} = num$ ，找出第一个三元组，在添加该三元组前可满足条件，在添加该三元组后无法满足。

这种最值问题，很容易联想到二分。若前 $x_1$ 个三元组时不满足条件，则前 $x_2(x_2 > x_1)$ 个三元组时一定也不满足，二分找出分界点即为答案。

接下来考虑如何有效地判断是否有满足条件的解。

对三元组按 $num$ 分类，同 $num$ 下的若干线段 $[l,r]$ ，由于数字两两不相同，也就是 $a_i = num$ 有唯一确定的 $i$ ，因此线段一定有交集，否则无解。

此外，还需要保证在 $[\min{l},\max{r}]$ 中，最小值为 $num$ ，因此若有 $num_2 < num$ 的线段 $[l,r]$ 位于其中，一定也不满足条件。

因此可以以 $num$ 为关键字降序排序，对 $num$ 相同的线段，计算出交集 $[ll,rr]$ 与并集 $[ml,mr]$ ，那么最小值点一定位于交集中，此时要求最小值点在 $[ll,rr]$ 区间内存在某点，放置后不会影响 $num_2 > num$ 的并集的最小值。

可以用线段树维护，每次查询 $[ll,rr]$ 的区间和，再将 $[ml,mr]$ 赋值为 $1$ ，若区间和等于区间长度，说明之前已经被并集覆盖完全，由于 $num$ 降序，此时 $[ll,rr]$ 区间内任一点设置为 $num$ 都会影响之前的最小值。

#include <algorithm>
#include <cstdio>
#include <ctype.h>

const int bufSize = 1e6;
#define DEBUG
inline char nc()
{
#ifdef DEBUG
    return getchar();
#endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline T read(T& r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 5e5 + 100;
int n, k;
struct node
{
    int l, r, num;
} A[maxn], B[maxn];
bool cmp(const node& a, const node& b)
{
    if (a.num == b.num) return a.l < b.l;
    return a.num > b.num;
}
int sum[maxn << 2], tag[maxn << 2];
#define ls p << 1
#define rs p << 1 | 1
inline void pushdown(const int& l, const int& r, const int& p)
{
    if (!tag[p]) return;
    int mid = l + r >> 1;
    sum[ls] = mid - l + 1;
    sum[rs] = r - mid;
    tag[ls] = tag[rs] = 1;
    tag[p] = 0;
}
void build(const int& l, const int& r, const int& p)
{
    sum[p] = tag[p] = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
}
void modify(const int& l, const int& r, const int& p, const int& ll, const int& rr)
{
    if (ll > rr || ll == 0) return;
    if (l >= ll && r <= rr)
    {
        sum[p] = r - l + 1;
        tag[p] = 1;
        return;
    }
    pushdown(l, r, p);
    int mid = l + r >> 1;
    if (ll <= mid) modify(l, mid, ls, ll, rr);
    if (rr > mid) modify(mid + 1, r, rs, ll, rr);
    sum[p] = sum[ls] + sum[rs];
}
int ask(const int& l, const int& r, const int& p, const int& ll, const int& rr)
{
    if (ll == 0 || rr == 0 || ll > rr) return 0;
    if (l >= ll && r <= rr) return sum[p];
    int mid = l + r >> 1, ans = 0;
    pushdown(l, r, p);
    if (ll <= mid) ans = ask(l, mid, ls, ll, rr);
    if (rr > mid) ans += ask(mid + 1, r, rs, ll, rr);
    return ans;
}
inline bool check(int x)
{
    build(1, n, 1);
    for (int i = 1; i <= x; ++i) B[i] = A[i];
    std::sort(B + 1, B + 1 + x, cmp);
    B[x + 1].num = -1;
    int ll = 0, rr = 0, mr = 0, ml = n;
    for (int i = 1; i <= x + 1; ++i)
    {
        if (B[i].num == B[i - 1].num) ll = std::max(ll, B[i].l), rr = std::min(rr, B[i].r), ml = std::min(ml, B[i].l), mr = std::max(mr, B[i].r);
        else
        {
            if (ll > rr) return true;
            if (ask(1, n, 1, ll, rr) == rr - ll + 1) return true;
            modify(1, n, 1, ml, mr);
            ml = ll = B[i].l, rr = mr = B[i].r;
        }
    }
    return false;
}
int main()
{
    read(n), read(k);
    for (int i = 1; i <= k; ++i) read(A[i].l), read(A[i].r), read(A[i].num);
    int l = 1, r = k, mid, ans = k + 1;
    B[0].num = -1;
    while (l <= r)
    {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", ans);
    return 0;
}