题意：。。求周长并。。。
解析：参考求面积并
图借鉴自：https://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464876.html
自下而上扫描 首先 加GH 接着 加 Node[1].numseg * 2 *（Edge[i+1].y - Edge[i].y）即两条竖边 然后 加 BD 但这时要减去GH 因为 LN = GH 重复加了一次
依次推理
与面积并不同的是 最上面的边不要忘了加上。。
#include#include #include #include #include #include #define mem(a, b) memset(a, b, sizeof(a))using namespace std;const int maxn = 10010, INF = 0x7fffffff;int X[maxn];struct node{ int l, r, w; // l 和 r 分别为线段树的左右端点 w记录边重叠的情况 int numseg; // 记录竖边的对数 int lx, rx, sum; // sum代表当前区间线段的长度，lx和rx为线段的真实端点 bool lcover, rcover; // 标记当前区间的左右端点 与 numseg有关}Node[maxn*4];struct edge{ // 存边 int lxx, rxx, y; int f;}Edge[maxn];int cmp(edge a, edge b){ return a.y < b.y;}void build(int k, int ll, int rr){ Node[k].l = ll, Node[k].r = rr; Node[k].lx = X[ll]; Node[k].rx = X[rr]; Node[k].w = Node[k].numseg = 0, Node[k].sum = 0; Node[k].lcover = Node[k].rcover = false; if(ll + 1 == rr) return; int m = (ll + rr) / 2; build(k*2, ll, m); build(k*2+1, m, rr);}void down(int k){ if(Node[k].w > 0) { Node[k].sum = Node[k].rx - Node[k].lx; Node[k].numseg = 1; Node[k].lcover = Node[k].rcover = true; return; } if(Node[k].l + 1 == Node[k].r) { Node[k].sum = 0; Node[k].numseg = 0; Node[k].lcover = Node[k].rcover = false; } else { Node[k].sum = Node[k*2].sum + Node[k*2+1].sum; Node[k].lcover = Node[k*2].lcover, Node[k].rcover = Node[k*2+1].rcover; Node[k].numseg = Node[k*2].numseg + Node[k*2+1].numseg; if(Node[k*2].rcover && Node[k*2+1].lcover) Node[k].numseg--; //注意这里是左区间的右端点 和 右区间的左端点 }}void update(int k, edge e){ if(Node[k].lx == e.lxx && Node[k].rx == e.rxx) { Node[k].w += e.f; down(k); return; } if(e.rxx <= Node[k*2].rx) update(k*2, e); else if(e.lxx >= Node[k*2+1].lx) update(k*2+1, e); else { edge temp = e; temp.rxx = Node[k*2].rx; update(k*2, temp); temp = e; temp.lxx = Node[k*2+1].lx; update(k*2+1, temp); } down(k);}int main(){ int n, cnt = 0; scanf("%d",&n); for(int i=0; i