[atcoder abc 371d]1D Country

题目描述

建议在 洛谷 查看。

---

求 $l$ 到 $r$ 区间的和，我们可以使用前缀和或二分等算法解决。

由于坐标 $x$ 在 $-10^9\sim 10^9$ 之间，所以不能直接使用前缀和。

考虑使用二分，先将坐标从小到大排序。

计算从 $l$ 到 $r$ 的区间，可以二分出 $a$ 中比 $l$ 大的值 $x$ 和比 $r$ 小的值 $y$。

用前缀和计算 $a$ 的前缀和，输出即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
struct node{int x, y;
}a[200010];
int b[200010];
//前缀和
long long sum[200010];
//排序
bool cmp(node p, node q){return p.x < q.x;
}
signed main(){scanf("%lld", &n);for(int i = 1; i <= n; ++ i){scanf("%lld", &a[i].x);}for(int i = 1; i <= n; ++ i){scanf("%lld", &a[i].y);}sort(a + 1, a + n + 1, cmp);for(int i = 1; i <= n; ++ i){b[i] = a[i].x;sum[i] = sum[i - 1] + a[i].y;}scanf("%lld", &m);while(m --){int x, y;输入 x, yif(y >= b[n]){y = b[n];}else if(y <= b[1]){x = b[1] - 1;}//二分int t1 = lower_bound(b + 1, b + n + 1, x) - b;int t2 = upper_bound(b + 1, b + n + 1, y) - b;t2 = min(t2, n);while(y < b[t2] && t2){-- t2;}while(x > b[t1] && t1 <= n){++ t1;}输出 sum[t2] - sum[t1 - 1]}return 0;
}

禁止抄袭!!!