CDQ分治样例输出1求调
查看原帖
CDQ分治样例输出1求调
999274
CNS_5t0_0r2楼主2024/7/27 11:25
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
const int N = 5e5 + 9;
int n,m;
struct OPTION{
	int x,y,id;
	int pos,opt,val;
	//val:该操作对后面查询的贡献(修改的贡献为1,查询操作没有贡献)
} OP[N << 5];
bool cmp_x(OPTION op1,OPTION op2){
	return (op1.x ^ op2.x) ? (op1.x < op2.x) : ((op1.y ^ op2.y) ? op1.y < op2.y : ((op1.id ^ op2.id) ? op1.id < op2.id : op1.val > op2.val));
}
bool cmp_y(OPTION op1,OPTION op2){
	return ((op1.y ^ op2.y) ? op1.y < op2.y : ((op1.id ^ op2.id) ? op1.id < op2.id : op1.val > op2.val));
}
int opt_cnt,query_cnt;
struct BinaryIndexedTree{
	int t[N];
	int lowbit(int x){
		return x & (-x);
	}
	int query(int pos){
		int ret = 0;
		for(int i = pos;i;i -= lowbit(i))
			ret += t[i];
		return ret;
	}
	void update(int pos,int v){
		for(int i = pos;i <= opt_cnt;i += lowbit(i))
			t[i] += v;
	}
	BinaryIndexedTree(){
		memset(t,0,sizeof t);
	}
} BIT;

int ans[N];
void CDQ(int l,int r){
	if(l >= r)
		return;
	CDQ(l,mid);CDQ(mid + 1,r);
	int i = l,j = mid + 1;
	sort(OP + l,OP + mid + 1,cmp_y);
	sort(OP + mid + 1,OP + r + 1,cmp_y);
	while(j <= r){
		while(i <= mid && OP[i].y <= OP[j].y){
			if(!OP[i].opt)//第i项操作是修改操作
				BIT.update(OP[i].id,OP[i].val);
			i++;
		}
		if(OP[j].opt){////第j项操作是查询操作
			int tmp = BIT.query(OP[j].id);
			ans[OP[j].pos] += tmp * OP[j].opt;
		}
		j++;
	}
	//撤销在树状数组上的修改
	for(int k = l;k < i;k++)
		if(!OP[k].opt)
			BIT.update(OP[k].id,-OP[k].val);
			
	
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		int x,y;
		cin >> x >> y;
		x += 2;y += 2;
		OP[++opt_cnt] = (OPTION){x,y,i,0,0,1};
	}
	for(int i = 1;i <= m;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x2 += 2;y2 += 2;
		x1++;y1++;
		query_cnt++;
		OP[++opt_cnt] = (OPTION){x2,y2,i,query_cnt,1,0};
		OP[++opt_cnt] = (OPTION){x1,y2,i,query_cnt,-1,0};
		OP[++opt_cnt] = (OPTION){x2,y1,i,query_cnt,-1,0};
		OP[++opt_cnt] = (OPTION){x1,y1,i,query_cnt,1,0};
	}
	sort(OP + 1,OP + opt_cnt + 1,cmp_x);
	CDQ(1,opt_cnt);
	
	
	for(int i = 1;i <= query_cnt;i++)
		cout << ans[i] << '\n';
	
	return 0;
}
2024/7/27 11:25
加载中...