[ Luogu 3709 ] 大爷的字符串题

\(\\\)

Description

原题题面太过混乱出题人语文凉凉

给出一个长为 \(n\) 的数列 \(A\) ，多次询问：

对于一个区间 \([L_i,R_i]\)，把区间内的所有数最少划分成多少个数集，使得每一个集合内没有相同元素。

\(A_i\le 10^9,n,m\le 2\times 10^5\)

\(\\\)

Solution

题目的模型很容易转化成区间众数问题。

莫队求解区间众数。

首先数据范围是假的，离散化之后就开的下桶了。

对于区间扩张，肯定是加一下桶，然后跟当前答案取 \(max\) 。

问题在于区间缩小时，删除一个数怎么搞。

\(\\\)

开始有一个 too simple 想法，是用堆去维护当前答案区间内所有数出现个数，然后懒惰删除法，每次更新时判断一下堆顶是否正确。

想一想是对的，但是 \(O(N\sqrt NlogN)\) 的复杂度对于 \(2\times 10^5\) 很吃力。

\(\\\)

一个机智的做法。

设 \(cnt[i]\) 表示 \(bkt[x]=i\) 的个数，也就是当前区间里出现次数为 \(i\) 的数的个数。

空间没有问题，因为最多出现数列长度的次数。

这样一来修改就容易了很多，减的时候只需要判断一下，当前数对应的 \(cnt\) 是否 \(>1\) 即可。

注意加减是对 \(cnt\) 和 \(bkt\) 的同时更新。

\(\\\)

Code

#include<cmath>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 200000

#define R register

#define gc getchar

using namespace std;

inline int rd(){

  int x=0; bool f=0; char c=gc();

  while(!isdigit(c)){if(c=='-')f=1;c=gc();}

  while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}

  return f?-x:x;

}

int n,m,ans,bl[N],cnt[N],bkt[N],s[N],tmp[N];

struct Q{int l,r,ans,id;}q[N];

inline bool cmp1(Q x,Q y){

  return bl[x.l]==bl[y.l]?x.r<y.r:bl[x.l]<bl[y.l];

}

inline bool cmp2(Q x,Q y){return x.id<y.id;}

inline void add(int p){

  --cnt[bkt[s[p]]];

  ++cnt[++bkt[s[p]]];

  ans=max(ans,bkt[s[p]]);

}

inline void del(int p){

  --cnt[bkt[s[p]]];

  if(ans==bkt[s[p]]&&!cnt[bkt[s[p]]]) --ans;

  ++cnt[--bkt[s[p]]];

}

int main(){

  n=rd(); m=rd();

  int t=sqrt(n),tot=0;

  for(R int i=1,cntt=1;i<=n;++i){

    tmp[i]=s[i]=rd();

    if(i%t==0) ++cntt;

    bl[i]=cntt;

  }

  sort(tmp+1,tmp+1+n);

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

    tmp[++tot]=tmp[i];

    while(tmp[i+1]==tmp[i]&&i<=n) ++i;

  }

  for(R int i=1;i<=n;++i) s[i]=lower_bound(tmp+1,tmp+1+tot,s[i])-tmp;

  for(R int i=1;i<=m;++i){

    q[i].l=rd(); q[i].r=rd(); q[i].id=i;

  }

  sort(q+1,q+1+m,cmp1);

  bkt[s[1]]=cnt[1]=ans=1;

  int nowl=1,nowr=1;

  for(R int i=1;i<=m;++i){

    while(nowl<q[i].l){del(nowl);++nowl;}

    while(nowl>q[i].l){--nowl;add(nowl);}

    while(nowr>q[i].r){del(nowr);--nowr;}

    while(nowr<q[i].r){++nowr;add(nowr);}

    q[i].ans=ans;

  }

  sort(q+1,q+1+m,cmp2);

  for(R int i=1;i<=m;++i) printf("%d\n",-q[i].ans);

  return 0;

}

巴特西

[ Luogu 3709 ] 大爷的字符串题

Description

Solution

Code

最新文章

热门文章