题目大意：

给定 $nn$n 个二维点（$i,f\left[i\right]i,f[i]$i,f[i]）， $mm$m 次查询，每次查询给定一个矩阵，求在这个矩阵中的点有多少个不同的纵坐标。

数据范围：

$1\le n,m\le 10^{5}1\; \backslash le\; n,m\; \backslash le\; 10^5$1≤n,m≤105

$0\le f\left[i\right]\le 10^{5}0\; \backslash le\; f[i]\; \backslash le\; 10^5$0≤f[i]≤105

矩阵： $1\le x_0\le x_1\le n,0\le y_0\le y_1\le 10^{5}1\; \backslash le\; x\_0\; \backslash le\; x\_1\; \backslash le\; n,0\; \backslash le\; y\_0\; \backslash le\; y\_1\; \backslash le\; 10^5$1≤x0​≤x1​≤n,0≤y0​≤y1​≤105 ，$(x_0,y_0)(x\_0,y\_0)$(x0​,y0​) 为矩阵左下角坐标，$(x_1,y_1)(x\_1,y\_1)$(x1​,y1​) 为矩阵左下角坐标

思路：

1. 莫队＋树状数组

   对于每次查询给的矩阵，第一维度x用莫队维护一个桶数组 $ansans$ans ，代表当前 $[x_0,x_1][x\_0,x\_1]$[x0​,x1​] 区间内纵坐标的分布，对于第二维度y，根据桶数组的情况在树状数组上更新，如果这个点 $pp$p 加入后 $ans\left[p\right]==1ans[p]==1$ans[p]==1 ，则树状数组对应位置+1，若这个点删除后 $ans\left[p\right]==0ans[p]==0$ans[p]==0 ，则树状数组对应位置-1。莫队移动完成后相当于查询树状数组中 $[y_0,y_1][y\_0,y\_1]$[y0​,y1​]的和。

   时间复杂度分析：

   对于第一维x的维护，单次莫队复杂度为$O\left(\surd n\right)O(\surd n)$O(√n)

   对于第二维y的维护，单次修改的复杂度为 $O\left(logn\right)O(logn)$O(logn) ，查询的复杂度为 $O\left(logn\right)O(logn)$O(logn)

   总体时间复杂度为 $O\left(m\surd nlogn\right)O(m\; \surd nlogn)$O(m√nlogn)

   注意:

   本题数据涉及到求0的lowbit，需要特判不然会死循环

   树状数组更新的上限应该到$10^{5}10^5$105，杭电数据薄弱，所有的 $f\left[i\right]f[i]$f[i] 都 $\le n\backslash le\; n$≤n

   #include <bits/stdc++.h>
   #define int long long
   const int N=1e5+10;
   using namespace std;
   int n,m,a[N],pos[N],tree[N],shu[N],y[N];
   struct node{
       int k,x0,y0,x1,y1;
       bool operator <(const node a)const{
           if(pos[x0]==pos[a.x0]){
               if(pos[x0]&1) return x1>a.x1;
               return x1<a.x1;
           }
           return pos[x0]<pos[a.x0];
       }
   }q[N];
   int lowbit(int x){
       if(x==0) return 1;
       return x&(-x);
   }
   void update(int idx,int zhi){
       while(idx<=100000){
           tree[idx]+=zhi;
           idx+=lowbit(idx);
       }
   }
   void change(int idx,int zhi){
       if(zhi==1){
           y[idx]++;
           if(y[idx]==1) update(idx,zhi);
       }else{
           y[idx]--;
           if(y[idx]==0) update(idx,zhi);
       }
   }
   int sum(int idx){
       if(idx==-1) return 0;
       int ans=0;
       while(idx){
           ans+=tree[idx];
           idx-=lowbit(idx);
       }
       return ans;
   }
   void solve(){
       cin>>n>>m;
       int sqr = sqrt(n);
       for(int i=1;i<=n;i++){
           tree[i]=y[i]=0;
           cin>>a[i];
           pos[i]=i/sqr;
       }
       for(int i=0;i<m;i++){
           cin>>q[i].x0>>q[i].y0>>q[i].x1>>q[i].y1;
           q[i].k=i;
       }
       sort(q,q+m);
       int l0=1,l1=0;
       for(int i=0;i<m;i++){
           while(l1<q[i].x1) change(a[++l1],1);
           while(l0<q[i].x0) change(a[l0++],-1);
           while(l1>q[i].x1) change(a[l1--],-1);
           while(l0>q[i].x0) change(a[--l0],1);
           shu[q[i].k]=sum(q[i].y1)-sum(q[i].y0-1);
       }
       for(int i=0;i<m;i++){
           cout<<shu[i]<<'\n';
       }
   }
   signed main() {
       ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
       int _=1;
       cin>>_;
       while(_--){
           solve();
       }
       return 0;
   }
   

2. 莫队 + 分块（优雅的暴力）

   第一维的维护如上，第二维的维护用分块实现，维护 $num\left[i\right]num[i]$num[i] 表示第 $ii$i 个位置上的值， $sum\left[i\right]sum[i]$sum[i] 代表第 $ii$i 块内值不为0的位置个数，每次只需单点修改 $num\left[i\right]num[i]$num[i] 和 $sum\left[i/block\_size\right]sum[i/block\backslash \_size]$sum[i/block_size] ，查询时只需要查中间完整的块和两端的散块。

   时间复杂度分析：

   对于第一维x的维护，单次莫队复杂度为$O\left(\surd n\right)O(\surd n)$O(√n)

   对于第二维y的维护，单次修改的复杂度为 $O\left(1\right)O(1)$O(1) ，查询的复杂度为 $O\left(\surd n\right)O(\surd n)$O(√n)

   总体时间复杂度为 $O\left(m\surd n\right)O(m\surd n)$O(m√n)

   注意：

   分块的块大小是以 $f\left[i\right]f[i]$f[i] 的最大值 $10^{5}10^5$105 来计算的，莫队的块大小是由 $nn$n 决定的

   #include <bits/stdc++.h>
   #define int long long
   const int N=1e5+10;
   using namespace std;
   int n,m,a[N],pos[N],sum[N],num[N],shu[N],sqr,L[N],R[N],pp[N];
   struct node{
       int k,x0,y0,x1,y1;
       bool operator <(const node a)const{
           if(pos[x0]==pos[a.x0]){
               if(pos[x0]&1) return x1>a.x1;
               return x1<a.x1;
           }
           return pos[x0]<pos[a.x0];
       }
   }q[N];
   
   void add(int x){
       if(num[x]==0){
           sum[pp[x]]++;
       }
       num[x]++;
   }
   void sub(int x){
       if(num[x]==1){
           sum[pp[x]]--;
       }
       num[x]--;
   }
   int query(int l,int r){
       int p=pp[l];
       int q=pp[r];
       int ans=0;
       if(p==q){
           for(int i=l;i<=r;i++){
               if(num[i]) ans++;
           }
       }else{
           for(int i=p+1;i<q;i++) ans+=sum[i];
           for(int i=l;i<=R[p];i++){
               if(num[i]) ans++;
           }
           for(int i=L[q];i<=r;i++){
               if(num[i]) ans++;
           }
       }
       return ans;
   }
   void init(){
       int t=sqrt(100000);
       for(int i=1;i<=t;i++){
           L[i]=(i-1)*t+1;
           R[i]=i*t;
       }
       if(R[sqr]<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++){
               pp[j]=i;
           }
       }
   }
   void solve(){
       cin>>n>>m;
       sqr = sqrt(n);
       memset(num,0,sizeof(num));
       memset(sum,0,sizeof(sum));
       for(int i=1;i<=n;i++){
           cin>>a[i];
           pos[i]=i/sqr;
       }
       for(int i=0;i<m;i++){
           cin>>q[i].x0>>q[i].y0>>q[i].x1>>q[i].y1;
           q[i].k=i;
       }
       sort(q,q+m);
       int l0=1,l1=0;
       for(int i=0;i<m;i++){
           while(l1<q[i].x1) add(a[++l1]);
           while(l0<q[i].x0) sub(a[l0++]);
           while(l1>q[i].x1) sub(a[l1--]);
           while(l0>q[i].x0) add(a[--l0]);
           shu[q[i].k]=query(q[i].y0,q[i].y1);
       }
       for(int i=0;i<m;i++){
           cout<<shu[i]<<'\n';
       }
   }
   signed main() {
       init();
       ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
       int _=1;
       cin>>_;
       while(_--){
           solve();
       }
       return 0;
   }