题意：有n个任务，第i个的存在时间是li~ri，有个权值。求t时刻第k大的权值。
这毒瘤...本来是前缀和 -> 主席树，我是树套树...然后光荣TLE。
其实很裸。一开始我写的是每个位置维护一个权值线段树。因为要片改点查，就用差分 + 树状数组搞定了。然后超时...
仔细思考，发现不带修可以直接用主席树。
把差分数组插入进去就行了，查询就是前缀和。这么一看好像主席树就是同时对多个数组做前缀和，每个数组就是线段树的一个位置。
我没用标记永久化，标记下传的时候直接新建的节点。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 100010, lm = 1e7, M = 20000010; 7 8 int n, m, tot, rt[N]; 9 int sum[M], ls[M], rs[M];10 LL Val[M];11 std::vector d[N];12 13 void insert(int x, int &y, int p, int v, int l, int r) {14 if(!y || x == y) {15 y = ++tot;16 sum[y] = sum[x];17 Val[y] = Val[x];18 }19 if(l == r) {20 sum[y] += v;21 Val[y] += v * r;22 return;23 }24 if(!ls[y]) {25 ls[y] = ls[x];26 }27 if(!rs[y]) {28 rs[y] = rs[x];29 }30 int mid = (l + r) >> 1;31 if(p <= mid) {32 insert(ls[x], ls[y], p, v, l, mid);33 }34 else {35 insert(rs[x], rs[y], p, v, mid + 1, r);36 }37 sum[y] = sum[ls[y]] + sum[rs[y]];38 Val[y] = Val[ls[y]] + Val[rs[y]];39 return;40 }41 42 LL ask(int k, int l, int r, int o) {43 if(!o) {44 return 0;45 }46 if(l == r) {47 return 1ll * std::min(k, sum[o]) * r;48 }49 int mid = (l + r) >> 1;50 if(k <= sum[ls[o]]) {51 return ask(k, l, mid, ls[o]);52 }53 else {54 return Val[ls[o]] + ask(k - sum[ls[o]], mid + 1, r, rs[o]);55 }56 }57 58 int main() {59 scanf("%d%d", &n, &m);60 for(int i = 1, x, y, z; i <= n; i++) {61 scanf("%d%d%d", &x, &y, &z);62 d[x].push_back(z);63 d[y + 1].push_back(-z);64 }65 66 // prework67 for(int i = 1; i <= m; i++) {68 if(!d[i].size()) {69 rt[i] = rt[i - 1];70 continue;71 }72 for(int j = 0; j < d[i].size(); j++) {73 // d[i][j]74 if(d[i][j] > 0) {75 insert(rt[i - 1], rt[i], d[i][j], 1, 1, lm);76 }77 else {78 insert(rt[i - 1], rt[i], -d[i][j], -1, 1, lm);79 }80 }81 }82 83 LL lastans = 1;84 for(int i = 1, t, y, z, w; i <= m; i++) {85 scanf("%d%d%d%d", &t, &y, &z, &w);86 lastans %= w;87 y %= w;88 int k = (lastans * y + z) % w + 1;89 lastans = ask(k, 1, lm, rt[t]);90 printf("%lld\n", lastans);91 }92 93 return 0;94 }