P3709 大爷的字符串题莫队离线求众数-白红宇的个人博客

发布日期：2021-09-25 23:58:06 浏览次数：4 分类：技术文章

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

~~比赛卡题挂机先溜了~~

离散化一下，让后记录一个cnt数组代表这个数出现次数，num数组记录出现次数为i的数有几个。让后直接维护就好了

#pragma GCC optimize(2)#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int cnt[N],a[N],id[N],num[N],ans[N];int now;struct Node{ int l,r; int id;}q[N];vector
                
                 v;int find(int x){ return lower_bound(v.begin(),v.end(),x)-v.begin();}bool cmp(Node a,Node b){ return id[a.l]^id[b.l]? a.l
                 
                  b.r);}void del(int x){ x=a[x]; if(now==cnt[x]&&num[cnt[x]]==1) now--; num[cnt[x]]--; num[--cnt[x]]++;}void add(int x){ x=a[x]; num[cnt[x]]--; num[++cnt[x]]++; now=max(now,cnt[x]);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); scanf("%d%d",&n,&m); int se=sqrt(n); se=ceil((double)n/se); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); v.pb(a[i]); } for(int i=1;i<=se;i++) for(int j=(i-1)*se+1;j<=i*se;j++) id[j]=i; sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); for(int i=1;i<=n;i++) a[i]=find(a[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&q[i].l,&q[i].r); q[i].id=i; } sort(q+1,q+1+m,cmp); int l=1,r=0; for(int i=1;i<=m;i++) { int lx=q[i].l,rx=q[i].r; while(l
                  
                   lx) add(--l); while(r
                   
                    rx) del(r--); ans[q[i].id]=now; } for(int i=1;i<=m;i++) printf("%d\n",-ans[i]); return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/108351541 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Vladik and fractions CodeForces - 743C 思维

下一篇：P4462 异或序列莫队 + 异或技巧

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章