这个题网上大多数是使用莫队+树状数组的办法写的，实际上有着更优秀的算法：线段树分治+树状数组

这个题是我在集训队论文上看到的，发现这个思想十分优秀，但是我貌似并不能很好的实现它。

这个做法的思路大概是：首先建一棵权值线段树，对于线段树的每个区间存权值范围在区间内的所有数，再将所有的操作都存入线段树中（分开存），因为权值线段树内的每个区间都限制了权值的范围，然后就可以对于线段树的每个区间去查询位置在\([l,r]\)之间的数有多少，第一问可以随便搞，对于第二问一个简洁的方法就是记下每种权值最后出现的位置，保证它只出现一遍就行了，修改查询用树状数组就可以优秀的解决。

时间复杂度我不会证，论文上写的是\(O((n+Q)log^2n)\)（Q为询问数，n为数的个数）

细节可以看代码(代码实现参考了yww大佬的博客)：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;void read(int &x) {    char ch; bool ok;    for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;    for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;}#define max(a,b) (a>b?a:b)#define rg registerint n,m,num,las[100001],z[100001],ans[1000010],ans1[1000010];struct oo{int l,r;}s[400001];struct o{int l,r,a,b,id;}f[100001];vector
        
         q[300001];vector
         
          g[300001];struct tree{ int w[100001]; #define lowbit(i) (i&(-i)) void add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))w[i]+=v;} int get(int x){int ans=0;for(int i=x;i;i-=lowbit(i))ans+=w[i];return ans;}}e1,e2;void build(int x,int l,int r){ s[x].l=l,s[x].r=r; if(l==r){num=max(num,x);return ;} int mid=(l+r)>>1; build(x<<1,l,mid),build(x<<1|1,mid+1,r);}void change(int x,oo y){ q[x].push_back(y); if(s[x].l==s[x].r)return ; int mid=(s[x].l+s[x].r)>>1; if(y.r<=mid)change(x<<1,y); else change(x<<1|1,y); }void add(int x,o y){ if(y.a<=s[x].l&&y.b>=s[x].r) { g[x].push_back(y); return ; } int mid=(s[x].l+s[x].r)>>1; if(y.a<=mid)add(x<<1,y); if(y.b>mid)add(x<<1|1,y);}bool cmp(o a,o b){return a.r