CTime_Pup_314

不能再颓废了

0%

[CERC2017]Intrinsic Interval

发表于 更新于 分类于 阅读次数： Valine：

题面描述

求一个区间被包含的最短重排后连续区间。

题解

判断区间是否连续有一个十分显然的做法，即判断 \(max-min=r-l\)，但是这样的做法并不能很好维护

但我们发现该区间重排后为等差数列，所以我们可以认为一个区间满足 \(|a-b|\le 1\) 的无序数对 \((a,\ b)\) 个数为 \(r-l\)，那么这个区间合法 这就十分容易维护了，把询问离线，考虑枚举右端点 \(r\)，首先每次移动只会因为前面有没有和 \(p_r\) 绝对值相差超过 \(1\) 而产生贡献，对于每个 \(l\) 维护 \(cnt+l\) 的值，由于 \(cnt\le r-l\) 那么在相应区间查最大值即可，在用一个堆维护合法询问，这个题就解决了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e5+5;
int n, m;
int val[N<<2], add[N<<2], p[N<<2];
void pusha(int x, int d) { add[x] += d, val[x] += d; }
void pushdown(int x) { if(add[x]) pusha(x<<1, add[x]), pusha(x<<1|1, add[x]), add[x] = 0; }
void pushup(int x) 
{ 
    if(val[x<<1] > val[x<<1|1]) p[x] = p[x<<1], val[x] = val[x<<1];
    else val[x] = val[x<<1|1], p[x] = p[x<<1|1];
}
void build(int x, int l, int r)
{
    if(l == r) return void(val[x] = p[x] = l);
    int mid = (l+r)>>1; 
    build(x<<1, l, mid), build(x<<1|1, mid+1, r);
    pushup(x);
}
void change(int x, int l, int r, int ql, int qr, int d)
{
    if(ql <= l&&r <= qr) return pusha(x, d);
    int mid = (l+r)>>1; pushdown(x);
    if(ql <= mid) change(x<<1, l, mid, ql, qr, d);
    if(qr > mid) change(x<<1|1, mid+1, r, ql, qr, d);
    pushup(x);
}
int ansl, ansr;
void query(int x, int l, int r, int ql, int qr)
{
    if(ql <= l&&r <= qr) return (void)(ansl = ansr<=val[x]?p[x]:ansl, ansr = max(ansr, val[x]));
    int mid = (l+r)>>1; pushdown(x);
    if(ql <= mid) query(x<<1, l, mid, ql, qr);
    if(qr > mid) query(x<<1|1, mid+1, r, ql, qr);
}
pair<int, int> ans[N];
bool valid(pair<int, int> p, int r)
{
    ansr = -1; query(1, 1, n, 1, p.first);
    if(ansr == r) return ans[p.second] = make_pair(ansl, ansr), true;
    else return false;
}
int f[N], g[N];
vector<pair<int, int> > s[N];
priority_queue<pair<int, int> > q;
int main()
{
    n = read(); build(1, 1, n);
    for(int i = 1; i <= n; ++i) f[i] = read(), g[f[i]] = i;
    m = read();
    for(int i = 1; i <= m; ++i)
    {
        int l = read(), r = read();
        s[r].push_back(make_pair(l, i));
    }
    for(int i = 1; i <= n; ++i)
    {
        if(f[i] != 1&&g[f[i]-1] < i) change(1, 1, n, 1, g[f[i]-1], 1);
        if(f[i] != n&&g[f[i]+1] < i) change(1, 1, n, 1, g[f[i]+1], 1);
        for(int k = 0; k < s[i].size(); ++k) q.push(s[i][k]);
        while(q.size()&&valid(q.top(), i)) q.pop();
    }
    for(int i = 1; i <= m; ++i) printf("%d %d\n", ans[i].first, ans[i].second);
    return 0;
}