洛谷3709：大爷的字符串题—

洛谷3709：大爷的字符串题——题解

阅读量：6209 次

发布时间：2019-06-21

本文共 1713 字，大约阅读时间需要 5 分钟。

给你一个字符串a，每次询问一段区间的贡献

贡献定义：

每次从这个区间中随机拿出一个字符x，然后把x从这个区间中删除，你要维护一个集合S

如果S为空，你rp减1

如果S中有一个元素不小于x，则你rp减1，清空S

之后将x插入S

由于你是大爷，平时做过的题考试都会考到，所以每次询问你搞完这段区间的字符之后最多还有多少rp？rp初始为0

询问之间不互相影响~

参考：

题面乱七八糟的，但是可以知道，我们每次加入当前区间最长上升序列就是最优解。

而一共有多少个这样的序列就是答案。

换句话讲，区间众数个数就是答案。

然而这题出题人没良心卡分块空间，所以考虑莫队。

莫队的add和del操作看代码吧，cnt[i]统计i个数的元素有多少，sum[i]表示元素i有多少个。

（个人感觉复杂度不是很明白……）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=200001;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct qu{ int pos,l,r;}q[N];int a[N],b[N],ans[N],cnt[N],sum[N],tmp,pos,n,m,lim,s;inline int bel(int x){ return (x-1)/s+1;}inline void LSH(){ sort(b+1,b+lim+1); lim=unique(b+1,b+lim+1)-b-1; for(int i=1;i<=n;i++){ a[i]=lower_bound(b+1,b+lim+1,a[i])-b; } return;}bool cmp(qu b,qu c){ return bel(b.l)==bel(c.l)?b.r
            
             
              tmp)tmp=sum[x]; return;}inline void del(int x){ cnt[sum[x]]--; sum[x]--; cnt[sum[x]]++; while(!cnt[tmp])tmp--; return;}int main(){ n=read();m=read(); s=sqrt(n); for(int i=1;i<=n;i++)a[i]=b[++lim]=read(); LSH(); for(int i=1;i<=m;i++){ q[i].pos=i; q[i].l=read(); q[i].r=read(); } sort(q+1,q+m+1,cmp); int ql=1,qr=0;cnt[0]=lim; for(int i=1;i<=m;i++){ while(ql
              
               q[i].l)add(a[--ql]); while(qr
               
                q[i].r)del(a[qr--]); ans[q[i].pos]=tmp; } for(int i=1;i<=m;i++)printf("-%d\n",ans[i]); return 0;}