【题解】LUOGU 4747 [CERC2017]Intrinsic Interval

请注意,本文编写于 99 天前,最后修改于 99 天前,其中某些信息可能已经过时。

Problem

给定 $1-n$ 的一个排列 $a$ ,定义一个有趣的区间 $[l,r]$ 满足 $\max_{i=l}^{r}\{a_i\}-\min_{i=l}^{r}\{a_i\}=r-l$

有 $m$ 次询问,每次询问一个区间 $[x,y]$ ,问最短的包含 $[x,y]$ 的有趣的区间的范围

Thought

由于 $\max_{i=l}^{r}\{a_i\}-\min_{i=l}^{r}\{a_i\}$ 这东西很不好维护,考虑转化
搞成一个比较好维护的东西: 二元组 $(i,i+1)$ 的数量

假设一个区间 $[l,r]$ 中有 $r-l$ 个形如 $(i,i+1)$ 的二元组,则该区间是个有趣的区间
显然,二元组个数的范围为 $[0,r-l]$ (在不考虑 $n$ 的限制的情况下),当它是个有趣的区间时这样的二元组个数最多

那么,我们枚举右端点 $r$ ,如果存在一个左端点 $l$ 加上 $[l,r]$ 中的二元组个数恰好为 $r$ ,那么$[l,r]$ 是一个有趣的区间

这东西显然可以用线段树维护,具体方法是:从左到右插入 $a[r]$ ,每次插入,显然会对包含 $a[r]-1$ 和 $a[r]+1$ 的区间使其二元组个数 $+1$

那么只需要找到 $a[r]-1$ 和 $a[r]+1$ 的位置,假设位置为 $pos$ ,易得 $l\in[1,pos]$ 的所有 $[l,r]$ 区间均 $+1$ ,所以只需要线段树上做前缀加法。然后维护区间内最大的 $i+val[i]$ 的值,如果为 $r$ ,那么说明该区间有位置 $l$ 满足 $[l,r]$ 为有趣的区间

那么怎么保证有趣的区间最短呢?

发现如果两个有趣的区间有交集,那么其交集必然是有趣的区间,换句话说,假设在当前 $r$ 已经找到一个最短的包含 $[x,y]$ 的区间 $[l,r]$ ,并且有个更短的右端点在 $r$ 右侧的区间 $[l',r']$ 也包含 $[x,y]$ ,那么必然有 $[l',r]$ 包含 $[x,y]$ 并且比 $[l,r]$ 要短,这与之前找到最短的 $[l,r]$ 矛盾,所以不存在这样的区间

那么只需要找出以 $r$ 为右端点的所有区间包含 $[x,y]$ 的最小区间即可,任何的 $r'>r$ 的区间都不会影响已经确定的答案

最后考虑如何计算出对于每个询问的答案

每次扩展 $r$ ,我们将所有右端点在 $r$ 的询问丢到一个以 $l$ 排序的数据结构里面
那么,如果在 $[1,l]$ 里面有符合 $l+val[l]=r$ 的区间,那么当前询问答案为 $(l,r)$
如果 $[1,r]$ 里面没有符合条件的区间,显然对于其他更小的 $l$ 不会有这样的区间,直接结束即可

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

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> P;
const int N = 100010;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
#define L (x << 1)
#define R (x << 1 | 1)
#define mid ((l + r) >> 1)
struct Seg {
    int key[N << 2];
    int pos[N << 2];
    int tag[N << 2];
    void pushdown(int x) {
        key[L] += tag[x];
        key[R] += tag[x];
        tag[L] += tag[x];
        tag[R] += tag[x];
        tag[x] = 0;
    }
    void update(int x) {
        if(key[L] > key[R])
            pos[x] = pos[L];
        else
            pos[x] = pos[R];
        key[x] = max(key[L], key[R]);
    }
    void build(int x, int l, int r) {
        if(l == r) {
            key[x] = l;
            pos[x] = l;
        }
        else {
            build(L, l, mid);
            build(R, mid + 1, r);
            update(x);
        }
    }
    void add(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr) {
            key[x] += 1;
            tag[x] += 1;
        }
        else {
            pushdown(x);
            if(mid >= ll) add(L, l, mid, ll, rr);
            if(mid < rr) add(R, mid + 1, r, ll, rr);
            update(x);
        }
    }
    P query(int x, int l, int r, int ll, int rr) {
        if(l >= ll && r <= rr)
            return make_pair(key[x], pos[x]);
        else {
            pushdown(x);
            P ans = make_pair(0, 0);
            if(mid >= ll) ans = max(ans, query(L, l, mid, ll, rr));
            if(mid < rr) ans = max(ans, query(R, mid + 1, r, ll, rr));
            return ans;
        }
    }
}tr;
int n, m, a[N], pos[N];
P Ans[N];
set < P, greater<P> > s;
struct Query {
    int l, r, id;
    bool operator < (const Query a) const {
        return r < a.r;
    }
}q[N];

int main() {
    n = read();
    for(int i = 1; i <= n; ++ i) {
        a[i] = read();
        pos[a[i]] = i;
    }
    m = read();
    for(int i = 1; i <= m; ++ i) {
        q[i].l = read();
        q[i].r = read();
        q[i].id = i;
    }
    tr.build(1, 1, n);
    sort(q + 1, q + m + 1);
    int top = 1;
    for(int i = 1; i <= n; ++ i) {
        if(pos[a[i] - 1] >= 1 && pos[a[i] - 1] <= i)
            tr.add(1, 1, n, 1, pos[a[i] - 1]);
        if(pos[a[i] + 1] >= 1 && pos[a[i] + 1] <= i)
            tr.add(1, 1, n, 1, pos[a[i] + 1]);
        while(top <= m && q[top].r == i) {
            s.insert(make_pair(q[top].l, q[top].id));
            ++ top;
        }
        while(!s.empty()) {
            P x = *s.begin();
            P ans = tr.query(1, 1, n, 1, x.first);
            if(ans.first == i) {
                Ans[x.second] = make_pair(ans.second, i);
                s.erase(s.begin());
            }
            else break;
        }
    }
    for(int i = 1; i <= m; ++ i)
        printf("%d %d\n", Ans[i].first, Ans[i].second);
    return 0;
}
Comments

添加新评论