自动搬运

查看原文

来自洛谷，原作者为

	聊机 梦开始的地方

搬运于2025-08-24 22:28:17，当前版本为作者最后更新于2023-08-02 20:40:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看讨论区有人问，就水了一下这题，居然没人交过。

一看题面就是扫描线，但是这是三角形，很不好处理了。看下数据范围发现非常小，于是想到一种大胆的做法，我们考虑对于一个面来说，除了三角形最上面的那个点，其他的点都会往后产生 1 的贡献，而三角形最上面的那个点会产生 0.5 的贡献，$n$ 和 $m$ 都非常小，于是我们就可以暴力维护这些顶点，每次把这些点往下走一格，然后一个个单点修改，每次的代价就是线段树里覆盖的所有点，加上没被线段树里的点覆盖的顶点个数除以 2。$x$，$y$ 很大，离散化后与一般板子的扫描线不同，我们直接枚举 $x$ 坐标而不是把三角形排序，复杂度 $O(n^2\operatorname{log}n)$。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+2;
const int N=2002;
struct Segment{//这部分可以直接用暴力省掉，并且复杂度更小
	int T[MAXN<<2],lz[MAXN<<2];
	#define ls p<<1
	#define rs p<<1|1
	void tag(int p,int l,int r,int x) {
		lz[p]+=x;
		if(lz[p]) T[p]=r-l+1;
		else T[p]=0;
	}
	void pushdown(int p,int l,int r,int mid) {
		if(!lz[p]) return ;
		tag(ls,l,mid,lz[p]);
		tag(rs,mid+1,r,lz[p]);
		lz[p]=0;
	}
	void update(int p,int l,int r,int L,int R,int x) {
		if(l>=L&&r<=R) return tag(p,l,r,x);
		int mid=l+r>>1;
		pushdown(p,l,r,mid);
		if(mid>=L) update(ls,l,mid,L,R,x);
		if(mid<R) update(rs,mid+1,r,L,R,x);
		T[p]=T[ls]+T[rs];
	}
	int ask(int p,int l,int r,int x) {
		if(l==r) return T[p];
		int mid=l+r>>1;
		pushdown(p,l,r,mid);
		if(mid>=x) return ask(ls,l,mid,x);
		else return ask(rs,mid+1,r,x);
	}
}tr;
struct Node{
	int x,y,m;
}s[N];
struct node{
	int y,m;
};
vector<node>v[MAXN];
pair<int,int>l1[N],l2[N];
int n;
typedef pair<int,int> P;
double ans;
#define fs first 
#define sc second 
P q[N],cp[N];
int s1,s2;
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d%d",&l1[i].fs,&l2[i].fs,&s[i].m);
		l1[i].sc=l2[i].sc=i;
	}
	sort(l1+1,l1+n+1);sort(l2+1,l2+n+1);
	for(int i=2;i<=n;i++) {//离散化部分
		if(l2[i].fs-l2[i-1].fs<=1000) s[l2[i].sc].y=s[l2[i-1].sc].y+l2[i].fs-l2[i-1].fs;
		else s[l2[i].sc].y=s[l2[i-1].sc].y+1000;
		if(l1[i].fs-l1[i-1].fs<=1000) s[l1[i].sc].x=s[l1[i-1].sc].x+l1[i].fs-l1[i-1].fs;
		else s[l1[i].sc].x=s[l1[i-1].sc].x+1000;
	}
	for(int i=1;i<=n;i++) 
		v[s[i].x].push_back((node){s[i].y,s[i].m});
	q[0].fs=-1;
	for(int i=0;i<MAXN-1;i++) {
		s2=0;
		for(int j=1;j<=s1;j++) {
			P p=q[j];--p.fs;
			if(--p.sc>0) tr.update(1,1,MAXN-2,p.fs,p.fs,-1);
			if(p.sc) cp[++s2]=p;
		}
		for(int j=1;j<=s2;j++)
			q[j]=cp[j]; s1=s2;
		for(int j=0;j<v[i].size();j++) {
			P p=P(v[i][j].m+v[i][j].y,v[i][j].m);
			if(v[i][j].m>1) tr.update(1,1,MAXN-2,v[i][j].y+1,p.fs-1,1);
			q[++s1]=p;
		}
		stable_sort(q+1,q+s1+1);//这里排序是防止位置相同的顶点算两次
		ans+=tr.T[1];
		for(int j=1;j<=s1;j++) {
			if(q[j].fs==q[j-1].fs) continue;//这里去重
			if(!tr.ask(1,1,MAXN-2,q[j].fs)) ans+=0.5;
		}
	}
	printf("%.1f",ans);
	return 0;
}

写到这里发现，其实因为 $n\times m$ 非常小，所以其实都不需要线段树，直接暴力即可（甚至复杂度更小）。