#C240926C. 三维世界(呲)

标签（Label）

• 扫描线
• 计算几何
• 单调队列

网址（Website）

题目详情 - 三维世界(呲) - Super

题解 - 三维世界(呲) - Super

题解（Solution）

$\qquad$先按 $x$ 从大到小排序，可以发现所有的 $type==2$ 的操作最后挖出来的是一个阶梯图形，随便用什么东西处理一下算出面积。

$\qquad$发现 $x$ 从大到小遍历操作，大的会对小的产生影响，而小的不会对大的产生影响。且提取出平面后，每次 $type$ 为 $1$ 或者 $3$ 的操作只需要计算最大的那个矩形，将矩形和原来的梯形求面积并即可。

代码（Code）

#include<bits/stdc++.h>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define x first
#define y second
inline int rd(){
	bool f=false;char c;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 1012345;
bool ST;

struct Att{int x,y,z,t;}a[N];
int n,ans,A,B,C,S;

deque<P> q;
void Solve_x(){
	sort(a+1,a+n+1,[&](Att a,Att b){
		return a.x==b.x ? (a.y==b.y ? a.z<b.z : a.y>b.y) : a.x>b.x;});
	
	int lst = 0;
	For(i,1,n){
		if(a[i].t!=2) continue;
		int x = a[i].y, wid = a[i].z - lst;
		if(wid<=0) continue;lst = a[i].z;
		S += x * wid, q.emplace_back(x,a[i].z);
	}
}

//维护队列 
inline void add(int x,int y){//x递减,y递增 
	int lst = 0;
	if(x==B){
		while(q.size() && q.front().y<=y){
			assert(q.front().y>=lst);
			S -= (q.front().y-lst) * q.front().x;
			lst = q.front().y, q.pop_front();
		}
		if(q.size()) S -= (y-lst) * q.front().x;
		S += x*y, q.emplace_front(x,y);
	}else{
		while(q.size() && q.back().x<=x){
			assert(q.back().x>=lst);
			S -= (q.back().x-lst) * q.back().y;
			lst = q.back().x, q.pop_back();
		}
		if(q.size()) S -= (x-lst) * q.back().y;
		S += x*y, q.emplace_back(x,y);
	}
}

void Solve_yz(){
	sort(a+1,a+n+1,[&](Att a,Att b){
		return a.x==b.x ? (a.y==b.y ? a.z>b.z : a.y>b.y) : a.x>b.x;});
	
	int lstx = A, high = 0;
	For(i,1,n){
		if(a[i].t==2) continue;
		if(a[i].x<lstx) high = lstx-a[i].x, ans += high * S, lstx = a[i].x;
		int j = i, mxy=0, mxz=0;
		for(;a[j].t==3 && a[j].x==lstx;j++) mxz = max(mxz, a[j].z);
		for(;a[j].t==1 && a[j].x==lstx;j++) mxy = max(mxy, a[j].y);
		if(mxy) add(mxy,C);
		if(mxz) add(B,mxz);
		i = j-1;
	}if(lstx) ans += lstx * S;
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	freopen("c.in","r",stdin);	
	freopen("c.out","w",stdout);	
	n=rd(),A=rd(),B=rd(),C=rd();
	int Tim = clock();
	For(i,1,n){
		int op = rd(), v = rd(), w = rd();
		switch(op){
			case 1:{a[i] = {v,w,C,op};break;}
			case 2:{a[i] = {A,v,w,op};break;}
			case 3:{a[i] = {w,B,v,op};break;}
		}
	}Solve_x(),Solve_yz();
	printf("%lld\n",ans);
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}