题目大意
给出一些任务开始的时间，结束的时间，和优先级。问在第k秒时的第k大优先级，，和前k小优先级的和。
思路
CQOI太良心，所有题都是512M。 这个题只需要按照时间轴弄一个可持久化线段树就行了，每个时间点对应着一个权值线段树，维护子节点的和和个数。 注意在没有操作的时候，当前时间点的线段树要复制上一个时间点的线段树。
CODE;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));elsereturn 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\n”, last_ans = Ask(bak, x));}return 0;}
天才就是这样，终身努力，便是天才。
