HDu 4417 Super Mario(ツリー配列)

構想:n個数を構造体配列で保存し、値と順序idを記録する

struct node{
    int num,id;
}a[MAX_];

m個のクエリを構造体配列で保存し,左右(L,R)およびHおよび順序idを記録する.

struct point {
    int L,R,id,value;
}b[MAX_];

はnum値で小さいから大きいまで並べ替えられ、value値で小さいから大きいまで並べ替えられる.
次に、シーケンスの最初のクエリとシーケンスのnum値の最初の値から、最初のクエリのvalueのnumより小さい場合は、そのidをすべてツリー配列に入れ、そのvalue値より大きい場合に

for(int q = 0, k = 0; q < m; ++q){
     while(k < n && b[q].value >= a[k].num){
        add(a[k].id,1);
        k++;
     }
     ans[b[q].id] = sum(b[q].R) - sum(b[q].L-1);
}

このとき,ツリー配列の和関数を用いてそのvalueに対応する(L,R)からそのクエリのanswerを求めることができる.次に2番目のクエリーを続けます.その後のvalueはますます大きくなるので、以前は要求に合っていました.numはずっと後ろに数えていればいいです.
原理は離散化であり,idに対して木状配列を行い,後続の値に影響を及ぼさない正確性を保証し,時間の複雑さを保証し,巧みである.
コード:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 100010;
const int INF = 0x7fffffff;
const int MAX = 100010;

struct point {
    int L,R,id,value;
} b[MAX_];

struct node {
    int num,id;
} a[MAX_];


int C[MAX_], ans[MAX_];
int T, n, m,l ,r;


int lowbit(int x) {
    return x&(-x);
}

void add(int x,int num) {
    while(x < MAX) {
        C[x] += num;
        x += lowbit(x);
    }
}

int sum(int x) {
    int cnt = 0;
    while(x > 0) {
        cnt += C[x];
        x -= lowbit(x);
    }
    return cnt;
}

bool cmp1(const point &a, const point &b) {
    return a.value < b.value;
}

bool cmp2(const node &a,const node& b) {
    return a.num < b.num;
}

int main() {
    int Case = 0;
    scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; ++i) {
            scanf("%d",&a[i].num);
            a[i].id = i+1;
        }
        for(int i = 0; i < m; ++i) {
            scanf("%d%d%d",&l,&r,&b[i].value);
            b[i].L = l + 1;
            b[i].R = r + 1;
            b[i].id = i ;
        }
        sort(a,a+n,cmp2);
        sort(b,b+m,cmp1);
        mst(C,0);
        mst(ans,0);

        for(int q = 0, k = 0; q < m; ++q) {
            while(k < n && b[q].value >= a[k].num) {
                add(a[k].id,1);
                k++;
            }
            ans[b[q].id] = sum(b[q].R) - sum(b[q].L-1);
        }
        printf("Case %d:
",++Case);
        for(int i = 0; i < m; ++i) {
            printf("%d
",ans[i]);
        }

    }
    return 0;
}