WA了好久,求调(蒟蒻求救)
查看原帖
WA了好久,求调(蒟蒻求救)
343342
Obviathy楼主2022/5/9 23:09
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+1;
int n,w,h;
long long ans;
bool fl[2][N*4];
struct node{
	int l;
	int r;
	int dat;
	int lmax;
	int rmax;
};
node tree[2][4*N];
inline void push_up(int d,int p){
	tree[d][p].dat = max(tree[d][2*p].rmax + tree[d][2*p+1].lmax,max(tree[d][2*p].dat , tree[d][2*p+1].dat));
	tree[d][p].lmax = tree[d][p*2].lmax;
	tree[d][p].rmax = tree[d][p*2+1].rmax;
	if(fl[d][p*2] == 1)
		tree[d][p].lmax += tree[d][p*2+1].lmax;
	if(fl[d][p*2+1] == 1)
		tree[d][p].rmax += tree[d][p*2].rmax;
	if(fl[d][p*2] == 1 && fl[d][p*2+1] == 1)
		fl[d][p] == 1;
	else fl[d][p] == 0;
}
void build(int d,int p,int l,int r){
	tree[d][p].l = l;
	tree[d][p].r = r;
	if(l == r){
		tree[d][p].dat = tree[d][p].lmax = tree[d][p].rmax = fl[d][p] = 1;
		return;
	}
	int mid = (l + r) / 2;
	build(d,p * 2,l,mid);
	build(d,p * 2 + 1,mid + 1,r);
	push_up(d,p);
	
}
inline void add(int d,int p,int x,int v){
	if(tree[d][p].l == tree[d][p].r){
		tree[d][p].dat = tree[d][p].lmax = tree[d][p].rmax = fl[d][p] = 0;
		return ;
	}
	int mid = (tree[d][p].l + tree[d][p].r) / 2;
	if(x <= mid)add(d,2 * p,x,v);
	else add(d,2 * p + 1,x,v);
	push_up(d,p);
}
int main(){
	cin >> w >> h >> n;
	build(0,1,1,w-1);
	build(1,1,1,h-1);
	for(int i = 1;i <= n;i ++){
		char s;
		int x;
		cin >> s >> x;
		if(s == 'H'){
			add(1,1,x,0);
			int t = tree[0][1].dat+1;
			int t1 = tree[1][1].dat+1;
			cout<<t*t1<<endl;
		}else{
			add(0,1,x,0);
			int t = tree[0][1].dat+1;
			int t1 = tree[1][1].dat+1;
			cout<<t*t1<<endl;
		}
	}
}
2022/5/9 23:09
加载中...