题意：
在二维平面的第一象限有(n(1 leq n leq 10^5))条平行于(x)轴的线段，接下来有(m)次射击(x \, a \, b \, c)。
每次射击会获得一定的分数，假设上一轮的分数为(pre)，那么这次射击就会在位置(x)处射击最近的(K=(a cdot pre + b) % c)个靶子。
每射中一个靶子就会获得靶子到(x)轴距离的分数，如果上一轮分数(pre > P)，那么本轮分数再乘(2)。
输出每次射击所得的分数。
分析：
首先从左到右扫描线段：
- 遇到线段的左端点，在这个线的位置射穿过去的话，靶的个数增加(1)，而且也会比原来多得到对应的分数
- 遇到线段的右端点，在这个线的位置射穿过去的话，靶的个数减少(1)，而且也会比原来少得到对应的分数
所以(n)条线段就有(2n)个事件，从左往右扫描，维护(2n)棵线段树，对应前(i)个事件发生后对应的靶子的个数以及到(x)轴距离之和。
然后每次计算出(K)，接下来就是求树中前(K)小个数字之和，这是主席树的拿手本领。
在(x)处射击，要找到对应的那棵线段树，具体来说就是：
位置小于(x)的事件已经发生了，位置等于(x)的左端点事件也发生了，其他的事件都还没发生。
对于位置相同的事件，我们可以把左端点事件排序在右端点事件前面，这样就可以二分查找到对应的线段树。
最后在这棵线段树里查询答案。
(Tips)：在计算(K)的过程注意取余，否则可能会溢出。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn = 100000 + 10;
const int INF = 0x3f3f3f3f;
const int maxnode = maxn << 5;
struct Event
{
int pos, sum, type;
bool operator < (const Event& t) const {
return pos < t.pos || (pos == t.pos && type < t.type);
}
};
struct Segment
{
int l, r, d;
};
Event events[maxn * 2];
Segment a[maxn];
int y[maxn], tot;
int n, m, X;
LL P;
int sz;
int cnt[maxnode], lch[maxnode], rch[maxnode];
LL sum[maxnode];
int root[maxn * 2];
int update(int pre, int L, int R, int pos, LL val, int type) {
int rt = ++sz;
lch[rt] = lch[pre];
rch[rt] = rch[pre];
cnt[rt] = cnt[pre] + type;
sum[rt] = sum[pre] + val;
if(L < R) {
int M = (L + R) / 2;
if(pos <= M) lch[rt] = update(lch[pre], L, M, pos, val, type);
else rch[rt] = update(rch[pre], M+1, R, pos, val, type);
}
return rt;
}
LL query(int rt, int L, int R, int k) {
if(L == R) {
if(cnt[rt] > k) return sum[rt] / cnt[rt] * k;
else return sum[rt];
}
int M = (L + R) / 2;
int num = cnt[lch[rt]];
if(num >= k) return query(lch[rt], L, M, k);
else return sum[lch[rt]] + query(rch[rt], M+1, R, k - num);
}
int main()
{
while(scanf("%d%d%d%lld", &n, &m, &X, &P) == 4) {
for(int i = 0; i < n; i++) {
scanf("%d%d%d", &a[i].l, &a[i].r, &a[i].d);
events[i * 2] = (Event){ a[i].l, a[i].d, 1 };
events[i*2+1] = (Event){ a[i].r + 1, a[i].d, -1 };
y[i] = a[i].d;
}
sort(events, events + n * 2);
sort(y, y + n);
tot = unique(y, y + n) - y;
sz = 0;
for(int i = 0; i < n * 2; i++) {
Event& e = events[i];
int pos = lower_bound(y, y + tot, e.sum) - y + 1;
root[i + 1] = update(root[i], 1, tot, pos, e.sum * e.type, e.type);
}
LL pre = 1;
while(m--) {
int x; LL a, b, c;
scanf("%d%lld%lld%lld", &x, &a, &b, &c);
int K = (a * pre + b) % c;
if(!K) { printf("0
"); pre = 0; continue; }
Event t;
t = (Event){ x, 0, 2 };
int rt = lower_bound(events, events + n * 2, t) - events;
LL ans;
if(K >= cnt[root[rt]]) ans = sum[root[rt]];
else ans = query(root[rt], 1, tot, K);
if(pre > P) ans <<= 1;
pre = ans;
printf("%lld
", ans);
}
}
return 0;
}