n、q<5000和5-11的特殊性质部分分都能拿到,我怀疑是算重复了,求问大佬是哪里有问题呢
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MXSZ=(1<<22)+8,WEI=24;
struct ILAND{
int id,a,b;
}ild[100002];
struct QRY{
int id,l,r,c,d,v;
}Q[200002];
int N,M,tr[2][MXSZ][2],idx[2],cnt[2][MXSZ],idst[200002],tmp[200002],calc;
vector<int> vec[MXSZ];
void add01(int id,int x,int wei,int p,int val)
{
// if(wei==WEI) cout<<" add"<<id<<" "<<x<<endl;
if(id==0) cnt[id][p]+=val;
if(wei==-1)
{
if(id) if(val>0) vec[p].push_back(val);
return ;
}
if(id==1)
{
if(tr[id][p][0]) cnt[id][tr[id][p][0]]+=cnt[id][p];
if(tr[id][p][1]) cnt[id][tr[id][p][1]]+=cnt[id][p];
cnt[id][p]=0;
}
if(tr[id][p][(x>>wei)&1]==0) tr[id][p][(x>>wei)&1]=++idx[id];
add01(id,x,wei-1,tr[id][p][(x>>wei)&1],val);
}
int qry0(int x,int wei,int p,int goal)
{
// if(wei==WEI) cout<<" qry0 "<<x<<" "<<goal;//<<endl;
if(wei==-1) return cnt[0][p];
int sum=0;
if((goal>>wei)&1)
{
if(tr[0][p][(x>>wei)&1]) sum+=cnt[0][tr[0][p][(x>>wei)&1]];
if(tr[0][p][!((x>>wei)&1)]) sum+=qry0(x,wei-1,tr[0][p][!((x>>wei)&1)],goal);
}
else if(tr[0][p][(x>>wei)&1]) sum+=qry0(x,wei-1,tr[0][p][(x>>wei)&1],goal);
// if(wei==WEI) cout<<" "<<sum<<endl;
return sum;
}
void add_qry1(int x,int wei,int p,int goal,int val)
{
if(wei==-1)
{
cnt[1][p]+=val;
return ;
}
if((goal>>wei)&1)
{
if(tr[1][p][(x>>wei)&1]) cnt[1][tr[1][p][(x>>wei)&1]]+=val;
if(tr[1][p][!((x>>wei)&1)]) add_qry1(x,wei-1,tr[1][p][!((x>>wei)&1)],goal,val);
}
else if(tr[1][p][(x>>wei)&1]) add_qry1(x,wei-1,tr[1][p][(x>>wei)&1],goal,val);
}
void upd1(int p,int wei,int val)
{
val+=cnt[1][p];
if(wei==-1)
{
for(int i=0;i<vec[p].size();i++)
Q[vec[p][i]].v+=val*calc;
return ;
}
if(tr[1][p][0]) upd1(tr[1][p][0],wei-1,val);
if(tr[1][p][1]) upd1(tr[1][p][1],wei-1,val);
}
int QI(int x,char k)
{
if(k=='b') return (x<=N?ild[x].b:Q[x].d);
else if(k=='a') return (x<=N?ild[x].a:Q[x].c);
else if(k=='i') return (x<=N?ild[x].id:Q[x].id);
}
bool mcp(int x,int y)
{
int x_id=(x<=N?ild[x].id:Q[x].id),y_id=(y<=N?ild[y].id:Q[y].id);
if(x_id!=y_id) return x_id<y_id;
else if(x!=y) return x<y;
else return QI(x,'b')>QI(y,'b');
}
bool mcp2(int x,int y)
{
return QI(x,'b')>QI(y,'b');
}
void CDQ(int l,int r)
{
if(l>=r) return ;
int i,j,li,ri,mid=(l+r)>>1,tli,tri;
CDQ(l,mid);CDQ(mid+1,r);
// sort(idst+l,idst+mid+1,mcp2);
// sort(idst+mid+1,idst+r+1,mcp2);
for(ri=mid+1,li=l;ri<=r;ri++)
{
if(idst[ri]<=N) continue;
for(;li<=mid;li++)
{
if(QI(idst[li],'b')<=QI(idst[ri],'b')) break;
if(idst[li]<=N) add01(0,ild[idst[li]].a,WEI,0,1);
}
Q[idst[ri]].v+=qry0(Q[idst[ri]].c,WEI,0,Q[idst[ri]].d)*calc;
}
for(li=l,ri=mid+1;li<=mid;li++)
{
if(idst[li]>N) continue;
for(;ri<=r;ri++)
{
if(QI(idst[li],'b')>QI(idst[ri],'b')) break;
if(idst[ri]>N) add01(1,QI(idst[ri],'a'),WEI,0,idst[ri]);
}
add_qry1(ild[idst[li]].a,WEI,0,ild[idst[li]].b,1);
}
upd1(0,WEI,0);
for(i=0;i<=1;i++) for(j=0;j<=idx[i];j++) tr[i][j][0]=tr[i][j][1]=cnt[i][j]=0,vec[j].clear();
idx[0]=idx[1]=0;
merge(idst+l,idst+mid+1,idst+mid+1,idst+r+1,tmp+l,mcp2);
for(i=l;i<=r;i++) idst[i]=tmp[i];
return ;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int i,j,k,l=1;
cin>>N>>M;
for(i=1;i<=N;i++) cin>>ild[i].a>>ild[i].b,ild[i].id=i,idst[i]=i;
for(i=N+1;i<=N+M;i++) cin>>Q[i].l>>Q[i].r>>Q[i].c>>Q[i].d,Q[i].id=Q[i].r,Q[i].v=0,idst[i]=i;
calc=1;
sort(idst+1,idst+N+M+1,mcp);
CDQ(1,N+M);
calc=-1;
for(i=N+1;i<=N+M;i++) Q[i].id=Q[i].l-1;
sort(idst+1,idst+N+M+1,mcp);
for(l=1;l<=N+M;l++) if(QI(idst[l],'i')!=0) break;
CDQ(l,N+M);
for(i=N+1;i<=N+M;i++) cout<<Q[i].v<<"\n";
return 0;
}
/*
6 1
190 81
230 131
10 238
189 198
183 13
45 193
1 4 119 239
3 1
1 1
4 2
2 7
1 3 6 5
*/