多校第二场HDU 6602 Longest Subarray

图片说明
根据题目要求

题意：给你一个串，问满足以下条件的子串中最长的是多长：对于每个数字，要么在这个子串没出现过，要么出现次数超过k次。
对于这类问题，常常转化为数据结构的询问问题。我们考虑枚举右端点，对于当前右端点，我们单独考虑每一种数的合法区间。假设当前枚举的右端点是i，考虑的数字是c,在右端点左边离i最近的数字c的位置是p1,离i第k远的数字c的位置是p2, 容易发现，数字c的合法区间为[1, p2]和[p1 + 1, i]，对应的情况是选择这个数至少k个和不选这个数。那么，如果我们用线段树来维护覆盖的区间，对于每一种数的合法区间在线段树上+1，这样我们只要找到在i前面值为c的最小的位置就是右端点为i的最优解。由于每次右端点只移动1，所以可以在O(logn)时间内维护一个数合法区间的变化。最小位置的找法可以通过维护区间最大值然后在线段树上二分即可。

具体做法
枚举右端点，当前区间肯定包含a[r]，所以先把不选这个数的区间置0，如果当前数字出现等于k次， $[1, p_1]$ 在线段树加1，大于k次在 $[p_{i-k}+1,p_{i-k+1}]$ 区间加1, 然后查找i前面值为c的最小的位置就是右端点为i的最优解。查完之后把不出现这个数区间 $[p_i+1,p_{i+1}-1]$ 加1，供下次使用

#include <bits/stdc++.h>
#define ls (o << 1)
#define rs (o << 1 | 1)
using namespace std;
const int maxn = 100010;
vector<int> pos[maxn];
int now[maxn];
int n, c, k;
int a[maxn];
struct SegmenTree {
   int mx, lz;
};
SegmenTree tr[maxn * 4];
void pushup(int o) {
   tr[o].mx = max(tr[ls].mx, tr[rs].mx);
}
void pushdown(int o) {
   if(tr[o].lz != 0) {
       tr[ls].mx += tr[o].lz;
       tr[rs].mx += tr[o].lz;
       tr[ls].lz += tr[o].lz;
       tr[rs].lz += tr[o].lz;
       tr[o].lz = 0;
   }
}
void build(int o, int l, int r) {
   tr[o].mx = 0;
   tr[o].lz = 0;
   if(l == r) {
       return;
   }
   int mid = (l + r) >> 1;
   build(ls, l, mid);
   build(rs, mid + 1, r);
   pushup(o);
}
void update(int o, int l, int r, int ql, int qr, int val) {
   if(ql > qr) return;
   if(l >= ql && r <= qr) {
       tr[o].lz += val;
       tr[o].mx += val;
       return;
   }
   pushdown(o);
   int mid = (l + r) >> 1;
   if(ql <= mid) update(ls, l, mid, ql, qr, val);
   if(qr > mid) update(rs, mid + 1, r, ql, qr, val);
   pushup(o);
}
int query(int o, int l, int r) {
   if(l == r) return l;
   int ans = -1, mid = (l + r) >> 1;
   pushdown(o);
   if(tr[ls].mx == c) ans = query(ls, l, mid);
   else if(tr[rs].mx == c) ans = query(rs, mid + 1, r);
   return ans;
}
int main() {
   while(~scanf("%d%d%d", &n, &c, &k)) {
       for (int i = 1; i <= c; i++) {
           pos[i].clear();
           pos[i].push_back(0);
       }
       for (int i = 1; i <= n; i++) {
           scanf("%d", &a[i]);
           pos[a[i]].push_back(i);
       }
       build(1, 1, n);
       for (int i = 1; i <= c; i++) {
           pos[i].push_back(n + 1);
           update(1, 1, n, pos[i][0] + 1, pos[i][1] - 1, 1);
           now[i] = 0;
       }
       int ans = 0;
       for (int i = 1; i <= n; i++) {
           int t = a[i];
           update(1, 1, n, pos[t][now[t]] + 1, pos[t][now[t] + 1] - 1, -1);
           now[t]++;
           if(now[t] == k) update(1, 1, n, 1, pos[t][now[t] - k + 1], 1);
           else if(now[t] > k) update(1, 1, n, pos[t][now[t] - k] + 1, pos[t][now[t] - k + 1], 1);
           int tmp = query(1, 1, n);
           if(tmp != -1)
               ans = max(ans, i - tmp + 1);
           update(1, 1, n, pos[t][now[t]] + 1, pos[t][now[t] + 1] - 1, 1);
       }
       printf("%d\n", ans);
   }
}