BZOJ 3932 CQOI 2015 퀘 스 트 조회 시스템 지속 가능 라인 트 리

제목 의 대의
미 션 시작 시간, 끝 날 시간, 우선 순 위 를 드 립 니 다.k 초 에 있 는 k 대 우선 순위 와 앞 k 작은 우선 순위 의 합 을 물 어보 세 요.
사고의 방향
CQOI 는 너무 양심 적 이어서 모든 문제 가 512 M 이다.이 문 제 는 시간 축 에 따라 지속 가능 한 선분 트 리 를 만 들 면 됩 니 다. 시간 마다 하나의 가중치 선분 트 리 에 대응 하여 하위 노드 의 합 과 개 수 를 유지 합 니 다.작업 이 없 을 때 현재 시간 대의 선분 트 리 는 이전 시간 대의 선분 트 리 를 복사 해 야 합 니 다.
CODE

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 
#define MAX 100010
#define MAXR 10000010
#define RANGE 10000000
using namespace std;

struct SegTree{
    int size, sum;
    SegTree *son[2];
}mempool[MAXR], *C = mempool, *root[MAX];

SegTree *NewSegTree(SegTree *_, SegTree *__, int _size, int _sum)
{
    C->son[0] = _;
    C->son[1] = __;
    C->size = _size;
    C->sum = _sum;
    return C++;
}

inline SegTree *Insert(SegTree *consult, int l, int r, int c, bool flag)
{
    if(l == r)
        return NewSegTree(consult->son[0], consult->son[1], consult->size + (flag ? 1:-1), consult->sum + c * (flag ? 1:-1));
    int mid = (l + r) >> 1;
    if(c <= mid)
        return NewSegTree(Insert(consult->son[0], l, mid, c, flag), consult->son[1], consult->size + (flag ? 1 : -1), consult->sum + c * (flag ? 1 : -1));
    else
        return NewSegTree(consult->son[0], Insert(consult->son[1], mid + 1, r, c, flag), consult->size + (flag ? 1 : -1), consult->sum + c * (flag ? 1 : -1));
}   

pair<int, int> Ask(SegTree *now, int l, int r, int x)
{
    if(l == r)  return make_pair(l, x);
    int mid = (l + r) >> 1;
    if(x <= now->son[0]->size)
        return Ask(now->son[0], l, mid, x);
    return Ask(now->son[1], mid + 1, r, x - now->son[0]->size);
}

int GetSum(SegTree *now, int l, int r, int x, int y)
{
    if(l == x && y == r)
        return now->sum;
    int mid = (l + r) >> 1;
    if(y <= mid)    return GetSum(now->son[0], l, mid, x, y);
    if(x > mid)     return GetSum(now->son[1], mid + 1, r, x, y);
    int left = GetSum(now->son[0], l, mid, x, mid);
    int right = GetSum(now->son[1], mid + 1, r, mid + 1, y);
    return left + right;
}

inline int Ask(int pos, int x)
{
    if(x >= root[pos]->size)
        return root[pos]->sum;
    pair<int, int> ans = Ask(root[pos], 1, RANGE, x);
    if(ans.first - 1 <= 0)  return ans.first * ans.second;
    return GetSum(root[pos], 1, RANGE, 1, ans.first - 1) + ans.first * ans.second;
}

int total, asks;

struct Complex{
    int pos, val;
    bool flag;

    Complex(int _, int __, bool ___):pos(_), val(__), flag(___) {}
    Complex() {}

    bool operator const Complex &a)const {
        return pos < a.pos;
    }
}stack[MAX];
int top;

int main()
{
    root[0] = NewSegTree(C, C, 0, 0);
    for(int i = 1; i < MAX; ++i)
        root[i] = root[0];
    cin >> total >> asks;
    for(int x ,y ,z, i = 1; i <= total; ++i) {
        scanf("%d%d%d", &x, &y, &z);
        stack[++top] = Complex(x, z, true);
        stack[++top] = Complex(y + 1, z, false);
    }
    sort(stack + 1, stack + top + 1);
    int last = 0;
    for(int i = 1; i <= top; ++i) {
        root[stack[i].pos] = Insert(root[last], 1, RANGE, stack[i].val, stack[i].flag);
        last = stack[i].pos;
    }
    int last_ans = 1;
    for(int x, a, b, c, i = 1; i <= asks; ++i) {
        scanf("%d%d%d%d", &x, &a, &b, &c);
        int bak = x;
        x = 1 + (a * last_ans + b) % c;
        printf("%d
", last_ans = Ask(bak, x));
    }
    return 0;
}