气死我啦气死我啦
#include<bits/stdc++.h>
#define P system("pause")
#define E puts("")
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct node{
//在p位置加了t
int p,t;
}op[N];
int n,m;
bool cmp(node A,node B){
return A.p<B.p;
}
int findL(int x){
//在升序的op.p里找到第一个>=x的
int L=1,R=n,mid;
while(L<R){
mid=L+R>>1;
if(op[mid].p<x)
L=mid+1;
else
R=mid;
}
return L;
}
int findR(int x){
//在升序的op.p里找到最后一个<=x的
int L=1,R=n,mid;
while(L<R){
mid=L+R+1>>1;
if(op[mid].p>x)
R=mid-1;
else
L=mid;
}
return L;
}
int read(){
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-'){
f = -1;
}
c = getchar();
}
while(c >= '0' && c <= '9'){
x = x*10+c-'0';
c = getchar();
}
return x*f;
}
int main(){
//scanf("%d%d",&n,&m);
n=read();m=read();
for(int i=1;i<=n;i++)
//scanf("%d%d",&op[i].p,&op[i].t);
op[i].p=read(),op[i].t=read();
sort(op+1,op+n+1,cmp);
// for(int i=1;i<=n;i++)
// printf("!%d %d\n",op[i].p,op[i].t);
int l,r,lp,rp;
for(int i=1;i<=m;i++){
//scanf("%d%d",&l,&r);
l=read();r=read();
if(l>op[n].p || r<op[1].p){
puts("0");
continue;
}
lp=findL(l);
rp=findR(r);
int ans=0;
for(int j=lp;j<=rp;j++)
ans+=op[j].t;
//cout<<lp<<"->"<<rp<<endl;
printf("%d\n",ans);
//P;
}
return 0;
}
谔谔原来是后面要用前缀和维护一下,我这线性求和太睿智了