// created on 23.05.13
目录A. 差值
考虑求长度为 \(i\) 的答案，肯定是长度 \(\geq i\) 的后缀，按照字典序排序后，相邻两个求解。
所以考虑倒着扫，每次对于 \(i\) 的后缀找到排名前后第一个后缀，求出两个长度为 \(i\) 的解。更新解（比大小）的部分用哈希和二分解决即可。
然后最后只要倒着贡献，用 \(i+1\) 的最优解贡献 \(i\) 即可（非 \(i+1\) 最有解一定无用）。
时间复杂度 \(O(n\log n)\) 。
B. 基础循环结构练习题
考虑非严格递增的部分，令 \(d_i=b_i-b_{i-1}\)，枚举 \(i\) 从 \(n\) 到 \(1\)，设计如下策略：
- 此时 \(i\) 是全局最大值，通过一次 mod 将其变为 \(0\) 。
- 全局加 \(d_i\) 。
注意到每次 mod 不会影响后缀，并且一个位置最终的值就是前侧 \(\sum d\) 。我们用 \(2n\) 次操作达到了目的。
如果非递增的话，考虑最后一步的 mod 。倒着做，相当于用 \(c=\max b+1\) 来调整 \(b\) 使得其为非严格递增即可。恰好只要多一次操作。
C. 基础计算几何练习题
观察一下，我们将点对按照点对间距离排序，每次取出距离最小的点对集合 \(S=\{(x_1,y_1),(x_2,y_2),\cdots\}\)，然后对于 \(x_i,y_i\)，如果之前两者答案都是 false，那么一起改成 true 。
怎么观察出来的？从链考虑，先考虑间隔最小的，肯定一步到位全是 true 。然后是次小的，如果和最小不相交也是 true 了，否则肯定不操作，不然就输了。
那么至此可以写出 50pts 。
我们用 KDT 维护每个点与周围 未删除点 的最小距离，并打包成二元组存入堆。每次取出堆头，检查最小距离是否是对的（可能与之形成最小距离的点已经被删了）。在踢掉所有非法的最小距离后，就得到了当前全局最小距离。接着不断地取出，拥有全局最小距离的点，并且这一轮我们会将这些点全部删除。如此往复直到点剩下小于两个。
时间复杂度未知（我们只需要注意一个点被错误取出的次数，感受一下这个次数很小，不知道能不能和平面最近点对一样分析？），但其实速度还行。
但其实有更好的做法：将网格划分成若干个 \(2^i\times 2^i\) 的格子，每次一个格子里只剩下至多一个点，查询时只需要考虑格子周围的格子中的点即可。
即，从 \(i=0\) 开始做，每次将 \(O(n)\) 个平面最近点对拿出来按照距离排序，然后按照暴力的方式模拟即可。此时 \(2^{i+1}\times 2^{i+1}\) 的格子中至多剩下一个点，否则在这一步肯定消掉了。于是，我们得到了 \(O(n\log V)\) 的做法。
D. 永恒悲剧
对于一个位置 \(1\leq i\leq n\) 而言，一个右端点 \(r\) 存在 \(p\leq r\) 满足合法左端点为 \(l\leq p\) 且稳定值一样。
\(p\) 的要求是：可以在 \([p+1,r]\) 中找到一个，opt 不同操作相交的位置 \(p'\) 。我们记 \(nxt_p\) 表示 \(p\) 后第一个满足要求的位置，\(lst_p\) 表示 \(p\) 前第一个满足要求的位置。
那么对于 \(r\) 而言有 \(p=\max\{lst_1,lst_2,\cdots,lst_r\}\) 。当有多个 \(i\) 的 \(lst_i\) 相同时，显然只要保留最小的 \(i\) 。此时若保留的 \(i\) 为 \(t\)，那么 \(nxt_{lst_t}=t\) 也是必然成立的。对于 \(i,j\) 若 \(lst_i=j,nxt_j=i\) 就记 \((j,i)\) 为一个 "稳定对" 。
不妨假设 \(p\) 是 max 操作，那么最后 \(r\) 得到的贡献为 \(p\times \min\{c_{p+1},\cdots,c_r\}\) 。
外层直接上线段树分治，修改 / 撤销 \(lst_i,nxt_i\)：每次插入 \(i\) 只要找到 \(lst_i,nxt_i\) 并检查是否形成 "稳定对" 即可。到了叶子就做一遍贡献（即对 \(ans_1,ans_2,\cdots,ans_r\) 贡献答案）。
于是问题来到怎么处理答案的贡献。考虑用线段树维护，并定义如下函数：
- \(\mathbf{push}(x,l,r,p,lim_c,c)\) 表示：\([x,l,r]\) 节点，前侧 \(lst_i\) 的最大值为 \(p\)，\(p\) 后续 \(c\) 的最小值（或最大值）为 \(lim_c\) 。一共要对 \(ans_i,l\leq i\leq r\) 贡献 \(c\) 次。
- \(\mathbf{push_{fix_p}}(x,l,r,type,lim_c,c)\) 表示：在 \(p\) 已经不会在 \([x,l,r]\) 中改变时，\(type\) 表示 \(p\) 的类型，\(lim_c\) 同理，\(c\) 同理（为了方便，可以把 \(p\) 乘入 \(c\) 中）。
在一次 \(\mathbf{push}(x,l,r,p,lim_c,c)\) 中：
- 如果到了叶子，更新并直接算贡献。
- 如果左侧 \(\max lst_i\) 比 \(p\) 大，那么往右侧打标记表示 "右侧节点被计算 \(c\) 次贡献"。此时 \(p,lim_c\) 不会影响右侧节点，递归进入左侧。
- 否则，左侧区间中 \(p\) 不会改变，用 \(\mathbf{push_{fix_p}}\) 递归计算贡献。然后再递归进入右侧继续计算。
在一次 \(\mathbf{push_{fix_p}}(x,l,r,type,lim_c,c)\) 中：
- 如果到了叶子，更新并直接算贡献。
- 如果左侧对 \(lim_c\) 没有影响，那么所有位置都加上 \(lim_c\times c\)，打标记处理。
- 否则，递归进入左侧计算。此时到右侧时，\(lim_c\) 只取决于左侧，所以可以在 \(x\) 打标记表示 " \(type\) 固定，用左侧对应 \(lim_c\)，递归进入右侧贡献系数加上 \(c\) "。
\(\mathbf{push_{fix_p}}\) 是 \(O(\log m)\) 的，\(\mathbf{push}\) 是 \(O(\log^2 m)\) 的。一共 \(O(m\log n)\) 次单点修改，于是 pushdown 的次数是 \(O(m\log n\log m)\) 。每次 pushdown 需要根据标记用 \(\mathbf{push},\mathbf{push_{fix_p}}\) 计算代价，那么复杂度是 \(O(m\log n\log^3 m)\) 的，但是常数较小。
//
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug(...) fprintf (stderr, __VA_ARGS__)
#define fi first
#define se second
#define lep(i, l, r) for (int i = (l), i##_end = (r); i <= i##_end; ++ i)
#define rep(i, r, l) for (int i = (r), i##_end = (l); i >= i##_end; -- i)
char _c; bool _f; template <class T> inline void IN (T & x) {
x = 0, _f = 0; while (_c = getchar (), ! isdigit (_c)) if (_c == '-') _f = 1;
while (isdigit (_c)) x = x * 10 + _c - '0', _c = getchar (); if (_f) x = - x;
}
template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }
const int N = 1e5 + 5;
const int INF = 1e9;
int n, m;
ll ans[N];
pair <int, int> opt[N];
// {{{ segment tree
#define lc ((x) << 1)
#define rc ((x) << 1 | 1)
#define mid ((l + r) >> 1)
bool act[N];
struct node {
int mi_c, mx_c, p, p_c;
ll l_to_r, fix_p[2], ans;
} t[N << 2];
void build (int x, int l, int r) {
t[x].mi_c = INF, t[x].mx_c = -1;
if (l == r) return t[x].p_c = opt[l].fi, void ();
build (lc, l, mid), build (rc, mid + 1, r);
}
inline void pushup (int x) {
t[x].mi_c = min (t[lc].mi_c, t[rc].mi_c);
t[x].mx_c = max (t[lc].mx_c, t[rc].mx_c);
if (t[lc].p > t[rc].p) {
t[x].p = t[lc].p;
if (opt[t[x].p].se == 1) t[x].p_c = min (t[lc].p_c, t[rc].mi_c);
if (opt[t[x].p].se == 2) t[x].p_c = max (t[lc].p_c, t[rc].mx_c);
} else {
t[x].p = t[rc].p, t[x].p_c = t[rc].p_c;
}
}
// {{{ pushdown
void push_fix_p (int x, int l, int r, int type, int p_c, ll buf) {
if (l == r) {
if (act[l]) {
if (type == 1 && opt[l].se == 2) chkmin (p_c, opt[l].fi);
if (type == 2 && opt[l].se == 1) chkmax (p_c, opt[l].fi);
}
ans[l] += 1ll * p_c * buf;
} else {
if ((type == 1 && t[lc].mi_c >= p_c) || (type == 2 && t[lc].mx_c <= p_c)) {
t[lc].ans += 1ll * p_c * buf;
push_fix_p (rc, mid + 1, r, type, p_c, buf);
} else {
t[x].fix_p[type - 1] += buf;
push_fix_p (lc, l, mid, type, p_c, buf);
}
}
}
void push (int x, int l, int r, int p, int p_c, int buf) {
if (l == r) {
if (act[l]) {
if (t[x].p > p) p = t[x].p, p_c = t[x].p_c;
else {
if (opt[p].se == 1 && opt[l].se == 2) chkmin (p_c, opt[l].fi);
if (opt[p].se == 2 && opt[l].se == 1) chkmax (p_c, opt[l].fi);
}
}
ans[l] += 1ll * p * p_c * buf;
} else {
if (t[lc].p >= p) {
t[x].l_to_r += buf;
push (lc, l, mid, p, p_c, buf);
} else {
if (p) push_fix_p (lc, l, mid, opt[p].se, p_c, 1ll * buf * p);
if (! p) push (rc, mid + 1, r, p, p_c, buf);
else {
if (opt[p].se == 1) push (rc, mid + 1, r, p, min (p_c, t[lc].mi_c), buf);
if (opt[p].se == 2) push (rc, mid + 1, r, p, max (p_c, t[lc].mx_c), buf);
}
}
}
}
inline void pushdown (int x, int l, int r) {
if (t[x].l_to_r) {
push (rc, mid + 1, r, t[lc].p, t[lc].p_c, t[x].l_to_r);
t[x].l_to_r = 0;
}
lep (o, 1, 2) if (t[x].fix_p[o - 1]) {
push_fix_p (rc, mid + 1, r, o, (o == 1 ? t[lc].mi_c : t[lc].mx_c), t[x].fix_p[o - 1]);
t[x].fix_p[o - 1] = 0;
}
}
// }}}
int lst[N], nxt[N];
void update (int x, int l, int r, int i) {
if (l == r) return t[x].p = lst[i], void ();
pushdown (x, l, r);
i <= mid ? update (lc, l, mid, i) : update (rc, mid + 1, r, i);
pushup (x);
}
void flip (int x, int l, int r, int i) {
if (l == r) {
act[i] ^= 1;
if (opt[i].se == 1) t[x].mx_c = act[i] ? opt[i].fi : -1;
if (opt[i].se == 2) t[x].mi_c = act[i] ? opt[i].fi : INF;
} else {
pushdown (x, l, r);
i <= mid ? flip (lc, l, mid, i) : flip (rc, mid + 1, r, i);
pushup (x);
}
}
/* lst and nxt */
int find_lst (int x, int l, int r, int i) {
if (l > i) return -1;
if (opt[i].se == 1 && t[x].mi_c > opt[i].fi) return -1;
if (opt[i].se == 2 && t[x].mx_c < opt[i].fi) return -1;
if (l == r) return l;
int ret = find_lst (rc, mid + 1, r, i);
return ~ ret ? ret : find_lst (lc, l, mid, i);
}
int find_nxt (int x, int l, int r, int i) {
if (r < i) return -1;
if (opt[i].se == 1 && t[x].mi_c > opt[i].fi) return -1;
if (opt[i].se == 2 && t[x].mx_c < opt[i].fi) return -1;
if (l == r) return l;
int ret = find_nxt (lc, l, mid, i);
return ~ ret ? ret : find_nxt (rc, mid + 1, r, i);
}
vector <pair <int, int> > s_nxt[21], s_lst[21];
inline void find_lst (int i, int & dep) {
int p = find_lst (1, 1, m, i);
if ( ~ p && find_nxt (1, 1, m, p) == i) {
if (nxt[p]) {
s_lst[dep].emplace_back ( nxt[p], p );
lst[nxt[p]] = 0, update (1, 1, m, nxt[p]);
}
s_nxt[dep].emplace_back ( p, nxt[p] ), nxt[p] = i;
s_lst[dep].emplace_back ( i, 0 ), lst[i] = p, update (1, 1, m, i);
}
}
inline void find_nxt (int i, int & dep) {
int p = find_nxt (1, 1, m, i);
if ( ~ p && find_lst (1, 1, m, p) == i) {
if (lst[p]) {
s_nxt[dep].emplace_back ( lst[p], p ), nxt[lst[p]] = 0;
}
s_nxt[dep].emplace_back ( i, 0 ), nxt[i] = p;
s_lst[dep].emplace_back ( p, lst[p] ), lst[p] = i, update (1, 1, m, p);
}
}
inline void join (int i, int & dep) {
flip (1, 1, m, i);
find_lst (i, dep), find_nxt (i, dep);
}
void collect (int x, int l, int r) {
if (l == r) return ans[l] += t[x].ans, void ();
pushdown (x, l, r);
if (t[x].ans) t[lc].ans += t[x].ans, t[rc].ans += t[x].ans;
collect (lc, l, mid), collect (rc, mid + 1, r);
}
#undef lc
#undef rc
#undef mid
// }}}
// {{{ divide
#define lc ((x) << 1)
#define rc ((x) << 1 | 1)
#define mid ((l + r) >> 1)
vector <int> stk[N << 2];
void insert (int x, int l, int r, int L, int R, int i) {
if (L <= l && r <= R) return stk[x].emplace_back (i), void ();
if (L <= mid) insert (lc, l, mid, L, R, i);
if (R > mid) insert (rc, mid + 1, r, L, R, i);
}
void divide (int x, int l, int r, int dep = 0) {
for (auto & i : stk[x]) join (i, dep);
if (l == r) push (1, 1, m, 0, 0, 1);
else {
divide (lc, l, mid, dep + 1);
divide (rc, mid + 1, r, dep + 1);
}
for (auto & i : stk[x]) flip (1, 1, m, i);
reverse (s_nxt[dep].begin (), s_nxt[dep].end ());
reverse (s_lst[dep].begin (), s_lst[dep].end ());
for (auto & [a, b] : s_nxt[dep]) nxt[a] = b;
for (auto & [a, b] : s_lst[dep]) lst[a] = b, update (1, 1, m, a);
s_nxt[dep].clear ();
s_lst[dep].clear ();
}
#undef lc
#undef rc
#undef mid
// }}}
signed main () {
IN (n), IN (m);
for (int op, l, r, c, i = 1; i <= m; ++ i) {
IN (op), IN (l), IN (r), IN (c);
opt[i] = { c, op };
insert (1, 1, n, l, r, i);
}
build (1, 1, m);
divide (1, 1, n);
collect (1, 1, m);
lep (i, 1, m) printf ("%lld%c", ans[i], " \n"[i == m]);
return 0;
}