「BZOJ 5259」「CERC 2017 I」区间

给定一个$1$到$n$的排列${ a }$,对于一个区间$[l, r]$,我们称该区间是连续的,如果将$a_l, . . . , a_r$排列之后得到的是一列连续的数。(换句话说,如果$x,y$都在该区间中,那么所有介于$x,y$之间的数也在该区间中)现在有$m$个询问,每个询问给出一个区间$[x_i, y_i]$,你需要找到一个长度最短的连续区间$[l_i,r_i]$,使得$[x_i,y_i]$属于 $[l_i, r_i]$。

其实类似的题有很多,看 Claris 的博客找到了这道题的做法,感觉是一个挺普遍的解法,所以记一下。

因为多个询问,每个询问不好单独下手,所以我们将所有询问离线后解决。考虑扫描线枚举 $l$,那么对于任意的 $r$来说,我们定义其权值 $w_r = (max_{l,r} - min_{l,r} - (r - l))\times N + r -l$,容易发现对于所有的 $w_r$ 来说,其长度为 $w_r \mod N$,且一个 $w_r$合法当且仅当 $w_r < N$,这样我们很好的将合法性的判断和长度的判断结合在了一起。

然后就很好处理了,我们从左向右移动 $l$,可以发现 $w$ 的变化总是一段连续的区间且区间个数是个常数,所以我们拿一个线段树维护一下区间历史极值即可。

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

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<ll, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int MAXN = 1e5 + 5;

const ll oo = 2e18;

struct tag {
    ll cl, sum;
    tag (ll cl = 0, ll sum = 0) : cl(cl), sum(sum) {}
};

inline tag operator + (const tag & a, const tag & b) { 
    ll cl = a.cl, sum = a.sum + b.sum;
    cmin(cl, a.sum + b.cl);
    return tag(cl, sum);
}

int a[MAXN], ge[MAXN], le[MAXN];
ll w[MAXN];

deque<int> q;

struct tree {
    pr v, mn;
    tag o;
}t[MAXN << 2];

inline void rel(int k){ 
    t[k].mn = t[k << 1].mn < t[k << 1 | 1].mn ? t[k << 1].mn : t[k << 1 | 1].mn; 
    t[k].v = t[k << 1].v < t[k << 1 | 1].v ? t[k << 1].v : t[k << 1 | 1].v;
}

void Build(int le, int ri, int k){
    t[k].o = tag();
    if (le == ri) {
        t[k].mn = t[k].v = make_pair(w[le], le);
        return;
    }
    int mi = (le + ri) >> 1;
    Build(le, mi, k << 1);
    Build(mi + 1, ri, k << 1 | 1);
    rel(k);
}

void mark(int k, const tag & o) {
    cmin(t[k].mn, make_pair(t[k].v.fi + o.cl, t[k].v.se));
    t[k].v.fi += o.sum;
    t[k].o = t[k].o + o;
}

void Pushdown(int k){
    mark(k << 1, t[k].o);
    mark(k << 1 | 1, t[k].o);
    t[k].o = tag();
}

void cg(int le, int ri, int k, int L, int R, ll v){
    if (le != ri)    Pushdown(k);
    if (L <= le && ri <= R) {
        mark(k, tag(min(v, 0LL), v));
        return; 
    }
    int mi = (le + ri) >> 1;
    if (L <= mi)    cg(le, mi, k << 1, L, R, v);
    if (mi + 1 <= R)    cg(mi + 1, ri, k << 1 | 1, L, R, v);
    rel(k);
}

pr get(int le, int ri, int k, int L, int R){
    if (le != ri) Pushdown(k);
    if (L <= le && ri <= R) return t[k].mn;
    int mi = (le + ri) >> 1; pr mn = make_pair(oo, 0);
    if (L <= mi)     cmin(mn, get(le, mi, k << 1, L, R));
    if (mi + 1 <= R)     cmin(mn, get(mi + 1, ri, k << 1 | 1, L, R));
    return mn;
}

void DFS(int le, int ri, int k){
    if (le != ri) Pushdown(k);
    else return (void)printf("%lld ", t[k].v);
    int mi = (le + ri) >> 1;
    DFS(le, mi, k << 1);
    DFS(mi + 1, ri, k << 1 | 1);
}

int N, Q;

struct Query {
    int le, ri, o;
    Query (int le = 0, int ri = 0, int o = 0) : le(le), ri(ri), o(o) {}
    inline bool operator < (const Query & v) const { return le < v.le; }
}qry[MAXN];

pr ans[MAXN];

int main(){
    scanf("%d", &N);
    up (i, 1, N) scanf("%d", &a[i]);
    a[N + 1] = N + 1; q.push_back(N + 1);
    down (i, N, 1) {
        while (!q.empty() && a[i] > a[q.back()]) q.pop_back();
        ge[i] = q.back();
        q.push_back(i);
    }
    while (!q.empty()) q.pop_back();
    a[N + 1] = 0; q.push_back(N + 1);
    down (i, N, 1) {
        while (!q.empty() && a[i] < a[q.back()]) q.pop_back();
        le[i] = q.back();
        q.push_back(i);
    }
    int mn = a[1], mx = a[1];
    up (i, 1, N) {
        cmin(mn, a[i]);
        cmax(mx, a[i]);
        w[i] = (ll)(mx - mn - (i - 1)) * N + i - 1; 
    }
    Build(1, N, 1);
    scanf("%d", &Q);
    up (i, 1, Q) {
        int le, ri; scanf("%d%d", &le, &ri);
        qry[i] = Query(le, ri, i);
    }
    sort(qry + 1, qry + Q + 1);
    int cur = 1;
//    DFS(1, N, 1); puts("");
    for (int cl = 1, cr; cl <= Q; cl = cr + 1) {
        cr = cl;
        while (cr + 1 <= Q && qry[cr + 1].le == qry[cl].le) cr++;
        while (cur + 1 <= qry[cl].le) {
              cg(1, N, 1, cur, N, N);
              int nxt = le[cur], x = cur + 1;
              while (x < nxt) {
                    int y = le[x];
                    cg(1, N, 1, x, min(y, nxt) - 1, -(ll)(a[x] - a[cur]) * N);
                    x = y;
              }
              nxt = ge[cur]; x = cur + 1;
              while (x < nxt) {
                    int y = ge[x];
                    cg(1, N, 1, x, min(y, nxt) - 1, -(ll)(a[cur] - a[x]) * N);
                    x = y;
              }
              cg(1, N, 1, cur, N, -1);
              cur++;
//              DFS(1, N, 1); puts("");
        }
        up (i, cl, cr) {
            pr w = get(1, N, 1, qry[i].ri, N);
            ans[qry[i].o] = make_pair(w.se - (w.fi % N), w.se);
        }
    }
    up (i, 1, Q) printf("%d %d\n", (int)ans[i].fi, (int)ans[i].se);
    return 0;
}

顺带吐槽一下 GUN7.0 在用 %d输出 long long的数时如果数据不溢出就不会报错,但是在更低版本的就出问题了..调了好久才发现。