题目链接

---

  有一张二维平面，现在全是空白的，我们的操作是给为左下角，为右上角的面涂黑，现在我们想知道所有的黑色块的周长。

  可以发现对于上部和下部的周长我们可以利用区间覆盖来进行计算，但是竖着的边我们该如何计算呢？容易想到的是，我们可以通过把“区间点”变成“区间块”这样的做法，使得原本表示的区间点，变成表示的区间块，表示块第到第。然后我们求的就是任意相邻两块之间的高度差之和。

  这个东西可以怎样维护呢？我们易发现，只有变大才会改变这个答案，所以其实就是维护最大值的这样一个操作。

  那么对于区间取最大值，然后区间查询这样的做法，实际上就是吉司机线段树了。

  于是，我们可以利用吉司机线段树来进行维护：

1. 区间最小值mi
2. 区间次小值md
3. 区间最小值对应的竖线个数cnt
4. 区间“显形”竖线高度和sum
5. 懒标记lazy（记录区间长度）
6. 区间最左端的竖线的高度lh
7. 区间最右端的竖线的高度rh

  于是，竖线就可以维护出来了，然后水平线，就是区间覆盖长度乘以2就可以了。

  细节很多，wa了很多次：

1. pushdown的时候别忘了更改lh和rh
2. 每次要更新sum的时候，除了取左右子区间的sum和，当一个比最小值大的值放入的时候要删去的贡献
3. 然后取块的时候，最好就是两端多各自开一个空点，这样方便计算最左边和最右边的竖线高度，不然需要最后算答案的时候。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define pii pair<int, int>
#define MP(a, b) make_pair(a, b)
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 2e5 + 7;
int N, lsan[maxN << 1], _UP;
struct Question
{int l, r, h;inline void In() { scanf("%d%d%d", &l, &r, &h); }
} q[maxN];
const int maxP = maxN << 3;
namespace Cover_Tree
{bool c[maxP]; int s[maxP];void Cover_Build(int rt, int l, int r){c[rt] =  false; s[rt] = 0;if(l == r) return;int mid = HalF;Cover_Build(Lson);Cover_Build(Rson);}void Cover_update(int rt, int l, int r, int ql, int qr){if(c[rt]) return;if(ql <= l && qr >= r){c[rt] = true;s[rt] = lsan[r + 1] - lsan[l];return;}int mid = HalF;if(qr <= mid) Cover_update(QL);else if(ql > mid) Cover_update(QR);else { Cover_update(QL); Cover_update(QR); }s[rt] = s[lsn] + s[rsn];if(s[rt] == lsan[r + 1] - lsan[l]) c[rt] = true;}
};
using namespace Cover_Tree;
namespace Segement_Tree_Beats
{int mi[maxP], md[maxP], cnt[maxP], lazy[maxP], lh[maxP], rh[maxP];ll sum[maxP];void build(int rt, int l, int r){mi[rt] = lazy[rt] = lh[rt] = rh[rt] = 0; sum[rt] = 0;cnt[rt] = 0;md[rt] = INF;if(l == r) return;int mid = HalF;build(Lson);build(Rson);}void pushup(int rt){sum[rt] = sum[lsn] + sum[rsn] + abs(rh[lsn] - lh[rsn]);lh[rt] = lh[lsn];rh[rt] = rh[rsn];if(mi[lsn] == mi[rsn]){mi[rt] = mi[lsn];md[rt] = min(md[lsn], md[rsn]);cnt[rt] = cnt[lsn] + cnt[rsn] + ((rh[lsn] == mi[rt]) ^ (lh[rsn] == mi[rt]));}else if(mi[lsn] < mi[rsn]){mi[rt] = mi[lsn];md[rt] = min(mi[rsn], md[lsn]);cnt[rt] = cnt[lsn] + (rh[lsn] == mi[rt]);}else{mi[rt] = mi[rsn];md[rt] = min(mi[lsn], md[rsn]);cnt[rt] = cnt[rsn] + (lh[rsn] == mi[rt]);}}void pushdown(int rt){if(lazy[rt]){if(mi[lsn] < lazy[rt]){sum[lsn] -= 1LL * (lazy[rt] - mi[lsn]) * cnt[lsn];mi[lsn] = lazy[rt];lazy[lsn] = lazy[rt];lh[lsn] = max(lh[lsn], lazy[rt]);rh[lsn] = max(rh[lsn], lazy[rt]);}if(mi[rsn] < lazy[rt]){sum[rsn] -= 1LL * (lazy[rt] - mi[rsn]) * cnt[rsn];mi[rsn] = lazy[rt];lazy[rsn] = lazy[rt];lh[rsn] = max(lh[rsn], lazy[rt]);rh[rsn] = max(rh[rsn], lazy[rt]);}lazy[rt] = 0;}}void update(int rt, int l, int r, int ql, int qr, int val){if(ql > r || qr < l || val <= mi[rt]) return;int mid = HalF;if(val >= md[rt]){pushdown(rt);update(QL, val);update(QR, val);pushup(rt);}else{if(ql <= l && qr >= r){lazy[rt] = val;sum[rt] -= 1LL * (val - mi[rt]) * cnt[rt];mi[rt] = val;lh[rt] = max(lh[rt], val);rh[rt] = max(rh[rt], val);}else{pushdown(rt);if(qr <= mid) update(QL, val);else if(ql > mid) update(QR, val);else { update(QL, val); update(QR, val); }pushup(rt);}}}
};
using namespace Segement_Tree_Beats;
int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &N); _UP = 0;for(int i=1; i<=N; i++){q[i].In();lsan[++_UP] = q[i].l;lsan[++_UP] = q[i].r;}sort(lsan + 1, lsan + _UP + 1);_UP = (int)(unique(lsan + 1, lsan + _UP + 1) - lsan - 1);for(int i=1; i<=N; i++){q[i].l = (int)(lower_bound(lsan + 1, lsan + _UP + 1, q[i].l) - lsan);q[i].r = (int)(lower_bound(lsan + 1, lsan + _UP + 1, q[i].r) - lsan);}Cover_Tree::Cover_Build(1, 1, _UP - 1);Segement_Tree_Beats::build(1, 0, _UP);for(int i=1; i<=N; i++){Cover_Tree::Cover_update(1, 1, _UP - 1, q[i].l, q[i].r - 1);Segement_Tree_Beats::update(1, 0, _UP, q[i].l, q[i].r - 1, q[i].h);printf("%lld\n", sum[1] + 2LL * s[1]);}}return 0;
}