【HDOJ6602】Longest Subarray（线段树，vector）

题意：给定一个长为n的序列，第i个数a[i]都是一个[1,c]中的整数

如果一段序列[l,r]中出现过的数字出现次数都>=K则称其为好的序列

求最长的好的序列的长度

n,k,c,a[i]<=1e5

思路：考虑固定右端点，对于每种数字来说合法的左端点都是两段

将对于每种数字来说合法的左端的位置都+1，则和为c的位置都是合法的，显然取最小的左端点

右端点右移的时候推一下左端点如何移动，用一个vector存每种数字出现的位置，往前k个就直接下标减k

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef unsigned int uint;

 typedef unsigned long long ull;

 typedef pair<int,int> PII;

 typedef pair<ll,ll> Pll;

 typedef vector<int> VI;

 typedef vector<PII> VII;

 typedef pair<ll,ll>P;

 #define N  100010

 #define M  200010

 #define fi first

 #define se second

 #define MP make_pair

 #define pi acos(-1)

 #define mem(a,b) memset(a,b,sizeof(a))

 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)

 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)

 #define lowbit(x) x&(-x)

 #define Rand (rand()*(1<<16)+rand())

 #define id(x) ((x)<=B?(x):m-n/(x)+1)

 #define ls p<<1

 #define rs p<<1|1

 const ll MOD=1e9+,inv2=(MOD+)/;

       double eps=1e-;

       int INF=<<;

       ll inf=5e13;

       int dx[]={-,,,};

       int dy[]={,,-,};

 int mx[N<<],tag[N<<],pos[N<<],n,C,k;

 VI c[N];

 int read()

 {

    int v=,f=;

    char c=getchar();

    while(c<||<c) {if(c=='-') f=-; c=getchar();}

    while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();

    return v*f;

 }

 void pushup(int p)

 {

     if(mx[ls]>=mx[rs])

     {

         mx[p]=mx[ls];

         pos[p]=pos[ls];

     }

      else

      {

          mx[p]=mx[rs];

          pos[p]=pos[rs];

      }

 }

 void pushdown(int p)

 {

     if(tag[p]!=)

     {

         tag[ls]+=tag[p];

         tag[rs]+=tag[p];

         mx[ls]+=tag[p];

         mx[rs]+=tag[p];

         tag[p]=;

     }

 }

 void build(int l,int r,int p)

 {

     mx[p]=tag[p]=;

     pos[p]=l;

     if(l==r) return;

     int mid=(l+r)>>;

     build(l,mid,ls);

     build(mid+,r,rs);

 }

 void update(int l,int r,int x,int y,int v,int p)

 {

     if(l>r) return;

     if(x>y) return;

     if(x<=l&&r<=y)

     {

         mx[p]+=v;

         tag[p]+=v;

         return;

     }

     pushdown(p);

     int mid=(l+r)>>;

     if(x<=mid) update(l,mid,x,y,v,ls);

     if(y>mid) update(mid+,r,x,y,v,rs);

     pushup(p);

 }

 int query(int l,int r,int x,int y,int p)

 {

     if(l>r) return ;

     if(x>y) return ;

     if(mx[p]!=C) return ;

     if(x<=l&&r<=y) return pos[p];

     pushdown(p);

     int mid=(l+r)>>;

     int res=query(l,mid,x,y,ls);

     if(res) return res;

     return query(mid+,r,x,y,rs);

 }

 int main()

 {

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

     {

         build(,n,);

         rep(i,,C)

         {

             c[i].clear();

             c[i].push_back();

         }

         int ans=;

         rep(i,,n)

         {

             //printf("i=%d\n",i);

             int x=read();

             update(,n,i,i,C-,);

             update(,n,c[x].back()+,i-,-,);

             c[x].push_back(i);

             int now=(int)c[x].size()-k-;

             if(now>=) update(,n,c[x][now]+,c[x][now+],,);

             int j=query(,n,,i,);

             if(j) ans=max(ans,i-j+);

         }

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

     }

     return ;

 }

巴特西

【HDOJ6602】Longest Subarray（线段树，vector）

最新文章

热门文章