rt
和正解拍了几万组没拍出错,但只有十分,都是前几行错的
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int n,m;
int c[10000005],ans[500005];
bool v[500005];
void add(int x,int y){
for(;x<=1e7;x+=x&-x)c[x]+=y;
}
int ask(int x){
int ans=0;
for(;x;x-=x&-x)ans+=c[x];
return ans;
}
struct node{
int op,x,y,a,b;
}q[1500005];
bool cmp(node x,node y){
return x.x<y.x;
}
signed main(){
freopen("data.in","r",stdin);
freopen("s.out","w",stdout);
n=read();m=read();
int tot=0;
for(int i=1;i<=n;i++){
q[++tot].op=0;q[tot].x=read(),q[tot].y=read();
q[tot].x++;q[tot].y++;
}
for(int i=1;i<=m;i++){
q[++tot].op=i;q[tot].x=read();q[tot].y=read();q[tot].a=read();q[tot].b=read();
q[tot].a++;q[tot].y++;q[tot].b++;
q[++tot].op=i;q[tot].x=q[tot-1].a;q[tot].y=q[tot-1].b;q[tot].a=q[tot-1].x,q[tot].b=q[tot-1].y;
}
sort(q+1,q+tot+1,cmp);
for(int i=1;i<=tot;i++){
if(!q[i].op)add(q[i].y,1);
else{
if(!v[q[i].op]){
v[q[i].op]=1;
ans[q[i].op]+=ask(q[i].b)-ask(q[i].y-1);
}
else{
ans[q[i].op]=ask(q[i].y)-ans[q[i].op]-ask(q[i].b-1);
}
}
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}