sinEagle

bottlecode

0%

HDU 1806（线段树维护区间众数）

发表于
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目链接

题意给定排好序的序列，即求出最长连续自序列, 细节很多

  1. 线段树维护区间众数模型 + 大批量查询。维护区间众数，区间最长连续子序列，区间最长连续上升子序列都是同一种做法，需要维护三个东西。
    ls区间左端点为起点的最大连续长度，rs区间右端点为终点的最大连续长度，ms区间的最大连续长度。
  2. 那么父区间的ls可以由左区间的ls向上合并得到，父区间的rs可以由右区间的rs向上合并得到。当然需要考虑左右区间为满区间的情况，如果相邻两个值相等且左右区间各自为满的情况需要考虑父区间的ls 和 rs跨到另一个区间的问题。父区间的ms可以由左区间的ms，右区间的ms，左区间的rs + 右区间的ls三者最大得到。
  3. 查询的时候先查出左区间最大，再查出右区间最大，最后如果相邻两个值相等的时候需要考虑跨区间的长度可能比左右区间最大还大一点。而且左区间的最大右连续的左端点比查询区间左端点还要远(端点值更小)，右区间的最大左连续的右端点比查询区间右端点还要远(端点值更大)两种情况。

参考博客

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1e5+10;

int n, q;
int a[N], b[N], vis[N], cnt[N];

int mx[N*4], siz[N*4], ls[N*4], rs[N*4];

void change(int k1, int l, int r) {
    int mid = l+r >> 1;
    ls[k1] = ls[k1*2];
    rs[k1] = rs[k1*2|1];
    mx[k1] = max(mx[k1*2], mx[k1*2|1]);
    if(a[mid] == a[mid+1]) {
        if(mx[k1*2] == mid-l+1) {
            ls[k1] += ls[k1*2+1];
        }
        if(mx[k1*2|1] == r-mid) {
            rs[k1] += rs[k1*2];
        }
        mx[k1] = max(mx[k1], rs[k1*2] + ls[k1*2+1]);
    }

}

void buildtree(int k1, int l, int r) {
    siz[k1] = r-l+1;
    if(l == r) {
        mx[k1] = ls[k1] = rs[k1] = 1;
        return;
    }
    int mid = l+r >> 1;
    buildtree(k1*2, l, mid);
    buildtree(k1*2+1, mid+1, r);
    change(k1, l, r);
}

int Find(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) {
        return mx[k1];
    }
    int mid = l+r >> 1;
    int m1 = Find(k1*2, l, mid, L, R);
    int m2 = Find(k1*2+1, mid+1, r, L, R);
    int ans = max(m1, m2);
    if(a[mid] == a[mid+1]) {
        ans = max(ans, min(rs[k1*2], mid-L+1)+min(ls[k1*2+1], R-mid));
    }
    return ans;
}

int main() {
    while(scanf("%d", &n) != EOF) {
        if(n == 0) break;
        scanf("%d", &q);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        buildtree(1, 1, n);
        for(int i = 1; i <= q; i++) {
            int x, y;
            scanf("%d%d", &x, &y);
            printf("%d\n", Find(1, 1, n, x, y));
        }
    }

    return 0;
}
求大佬赏个饭