#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
inline void Get_Int(int &x)
{
x=; char ch=getchar(); int f=;
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;
}
inline void Put_Int(int x)
{
char ch[]; int top=;
if (x==) ch[++top]='';
while (x) ch[++top]=x%+'',x/=;
while (top) putchar(ch[top--]); putchar('\n');
}
//===================================================
const int Maxn=;
const int Maxm=;
struct Node{int l,r,u,v,id;}q[Maxm]; int n,m,s[Maxn],Block,Ans[Maxm],b[Maxn],B[Maxn];//Ans开Maxm
inline int Get(int x) {return (x-)/Block+;}
inline int Query(int x,int y)
{
int l=Get(x),r=Get(y),ret=;
if (l==r)
{
for (int i=x;i<=y;i++) if (b[i]) ret++;
return ret;
}
for (int i=l+;i<r;i++) ret+=B[i];
for (int i=x;Get(i)==l;i++) if (b[i]) ret++;
for (int i=y;Get(i)==r;i--) if (b[i]) ret++;
return ret;
}
inline bool cmp(Node A,Node B)
{
if (Get(A.l)==Get(B.l)) return A.r<B.r;
return Get(A.l)<Get(B.l);
}
inline void Del(int x)
{if (b[s[x]]==) B[Get(s[x])]--; b[s[x]]--;}
inline void Add(int x)
{if (b[s[x]]==) B[Get(s[x])]++; b[s[x]]++;} int main()
{
Get_Int(n),Get_Int(m); Block=(int)sqrt(n);
for (int i=;i<=n;i++) Get_Int(s[i]);
for (int i=;i<=m;i++)
Get_Int(q[i].l),Get_Int(q[i].r),Get_Int(q[i].u),Get_Int(q[i].v),q[i].id=i;
memset(b,,sizeof(b));
memset(B,,sizeof(B));
sort(q+,q+m+,cmp);
int L=,R=; for (int i=;i<=m;i++)
{
while (R<q[i].r) R++,Add(R);
while (L>q[i].l) L--,Add(L);
while (L<q[i].l) Del(L),L++;
while (R>q[i].r) Del(R),R--;
Ans[q[i].id]=Query(q[i].u,q[i].v);
}
for (int i=;i<=m;i++) Put_Int(Ans[i]);
return ;
}
分块 40s
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
#define pa pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
using namespace std;
inline void Get_Int(int &x)
{
x=; char ch=getchar(); int f=;
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();} x*=f;
}
inline void Put_Int(int x)
{
char ch[]; int top=;
if (x==) ch[++top]='';
while (x) ch[++top]=x%+'',x/=;
while (top) putchar(ch[top--]); putchar('\n');
}
//===================================================
const int Maxn=;
const int Maxm=;
struct Node{int l,r,u,v,id;}q[Maxm]; int c[Maxn],n,m,s[Maxn],Block,Ans[Maxm],b[Maxn];//Ans开Maxm
inline int lowbit(int x) {return x&(-x);}
inline int Query(int x)
{int ret=; for (int i=x;i;i-=lowbit(i)) ret+=c[i];return ret;}
inline void Modify(int x,int v)
{for (int i=x;i<=n;i+=lowbit(i)) c[i]+=v;}
inline int Get(int x) {return (x-)/Block+;}
inline bool cmp(Node A,Node B)
{
if (Get(A.l)==Get(B.l)) return A.r<B.r;
return Get(A.l)<Get(B.l);
}
inline void Del(int x)
{if (b[s[x]]==) Modify(s[x],-);b[s[x]]--;}
inline void Add(int x)
{if (b[s[x]]==) Modify(s[x],); b[s[x]]++;} int main()
{
Get_Int(n),Get_Int(m); Block=(int)sqrt(n/);
for (int i=;i<=n;i++) Get_Int(s[i]);
for (int i=;i<=m;i++)
Get_Int(q[i].l),Get_Int(q[i].r),Get_Int(q[i].u),Get_Int(q[i].v),q[i].id=i;
memset(b,,sizeof(b));
memset(c,,sizeof(c));
sort(q+,q+m+,cmp);
int L=,R=;
for (int i=;i<=m;i++)
{
while (R<q[i].r) R++,Add(R);
while (L>q[i].l) L--,Add(L);
while (L<q[i].l) Del(L),L++;
while (R>q[i].r) Del(R),R--;
Ans[q[i].id]=Query(q[i].v)-Query(q[i].u-);
}
for (int i=;i<=m;i++) Put_Int(Ans[i]);
return ;
}
BIT 77s
对权值分块复杂度更优.