HDU - 6888（线段树）

[题目链接](https://vjudge.net/problem/HDU-6888) ------------ 将周长分为两部分考虑： 平行于$x$轴的边的长度和与平行于$y$的边的长度和 需要$STB$实现区间最值操作 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=4e5+5,inf=0x3f3f3f3f; int n,m,w[M]; vector< pair<int,int> > vt; struct ask{int l,r,h;}q[M]; struct d { int l,r,wid,tag,cover,len,lv,rv,cnt,mn1,mn2; ll sum; #define ls (i<<1) #define rs (i<<1|1) }tree[M*4]; void up(int i) { tree[i].wid=tree[ls].wid+tree[rs].wid; tree[i].len=tree[ls].len+tree[rs].len; tree[i].sum=tree[ls].sum+tree[rs].sum+abs(tree[ls].rv-tree[rs].lv); tree[i].lv=tree[ls].lv; tree[i].rv=tree[rs].rv; if(tree[ls].mn1<tree[rs].mn1) { tree[i].mn1=tree[ls].mn1; tree[i].mn2=min(tree[rs].mn1,tree[ls].mn2); tree[i].cnt=tree[ls].cnt; } else if(tree[ls].mn1>tree[rs].mn1) { tree[i].mn1=tree[rs].mn1; tree[i].mn2=min(tree[ls].mn1,tree[rs].mn2); tree[i].cnt=tree[rs].cnt; } else { tree[i].mn1=tree[ls].mn1; tree[i].mn2=min(tree[rs].mn2,tree[ls].mn2); tree[i].cnt=tree[ls].cnt+tree[rs].cnt+((tree[ls].rv==tree[rs].lv&&tree[ls].rv==tree[i].mn1)?-1:0); } } void down(int i) { if(tree[i].cover) { tree[ls].len=tree[ls].wid; tree[rs].len=tree[rs].wid; tree[ls].cover=tree[rs].cover=1; tree[i].cover=0; } if(tree[i].tag) { if(tree[ls].mn1<tree[i].tag) { tree[ls].tag=max(tree[ls].tag,tree[i].tag); int tmp=0; if(tree[ls].lv==tree[ls].mn1)tmp++; if(tree[ls].rv==tree[ls].mn1)tmp++; tree[ls].lv=max(tree[ls].lv,tree[i].tag); tree[ls].rv=max(tree[ls].rv,tree[i].tag); tree[ls].sum-=(ll)(2*tree[ls].cnt-tmp)*(tree[i].tag-tree[ls].mn1); tree[ls].mn1=tree[i].tag; } if(tree[rs].mn1<tree[i].tag) { tree[rs].tag=max(tree[rs].tag,tree[i].tag); int tmp=0; if(tree[rs].lv==tree[rs].mn1)tmp++; if(tree[rs].rv==tree[rs].mn1)tmp++; tree[rs].lv=max(tree[rs].lv,tree[i].tag); tree[rs].rv=max(tree[rs].rv,tree[i].tag); tree[rs].sum-=(ll)(2*tree[rs].cnt-tmp)*(tree[i].tag-tree[rs].mn1); tree[rs].mn1=tree[i].tag; } tree[i].tag=0; } } void build(int i,int l,int r) { tree[i].l=l;tree[i].r=r; tree[i].cover=tree[i].tag=0; tree[i].mn1=0; tree[i].mn2=inf; if(l==r) { tree[i].wid=w[l]; tree[i].len=0; tree[i].lv=tree[i].rv=0; tree[i].cnt=1; tree[i].sum=0; return ; } int mid=(l+r)/2; build(ls,l,mid); build(rs,mid+1,r); up(i); } void upd(int i,int l,int r,int h) { if(tree[i].mn1>=h)return ; if(h<tree[i].mn2&&l<=tree[i].l&&tree[i].r<=r) { tree[i].cover=1; tree[i].len=tree[i].wid; tree[i].tag=max(tree[i].tag,h); int tmp=0; if(tree[i].lv==tree[i].mn1)tmp++; if(tree[i].rv==tree[i].mn1)tmp++; tree[i].lv=max(tree[i].lv,h); tree[i].rv=max(tree[i].rv,h); tree[i].sum-=(ll)(2*tree[i].cnt-tmp)*(h-tree[i].mn1); tree[i].mn1=h; return ; } down(i); int mid=(tree[i].l+tree[i].r)/2; if(l<=mid)upd(ls,l,r,h); if(r>mid)upd(rs,l,r,h); up(i); } ll que(){return tree[1].sum+tree[1].lv+tree[1].rv+2*tree[1].len;} int main() { int T;scanf("%d",&T); while(T--) { vt.clear(); m=0; scanf("%d",&n); for(int i=1;i<=n;i++) { q[i].l=q[i].r=-1; int l,r;scanf("%d%d%d",&l,&r,&q[i].h); vt.push_back(make_pair(l,i)); vt.push_back(make_pair(r,i)); } sort(vt.begin(),vt.end()); q[vt[0].second].l=1; for(int i=1;i<vt.size();i++) { if(vt[i].first!=vt[i-1].first)w[++m]=vt[i].first-vt[i-1].first; if(q[vt[i].second].l==-1)q[vt[i].second].l=m+1; else q[vt[i].second].r=m; } build(1,1,m); for(int i=1;i<=n;i++) { upd(1,q[i].l,q[i].r,q[i].h); printf("%lld\n",que()); } } return 0; } ```