艾莎女王又开始用冰雪魔法盖宫殿了。
她决定先造一堵墙，于是释放魔法让形为直角梯形的冰砖从天而降，定入冻土之中。
现在你将回答女王的询问：某段冻土上冰砖的面积。
注：多块冰砖之间会互相重叠，重叠部分要多次计算。
Input
第一行一个整数n，表示有n个冰砖先后定入了冻土之中。
冻土上刚开始并没有冰砖。
接下来n行，每行6个整数，x1i,h1i,x2i,h2i,li,ri。
表示一次如图所示的冰砖下落，并询问在这之后，落在[li,ri]内冰砖的总面积。
2≤n≤100000,−108≤li<ri≤108,−108≤x1i<x2i≤108,0≤h1i,h2i≤10000,x2i−x1i≤105
Output
输出n行，每行输出一个浮点数，作为对该询问的回答。误差小于1e-6的回答都被当作正确回答
解题报告
首先由于范围很大，我们对X轴上的点进行离散化
注意到这个四边形就是给一段区间增加一段等差数列.
并且注意到等差数列叠加后依然还是等差数列
那么我们在线段树中就存储四个值:
1.double st; //该区间左端应该加的值
2.double ed; //该区间右端应该加的值
3.double k; //等差数列的k值，不多说
4.double sum; //该区间的面积之和
那么面积我们就转换成梯形计算:
SUM = (st + ed) * 0.5 * Len; //注意到这个Len是这个区间的实际长度！！
这样.
还有两点需要注意！
1.区间建立的时候是[L,R] → [L,mid] + [mid,R]
2. updata操作有三种情况,三种情况的更新各不同，这点需要注意
分别对应ql ,qr 在mid 的左 / 右 / 中三种情况，需分开讨论
注意上以上几点，那么本题也就迎刃而解了.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + ;
int n;
int pos[maxn*];
int hashpos[maxn*]; typedef struct Query
{
int l,r,x1,y1,x2,y2,id[];
}; typedef struct Data
{
int l,r,len;
double sum,st,ed,k;
void updata(const double &x,const double &y,const double &z)
{
st += x;
ed += y;
k += z;
sum += (double)(x+y)*len*0.5;
}
}; Query q[maxn*];
Data tree[maxn*];
int size = ; void push_up(int cur)
{
tree[cur].sum = tree[cur*].sum + tree[cur*+].sum;
} inline double get_(int x1,int x2,double st,double k)
{
return (double)(hashpos[x2]-hashpos[x1]) * k + st;
} void push_down(int cur)
{
double st = tree[cur].st;
double ed = tree[cur].ed;
double k = tree[cur].k;
int l = tree[cur].l;
int r = tree[cur].r;
int mid = l + (r-l)/;
double news = get_(tree[cur].l,mid,st,k);
tree[*cur].updata(st,news,k);
tree[*cur+].updata(news,ed,k);
tree[cur].st = tree[cur].ed = tree[cur].k = .;
} void build_tree(int cur,int l,int r)
{
tree[cur].l = l , tree[cur].r = r;
tree[cur].len = hashpos[r] - hashpos[l];
tree[cur].st = tree[cur].ed = tree[cur].k = tree[cur].sum = .;
if (r -l > )
{
int mid = l + (r-l)/;
build_tree(*cur,l,mid);
build_tree(*cur+,mid,r);
}
} void updata(int ql,int qr,int cur,double st,double ed,double k)
{
int l = tree[cur].l , r = tree[cur].r;
if (l >= ql && r <= qr)
{
tree[cur].updata(st,ed,k);
}
else
{
push_down(cur);
int mid = l + (r-l) / ;
//三种情况，分开讨论
if (qr <= mid) updata(ql,qr,*cur,st,ed,k);
else if(ql >= mid) updata(ql,qr,*cur+,st,ed,k);
else
{
double news = get_(ql,mid,st,k);
updata(ql,mid,*cur,st,news,k);
updata(mid,qr,*cur+,news,ed,k);
}
push_up(cur);
}
} double query(int ql,int qr,int cur)
{
int l = tree[cur].l , r = tree[cur].r;
if (l >= ql && r <= qr)
return tree[cur].sum;
else
{
push_down(cur);
double res = .;
int mid = l + (r-l)/;
if (mid > ql)
res += query(ql,qr,*cur);
if (mid < qr)
res += query(ql,qr,*cur+);
push_up(cur);
return res;
}
} inline double getk(int x1,int x2,int y1,int y2)
{
return (double)(y2-y1) / (double)(x2-x1);
} int main(int argc,char *argv[])
{
scanf("%d",&n);
for(int i = ; i < n ; ++ i)
{
int x1,y1,x2,y2,l,r;
scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&l,&r);
q[i].id[] = size;
pos[size++] = x1;
q[i].id[] = size;
pos[size++] = x2;
q[i].id[] = size;
pos[size++] = l;
q[i].id[] = size;
pos[size++] = r;
q[i].x1 = x1;
q[i].x2 = x2;
q[i].y1 = y1;
q[i].y2 = y2;
q[i].l = l;
q[i].r = r;
}
memcpy(hashpos,pos,sizeof(int)*size);
sort(hashpos,hashpos+size);
int c = unique(hashpos,hashpos+size) - hashpos;
for(int i = ; i < size ; ++ i)
pos[i] = lower_bound(hashpos,hashpos+c,pos[i]) - hashpos;
build_tree(,,c-);
for(int i = ; i < n ; ++ i)
{
int x1 = q[i].x1;
int y1 = q[i].y1;
int x2 = q[i].x2;
int y2 = q[i].y2;
double k = getk(x1,x2,y1,y2);
updata(pos[q[i].id[]],pos[q[i].id[]],,(double)y1,(double)y2,k);
double res = query(pos[q[i].id[]],pos[q[i].id[]],);
printf("%.9lf\n",res);
}
return ;
}