HDU 4417(主席の木の模版の題、区間の値を求めてkの個数に等しいことより小さいです)

タイトルリンク：ゴマ開門

題意:1つの配列が与えられ、質問区間[L,R]毎に値<=hの個数が与えられる.
考え方:最初はずっとwaで、自分のqueryが非再帰的であるため、L==Rに特判が必要な場合を考慮しました.
buildおよびupdateは静的議長ツリーと変わらない.クエリーの場合、X[mid]<=h、ans+=左サブツリーのすべての値をクエリーし、右サブツリーをクエリーしないと左サブツリーのクエリーを続行します.最後にL==Rの場合を特審します.
 
ACコード:

#include
#define debug(x) cout << "[" << #x <
#define clr(a,b) memset((a),b,sizeof(a))
#define rep(i,a,b) for(int i = a;i < b;i ++)
#define pb push_back
#define MP make_pair
#define LL long long
#define ull unsigned LL
#define ls i << 1
#define rs i << 1 + 1
#define INT(t) int t; scanf("%d",&t)

using namespace std;

const int maxn = 1e5 + 10;
const int M = maxn * 40;
int K[maxn],X[maxn],T[maxn];
int C[M],lson[M],rson[M];
int tot,en;

int build(int l,int r){
    int rt = tot ++;
    C[rt] = 0;
    if(l != r){
        int mid = (l + r) >> 1;
        lson[rt] = build(l,mid);
        rson[rt] = build(mid + 1,r);
    }
    return rt;
}

int getId(int x){
    return lower_bound(X + 1,X + 1 + en,x) - X;
}

int udt(int rt,int pos,int val){
    int newrt = tot ++, tmp = newrt;
    C[newrt] = C[rt] + val;
    int l = 1,r = en;
    while(l < r){
        int mid = (l + r) >> 1;
        if(pos <= mid){
            lson[newrt] = tot ++;
            rson[newrt] = rson[rt];
            newrt = lson[newrt];
            rt = lson[rt];
            r = mid;
        }
        else {
            rson[newrt] = tot ++;
            lson[newrt] = lson[rt];
            newrt = rson[newrt];
            rt = rson[rt];
            l = mid + 1;
        }
        C[newrt] = C[rt] + val;
    }
    return tmp;
}

int query(int ql,int qr,int k){
    int lrt = T[ql - 1];
    int rrt = T[qr];
    int l = 1,r = en,ans = 0;
    while(l < r){
        int mid = (l + r) >> 1;
        if(X[mid] <= k){
            ans += C[lson[rrt]] - C[lson[lrt]];
            lrt = rson[lrt];
            rrt = rson[rrt];
            l = mid + 1;
        }
        else {  /// X[mid] > k
            lrt = lson[lrt];
            rrt = lson[rrt];
            r = mid;
        }
    }
    /// if(l == r)  wa 
    if(l == r){
        if(X[l] <= k)
            ans += C[rrt] - C[lrt];
    }
    return ans;
}

int main() {
    int t; scanf("%d",&t);
    int cas = 0;
    while(t --){
        tot = 0;
        int n,m; scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;++ i){
            scanf("%d",&K[i]);
            X[i] = K[i];
        }
        sort(X + 1,X + 1 + n);
        en = unique(X + 1,X + 1 + n) - X - 1;
        T[0] = build(1,en);
        for(int i = 1;i <= n;++ i)
            T[i] = udt(T[i - 1],getId(K[i]),1);
        printf("Case %d:
",++ cas);
        while(m --){
            int l,r,k; scanf("%d%d%d",&l,&r,&k);
            printf("%d
",query(l + 1,r + 1,k));
        }
    }
    return 0;
}