求问边界维护的一个问题
  • 板块学术版
  • 楼主yanglang1
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/9/7 23:07
  • 上次更新2024/9/8 11:39:00
查看原帖
求问边界维护的一个问题
650565
yanglang1楼主2024/9/7 23:07

蒟蒻的我在打abc时被abc370T4卡了半天, 赛后又改了一个小时,发现边界不能设定在值域两端内,我做法也是用set二分维护每行每列,为了不删到区块外面, 我就让1和n(或1和m)永远删不掉,然后wa一半一直没检查出QWQ。把删不掉到墙设置成0和n+1(m+1)就A了。想问下有大佬可以帮我解答一下什么会这样吗?

Ac代码如下

#include<bits/stdc++.h>
using namespace std;
const long long N = 4e5+5;
long long n, m, q;
set<long long> xk[N], yk[N], se;//xk横着 yk竖着
map<long long, long long> bi[N]; 
long long x1, x2, y11, y2;
void lowe(long long x, long long y){
	set<long long>::iterator it;
	it = xk[x].lower_bound(y);
	x1 = *it;
	it--; x2 = *it;
	
	it = yk[y].lower_bound(x);
	y11 = *it;
	it--; y2 = *it;
}
void dete(long long x, long long y){
	if(y != m+1 && y != 0)xk[x].erase(y);
	if(x != n+1 && x != 0)yk[y].erase(x);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for(long long i=1;i<=n;i++){
		xk[i].insert(0); xk[i].insert(m+1);
	}
	for(long long j=1;j<=m;j++){
		yk[j].insert(0); yk[j].insert(n+1);
	}
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			xk[i].insert(j);
			yk[j].insert(i);
		}
	}
	long long xc, yc;
	while(q--){
		cin >> xc >> yc;
		if(bi[xc][yc] == 0){
			bi[xc][yc] = 1;
			
			dete(xc, yc); 
		}
		else{
			lowe(xc, yc);
			bi[xc][x1] = bi[xc][x2] = bi[y11][yc] = bi[y2][yc] = 1;
			
			dete(xc, x1);
			dete(xc, x2);
			dete(y11, yc);
			dete(y2, yc); 	
		}
	}
	long long ans = 0;
	for(long long i=1;i<=n;i++){
		for(long long j=1;j<=m;j++){
			ans += (bi[i][j]==0);
		}
	}
	cout << ans;
	return 0;
}
2024/9/7 23:07
加载中...