2019多校第二场 HDU6602 Longest Subarray（思维，线段树区间修改维护最值）

链接：HDU6602 Longest Subarray

题意：

含有 长度为N的序列 a[1]、a[2]、… 、a[N]（其中 1 ≤ a[i] ≤ C ）

连续子序列 a[L]、a[L+1]、… 、a[R]， 对于 1 ~ C的任意一个数，如果出现了，其 出现次数必须 ≥ K（即要求 出现次数 == 0 或 ≥ K）

问满足上述条件的最长连续子序列长度为多少？(N,C,K ≤ 10⁵)

分析：

对于任意一个右端点R，因为是连续子序列，所以要找到 最远的（下标最小的）那个符合要求的左端点L。

这题的方法就是设定一个数组 t[]，t的下标即表示左端点L。

当R=i，t[j] = m ：表示当右端点R=i时，j 是1~ C中 m个数的可行左端点L，所以只有当 t[j] = C时，j 是右端点R = i 时的可行左端点。

所以 对于序列中的数 x，若 j 是此时的可行左端点，则t[j]++，每次只需要找 j 最小的 t[j] = C即可得出最终答案。

以上就是大致思路，但是具体实现要用线段树去维护数组 t[]

当K==1，显然答案直接就是N，以下我们仅讨论K>1的情况

假设 K=3，N=15（ * 表示其他数）：

x有5个位置，分别为 pos[1]=2，pos[2]=5，pos[3]=8，pos[4]=12，pos[5]=14

当R=i，a[i]=x，且这是第p个位置的x 时

① 首先 t[i] 是肯定可以作为 C-1（x自身除外）个数的左端点的，所以先令 t[i] + (C-1)

② 当x前一个数不是x时（即pos[p-1]+1 ≤ pos[p] - 1 ）， pos[p-1]+1 到 pos[p] - 1 原本是x的可行左端点，但现在变得不可行。
以 a[8] 为例（p=3），在 R=6和R=7时，6,7均是x的可行左端点，但当 R=8时，变得不可行。
所以令 pos[p-1]+1 到 pos[p] - 1 的t[] -1

③ 若 p ≥ K，可以发现 pos[p-K]+1 到 pos[p-K+1] 本身x不可行的左端点，但现在变为了可行。
以 a[14] 为例（p=5），在 R=8~13时，6,7,8均是x的不可行左端点，但当 R=14时，变得可行。
所以 令 pos[p-K]+1 到 pos[p-K+1] 的t[] +1

线段树的话具体就是维护最大值，每次找最大值的为C的子树，左右子树最大值都是C，那就往左子树找，这样就能找到最远的可行左端点。

涉及区间修改就要用到线段树的懒标记了，具体看代码。

以下代码：

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e5+50;
int N,C,K,a[maxn];
int t[maxn<<2],laz[maxn<<2];
void pushdown(int rt,int l,int r)
{
    if(laz[rt]==0)return;           //线段树维护的是最大值t[rt<<1]+=laz[rt];    //子树全部+laz[rt]，那么最大值肯定也会+laz[rt]laz[rt<<1]+=laz[rt];  //懒标记也要pushdownt[rt<<1|1]+=laz[rt];laz[rt<<1|1]+=laz[rt];laz[rt]=0;
}
void updata(int rt,int l,int r,int a,int b,int c)
{
                             //区间更新,[a,b]全部加上cif(a<=l&&r<=b){
    t[rt]+=c;laz[rt]+=c;return;}pushdown(rt,l,r);int mid=(l+r)>>1;if(b<=mid)updata(rt<<1,l,mid,a,b,c);else if(a>mid)updata(rt<<1|1,mid+1,r,a,b,c);else{
    updata(rt<<1,l,mid,a,b,c);updata(rt<<1|1,mid+1,r,a,b,c);}t[rt]=max(t[rt<<1],t[rt<<1|1]);
}
int query(int rt,int l,int r)
{
    if(l==r)return l;      //返回可行左端点的下标pushdown(rt,l,r);  //先pushdownint mid=(l+r)>>1;if(t[rt<<1]==C)         //优先左子树return query(rt<<1,l,mid);else if(t[rt<<1|1]==C)  //否则右子树return query(rt<<1|1,mid+1,r);elsereturn -1;          //都没有则返回-1
}
int main()
{
    while(~scanf("%d %d %d",&N,&C,&K)){
    vector<int> pos[maxn];for(int i=1;i<=C;i++)pos[i].push_back(0);  //方便起见，pos[x][0]均等于0for(int i=1;i<=N;i++){
    scanf("%d",&a[i]);pos[a[i]].push_back(i);}if(K==1)   //特判{
    printf("%d\n",N);continue;}memset(t,0,sizeof(t));     //初始化memset(laz,0,sizeof(laz));int ans=0,cur[maxn]={
    0};for(int i=1;i<=N;i++){
    int x=a[i];int p=++cur[x];updata(1,1,N,i,i,C-1);if(pos[x][p-1]+1<=pos[x][p]-1)updata(1,1,N,pos[x][p-1]+1,pos[x][p]-1,-1);if(p>=K)updata(1,1,N,pos[x][p-K]+1,pos[x][p-K+1],1);int temp=query(1,1,N);if(temp!=-1)ans=max(ans,i-temp+1);}printf("%d\n",ans);}return 0;
}