CDQ分治卡常,结果 WA on #7
查看原帖
CDQ分治卡常,结果 WA on #7
999274
CNS_5t0_0r2楼主2024/7/27 16:32
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
using namespace std;
inline char gc(){
    static char buf[10000005],*t1 = buf,*t2 = buf;
    return t1 == t2 && (t2 = (t1 = buf) + fread(buf,1,1000000,stdin),t1 == t2) ? EOF : *t1++;
}
inline int read(){
	char c = gc();
	int x = 0;
	while(c < '0' || c > '9')
		c = gc();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - 48;
		c = gc();
	}
	return x;
}
const int N = 5e5 + 9;
int n,m;
struct OPTION{
	int x,y,id;
	int pos;
	short opt;
} OP[N << 5],tmp[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);
}
bool cmp_y(OPTION op1,OPTION op2){
	return (op1.y ^ op2.y) ? op1.y < op2.y : op1.id < op2.id;
}
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,const short 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(const int l,const int r){
	if(l >= r)
		return;
	CDQ(l,mid);CDQ(mid + 1,r);
	//sort(OP + l,OP + mid + 1,cmp_y);
	int pos1 = l,pos2 = ((l + mid) >> 1) + 1;
	for(int i = l;i <= mid;i++){
        if(pos2 > mid || pos1 <= ((l + mid) >> 1) && OP[pos1].y < OP[pos2].y)
            tmp[i] = OP[pos1++];
        else
            tmp[i] = OP[pos2++];
    }
	for(int i = l;i <= mid;i++)
		OP[i] = tmp[i];
	//sort(OP + mid + 1,OP + r + 1,cmp_y);
	pos1 = mid + 1,pos2 = ((mid + 1 + r) >> 1) + 1;
	for(int i = mid + 1;i <= r;i++){
        if(pos2 > r || pos1 <= ((mid + 1 + r) >> 1) && OP[pos1].y < OP[pos2].y)
            tmp[i] = OP[pos1++];
        else
            tmp[i] = OP[pos2++];
    }
	for(int i = mid + 1;i <= r;i++)
		OP[i] = tmp[i];

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

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