D - 1D Country(AtCoder Beginner Contest 371)
题目链接:
D - 1D Country (atcoder.jp)
题目描述:
数据范围:
输入输出:
题目分析:
典型的l, r 区间问题，即是前缀和问题，但是注意到数据范围, 数据范围1e-9 到 1e9 数据范围，要是从最小到最大直接for循环去模拟的话，时间复杂度太高了O(2e9)，注意到极限总共才2e5个居民，要去想到映射，不在关心他们的位置，而去把下标转换为从1开始的，然后在询问l, r这段区间的时候二分去查到对应的l, r他们映射后的位置，然后用前缀和公式sum[映射后的r] - sum[映射后的l - 1]就是最后的答案，但是我用map去写的时候卡到了最后一个数据，但是用数组就过掉了，why?
最后一个数据没过的代码:
#include<bits/stdc++.h>
#define int long long using namespace std;const int N = 2e5 + 10;map<int, int>mp, ren, sum;
//map<int, int>ren;
int a[N];signed main() {int n, m;cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> a[i];}for(int i = 1; i <= n; i ++ ) {int x;cin >> x;mp[a[i]] += x;}
// sort(a + 1, a + n + 1);//a[0] = 0;
// sum[a[1] - 1] = 0;sum[a[1]] = mp[a[1]];for(int i = 2; i <= n; i ++ ) {sum[a[i]] = sum[a[i - 1]] + mp[a[i]]; }
// for(int i = 1; i <= n; i ++ ) {
// cout << "a[i] = " << a[i] << " sum = " << sum[a[i]] << endl;
// }cin >> m;// 二分的是位置 while(m -- ) {int l, r;cin >> l >> r;// 二分第一个大于等于l的位置int ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] < l) ll = mid;else rr = mid;}int st = ll + 1;// cout << "st = " << st << endl;// 二分最后一个小于等于r的位置 ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] <= r)ll = mid;else rr = mid;}int en = ll;if(r > a[n]) {en = n;}if(l < a[1]) {st = 1;}
// cout << "st - 1 = " << st - 1 << endl;
// cout << "a[st - 1] = " << a[st - 1] << endl;
// cout << "en = " << en << endl;
// cout << "sumEnd = " << sum[a[en]] << endl;
// cout << "sumStart = " << sum[a[st - 1]] << endl;if(st == 1) {cout << sum[a[en]] << endl;} else {cout << sum[a[en]] - sum[a[st - 1]] << endl;}}return 0;
}
/*
7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
1
-10 -4*/
运行结果:
正确代码：
#include<bits/stdc++.h>
#define int long long using namespace std;const int N = 2e5 + 10;int a[N], sum[N];signed main() {int n, m;cin >> n;for(int i = 1; i <= n; i ++ ) {cin >> a[i];}for(int i = 1; i <= n; i ++ ) {int x;cin >> x;sum[i] = sum[i - 1] + x;}cin >> m;// 二分的是位置 while(m -- ) {int l, r;cin >> l >> r;// 二分第一个大于等于l的位置int ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] < l) ll = mid;else rr = mid;}int st = ll + 1;// cout << "st = " << st << endl;// 二分最后一个小于等于r的位置 ll = 0, rr = n + 1;while(ll + 1 < rr) {int mid = ll + rr >> 1;if(a[mid] <= r)ll = mid;else rr = mid;}int en = ll;cout << sum[en] - sum[st - 1] << endl; }return 0;
}
运行结果:
