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]); }
原文：https://www.cnblogs.com/mastervan/p/11380841.html
