Luogu P4747 [CERC2017]Intrinsic Interval

题目描述

https://www.luogu.com.cn/problem/P4747

简要题意：给定一个长度为 $n$ 的排列 $p$，如果区间 $[l,r]$ 内的数排序之后是连续正整数，则称 $[l,r]$ 为一个合法区间，现在有 $m$ 次询问，每次询问给定一个区间 $[x,y]$，求最小的一个合法区间 $[l,r]$ 满足 $l\le x\le y\le r$

$n,m \le 10^5$

Solution

首先我们分析一下合法区间的性质：

对于两个有交的合法区间，它们的交一定也是一个合法区间
根据 1，容易得到对于一个区间 $[x,y]$，包含的它的最小合法区间一定是所有包含的合法区间中左端点最大以及右端点最小的那个合法区间

然后注意到操作并无修改，我们考虑扫描线，我们考虑在固定右端点的时候如何判断一个区间是否合法以及如何在右端点增加的时候维护这个东西

我们将合法区间的条件转换一下，考虑数对 $(i,j)$，且 $p_i-p_j=1$，注意到一个区间 $[l,r]$ 合法，当且仅当这个区间内恰有 $r-l$ 个这样的数对，另外这样的数对一共只有 $n$ 个

那么做法就呼之欲出了，我们在右端点递增的时候通过合法数对来做区间加即可，另外在右端点递增到 $i$ 的时候，将 $i$ 的值置为 $i$，那么合法区间的值就应该是刚好是 $r$

现在的问题是如何对于每个区间求答案，方法是将每个询问区间挂到 $r$ 上，然后在扫到这里时候，将其加入按照区间左端点排序的大根堆中，每次右端点递增完之后依次求答案即可，求答案可以用线段树实现

时间复杂度 $O(n\log n)$

#include <iostream>
#include <vector>
#include <queue>
#define maxn 100010
using namespace std;

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    int v, add; 
} T[maxn * 4];
inline void maintain(int i) { T[i].v = max(T[lc].v, T[rc].v); }

inline void Update(int i, int v) { T[i].v += v; T[i].add += v; }

inline void pushdown(int i) {
    int &add = T[i].add; if (!add) return ;
    Update(lc, add); Update(rc, add);
    add = 0;
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i); 
}

void update(int i, int l, int r, int k, int v) {
    if (l == r) return T[i].v = v, void();
    int m = l + r >> 1; pushdown(i);
    if (k <= m) update(lc, l, m, k, v);
    else update(rc, m + 1, r, k, v);
    maintain(i);
}

int query(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L || T[i].v < v) return 0;
    if (l == r) return T[i].v == v ? l : 0; pushdown(i); 
    int m = l + r >> 1, t = query(rc, m + 1, r, L, R, v);
    if (t) return t;
    else return query(lc, l, m, L, R, v); 
}

int n, m, a[maxn], p[maxn];
vector<pair<int, int>> A[maxn];

pair<int, int> ans[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; priority_queue<pair<int, int>> Q; 
    for (int i = 1; i <= n; ++i) cin >> a[i], p[a[i]] = i;
    cin >> m;
    for (int i = 1, x, y; i <= m; ++i) cin >> x >> y, A[y].emplace_back(x, i);
    for (int i = 1; i <= n; ++i) {
        update(1, 1, n, i, i); 
        if (a[i] > 1 && p[a[i] - 1] < i) update(1, 1, n, 1, p[a[i] - 1], 1);
        if (a[i] < n && p[a[i] + 1] < i) update(1, 1, n, 1, p[a[i] + 1], 1);
        for (auto t : A[i]) Q.push(t); 
        while (!Q.empty()) {
            pair<int, int> t = Q.top();
            int v = query(1, 1, n, 1, t.first, i);
            if (v == 0) break; Q.pop();
            ans[t.second] = make_pair(v, i); 
        }
    }
    for (int i = 1; i <= m; ++i) cout << ans[i].first << " " << ans[i].second << "\n";
    return 0; 
}