题意：
在二维平面的第一象限有\(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#include #include 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\n"); 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\n", ans); } } return 0;}