一开始想到是树套树，空间28m树套树就狗带了

这题可以用莫队去做，如果在莫队下跑的是树状数组或者线段树的话复杂度要多带个log，可能跑不过

所以换成是分块。为什么分块，因为分块可以o（1）修改。

这里分块是针对值域来分而不是下标，外面套个莫队时间复杂度m*sqrt(n)+n*sqrt(n)

代码：

#include
     
      using namespace std;#define MAXN 100005#define MAXM 1000006int ret;char c;inline int read() {    ret=0;c=getchar();    while(c>'9'||c<'0') c=getchar();    while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();    return ret;}int s[MAXN],ans[MAXM],n,m,qsz;struct que{    int l,r,a,b,id;}q[MAXM];int bl[MAXN],cnt[MAXN],blk[MAXN];bool cmp(que a,que b) {
   return bl[a.l]==bl[b.l]?a.r
      
       
        =l;i--) ret+=(bool)cnt[i];    for(int i=bl[r]*qsz;i<=r;i++) ret+=(bool)cnt[i];    return ret;}int main() {    n=read();m=read();    qsz=(int)sqrt(n);    for(int i=1;i<=n;i++) s[i]=read();    for(int i=1;i<=n;i++) bl[i]=i/qsz;    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;    for(int i=1;i<=m;i++) {        while(r
        
         q[i].l) Up(s[--l]);        while(r>q[i].r) Down(s[r--]);        while(l