题意：
给定一个长度为 n ( 1 ≤ n ≤ 1 0 5 )的正整数序列 s ( 1 ≤ s i ≤ n )，对于 m ( 1 ≤ m ≤ 1 0 6 )次询问 l , r , a , b l每次输出 s l ⋯ s r中，权值 ∈ [ a , b ]的权值的种类数。
思路：
先考虑离线做法不难想到莫队，但是莫队没有办法维护权值的范围。由于权值1 < = a i < = n，考虑进行值域分块，莫队复杂度O ( n m )，询问复杂度O ( m n )，总的时间复杂度为O ( n n )级别。
具体做法为：
将所有询问保存并排序，莫队的基本操作
对于值域进行分块
在莫队的a d d , d e l函数里，维护一个c o l数组表示每个数出现的次数，s u m数组表示分块后每一块的不同数的个数。
查询的时候，要注意对于非整块区间，增加的贡献为数的个数，即r e s + = ( c o l [ i ] > 0 ) ;
代码：
// Problem: P4867 Gty的二逼妹子序列 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P4867 // Memory Limit: 32 MB // Time Limit: 5000 ms // Author:Cutele // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=100000+10,maxm=1000000+10; int n,m,a[maxn]; struct node{ int l,r,a,b,id; }q[maxm]; int L[1100],R[1100],sum[1100],ans[maxm],col[maxn],pos[maxn]; bool cmp(node a,node b){ if(pos[a.l]==pos[b.l]) return a.r<b.r; return pos[a.l]<pos[b.l]; } void add(int id){ int t=a[id]; col[t]++; if(col[t]==1) sum[pos[t]]++; } void del(int id){ int t=a[id]; col[t]--; if(!col[t]) sum[pos[t]]--; } int qask(int l,int r){ int res=0; int bl=pos[l],br=pos[r]; if(bl==br){ rep(i,l,r) res+=(col[i]>0); return res; } rep(i,bl+1,br-1) res+=sum[i]; rep(i,l,R[bl]) res+=(col[i]>0); rep(i,L[br],r) res+=(col[i]>0); return res; } int main(){ n=read,m=read; int block=sqrt(n); memset(L,0x3f,sizeof L); rep(i,1,n){ a[i]=read; pos[i]=(i-1)/block+1; L[pos[i]]=min(L[pos[i]],i); R[pos[i]]=max(R[pos[i]],i); } rep(i,1,m){ q[i].l=read,q[i].r=read,q[i].a=read,q[i].b=read,q[i].id=i; } sort(q+1,q+1+m,cmp); int nowl=0,nowr=0; rep(i,1,m){ int ql=q[i].l,qr=q[i].r; while(nowl<ql) del(nowl++); while(nowl>ql) add(--nowl); while(nowr>qr) del(nowr--); while(nowr<qr) add(++nowr); ans[q[i].id]=qask(q[i].a,q[i].b); } rep(i,1,m) printf("%d\n",ans[i]); return 0; }
