请问哪里算重了呢?
查看原帖
请问哪里算重了呢?
444063
Jessica2333楼主2024/5/14 19:59

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
*/
2024/5/14 19:59
加载中...