转载

P3709 大爷的字符串题(莫队+结论)

题目

P3709 大爷的字符串题

做法

有一个显然的结论:一段区间里最小答案为众数的个数

用莫队来离线求众数

\(tmp_i\)表示出现\(i\)次的数的个数,\(num_i\)表示\(i\)出现的次数

缩小区间:答案可能减小,看答案所在的\(tmp\)是否不唯一

扩大区间:答案增大

Code

#include<bits/stdc++.h> typedef int LL; const LL maxn=1e6+9; inline LL Read(){ LL x(0),f(1); char c=getchar(); while(c<'0' || c>'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0' && c<='9'){ x=(x<<3ll)+(x<<1ll)+c-'0'; c=getchar(); }return x*f; } struct node{ LL l,r,id; }qy[maxn]; LL n,m,ret; LL ans[maxn],num[maxn],tmp[maxn],a[maxn],b[maxn],bel[maxn]; inline bool cmp(node xx,node yy){ return bel[xx.l]<bel[yy.l] || (bel[xx.l]==bel[yy.l] && (bel[xx.l]&1?xx.r<yy.r:xx.r>yy.r)); } inline void Modify(LL val,LL op){ if(!op){ if(ret==num[val] && tmp[ret]==1) --ret; --tmp[num[val]]; ++tmp[--num[val]]; }else{ if(ret==num[val]) ++ret; --tmp[num[val]]; ++tmp[++num[val]]; } } int main(){ n=Read(); m=Read(); for(LL i=1;i<=n;++i) a[i]=b[i]=Read(); std::sort(b+1,b+1+n); for(LL i=1;i<=n;++i) a[i]=std::lower_bound(b+1,b+1+n,a[i])-b;//,printf("%d ",a[i]);puts(""); for(LL i=1;i<=m;++i) qy[i]=(node){Read(),Read(),i}; LL pieces(sqrt(n)),size(n/pieces); for(LL i=1;i<=pieces;++i){ for(LL j=(i-1)*size+1;j<=i*size;++j) bel[j]=i; } for(LL i=pieces*size+1;i<=n;++i) bel[i]=pieces+1; std::sort(qy+1,qy+1+m,cmp); tmp[0]=n; LL nl(1),nr(0); for(LL i=1;i<=m;++i){ LL ql(qy[i].l),qr(qy[i].r); while(nl<ql) Modify(a[nl++],0); while(nl>ql) Modify(a[--nl],1); while(nr<qr) Modify(a[++nr],1); while(nr>qr) Modify(a[nr--],0); ans[qy[i].id]=ret; } for(LL i=1;i<=m;++i) printf("-%d\n",ans[i]); return 0; }

转载于:https://www.cnblogs.com/y2823774827y/p/11120270.html

正文到此结束
本文目录