1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ls Tree[t].l
#define rs Tree[t].r
#define Ls Tree[t1].l
#define Rs Tree[t1].r
#define mid ((l+r)>>1)
using namespace std;
const int Maxn=(int)1e9;
int l,r,k,i,j,m,n,p,T,tot,ans,root[200005],a[200005],Q,sum1,sum2;
struct Node{int l,r,sum;}Tree[10000005];
void update(int ll,int l,int r,int t,int t1)
{
      if (l==r) Tree[t].sum++;
      else 
      {
          if(ll<=mid)
          {
              ls=++tot;
              Tree[ls]=Tree[Ls];
              update(ll,l,mid,ls,Ls);
          }
          else 
          {
              rs=++tot;
              Tree[rs]=Tree[Rs];
              update(ll,mid+1,r,rs,Rs);
          }
          Tree[t].sum=Tree[ls].sum+Tree[rs].sum;
      }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX