初见安~这里是传送门：洛谷P3168 [CQOI2015]任务查询系统
题意显然是告诉你每个有优先级事件有覆盖的时间段，每次问你某个时间点的优先级前k小的事件的优先级的和。
一个是时间轴，一个是优先级，同样是二维限制，我们可以想到可持久化权值线段树，也就是在时间轴上建权值线段树。
关于这一点的处理比较多【大概吧】。
首先是优先级的值要离散化一下，1e7线段树会炸掉。
其次是对每个事件的时间处理。因为很容易想到用差分序列，即对每个事件处理开始的节点和结束的节点即可，所以如果是对每个时间都开一个root的话会有同一时间多点修改的情况【好像没啥问题】。我太菜了就写的每个有修改的事件才去修改主席树，导致如果查询的x没有单独的事件的话需要二分去找一个最近的不超过现在的时间节点来查询。而二分又会出现一个细节就是如果当前x比最早的一个修改操作的时间还要早。所以二分下标的时候下界要放到0去。【这就是自作孽不可活吗。】
再者是权值线段树上的事。显然我们会用主席树求第k小，求前k小的时候维护一下数的个数和总和就好，但是如果第k个数的值有多个，我们直接返回总和就会多算。所以要记得处理一下【见代码ask 函数 l==r时的处理】。
题目本身不难，第2个和第8个测试点卡了我好久……数据真的是太好了，无死角卡细节：）
上代码——
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<cmath> #include<queue> #include<map> #define maxn 200005 using namespace std; typedef long long ll; const int lim = 2e5; int read() { int x = 0, f = 1, ch = getchar(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();} while(isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * f; } int n, m; map<int, int> mp; int root[maxn], tot = 0; struct SegmentTree { int l, r, cnt; ll val; }t[maxn << 5]; int srt[maxn], sum = 0, ed[maxn]; int add(int rt, int l, int r, int x, int op) { register int p = ++tot; t[p] = t[rt]; t[p].val += 1ll * op * srt[x], t[p].cnt += op;//记得累和的时候x要映射回原值 if(l == r) return p; register int mid = l + r >> 1; if(x <= mid) t[p].l = add(t[rt].l, l, mid, x, op); else t[p].r = add(t[rt].r, mid + 1, r, x, op); return p; } ll ask(int p, int l, int r, int k) { if(l == r) return min(t[p].val, 1ll * srt[l] * k);//这里这里 register int mid = l + r >> 1, ans = t[t[p].l].cnt;//找第k小常规操作 if(k <= ans) return ask(t[p].l, l, mid, k); else return t[t[p].l].val + ask(t[p].r, mid + 1, r, k - ans); } struct node { int t, p, op; bool operator < (const node &x) const {return t < x.t;} }tsk[maxn]; int find(int x) { register int l = 0, r = sum, mid, res;//注意l…… while(l <= r) { mid = l + r >> 1; if(tsk[mid].t <= x) res = mid, l = mid + 1; else r = mid - 1; } return res; } signed main() { n = read(), m = read(); for(int i = 1, s, t, p; i <= n; i++) s = read(), t = read(), p = read(), tsk[++sum] = {s, p, 1}, tsk[++sum] = {t + 1, p, -1}, srt[i] = p; //tsk是任务，srt是用来离散化的 sort(tsk + 1, tsk + 1 + sum); sort(srt + 1, srt + 1 + n); for(int i = 1; i <= n; i++) mp[srt[i]] = i; for(int i = 1; i <= sum; i++) {//按时间顺序插入 tsk[i].p = mp[tsk[i].p]; root[i] = add(root[i - 1], 1, lim, tsk[i].p, tsk[i].op); } ll ans = 1; for(int i = 1; i <= m; i++) { register int k, x = read(), a = read(), b = read(), c = read(); k = 1 + (a * ans + b) % c; x = find(x), ans = ask(root[x], 1, lim, k);//二分找到等效的x printf("%lld\n", ans); } return 0; }卡了大半天。绝了。
迎评：） ——End——
