花都建网站公司/方法seo

https://www.luogu.org/problem/P3709

分析

从题目描述可以看出来出题人语文不行

理清题目描述后，其实是问在一个区间内取出一个严格上升数列，取完区间需要多少次

这个再思考一下，其实就是在问出现最多的数出现了多少次

由于值域1e9，我们考虑离散

由于可以离线的不带修区间操作，我们考虑莫队

离散后，times数组记录某数字出现了多少次，num数组记录有多少数字出现了i次

至于为什么涉及到答案时是O(1)的，因为当前答案失效后，它也只减少了一次出现次数啊，所以是原答案-1

 

#include <iostream> 
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2e5+10;
struct Query {int l,r,id;
}t[N];
int n,fn,m,fm;
int a[N],b[N],times[N],num[N],id[N],ans[N],lans;bool CMP(Query a,Query b) {return id[a.l]<id[b.l]||id[a.l]==id[b.l]&&(((id[a.l]&1)^1)^(a.r<b.r));
}void Solve(int x,bool type) {if (type) {num[times[x]]--;times[x]++;num[times[x]]++;lans=max(lans,times[x]);}else {num[times[x]]--;if (lans==times[x]&&num[times[x]]==0) lans--;times[x]--;num[times[x]]++;}
}int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=a[i];sort(b+1,b+n+1);fn=unique(b+1,b+n+1)-b-1;for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+fn+1,a[i])-b;for (int i=1;i<=m;i++) scanf("%d%d",&t[i].l,&t[i].r),t[i].id=i;fm=sqrt(m);for (int i=1;i<=m;i++) id[i]=i/fm+(i%fm>0);sort(t+1,t+m+1,CMP);num[0]=n;int l=1,r=1;Solve(a[1],1);for (int i=1;i<=m;i++) {while (r<t[i].r) Solve(a[++r],1);while (t[i].l<l) Solve(a[--l],1);while (l<t[i].l) Solve(a[l++],0);while (t[i].r<r) Solve(a[r--],0);ans[t[i].id]=lans;}for (int i=1;i<=m;i++) printf("%d\n",-ans[i]);
}