HDU 4866 슈팅 문제 풀이: 주석 트 리

이 문제 의 주요 구 덩이 는 바로 그 가 너 에 게 준 사격 목표 가 겹 치 는 부분 이 있다 는 것 이다. 만약 에 이런 겹 치 는 부분 에 사격 을 한다 면 두 가지 상황 을 고려 해 야 한다.
사격 목표 수량 ≥ 중합 수량: 전부 추가
사격 목표 수량 ≤ 중합 수량: 거리 만 증가 * 사격 목표 수량
그러나 이 문제 의 메모 리 는 양심 적 이 고 전체적으로 물 을 비교 해 보 자.
주요 방법 은 가로 좌표 1 ~ x 에 따라 주석 나 무 를 만 드 는 것 이다. 모든 주석 나 무 는 l, r 구간 의 설계 목표 수량 과 이런 수량 이 모두 사격 을 받 아 얻 은 점 수 를 유지 하 는 것 이다. 이런 것들 은 나 무 를 만 들 때 잘 유지 된다.
그 다음 에 이 라인 에 대한 처 리 는 스캐닝 라인 의 사상 으로 (왼쪽 점) 하나의 (+ 1) 입 점 을 구축 하고 (오른쪽 점 + 1) 의 위치 에 (- 1) 출 점 을 만 든 다음 에 왼쪽 에서 오른쪽으로 한 번 스 캔 하면 된다.
구체 적 인 과정 은 코드 참조:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#define INF 2*0x3f3f3f3f

using namespace std;

int n, m, x, p;

struct N { int ls, rs, w; long long sum; } tree[6000100];
int roots[200010];
int b[200010], tot, cnt;

int build_tree(int l, int r) {
    int newnode = tot++;
    tree[newnode].w = 0;
    tree[newnode].sum = 0;
    if (l != r) {
        int mid = (l + r) / 2;
        tree[newnode].ls = build_tree(l, mid);
        tree[newnode].rs = build_tree(mid + 1, r);
    }
    return newnode;
}

int updata(int rt, int pos, int val) {
    int newnode = tot++, tmp = newnode;
    long long add = b[pos - 1];
    tree[newnode].sum = tree[rt].sum + add * val;
    tree[newnode].w = tree[rt].w + val;
    int l = 1, r = cnt;
    while (l < r) {
        int mid = (l + r) / 2;
        if (pos <= mid) {
            tree[newnode].ls = tot++;
            tree[newnode].rs = tree[rt].rs;
            newnode = tree[newnode].ls;
            rt = tree[rt].ls;
            r = mid;
        }
        else {
            tree[newnode].ls = tree[rt].ls;
            tree[newnode].rs = tot++;
            newnode = tree[newnode].rs;
            rt = tree[rt].rs;
            l = mid + 1;
        }
        tree[newnode].sum = tree[rt].sum + add * val;
        tree[newnode].w = tree[rt].w + val;
    }
    return tmp;
}

long long query(int rt, int k) {
    //printf("rt = %d k = %d
",rt,k);
    int l = 1, r = cnt;
    long long ans = 0;
    while (l < r) {
        int mid = (l + r) / 2;
        int tmp = tree[tree[rt].ls].w;
        if (tmp >= k) {
            rt = tree[rt].ls;
            r = mid;
        }
        else {
            k -= tmp;
            ans += tree[tree[rt].ls].sum;
            rt = tree[rt].rs;
            l = mid + 1;
        }
    }
    if (tree[rt].w != 0)
        ans += tree[rt].sum / tree[rt].w * min(k, tree[rt].w);
    return ans;
}

struct P {
    int x, y, val;
    P() {}
    P(int _x, int _y, int _val) : x(_x), y(_y), val(_val) {}
    bool operator < (const P &rhs) const {
        return x < rhs.x;
    }
} pois[500010];

void print(int rt, int l = 1, int r = cnt) {
    printf("l = %d r = %d w = %d sum = %I64d
", l, r, tree[rt].w, tree[rt].sum);
    if (l != r) {
        int mid = (l + r) / 2;
        print(tree[rt].ls, l, mid);
        print(tree[rt].rs, mid + 1, r);
    }
}

int main() {
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    while (scanf("%d %d %d %d", &n, &m, &x, &p) != EOF) {
        int l1, l2, d;
        int ps = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d %d", &l1, &l2, &d);
            b[i] = d;
            pois[ps++] = P(l1, d, 1);
            pois[ps++] = P(l2 + 1, d, -1);
        }
        sort(b, b + n);
        cnt = unique(b, b + n) - b;

        sort(pois, pois + ps);

        tot = 0;
        roots[0] = build_tree(1, cnt);
        int t = 0;
        for (int i = 1; i <= x; i++) {
            roots[i] = roots[i - 1];
            while (t < ps && pois[t].x == i) {
                int tmp = (int)(lower_bound(b, b + cnt, pois[t].y) - b) + 1;
                roots[i] = updata(roots[i], tmp, pois[t].val);
                t++;
            }
        }
        /*
        for (int i = 1; i <= x; i++) {
            printf("**********************tree %d is : 
", i);
            print(roots[i]);
        }
        */

        long long now = 1;
        int xs, as, bs, cs;
        for (int i = 0; i < m; i++) {
            //printf("i = %d
", i);
            scanf("%d %d %d %d", &xs, &as, &bs, &cs);
            long long tmp = query(roots[xs], (now * as + bs) % cs);
            if (now > p) tmp *= 2;
            printf("%I64d
", tmp);
            now = tmp;
        }
}
return 0;
}