题面：Luogu3709 像我这种语文烂到不行的人啊……看题看了个把小时总算看懂了 它的操作就是在保持这个集合的严格单调性，如果加进来的数不单调了，这个序列就清空并rp– 这个过程相当于在区间内构造了若干个严格递增序列，贡献就是负的序列个数 因为严格递增，所以可以想到答案就是负的区间众数的个数 这个用莫队就可以了。貌似主席树也可以做？ 本题重在语文水平！！！
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <iostream> #include <ctime> #include <map> #include <queue> #include <cstdlib> #include <string> #include <climits> #include <set> #include <vector> using namespace std; inline int read(){ int k=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();} return k*f; } struct ppap{int l,r,k,x;}q[200010]; inline bool cmp(ppap a,ppap b){return a.k==b.k?a.r<b.r:a.k<b.k;} int n,m,a[200010],b[200010],ans[200010]; int d[200010],k[200010],now=0,bs; inline void xg(int x,int y){ if(y==1&&now==k[x])now++; if(y==-1&&now==k[x]&&d[k[x]]==1)now--; d[k[x]]--;k[x]+=y;d[k[x]]++; } inline void work(){ int l=1,r=0;d[0]=bs; for(int i=1;i<=m;i++){ while(r<q[i].r)r++,xg(a[r],1); while(l>q[i].l)l--,xg(a[l],1); while(r>q[i].r)xg(a[r],-1),r--; while(l<q[i].l)xg(a[l],-1),l++; ans[q[i].x]=-now; } } int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=b[i]=read(); sort(b+1,b+n+1);bs=unique(b+1,b+n+1)-b-1; for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+bs+1,a[i])-b; int p=sqrt(n); for(int i=1;i<=m;i++){ q[i].l=read();q[i].r=read();q[i].k=(q[i].l-1)/p+1;q[i].x=i; } sort(q+1,q+m+1,cmp); work(); for(int i=1;i<=m;i++)printf("%d\n",ans[i]); return 0; }