错了一个挺大的数据。
求调,谢谢!
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入格式 第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式 共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围 −109≤x≤109, 1≤n,m≤105, −109≤l≤r≤109, −10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
我的代码:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n,m;
int top=0;
int use[400010];
int ci[400010];
struct pairr{
int lw,rn;
}a[400010],c[400010];
int ef(int x){
int l=1,r=top;
while(l<r){
int mid=l+r>>1;
if(use[mid]>=x) r=mid;
else l=mid+1;
}
return r;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].lw>>a[i].rn;
use[++top]=a[i].lw;
}
for(int i=1;i<=m;i++){
cin>>c[i].lw>>c[i].rn;
use[++top]=c[i].lw;
use[++top]=c[i].rn;
}
sort(use+1,use+top+1);
unique(use+1,use+top+1);
for(int i=1;i<=top;i++){
if(use[i+1]<=use[i]){
top=i;
break;
}
}
use[top+1]=0;
for(int i=top+2;i<=400010;i++){
use[i]=use[i-1];
}
for(int i=1;i<=n;i++){
ci[ef(a[i].lw)]=a[i].rn;
}
for(int i=1;i<=top;i++) ci[i]+=ci[i-1];
for(int i=1;i<=m;i++){
cout<<ci[ef(c[i].rn)]-ci[ef(c[i].lw)-1]<<endl;
}
return 0;
}