首页 > 其他 > 详细

大爷的字符串题

时间:2019-10-18 12:46:14      阅读:52      评论:0      收藏:0      [点我收藏+]

 莫队毒瘤题

出题人语文水平极高,题意理解一下

就是求区间众数出现次数(什么毒瘤题目)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5211314;
int a[maxn], pos[maxn], s[maxn],d[maxn];
int cnt[maxn],ans[maxn],lx,n,m;
int re(){
    int x=0,w=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)w=-1;ch=getchar();}
    while(ch>=0&&ch<=9)x=x*10+ch-0,ch=getchar();
    return x*w;
}
struct query{
    int l,r,id;
}q[maxn]; 
bool cmp(query a,query b){
    return (pos[a.l]==pos[b.l])?((pos[a.l]&1)?a.r<b.r:a.r>b.r):pos[a.l]<pos[b.l]; 
} 
inline void add(int x){
    s[cnt[a[x]]++]--;s[cnt[a[x]]]++;lx=max(lx,cnt[a[x]]);
}
inline void del(int x){
    s[cnt[a[x]]]--;if(cnt[a[x]]==lx&&!s[lx])lx--;s[--cnt[a[x]]]++;
}
int main() {
    n=re(),m=re(); 
    int size=sqrt(n); 
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        d[i]=a[i]; 
        pos[i] = (i - 1) / size + 1;
    }
    sort(d+1,d+n+1);int len=unique(d+1,d+n+1)-d-1; 
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(d+1,d+len+1,a[i])-d;
    for(int i=1;i<=m;i++){
        q[i].l=re(),q[i].r=re(); 
        q[i].id=i; 
    } 
    sort(q+1,q+m+1,cmp);
    int r=0,l=1;
    for (int i = 1; i <= m; i++) {
        while(r<q[i].r)add(++r);
        while(r>q[i].r)del(r--);
        while(l<q[i].l)del(l++);
        while(l>q[i].l)add(--l);
        ans[q[i].id]=lx;
    }
    for(int i=1;i<=m;i++)printf("%d\n",-ans[i]); 
}

 

大爷的字符串题

原文:https://www.cnblogs.com/wilxx/p/11697524.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!