[cdoj843] 冰雪奇缘（线段树+离散）

[线段树 + 离散化]

Description

艾莎女王又开始用冰雪魔法盖宫殿了。

她决定先造一堵墙，于是释放魔法让形为直角梯形的冰砖从天而降，定入冻土之中。

现在你将回答女王的询问：某段冻土上冰砖的面积。

注：多块冰砖之间会互相重叠，重叠部分要多次计算。

Input

第一行一个整数nn，表示有nn个冰砖先后定入了冻土之中。

冻土上刚开始并没有冰砖。

接下来n行，每行6个整数，x1i,h1i,x2i,h2i,li,ri

表示一次如图所示的冰砖下落，并询问在这之后，落在[li,ri][li,ri]内冰砖的总面积。

$2≤n≤100000, −10^8≤li，ri≤10^8,$

$−10^8≤x1i<x2i≤10^8,0≤h1i,h2i≤10000,x2i−x1i≤10^5，$

$2 ≤ n ≤ 100000,−10^8≤li<ri≤10^8,−10^8≤x1i<x2i≤10^8,$

$0≤h1i,h2i≤10000,x2i−x1i≤10^5 $

Output

输出nn行，每行输出一个浮点数，作为对该询问的回答。误差小于1e-6的回答都被当作正确回答。

Sample Input

2

1 1 3 2 -5 5

2 2 4 1 2 3

Sample Output

3.0000000

3.50000000

Hint

如图是对样例输入的解释。

重叠部分需多次计算。

这是一道比较有意义的线段树题目，线段树的每个节点主要保存的是一段区间内的面积和。

然后要想到的是，因为是区间更新区间查询，所以需要用到懒惰标记，避免超时。

想好要用到什么方法，接下来就思考具体方案。

首先，因为是梯形，所以更新是要用到左边高度和右边高度，即梯形的上底和下底，懒惰标记也需要传递这两个值。在往下传递的时候，可以把中间的一条线分两次计算，即把梯形分成矩形和三角形两个部分，第一个部分很好得，直接是矩形的上底，第二个部分可以用相似三角形来求。

需要注意的是，由于l ~ r 中存储的是l ~ r+1的值，所以左子树中存储l ~ mid+1，,右子树中存储mid+1 ~ r+1

还需要注意的一点是，题目中由于x 范围很大，需要离散化。

下面是代码

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

#define ls u<<1,l,mid

#define rs u<<1|1,mid+1,r

const int maxn = 1e5 + 5;

int n;

int cnt = 1;//离散化之后点的总数

int num[maxn << 2];

struct node {// 在线段树中， l ~ r维护的是l ~ r+1 的值

	double sum;

	double addl,addr;

}nod[maxn << 2 << 2];

struct que { //存储询问，因为需要先读入所有点用于离散化

	int xl,xr,hl,hr,x,y;

}q[maxn];

void pushup(int u){

	nod[u].sum = nod[u<<1].sum + nod[u<<1|1].sum;

}

void build(int u,int l,int r){

	if(l == r) return;

	int mid = (l + r) >> 1;

	build(ls);

	build(rs);

	pushup(u);

}

void init(){// 读入询问，离散化，建树

	scanf("%d",&n);

	for(int i = 1;i <= n;i++){

		scanf("%d%d%d%d%d%d",&q[i].xl,&q[i].hl

							,&q[i].xr,&q[i].hr

							,&q[i].x ,&q[i].y );

		num[cnt] = q[i].xl;cnt++;

		num[cnt] = q[i].xr;cnt++;

		num[cnt] = q[i].x;cnt++;

		num[cnt] = q[i].y;cnt++;

	}

	sort(num + 1, num + cnt);

	cnt = unique(num+1,num+cnt) - num - 1;

	build(1,1,cnt-1);

}

void pushdown(int u,int l,int r){

	if(l == r){nod[u].addl = nod[u].addr == 0;return;}

	//计算中间点的高度

	int mid = (l + r) >> 1;

	int rr = num[r+1] - num[l];

	int midd = num[mid+1] - num[l];

	double add = nod[u].addl + (nod[u].addr - nod[u].addl) * midd / rr;

	//向下传递sum值

	nod[u<<1].sum += (nod[u].addl + add) * midd / 2;

//	nod[u<<1|1].sum += (nod[u].addr + add) * (rr - midd) / 2;

	nod[u<<1|1].sum = nod[u].sum - nod[u<<1].sum;

	//向下传递add，并将当前节点add值清零

	nod[u<<1].addl += nod[u].addl; nod[u].addl = 0;

	nod[u<<1].addr += add;

	nod[u<<1|1].addr += nod[u].addr; nod[u].addr = 0;

	nod[u<<1|1].addl += add;

}

void update(int u,int l,int r,int x,int y,double hl,double hr){

	if(l == x && r+1 == y){

		nod[u].addl += hl;

		nod[u].addr += hr;

		nod[u].sum += (hl + hr) * (num[y]-num[x]) / 2;

		return;

	}

	int mid = (l + r) >> 1;

	if(nod[u].addl || nod[u].addr)pushdown(u,l,r);

	if(y <= mid+1) update(ls,x,y,hl,hr);

	else if(x >= mid+1) update(rs,x,y,hl,hr);

	else {

		int rr = num[y] - num[x];

		int midd = num[mid+1] - num[x];

		double add = hl + (hr - hl) * midd / rr;

		update(ls,x,mid+1,hl,add);

		update(rs,mid+1,y,add,hr);

	}

	pushup(u);

}

double query(int u,int l,int r,int x,int y){

	if(l == x && r + 1 == y)return nod[u].sum;

	int mid = (l + r) >> 1;

	if(nod[u].addl || nod[u].addr)pushdown(u,l,r);

	if(y <= mid+1) return query(ls,x,y);

	if(x >= mid+1)  return query(rs,x,y);

	return query(ls,x,mid+1) + query(rs,mid+1,y);

}

void work(){

	for(int i = 1;i <= n;i++){

		int x = lower_bound(num + 1,num + cnt + 1,q[i].xl) - num ;

		int y = lower_bound(num + 1,num + cnt + 1,q[i].xr) - num ;

		update(1,1,cnt-1,x,y,q[i].hl,q[i].hr);

		x = lower_bound(num + 1,num + cnt + 1,q[i].x) - num ;

		y = lower_bound(num + 1,num + cnt + 1,q[i].y) - num ;

		printf("%lf\n",query(1,1,cnt-1,x,y));

	}

}

int main(){

	init();

	work();

	return 0;

}

巴特西

[cdoj843] 冰雪奇缘（线段树+离散）

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

巴特西

[cdoj843] 冰雪奇缘 （线段树+离散）

Description

Input

Output

Sample Input

Sample Output

Hint

最新文章

热门文章

[cdoj843] 冰雪奇缘（线段树+离散）