HDU 6602 Longest Subarray(线段树)

作者：知新_RL | 2024-03-02 11:36:06

踩

原题地址:http://acm.hdu.edu.cn/showproblem.php?pid=6602

题意:给出一个序列,找到一个一个最长的串,使得这个串里的出现的每个数字的次数都>=k

思路:我们可以枚举右端点r,那么对于这个右端点的数字,从右向左的第k个位置pos,在[1,pos]是合法的,(pos,r)是非法的,每次维护当前枚举的右端点r的合法左区间,如果合法就区间+1,非法就区间-1,这样子我们只需要找当前右端点r最左边的端点l,每次更新答案即可.

PS:好久都没写过线段树了,代码有点丑陋
需要注意的是,我下面的写法处理k=1的时候有点问题,特判即可.

#include <bits/stdc++.h>

#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define CLR(x, y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int mx[maxn << 2];//求区间最大值
int lazy[maxn << 2];//区间加减法
int a[maxn];

void push_up(int rt) {
    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}

void push_down(int rt) {
    if (lazy[rt] != 0) {
        mx[rt << 1] += lazy[rt];
        mx[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int l, int r, int rt) {
    lazy[rt] = 0;
    mx[rt] = 0;
    if (l == r) {
        mx[rt] = 0;
        lazy[rt] = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int l, int r, int rt, int L, int R, int add) {
    if (L <= l && R >= r) {
        mx[rt] += add;
        lazy[rt] += add;
        return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (L <= mid) update(lson, L, R, add);
    if (mid < R) update(rson, L, R, add);
    push_up(rt);
}

//query最左边的为0的位置
int query(int l, int r, int rt) {
    if (l == r) {
        if (mx[rt] == 0)return l;
        else return -1;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (mx[rt << 1] == 0) return query(lson);
    else if (mx[rt << 1 | 1] == 0) return query(rson);
    else return -1;
}

int n, c, k;
vector<int> vec[maxn];
int lst[maxn];
int num[maxn];

int main() {
    while (~scanf("%d%d%d", &n, &c, &k)) {
        for (int i = 1; i <= c; i++) {
            vec[i].clear();
            num[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            vec[a[i]].push_back(i);
        }

        if (k == 1) {
            printf("%d\n", n);
            continue;
        }

        for (int i = 1; i <= n; i++) {
            lst[i] = 1;
        }
        build(1, n, 1);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int cnt = num[a[i]];
            num[a[i]]++;
            if (cnt == 0) {//第一次出现,区间减法,k=1已经在上面特判,以下都是k>=2的
                update(1, n, 1, 1, i, -1);
            } else {
                if (cnt + 1 < k) {//需要注意的是已经对于当前数字,之前已经减过的区间不用再减,所以需要用vector记录位置
                    int p1 = vec[a[i]][cnt - 1];
                    int p2 = vec[a[i]][cnt];
                    update(1, n, 1, p1 + 1, p2, -1);
                } else {//每次都会多一块合法区间和一块非法区间
                    int p1 = vec[a[i]][cnt - 1];
                    int p2 = vec[a[i]][cnt];

                    update(1, n, 1, p1 + 1, p2, -1);
                    int p3 = vec[a[i]][cnt - k + 1];

                    update(1, n, 1, lst[a[i]], p3, 1);
                    lst[a[i]] = p3 + 1;


                }
            }
            int pos = query(1, n, 1);
            if (pos > i) continue;//需要找最左边的,在右端点右边的是非法的
            if (pos != -1) ans = max(ans, i - pos + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}


/*

5 3 2
2 1 3 1 3


6 3 2
1 2 1 2 1 3


2 2 2
1 2
 * */


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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

//代码2
#include <bits/stdc++.h>

#define eps 1e-8
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define CLR(x, y) memset((x),y,sizeof(x))
#define fuck(x) cerr << #x << "=" << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int seed = 131;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
int mx[maxn << 2];//求区间最大值
int lazy[maxn << 2];//区间加减法
int a[maxn];
int pos[maxn << 2];
//pos用于求区间最左边的0
void push_up(int rt) {
    mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
    if (mx[rt] == mx[rt << 1]) pos[rt] = pos[rt << 1];
    else pos[rt] = pos[rt << 1 | 1];
}

void push_down(int rt) {
    if (lazy[rt] != 0) {
        mx[rt << 1] += lazy[rt];
        mx[rt << 1 | 1] += lazy[rt];
        lazy[rt << 1] += lazy[rt];
        lazy[rt << 1 | 1] += lazy[rt];
        lazy[rt] = 0;
    }
}

void build(int l, int r, int rt) {
    lazy[rt] = 0;
    mx[rt] = 0;
    pos[rt] = l;
    if (l == r) {
        return;
    }
    int mid = (l + r) / 2;
    build(lson);
    build(rson);
    push_up(rt);
}

void update(int l, int r, int rt, int L, int R, int add) {
    if (L <= l && R >= r) {
        mx[rt] += add;
        lazy[rt] += add;
        return;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (L <= mid) update(lson, L, R, add);
    if (mid < R) update(rson, L, R, add);
    push_up(rt);
}

//query最左边的为0的位置
int query(int l, int r, int rt) {
    if (l == r) {
        if (mx[rt] == 0)return l;
        else return -1;
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (mx[rt << 1] == 0) return query(lson);
    else if (mx[rt << 1 | 1] == 0) return query(rson);
    else return -1;
}

int query(int l, int r, int rt, int L, int R) {
    if (mx[rt] != 0) return -1;
    if (L <= l && R >= r) {
        return pos[rt];
    }
    push_down(rt);
    int mid = (l + r) / 2;
    if (L <= mid) {
        int t = query(lson, L, R);
        if (t != -1) return t;
    }
    if (R > mid) {
        return query(rson, L, R);
    }
    return -1;
}

int n, c, k;
vector<int> vec[maxn];
int lst[maxn];
int num[maxn];

int main() {
    while (~scanf("%d%d%d", &n, &c, &k)) {
        for (int i = 1; i <= c; i++) {
            vec[i].clear();
            num[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            vec[a[i]].push_back(i);
        }

        if (k == 1) {
            printf("%d\n", n);
            continue;
        }

        for (int i = 1; i <= n; i++) {
            lst[i] = 1;
        }
        build(1, n, 1);
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int cnt = num[a[i]];
            num[a[i]]++;
            if (cnt == 0) {//第一次出现,区间减法,k=1已经在上面特判,以下都是k>=2的
                update(1, n, 1, 1, i, -1);
            } else {
                if (cnt + 1 < k) {//需要注意的是已经对于当前数字,之前已经减过的区间不用再减,所以需要用vector记录位置
                    int p1 = vec[a[i]][cnt - 1];
                    int p2 = vec[a[i]][cnt];
                    update(1, n, 1, p1 + 1, p2, -1);
                } else {//每次都会多一块合法区间和一块非法区间
                    int p1 = vec[a[i]][cnt - 1];
                    int p2 = vec[a[i]][cnt];

                    update(1, n, 1, p1 + 1, p2, -1);
                    int p3 = vec[a[i]][cnt - k + 1];

                    update(1, n, 1, lst[a[i]], p3, 1);
                    lst[a[i]] = p3 + 1;


                }
            }
//            int pos = query(1, n, 1);
//            if (pos > i) continue;//需要找最左边的,在右端点右边的是非法的
//            if (pos != -1) ans = max(ans, i - pos + 1);

            int pos = query(1, n, 1, 1, i);
            if (pos != -1) ans = max(ans, i - pos + 1);

        }
        printf("%d\n", ans);
    }
    return 0;
}


/*

5 3 2
2 1 3 1 3


6 3 2
1 2 1 2 1 3


2 2 2
1 2
 * */



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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】