划分树几道题目(二)

划分树hdu 4417SuperMario （求给定数在给定区间的中比它小的数的个数，或大小位置）（求逆序数）(通过修改query)（也可以二分答案！！！！！！！！！！！）

typedef long long LL;
typedef unsigned long long ULL;
typedef vector 
  
    VI;
const int INF = 1000000000;
const int maxn = 100010;
const int deep = 20;
 
#define lson l, m, dep + 1
#define rson m + 1, r, dep + 1
 
int t[deep][maxn];
int tol[deep][maxn];
int st[maxn];
int n;
void build(int l, int r, int dep)
{
   if (l == r) return;
   int m = (l + r) >> 1;
   int same = m - l + 1;
   FE(i, l, r)
       if (t[dep][i] < st[m]) same--;
   int lpos = l;
   int rpos = m + 1;
   FE(i, l, r)
    {
       if (t[dep][i] < st[m]) t[dep + 1][lpos++] = t[dep][i];
       else if (t[dep][i] == st[m] && same > 0) { t[dep + 1][lpos++]=  t[dep][i]; same--; }
       else t[dep + 1][rpos++] = t[dep][i];
       tol[dep][i] = tol[dep][l - 1] + lpos - l;
    }
   build(lson);
   build(rson);
}
 
int ans;
int h;
void query(int L, int R, int l, int r, intdep)
{
   if (L == R)
    {
       if (t[dep][L] <= h)
           ans++;
       return ;
    }
   int m = (l + r) >> 1;
   int cnt = tol[dep][R] - tol[dep][L - 1];
 
//   int ln1 = tol[dep][L - 1] - tol[dep][l - 1];
//   int rn1 = L - l - ln1;
//
//   int ln2 = cnt;
//   int rn2 = R - L - cnt + 1;
//
//   int lr = t[dep + 1][l - 1 + ln1 + ln2];
//   int rl = t[dep + 1][m + rn1 + 1];
 
   if (st[m] > h)
    {
       int newl = l + tol[dep][L - 1] - tol[dep][l - 1];
       int newr = newl + cnt - 1;
       if (newl <= newr)/// ！！！！！！！！！！！
       query(newl, newr, lson);
    }
    else
    {
       ans += cnt;
       int newr = R + tol[dep][r] - tol[dep][R];
       int newl = newr - (R - L - cnt);
       if (newl <= newr)/// ！！！！！！！！！！！
       query(newl, newr, rson);
    }
}
 
int T;
 
int main()
{
   int x, y, z;
   int T;
   int p = 1;
   RI(T);
   while (T--)
    {
       //初始化
       printf("Case %d:\n",p++);
       CLR(t, 0);
       CLR(tol, 0);
       int m;
       RII(n, m);
       FE(i, 1, n)///
       {
           RI(t[0][i]);
           st[i] = t[0][i];
       }
       sort(st + 1, st + n + 1);
       build(1, n, 0);
 
       while (m--)
       {
           RIII(x, y, z);
           h = z;
           ans = 0;
           query(++x, ++y, 1, n, 0);
           cout << ans << endl;
       }
    }
}