【题意】莫队加树状数组的做法很显然,解法借鉴HZWER大牛,这道题可以这样做,考虑对权值分块,这样使得每次查询复杂度变为√n,而修改的复杂度变为O1
总复杂度降为m√n,其实我自己一直没怎么想懂这个问题,感觉这个复杂度确实没优化多少。
【AC 代码】
#include <math.h>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
int n,m,sz;
int a[maxn],ans[1000010];
int pos[maxn],l[maxn],r[maxn];
int c[maxn],blockans[maxn];//BIT
struct node{
    int l,r,a,b,id;
    friend bool operator<(const node &aa,const node &bb){
        if(pos[aa.l]==pos[bb.l]) return aa.r<bb.r;
        return aa.l<bb.l;
    }
}q[1000010];

int queryans(int x,int y){
    int tmp=0;
    int L=pos[x],R=pos[y];
    for(int i=L+1; i<R; i++) tmp+=blockans[i];
    if(L==R){
        for(int i=x; i<=y; i++){
            if(c[i]) tmp++;
        }
    }else{
        for(int i=x; i<=r[L]; i++){
            if(c[i]) tmp++;
        }
        for(int i=l[R]; i<=y; i++){
            if(c[i]) tmp++;
        }
    }
    return tmp;
}

void del(int x){
    c[x]--;
    if(c[x]==0) blockans[pos[x]]--;
}
void add(int x){
    c[x]++;
    if(c[x]==1) blockans[pos[x]]++;
}
void solve()
{
    int l=1,r=0;
    for(int i=1; i<=m; i++){
        while(l<q[i].l) del(a[l]),l++;
        while(r>q[i].r) del(a[r]),r--;
        while(l>q[i].l) l--,add(a[l]);
        while(r<q[i].r) r++,add(a[r]);
        ans[q[i].id]=queryans(q[i].a,q[i].b);
    }
}

int main()
{
    memset(c,0,sizeof(c));
    memset(blockans,0,sizeof(blockans));
    memset(l,0,sizeof(l));
    memset(r,0,sizeof(r));
    scanf("%d%d",&n,&m);
    sz=(int)sqrt(n);
    for(int i=1; i<=n; i++){
        pos[i]=i/sz;
    }
    for(int i=1; i<=n; i++){
        r[pos[i]]=i;
        if(!l[pos[i]]) l[pos[i]]=i;
    }
    for(int i=1; i<=n; i++){
        scanf("%d",&a[i]);
    }
    for(int i=1; i<=m; i++){
        scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);
        q[i].id=i;
    }
    sort(q+1,q+m+1);
    solve();
    for(int i=1; i<=m; i++){
        printf("%d\n",ans[i]);
    }
}