题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3809
容易想到树状数组维护值域。但修改和查询都是 log 太慢。
考虑有 nsqrt(n) 个修改、m个查询，所以给查询 sqrt(n) ，给修改 O(1) 。对值域分块即可。（msqrt(n)也能过？）
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+5,M=1e6+5,K=320; int n,m,a[N],base,bh[N],cnt[N],sm[K],ans[M]; struct Ques{ int l,r,a,b,bh; }q[M]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } bool cmp(Ques u,Ques v){return bh[u.l]==bh[v.l]?u.r<v.r:bh[u.l]<bh[v.l];} void add(int x) { if(!cnt[x])sm[bh[x]]++; cnt[x]++; } void del(int x) { cnt[x]--; if(!cnt[x])sm[bh[x]]--; } int query(int l,int r) { int ret=0; if(bh[r]-bh[l]<=1) { for(int i=l;i<=r;i++)if(cnt[i])ret++; return ret; } for(int i=bh[l]+1;i<bh[r];i++) ret+=sm[i]; int L=base*bh[l],R=base*(bh[r]-1); for(int i=l;i<=L;i++)if(cnt[i])ret++; for(int i=R+1;i<=r;i++)if(cnt[i])ret++; return ret; } int main() { n=rdn(); m=rdn(); base=sqrt(n); for(int i=1;i<=n;i++) a[i]=rdn(),bh[i]=(i-1)/base+1; for(int i=1;i<=m;i++) q[i].l=rdn(),q[i].r=rdn(),q[i].a=rdn(),q[i].b=rdn(),q[i].bh=i; sort(q+1,q+m+1,cmp); int L=0,R=0; for(int i=1;i<=m;i++) { int l=q[i].l,r=q[i].r; while(L>l)add(a[--L]); while(R<r)add(a[++R]); while(L<l)del(a[L++]); while(R>r)del(a[R--]); ans[q[i].bh]=query(q[i].a,q[i].b); } for(int i=1;i<=m;i++)printf("%d ",ans[i]); return 0; }