第一种做法：

建两棵主席树分别处理两个问题。

第一个问题水，第二个问题参考

但是代码量巨大，显然不能写。

第二种做法：

参考：

对询问离线莫队，然后莫队里面套值域分块。

……值域分块还是很好写的就不讲了。

可以看出代码量巨短。

（emmm果然数据结构学傻了想的第一种做法敲了十分钟果断弃了查题解。）

（莫队还是太菜了要多练。）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int N=1e5+5;const int M=1e6+5;inline int read(){ int x=0,w=1;char ch=0; while(ch<'0'||ch>'9'){ if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*w;}struct data{ int pos,l,r,a,b;}q[M];int a[N],cnt[N],ans[M][2],v[N],num[N],s,n,m;inline int bel(int x){ return (x-1)/s+1;}inline bool cmp(data a,data b){ return bel(a.l)==bel(b.l)?a.r
           
            
             q[i].l)add(a[--ql]); while(qr
             
              q[i].r)del(a[qr--]); query(q[i].pos,q[i].a,q[i].b); } for(int i=1;i<=m;i++){ printf("%d %d\n",ans[i][0],ans[i][1]); } return 0;}
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。 　　　　　　　　　　　　　　+

+欢迎访问我的博客：

+++++++++++++++++++++++++++++++++++++++++++