AcWing 802. 区间和 （离散化）

张开发
• 2026/4/23 6:06:18 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

AcWing 802. 区间和 （离散化）
#include bits/stdc.h using namespace std; typedef pairint, int PII; const int N 300010; int a[N], al; int b[N], s[N]; // 假定有一个无限长的数轴数轴上每个坐标上的数都是 0 PII q[N], p[N]; int ql, pl; int n, m; // 手写二分 int lower_bound(int q[], int l, int r, int x) { while (l r) { int mid (l r) 1; if (q[mid] x) r mid; else l mid 1; } return l; } int main() { cin n m; while (n--) { int x, c; cin x c; p[pl] {x, c}; a[al] x; } int l, r; while (m--) { cin l r; q[ql] {l, r}; a[al] l, a[al] r; } // ① 排序去重 sort(a, a al); // ② 使用STL的去重函数去重不用手写的去重原因只排序一次去重一次不像是二分需要重复使用性能差别不大但代码就短的多 al unique(a, a al) - a; // 处理一下某个x上加c的事情 for (int i 0; i pl; i) { int x lower_bound(a, 0, al, p[i].first) 1; // 下标从0开始需要加1个偏移量 b[x] p[i].second; } // 一维前缀和 for (int i 1; i N; i) s[i] s[i - 1] b[i]; // 处理询问(前缀和应用) for (int i 0; i ql; i) { // 根据原来的位置值计算出映射后的位置值 l lower_bound(a, 0, al, q[i].first) 1; r lower_bound(a, 0, al, q[i].second) 1; // 利用一维前缀和计算区间和 printf(%d\n, s[r] - s[l - 1]); } return 0; }

更多文章