假定有一个无限长的数轴,数轴上每个坐标上的数都是 00。
现在,我们首先进行 nn 次操作,每次操作将某一位置 xx 上的数加 cc。
接下来,进行 mm 次询问,每个询问包含两个整数 ll 和 rr,你需要求出在区间 [l,r][l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 nn 和 mm。
接下来 nn 行,每行包含两个整数 xx 和 cc。
再接下来 mm 行,每行包含两个整数 ll 和 rr。
输出格式
共 mm 行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109−109≤x≤109,
1≤n,m≤1051≤n,m≤105,
−109≤l≤r≤109−109≤l≤r≤109,
−10000≤c≤10000−10000≤c≤10000
输入样例:
- 3 3
- 1 2
- 3 6
- 7 5
- 1 3
- 4 6
- 7 8
输出样例:
- 8
- 0
- 5
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
在求区间和的时候,我们可以直接想到用前缀和的思想去实现,我们去查找alls中的x的下标的时
候,使用二分查找法可以大大提高时间效率,可以去找一个方法去让所有数据变得单调。同时需要
给alls进行去重操作,alls中存储的一定会存在重复使用的下标
- #include
- using namespace std;
-
- typedef pair<int,int> PII;
- const int N=3e5+10;
-
- int a[N],s[N]; //a[] 是用来存放值 s[]是用来求前缀和
-
- vector<int>alls; //这个用来存储离散下标的
- vector
add,query; -
- int find(int x)//得到离散化后的坐标!
- {
- int l=0,r=alls.size()-1;
- while(l
- {
- int mid=l+r>>1;
- if(alls[mid] >= x) r=mid;
- else l=mid+1;
- }
- return r+1;//之所以要r+1 是方便之后的前缀和运算
- }
-
- int main()
- {
- int n,m;
- scanf("%d %d",&n,&m);
- int x,c;
- for(int i=1;i<=n;i++)
- {
- scanf("%d %d",&x,&c);
- alls.push_back(x);
- add.push_back({x,c});
- }
- int l,r;
- for(int i=1;i<=m;i++)
- {
- scanf("%d %d",&l,&r);
- alls.push_back(l);
- alls.push_back(r);
- query.push_back({l,r});
- }
- sort(alls.begin(),alls.end());//排序
- alls.erase(unique(alls.begin(),alls.end()),alls.end());//去重
-
- //插入操作
- for(auto item : add)
- {
- int x=find(item.first);
- a[x]+=item.second;
- }
-
- //已经插入好所有数据 可以来求前缀和
- for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
-
- for(auto item : query)
- {
- int l=find(item.first);
- int r=find(item.second);
- printf("%d\n",s[r]-s[l-1]);
- }
- }
GYX