P3709 大爷的字符串题

在卡壳的时候吐槽了一句大爷的题果然做不动之后就思如泉涌是什么鬼？？
甚至发现了双倍经验？
传送
显然这个题的本质是道语文题。
先来分析分析大爷想要干什么

我们发现每次取一个严格递增的数列对\(rp\)的减少是最少的，所以我们要求一段区间里严格上升的数列的数量。由于是严格上升，所以这段区间里出现最多的那个数的次数就是答案。
所以问题就是每次询问一段区间内的区间众数出现的次数。

看起来可以用莫队搞一搞的样子。
维护答案：设\(cnt[i]\)表示数字\(i\)出现的次数，\(num[i]\)表示有多少个出现了\(i\)次的数。答案就是\(num\)中，非0数的最大下标。对于\(num\)来说，每次\(add\)或\(del\)都会使一个+1,一个-1，所以如果要更新答案，直接+1/-1即可。
蒟蒻曾经甚至想过把出现的次数扔进堆里，但发现复杂度似乎会炸

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=214748364;
inline int read()
{
    char ch=getchar();
    int x=0;bool f=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return f?-x:x;
}
int w,n,m,a[200009],cnt[200009],bl[200009],b[200009];
int ans[200009],all=-inf,num[200009];
struct Q{ 
    int id,l,r;
}qry[200009]; 
int fd(int a)
{
    int l=1,r=w;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(b[mid]==a) return mid;
        else if(b[mid]<a) l=mid+1;
        else  r=mid-1;
    }
    if(b[l]>a) l--;
    return l;
}
bool cmp(Q a,Q b)
{
    return (bl[a.l]^bl[b.l])?(bl[a.l]>bl[b.l]):((bl[a.l]%2)?(a.r<b.r):(a.r>b.r));
}
void add(int k)
{
    num[cnt[a[k]]]--;
    cnt[a[k]]++;
    num[cnt[a[k]]]++;
    all=max(all,cnt[a[k]]);
}
void del(int k)
{   
    num[cnt[a[k]]]--;
    if(!num[cnt[a[k]]]&&all==cnt[a[k]])
     all--;
    cnt[a[k]]--;
    num[cnt[a[k]]]++;
}
int main()
{  
    n=read();m=read();
    for(int i=1;i<=n;i++)
     a[i]=read(),b[i]=a[i];
    for(int i=1;i<=m;i++)
    {
        qry[i].id=i;qry[i].l=read();qry[i].r=read();
    } 
    int sn=sqrt(n);
    for(int i=1;i<=n;i++)
        bl[i]=(i-1)/sn; 
    sort(b+1,b+1+n);
    w=unique(b+1,b+1+n)-b-1;    
    for(int i=1;i<=n;i++)
     a[i]=fd(a[i]);
    sort(qry+1,qry+1+m,cmp); 
    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        while(r<qry[i].r) add(++r);
        while(r>qry[i].r) del(r--);
        while(l<qry[i].l) del(l++);
        while(l>qry[i].l) add(--l);
        ans[qry[i].id]=-all;
    }
    for(int i=1;i<=m;i++)
     printf("%d\n",ans[i]);
}

最后附上双倍经验

P3709 大爷的字符串题

原文：https://www.cnblogs.com/lcez56jsy/p/12157527.html