这是一道恶心至极的莫队套分块题。
考虑维护一个莫队，维护在 \([l,r]\) 值域下的答案。
考虑维护一个值域分块，维护在只余下 \([a,b]\) 的答案。
单点修改对答案带来的变化：
\(ans1\) 块：直接在 \(pos\) 位置上面做一个修改操作，然后去 \(\Theta(1)\) 地维护 \(pos[i]\) 块。
\(ans2\) 块：当 \(pos\) 无值时做单点修改，反之无视这一次的操作。
区间修改累积答案
\(ans1/2\) 块：分块地统计在 \([a,b]\) 中的答案。
然后圆润一下细节就行了。
code
#include <bits/stdc++.h>
#define re read()
#define pos block
#define PRINTF printf
using namespace std;
const int N=1e5+10,M=1e5+10,sqrt_N=1e3+5,maxn=1e5+1;
int a[N],tree[N],tree2[N],out[M],c[N],block[N],a1[N],b1[N],st[N],ed[N],a2[N],b2[N];
int n,m;
inline int read(){
register int x=0;
char c=getchar();
while(!isdigit(c)){
c=getchar();
}
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
struct QUERY{int l,r,block,a,b,rk;}ask[M];
inline bool cmp(QUERY a,QUERY b){
if(a.block!=b.block)return a.block<b.block;
else if(a.block & 1) return a.r>b.r;
return a.r<b.r;
}
int sz,cntblock;
inline void init(void){
sz=sqrt(maxn)+1;
cntblock=n/sz;
for(register int i=1;i<=maxn;++i){
block[i]=(i-1)/sz+1;
}
if(n%sz)++cntblock;
for(register int i=1;i<=cntblock;++i){
st[i]=(i-1)*sz+1;
ed[i]=i*sz;
}
ed[cntblock]=n;
return;
}
void write(int x){
if(x>9) write(x/10);
putchar((x%10)^48);
}
inline void input(void){
n=re,m=re;
int leng=n/sqrt(m)+1;
for(register int i=1;i<=n;++i)
a[i]=re;
for(register int i=1;i<=m;++i)
ask[i].l=re,ask[i].r=re,ask[i].a=re,ask[i].b=re,
ask[i].rk=i,ask[i].block=((ask[i].l-1)/leng)+1;
sort(ask+1,ask+m+1,cmp);
}
// init
int tree1[N];
inline void update1(int x,int k){
a1[x]+=k;
b1[pos[x]]+=k;
}
inline int query1(int L,int R){
int res=0;
if(pos[L]^pos[R]){
for(register int i=L;i<=ed[pos[L]];++i)
res+=a1[i];
for(register int i=st[pos[R]];i<=R;++i)
res+=a1[i];
for(register int i=pos[L]+1;i<=pos[R]-1;++i)
res+=b1[i];
}else{
for(register int i=L;i<=R;++i){
res+=a1[i];
}
}
return res;
}
inline void update2(int x,int k){
a2[x]+=k;
b2[pos[x]]+=k;
}
inline int query2(int L,int R){
int res=0;
if(pos[L]^pos[R]){
for(register int i=L;i<=ed[pos[L]];++i)
res+=a2[i];
for(register int i=st[pos[R]];i<=R;++i)
res+=a2[i];
for(register int i=pos[L]+1;i<=pos[R]-1;++i)
res+=b2[i];
}else{
for(register int i=L;i<=R;++i)
res+=a2[i];
}
return res;
}
inline void del(int x){
x=a[x];
c[x]--;
if(!c[x]) update2(x,-1);
update1(x,-1);
}
inline void add(int x){
x=a[x];
if(!c[x])update2(x,1);
update1(x,1);
c[x]++;
}
int ans1,ans2;
int put1[M],put2[M];
inline void calc(int a,int b){
ans1=query1(a,b);
ans2=query2(a,b);
}
int curl,curr;
inline void work(void){
int curl=ask[1].l,curr=ask[1].r;
for(register int i=curl;i<=curr;++i)
add(i);
calc(ask[1].a,ask[1].b);
put1[ask[1].rk]=ans1,put2[ask[1].rk]=ans2;
for(register int i=2;i<=m;++i){
while(curl<ask[i].l) del(curl++);
while(curl>ask[i].l) add(--curl);
while(curr<ask[i].r) add(++curr);
while(curr>ask[i].r) del(curr--);
calc(ask[i].a,ask[i].b);
put1[ask[i].rk]=ans1,put2[ask[i].rk]=ans2;
}
return;
}
inline void output(void){
for(register int i=1;i<=m;++i){
write(put1[i]);
putchar(' ');
write(put2[i]);
putchar('\n');
}
return;
}
inline void forall(void){
input(),init(),work(),
output();
}
int main(void){
forall();
}
失误：\(belong\) 处理。然后就寄了。