DAY5共2题：
- 储物点的间隔（前缀和）
- 糖糖别胡说，我真的不是签到题目（multiset，思维）
作者：Eriktse
简介：19岁，211计算机在读，现役ACM银牌选手力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）
原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1096.html
储物点的间隔
题目链接：https://ac.nowcoder.com/acm/problem/14683
预处理出各点搬运到点1和点n的代价前缀和，以及区间分量和。
如果咱们要将区间[5, 7]的物品全副搬运到3，代价应该是区间[5, 7]的物品全副搬运到的1，而后减去多搬的代价：[5, 7]的分量和 * dist(1, 3)。
下面是x < l的状况，x > r的状况相似。
当l <= x <= r只需将区间[l, r]分为两局部求和即可。
记得取模，间隔要取模，前缀和也要取模。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 2e5 + 9, p = 1e9 + 7;//sum_l[i]示意区间[1, i]的物品都运到点1的代价之和//prefix_a[i]示意区间[1, i]的物品分量之和//pos[i]是第i个点的地位，通过a[]作前缀和失去int a[maxn], pos[maxn], sum_l[maxn], sum_r[maxn], prefix_a[maxn];int n, m;//取模函数int mo(int x){return (x % p + p) % p;}int f(int x, int l, int r){ if(l > r)return 0; int res = 0; if(x <= l) { res = mo(sum_l[r] - sum_l[l - 1]); res = mo(res - mo(pos[x] - pos[1]) * mo(prefix_a[r] - prefix_a[l - 1]) % p); } else if(x >= r) { res = mo(sum_r[r] - sum_r[l - 1]); res = mo(res - mo(pos[n] - pos[x]) * mo(prefix_a[r] - prefix_a[l - 1]) % p); } return res;}signed main(){ scanf("%lld %lld",&n, &m); pos[1] = 1; for(int i = 2, d;i <= n; ++ i)scanf("%lld", &d), pos[i] = pos[i - 1] + d; for(int i = 1;i <= n; ++ i)scanf("%lld", a + i); for(int i = 1;i <= n; ++ i) { sum_l[i] = mo(sum_l[i - 1] + a[i] * mo(pos[i] - pos[1]) % p); sum_r[i] = mo(sum_r[i - 1] + a[i] * mo(pos[n] - pos[i]) % p); } for(int i = 1;i <= n; ++ i)prefix_a[i] = mo(prefix_a[i - 1] + a[i]); while(m --) { int x, l, r;scanf("%lld %lld %lld", &x, &l, &r); int ans = 0; if(l <= x and x <= r)ans = mo(f(x, l, x - 1) + f(x, x + 1, r)); else ans = f(x, l, r); printf("%lld\n", ans); } return 0;}糖糖别胡说，我真的不是签到题目
题目链接：https://ac.nowcoder.com/acm/problem/14583
本题有两种解法，第一种容易了解，第二种效率更优。
第一种解法：正向，multiset。
发功次数能够用一个桶来记录，让[1, i]的所有点的属性值都+1，相当于把前面的都-1，用一个fix示意偏移量。
建设两个multiset示意两组中的糖糖，益处是能够疾速找出能力值最小的，从而去除掉。
扫一遍，把第i只糖糖退出到属于它的汇合中，而后将另外一个汇合中已有的能力值小的糖糖进行删除，再查看此时是否有发功。
最初汇合中留下的糖糖个数即为答案。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e6 + 9, inf = 8e18;struct Node{ int a, b;}p[maxn];int add[maxn];void solve(){ int n, m;scanf("%lld %lld",&n, &m); memset(add, 0, sizeof(int) * (n + 2)); for(int i = 1;i <= n; ++ i) scanf("%lld %lld", &p[i].a, &p[i].b); //留神同一时间可能施法屡次 for(int i = 1, x;i <= m; ++ i)scanf("%lld", &x), add[x] ++; int fix = 0, cnt = 0; multiset<int> st[2]; for(int i = 1;i <= n; ++ i) { int a = p[i].a, b = p[i].b - fix; st[a].insert(b); while(!st[a ^ 1].empty() and *st[a ^ 1].begin() < b) st[a ^ 1].erase(st[a ^ 1].begin()), cnt ++; fix += add[i]; } printf("%lld\n", n - cnt);}signed main(){ int _;scanf("%lld", &_); while(_ --)solve(); return 0;}第二种解法：反向，思维。
咱们想这么一个问题，一个糖糖x是否会被删除取决于在x呈现之后，在另外一个汇合中，是否呈现了能力值高于x的能力值的糖糖y。
那么咱们逆向遍历，保护两个汇合的最值，以后的新退出的糖糖x的能力值如果低于另外一个汇合中曾经存在的（即左边的）糖糖能力值的最大值，阐明他前面会被某个糖糖y删除掉，间接打上标记，然而咱们不必真的删除。
糖糖x还能够用于删除右边的另一个汇合的能力值较小的糖糖。留神此时的发功应该在循环开始时进行批改。
#include <bits/stdc++.h>#define int long longusing namespace std;const int maxn = 1e6 + 9, inf = 8e18;struct Node{ int a, b;}p[maxn];int add[maxn];void solve(){ int n, m;scanf("%lld %lld",&n, &m); memset(add, 0, sizeof(int) * (n + 2)); for(int i = 1;i <= n; ++ i) scanf("%lld %lld", &p[i].a, &p[i].b); //留神同一时间可能施法屡次 for(int i = 1, x;i <= m; ++ i)scanf("%lld", &x), add[x] ++; int fix = 0, cnt = 0; int mx[2] = {-inf, -inf}; for(int i = n;i >= 1; -- i) { fix += add[i]; int a = p[i].a, b = p[i].b + fix; mx[a] = max(mx[a], b); if(mx[a ^ 1] > b)cnt ++; } printf("%lld\n", n - cnt);}signed main(){ int _;scanf("%lld", &_); while(_ --)solve(); return 0;}本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞、珍藏⭐、留言