[文章目录]
Description
给你长度为n的区间，每个点有一个颜色，种类为[1,n]，给出m次询问，每次询问区间[l,r]中[a,b]种类颜色出现的个数。
第一反应：主席树。写了之后样例都不过，才发现理解错题意了。答案需要求的不是颜色属于[a,b]的节点个数，而是[a,b]中颜色出现的个数。
80s+28MB 那么就用莫队+树状数组吧。
发现所有的区间移动是logn维护的，那么总时间复杂度就是O()的，显然会爆掉。那么考虑一种数据结构使得移动区间修改时的时间复杂度不是那么高。发现分块可以做到O(1)修改，O()查询。
那么时间复杂度就变成了1.排序O()，2.区间移动：O()，3.查询：O()。
另外，神一般的28MB一定要规划好，在struct里直接记录所属的块会MLE。不如直接在cmp里直接计算所属的块更加清晰。
第一次写分块，调试的时候发现在计算零散的节点的时候需要注意l<=r。
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,blo,col[100010],sum[1000],num[100010];
struct quest
{
int l,r,a,b,id,ans;
}q[1000010];
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
bool cmp1(quest x,quest y)
{
return x.l/blo==y.l/blo ? x.r<y.r:x.l/blo<y.l/blo;
}
bool cmp2(quest x,quest y)
{
return x.id<y.id;
}
int main()
{
n=read();m=read(); blo=sqrt(1.0*n)+1;
int i,j;
for(i=1;i<=n;i++) col[i]=read();
for(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,cmp1);
int L=1,R=1;num[col[1]]=1;sum[col[1]/blo]=1;
for(i=1;i<=m;i++)
{
while(L>q[i].l){L--; if(!num[col[L]]) sum[col[L]/blo]++; num[col[L]]++; }
while(R<q[i].r){R++; if(!num[col[R]]) sum[col[R]/blo]++; num[col[R]]++; }
while(L<q[i].l){num[col[L]]--; if(!num[col[L]]) sum[col[L]/blo]--; L++; }
while(R>q[i].r){num[col[R]]--; if(!num[col[R]]) sum[col[R]/blo]--; R--; }
while(q[i].a%blo&&q[i].a<=q[i].b) q[i].ans+=(num[q[i].a]>0),q[i].a++;
while(q[i].b%blo!=blo-1&&q[i].b>=q[i].a) q[i].ans+=(num[q[i].b]>0),q[i].b--;
if(q[i].a<=q[i].b) for(j=q[i].a/blo;j<=q[i].b/blo;j++) q[i].ans+=sum[j];
}
sort(q+1,q+m+1,cmp2);
for(i=1;i<=m;i++)
printf("%d\n",q[i].ans);
return 0;
}