【cdoj 843】冰雪奇缘 线段树保留区间

【cdoj 843】冰雪奇缘 线段树保留区间

回想我们的梯形面积公式 (上底+下底)*高/2 这里的每一次添加对于一段区间来说高不会变，只是上底和下底增加（也可以看做变成了一个更大的梯形），所以只需要用维护上底和下底的懒惰标记和面积就行了

这里主要来谈谈关于线段树维护区间，因为我以前的写法都太麻烦，因为这里是给出的坐标所以如果用叶子节点来维护坐标再求值由于二分的时候就会空出mid所以我们选择直接维护区间，写法基本框架不会变同样的，只是在建树的过程里把if (l==r)改成 if(l==r-1)然后每一次二分的时候 不会mid+1无论是左右儿子都是直接用mid就ok了，在判断的时候也把所有的>mid改作>=至于证明我感觉很迷

#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
#include<algorithm>
#define maxn 300020
#define ls u<<1,l,mid
#define rs u<<1|1,mid,r
using namespace std;
int n,cnt;
map<int ,int>Mat;
struct ques{int x1,x2,h1,h2,l,r;
}que[maxn];struct node{int l,r,;double ladd,radd,lh,rh,s,len;
}nod[maxn*4];int cur[maxn*6];
bool cmp(int a,int b){return a<b;}void front(){sort(cur+1,cur+1+cnt,cmp);cnt=unique(cur+1,cur+1+cnt)-cur-1;for(int i=1;i<=cnt;i++)Mat[cur[i]]=i;
}void build(int u,int l,int r){nod[u].ladd=nod[u].radd=nod[u].lh=nod[u].rh=nod[u].s=0;nod[u].l=l,nod[u].r=r;nod[u].len=cur[r]-cur[l];if(l==r-1)return ;int mid=l+r>>1;build(ls);build(rs);
}void push_up(int u){nod[u].s=nod[u<<1].s+nod[u<<1|1].s;
}double H(int x,double y,int a,double b,int mid){return y+(b-y)*(cur[mid]-cur[x])*1.0/(cur[a]-cur[x]);
}void push_down(int u){if(nod[u].ladd==0&&nod[u].radd==0)return ;double x=H(nod[u].l,nod[u].ladd,nod[u].r,nod[u].radd,nod[u].r+nod[u].l>>1);nod[u<<1].ladd+=nod[u].ladd;nod[u<<1].radd+=H(nod[u].l,nod[u].ladd,nod[u].r,nod[u].radd,nod[u].r+nod[u].l>>1);nod[u<<1|1].radd+=nod[u].radd;nod[u<<1|1].ladd+=H(nod[u].l,nod[u].ladd,nod[u].r,nod[u].radd,nod[u].r+nod[u].l>>1);nod[u<<1].s+=(nod[u].ladd+x)*nod[u<<1].len/2.0;nod[u<<1|1].s+=(x+nod[u].radd)*nod[u<<1|1].len/2.0;nod[u].ladd=nod[u].radd=0;
}void updata(int u,int l,int r,int x,int y,double add1,double add2){if(l==x&&r==y){nod[u].s+=(add1+add2)*nod[u].len/2.0;nod[u].ladd+=add1;nod[u].radd+=add2;return;}push_down(u);int mid=l+r>>1;if(x>=mid)updata(rs,x,y,add1,add2);else if(y<=mid)updata(ls,x,y,add1,add2);else{updata(ls,x,mid,add1,H(x,add1,y,add2,mid));updata(rs,mid,y,H(x,add1,y,add2,mid),add2);}push_up(u);
}double query(int u,int l,int r,int x,int y){if(x==l&&r==y)return nod[u].s;push_down(u);int mid=(l+r)>>1;if(x>=mid)return query(rs,x,y);else if(y<=mid)return query(ls,x,y);else return query(ls,x,mid)+query(rs,mid,y);
}int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d%d%d%d",&que[i].x1,&que[i].h1,&que[i].x2,&que[i].h2,&que[i].l,&que[i].r);cur[++cnt]=que[i].x1;cur[++cnt]=que[i].x2,cur[++cnt]=que[i].l,cur[++cnt]=que[i].r;}front();build(1,1,cnt);for(int i=1;i<=n;i++){updata(1,1,cnt,Mat[que[i].x1],Mat[que[i].x2],(double)que[i].h1,(double)que[i].h2);printf("%.8fn",query(1,1,cnt,Mat[que[i].l],Mat[que[i].r]));}return 0;
}