AcWing 802. 区间和

题目连接

https://www.acwing.com/problem/content/804/

思路

用一个map用来映射我们的真实地址和逻辑地址，然后用一个map来存储真实地址的值，然后再单独开一个b数组求得是逻辑地址得前缀和，然后二分一下l和r输出即可，这里要注意边界问题

代码

#include
using namespace std;
#define ll long long
#define mod 1000000009
#define endl "\n"
#define PII pair
const int N = 2e6+10;
ll n,m,a[N];
ll b[N];
map loc,value;

int main()
{
	cin>>n>>m;
	int x,c;
	int cnt = 0;
	for(int i = 1;i >x>>c;
		if(!value[x])
			a[++cnt] = x;
		value[x] += c;
	}
	sort(a+1,a+1+cnt);
	for(int i = 1;i l>>r;
		L = lower_bound(a + 1,a + cnt + 1,l) - a;
		R = lower_bound(a + 1,a + cnt + 1,r) - a;
		if(a[R] != r) R--;
		cout