洛谷P3709

看起来知识点 + 思维难度大概蓝题，读题难度大概紫题？

因为说实话我现在还是很难独立描述清楚题面的意思

Description

要求从区间每次取一个数与给定的 (x) 作比较，若取出的数小于 (x) 则分数减一，求最大分数

因为没有加分操作只有扣分操作，所以也可以看成要求扣分最小化

因此本质是每次从区间中取出一个严格上升的序列，然后问最少取几次（还是引用了楼叉楼的话，因为个人能力无法做成更言简意赅的描述了）

Solution

那就是找出现次数最多的数的出现次数咯

这么一说就简单多了，莫队搞一下就可以了

先给数据离散化，然后通过维护每个数的出现次数和出现这么多次的数的个数来转移区间更新答案即可

注意收缩区间时要确定删去的这个数是否有唯一性，或者说是否对答案有影响，具体内容看代码

看起来这么做不加任何优化依然跑得飞快（？）

最后的答案就是出现最多的数的出现次数的相反数

Code

#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<iostream>
#include<algorithm>
#define maxn 1000010
#define INF 0x3f3f3f3f
//#define int long long

using namespace std;

int n,m,Ans,len,L=1,R=0,tot;
int sum[maxn],num[maxn],cnt[maxn];
int ans[maxn],b[maxn],a[maxn],siz[maxn];
struct question{int now,l,r;}q[maxn];
 
int read(){
    int s=0,w=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
    return s*w;
}

bool cmp(question x,question y){
    return (x.l/len)^(y.l/len)?x.l<y.l:x.r<y.r;
}

void build(){
    n=read();m=read();len=sqrt(n+0.5);
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
    sort(b+1,b+n+1);tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    for(int i=1;i<=m;i++)q[i].l=read(),q[i].r=read(),q[i].now=i;    
    sort(q+1,q+m+1,cmp);
}

void Add(int x){
    num[cnt[a[x]]]--;num[++cnt[a[x]]]++;
    Ans=max(Ans,cnt[a[x]]);
}

void Del(int x){    
    num[cnt[a[x]]]--;num[--cnt[a[x]]]++;
    if(Ans==cnt[a[x]]+1&&!num[cnt[a[x]]+1]) Ans--;
    //若删除的那个数的出现次数就是答案并且出现这么多次的数只有那一个时，删去它会使得答案变劣
}

int main(){
    build();
    for(int i=1;i<=m;i++){
        while(L>q[i].l) Add(--L);
        while(R<q[i].r) Add(++R);
        while(L<q[i].l) Del(L++);
        while(R>q[i].r) Del(R--);
        ans[q[i].now]=Ans;
    }
    for(int i=1;i<=m;i++) printf("%d
",ans[i]);
    return 0;
}