[2019杭电多校第二场][hdu6602]Longest Subarray(线段树)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6602

题目大意为求最长的区间，满足C种数字在区间内要么不出现，要么出现的次数都不小于K。

大致的分析一下，可以知道对于以R为右端点的区间来说，每种颜色的合法区间在[1~出现k次]和(上一次出现~下一次出现)。PS:[]为闭区间,()为开区间。

所以可以线段树维护一下，枚举区间右端点，然后在线段树上将上一次更新这种颜色的操作撤销(上次是+1，则当前-1)，然后再次更新(+1)。

对于每个区间右端点，最大的有效区间为线段树上种类为C的最左边的位置。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<string>

 #include<cmath>

 #include<vector>

 #define lson l,mid,i<<1

 #define rson mid+1,r,i<<1|1

 using namespace std;

 typedef long long ll;

 const int maxn = 2e5 + ;

 const ll mod = ;

 int Max[maxn * ], lazy[maxn * ];

 vector<int>cnt[maxn];

 int num[maxn];

 int n, c, k;

 void up(int i) {

     Max[i] = max(Max[i << ], Max[i <<  | ]);

 }

 void down(int i) {

     if (lazy[i]) {

         lazy[i << ] += lazy[i];

         lazy[i <<  | ] += lazy[i];

         Max[i <<  | ] += lazy[i];

         Max[i << ] += lazy[i];

         lazy[i] = ;

     }

 }

 void build(int l, int r, int i) {

     Max[i] = lazy[i] = ;

     if (l == r)

         return;

     int mid = l + r >> ;

     build(lson);

     build(rson);

     up(i);

 }

 void  update(int L, int R, int k, int l, int r, int i) {

     if (L > R)return;

     if (L <= l && r <= R) {

         Max[i] += k;

         lazy[i] += k;

         return;

     }

     down(i);

     int mid = l + r >> ;

     if (L <= mid)update(L, R, k, lson);

     if (R > mid)update(L, R, k, rson);

     up(i);

 }

 int query(int l, int r, int i) {

     if (l == r)return l;

     int ans = -, mid = l + r >> ;

     down(i);

     if (Max[i << ] == c)ans = query(lson);

     else if (Max[i <<  | ] == c)ans = query(rson);

     return ans;

 }

 int a[maxn];

 int main() {

     while (scanf("%d%d%d", &n, &c, &k) != EOF) {

         for (int i = ; i <= c; i++)

             cnt[i].clear(), cnt[i].push_back(), num[i] = ;

         for (int i = ; i <= n; i++) {

             scanf("%d", &a[i]);

             cnt[a[i]].push_back(i);

         }

         build(, n, );

         for (int i = ; i <= c; i++) {

             cnt[i].push_back(n + );

             update(cnt[i][] + , cnt[i][] - , , , n, );

         }

         int ans = ;

         for (int i = ; i <= n; i++) {

             update(cnt[a[i]][num[a[i]]] + , cnt[a[i]][num[a[i]] + ] - , -, , n, );

             if (num[a[i]] >= k)

                 update(, cnt[a[i]][num[a[i]] - k + ], -, , n, );

             num[a[i]]++;

             update(cnt[a[i]][num[a[i]]] + , cnt[a[i]][num[a[i]] + ] - , , , n, );

             if (num[a[i]] >= k)

                 update(, cnt[a[i]][num[a[i]] - k + ], , , n, );

             int q = query(, n, );

             if (q != -)

                 ans = max(ans, i - q + );

         }

         printf("%d\n", ans);

     }

 }

巴特西

[2019杭电多校第二场][hdu6602]Longest Subarray(线段树)

最新文章

热门文章