第一问分块,第二份借鉴题解莫队,最后一个WA,问题在第二问上,球调
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
using namespace std;
inline int read(){
int 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;
}
const int N=1e5+10;
const int M=sqrt(N)+1;
const int MAXN=2e5+10;
int n,m,t,base[N],L[N],R[N],pos[N];
int B,maxn,bl[MAXN],blv[MAXN],ans[MAXN],res[MAXN],s1[MAXN],s2[MAXN];
unsigned short sum[M][N];
int solve(int l,int r,int a,int b){
int p=pos[l],q=pos[r],s=0;
if(p==q){
for(int i=l;i<=r;i++)
if(a<=base[i]&&base[i]<=b)
s++;
return s;
}
for(int i=p+1;i<=q-1;i++)
s+=(sum[i][b]-sum[i][a-1]);
for(int i=l;i<=R[p];i++)
if(a<=base[i]&&base[i]<=b)
s++;
for(int i=L[q];i<=r;i++)
if(a<=base[i]&&base[i]<=b)
s++;
return s;
}
struct question{
int id,l,r,a,b;
}q[N];
bool cmp(question a, question b){
return (bl[a.l]^bl[b.l])?bl[a.l]<bl[b.l]:((bl[a.l]&1)?a.r<b.r:a.r>b.r);
}
void del(int p){
s2[base[p]]--;
if(s2[base[p]]<=0)
s1[blv[base[p]]]--;
}
void add(int p){
s2[base[p]]++;
if(s2[base[p]]<=1)
s1[blv[base[p]]]++;
}
int query(int l,int r){
int ret=0;
r=min(r,maxn);
if(l>maxn)
return 0;
int ll=blv[l]+1,rr=blv[r]-1;
if(blv[l]==blv[r]){
for(int i=l;i<=r;i++)
ret+=(bool)s2[i];
return ret;
}
for(int i=ll;i<=rr;i++)
ret+=s1[i];
for(int i=l;blv[i]==blv[l]&&l<=maxn;i++)
ret+=(bool)s2[i];
for(int i=r;blv[i]==blv[r]&&r>=0;i--)
ret+=(bool)s2[i];
return ret;
}
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
n=read(),m=read();
t=sqrt(n);
B=1.0*n/sqrt(m)+1;
for(int i=1;i<=n;i++){
base[i]=read();
maxn=max(maxn,base[i]),bl[i]=i/B;
}
for(int i=1;i<=t;i++){
L[i]=(i-1)*t+1;
R[i]=i*t;
}
if(R[t]<n){
t++;
L[t]=R[t-1]+1;
R[t]=n;
}
for(int i=1;i<=t;i++){
for(int j=L[i];j<=R[i];j++)
pos[j]=i;
for(int j=L[i];j<=R[i];j++)
sum[i][base[j]]++;
for(int j=1;j<=n;j++)
sum[i][j]=sum[i][j-1]+sum[i][j];
}
for(int i=1;i<=m;i++)
q[i].l=read(),q[i].r=read(),q[i].a=read(),q[i].b=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
int l=1,r=0;
B=sqrt(maxn)+1;
for(int i=0;i<=maxn;i++)
blv[i]=i/B;
for(int i=1;i<=m;i++){
int a=q[i].a,b=q[i].b;
while(l<q[i].l)
del(l++);
while(l>q[i].l)
add(--l);
while(r<q[i].r)
add(++r);
while(r>q[i].r)
del(r--);
res[q[i].id]=solve(q[i].l,q[i].r,a,b);
ans[q[i].id]=query(a,b);
}
for(int i=1;i<=m;i++)
printf("%d %d\n",res[i],ans[i]);
return 0;
}