特辑(线段树)

太久不打线段树手已生
Problem A: 高速公路 假期望题,分母显然为 \(C_{R - L + 1}^2\).把区间内所有子段的和求出来就万事了。
然后考虑线段树区间合并,似乎不可做。
这时SX红太阳郭老师开导了我,我们可以采取类似于树上染色的思路,考虑每条边可以被经过几次。
这就比较显然了,为\((R - i + 1)(i - L + 1)\).那么分子就是\(\sum \limits _{i = L} ^ R (R - i + 1)(i - L + 1) w_i\).
化简一下就是 \(\sum \limits _{i = L} ^ R (R - L + 1 - LR)w_i + (L + R) i w_i - i^2 w_i\).
线段树记3个tag:\(s_1 = w_i, s_2 = i w_i, s_3 = i^2 w_i\).
【特辑(线段树)】区间合并直接加起来。
再考虑修改边权,就是加个 \(v (R - L + 1 - LR)\) \(v (L + R) \sum i\) 和 $ -v i ^2$.
再记\(s_4 = \sum i, s_5 = \sum i^2\).
这道题就完了。
注意坑点:

  1. 给的是点,我们维护的是线段,需要处理一下
  2. 能开 long long 就开 long long !!别吝啬!!如果你WA20了,大约就是该开的long long没开
#include #define ll long longconst int N = 100000 + 233; ll n, m, sum[5]; char opt[5]; struct SegTree { ll l, r, s[8], tag; } t[N << 2]; inline void Pushup(ll p) { for (int i = 1; i <= 3; i++) t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i]; }ll gcd(ll x, ll y) { return y == 0 ? x : gcd(y, x % y); }void Build(ll p, ll l, ll r) { t[p].l = l, t[p].r = r; if (l == r) return (void) (t[p].s[4] = l, t[p].s[5] = l * l); ll mid = (l + r) >> 1; Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r); for (int i = 4; i <= 5; i++) t[p].s[i] = t[p << 1].s[i] + t[p << 1 | 1].s[i]; }inline void Add(ll p, ll k) { t[p].s[1] += (t[p].r - t[p].l + 1) * k; t[p].s[2] += k * t[p].s[4]; t[p].s[3] += k * t[p].s[5]; t[p].tag += k; }inline void Pushdown(ll p) { Add(p << 1, t[p].tag), Add(p << 1 | 1, t[p].tag); t[p].tag = 0; }void Change(ll p, ll l, ll r, ll v) { if (l <= t[p].l && r >= t[p].r) return (void) Add(p, v); ll mid = (t[p].l + t[p].r) >> 1; if (t[p].tag) Pushdown(p); if (l <= mid) Change(p << 1, l, r, v); if (r > mid) Change(p << 1 | 1, l, r, v); Pushup(p); }void Ask(ll p, ll l, ll r) { if (l <= t[p].l && r >= t[p].r) { for (int i = 1; i <= 3; i++) sum[i] += t[p].s[i]; return; } ll mid = (t[p].l + t[p].r) >> 1; if (t[p].tag) Pushdown(p); if (l <= mid) Ask(p << 1, l, r); if (r > mid) Ask(p << 1 | 1, l, r); }inline void print(ll x, ll y) { ll g = gcd(x, y); printf("%lld/%lld\n", x / g, y / g); }signed main() { scanf("%lld%lld", &n, &m); Build(1, 1, n); for (ll i = 1, l, r; i <= m; i++) { ll v; scanf("%s%lld%lld", opt, &l, &r); r--; if (opt[0] == 'C') { scanf("%lld", &v), Change(1, l, r, v); } else { sum[1] = sum[2] = sum[3] = 0; Ask(1, l, r); ll a = (r - l + 1 - l * r) * sum[1] + (r + l) * sum[2] - sum[3]; ll b = (r - l + 2) * (r - l + 1) / 2; print(a, b); } } return 0; }

Problem D:排序 第四次听这题(
第一次在SJZEZ听死宅邢泽宇讲
第二次在SDFZ听高胜寒鸽鸽讲
第三次在TYWZ听真-SX红太阳李嘉图聚聚讲
第四次在HZ听考拉巨巨讲
真实大众题(
本题最重要的一点就是询问只有一个位置,而答案显然具有单调性,你二分就完事
给排列排序太磨叽,转成01序列,0表示小于,1为大于等于,这样就可以用线段树维护“排序”的过程。
然而本题数据过水,桶排神优化一下也能过(((
#include const int N = 100005 + 233; int n, m, q, ans, a[N]; struct Command { int l, r, op; } cmd[N]; struct SegTree { int l, r, sum, tag; #define l(p) tree[p].l #define r(p) tree[p].r #define sum(p) tree[p].sum #define tag(p) tree[p].tag #define ls(p) p << 1 #define rs(p) p << 1 | 1 } tree[N << 2]; inline int R() { int a = 0; char c = getchar(); while (!isdigit(c)) c = getchar(); while (isdigit(c)) a = a * 10 + c - '0', c = getchar(); return a; }void Build(int p, int l, int r, int v) { l(p) = l, r(p) = r, tag(p) = -1; if (l == r) return (void) (sum(p) = a[l] >= v); int mid = (l + r) >> 1; Build(ls(p), l, mid, v), Build(rs(p), mid + 1, r, v); sum(p) = sum(ls(p)) + sum(rs(p)); }void Pushdown(int p) { if (tag(p) != -1) { sum(ls(p)) = (r(ls(p)) - l(ls(p)) + 1) * tag(p); sum(rs(p)) = (r(rs(p)) - l(rs(p)) + 1) * tag(p); tag(ls(p)) = tag(rs(p)) = tag(p); tag(p) = -1; } }void Change(int p, int l, int r, int v) { if (l <= l(p) && r >= r(p)) { sum(p) = (r(p) - l(p) + 1) * v; tag(p) = v; } else { Pushdown(p); int mid = (l(p) + r(p)) >> 1; if (l <= mid) Change(ls(p), l, r, v); if (r > mid) Change(rs(p), l, r, v); sum(p) = sum(ls(p)) + sum(rs(p)); } }int Query(int p, int l, int r) { if (l <= l(p) && r >= r(p)) return sum(p); Pushdown(p); int mid = (l(p) + r(p)) >> 1, ret = 0; if (l <= mid) ret += Query(ls(p), l, r); if (r > mid) ret += Query(rs(p), l, r); return ret; }bool Check(int x) { Build(1, 1, n, x); for (int i = 1; i <= m; i++) { int cnt = Query(1, cmd[i].l, cmd[i].r); if (cnt != 0 && cnt != cmd[i].r - cmd[i].l + 1) { if (cmd[i].op) { Change(1, cmd[i].l, cmd[i].l + cnt - 1, 1); Change(1, cmd[i].l + cnt, cmd[i].r, 0); } else { Change(1, cmd[i].l, cmd[i].r - cnt, 0); Change(1, cmd[i].r - cnt + 1, cmd[i].r, 1); } } } return Query(1, q, q); }signed main() { n = R(), m = R(); for (int i = 1; i <= n; i++) a[i] = R(); for (int i = 1; i <= m; i++) cmd[i].op = R(), cmd[i].l = R(), cmd[i].r = R(); q = R(); int l = 1, r = n, mid; while (l <= r) { mid = (l + r) >> 1; if (Check(mid)) { ans = mid; l = mid + 1; } else r = mid - 1; } return !printf("%d\n", ans); }

Problem C:Monotonicity 2 首先我们可以得到一个DP方程:\(f[i] = max{f[j] + 1}\).
这个方程真是太简洁明了啦(雾,然后ning干必死
考拉的主人都说这是线段树优化DP了,那我们就考虑线段树。
我们要找出最大的f[j],那我们就开三棵线段树,给每个符号开一棵,都用来维护区间最大值。
这个线段树应该是建立在值域上的,用来存DP值。
查询时把三种符号的答案都求出来,取最大值。再把求出来的DP的值插到当前符号的线段树里。
这种优化方式可以让我们找最大的f[j]之类的线段树容易u维护的东西时更快一点,感觉可能会蛮通用一点。
#include const int N = 1000005; int n, k, a[N], op[N], ans, a_mx, f[N]; struct SegTree { int l, r, mx; } t[N << 2][4]; void Build(int p, int l, int r) { for (int i = 1; i <= 3; i++) t[p][i].l = l, t[p][i].r = r, t[p][i].mx = 0; if (l == r) return; int mid = (l + r) >> 1; Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r); }void Pushup(int p, int op) { t[p][op].mx = std::max(t[p << 1][op].mx, t[p << 1 | 1][op].mx); }void Change(int p, int x, int v, int op) { if (t[p][op].l == t[p][op].r) return (void) (t[p][op].mx = std::max(t[p][op].mx, v)); int mid = (t[p][op].l + t[p][op].r) >> 1; if (x <= mid) Change(p << 1, x, v, op); if (x > mid) Change(p << 1 | 1, x, v, op); Pushup(p, op); }int Query(int p, int l, int r, int op) { if (l <= t[p][op].l && r >= t[p][op].r) return t[p][op].mx; int mid = (t[p][op].l + t[p][op].r) >> 1, ret = 0; if (l <= mid) ret = std::max(ret, Query(p << 1, l, r, op)); if (r > mid) ret = std::max(ret, Query(p << 1 | 1, l, r, op)); return ret; } signed main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a_mx = std::max(a_mx, a[i]); for (int i = 1; i <= k; i++) { char o[4]; scanf("%s", o); if (o[0] == '>') op[i] = 1; else if (o[0] == '=') op[i] = 2; else op[i] = 3; } Build(1, 1, a_mx); for (int i = 1; i <= n; i++) { int ans_1 = Query(1, a[i] + 1, a_mx, 1) + 1; int ans_2 = Query(1, a[i], a[i], 2) + 1; int ans_3 = Query(1, 1, a[i] - 1, 3) + 1; //std::cout << ans_1 << " " << ans_2 << " " << ans_3 << "\n"; f[i] = std::max(f[i], std::max(ans_1, std::max(ans_2, ans_3))); ans = std::max(f[i], ans); Change(1, a[i], f[i], op[(f[i] - 1) % k + 1]); } return !printf("%d\n", ans); }

Problem B:CPU监控 我真的佛了,标记下传神题
第一眼就秒出思路,维护一个max和一个历史最大值hmax,维护加法add,维护改变set。
然而这样是布星的。想一种情况,你有一个add,如果下传下去下面的max就会成为新的hmax,但有个set截了胡,把这个add覆盖掉了,那这个add还没更新答案就挂掉了,答案就错了。
我们的问题既然是出现在了这里,我们就再维护一个截至到上次pushdown的最大add hadd和最大set hset。
然后就是喜闻乐见的pushdown函数的设计了
首先有一个思路,就是先用父节点传下来的h-信息更新了子节点的h-信息,再更新子节点的普通信息。
pushdown这部分的思路写在了代码注释里。
还是说个坑点:建树和pushdown结束后记得给(h)set赋个初值。由于有可能出现负数,你这初值得是负的,-INF。
再说下我自己的Sb错误:query_history是直接copy的query_now,change是直接copy的add,导致我不断在change里调用add。。。。复制粘贴需谨慎啊喂!!!!一晚上啊!!!!我猛男落泪了。。。
像这样令人口区的线段树毒瘤题。。当然是很多了(逃,比如[SCOI2011]棘手的操作,[SDOI2017]相关分析,这些提题有一个共性特点就是tag之间的关系太过复杂,如果没想清就码码码很容易陷入混沌之中。所以在写这种毒瘤题的时候最好给pushdown列个草稿,把自己分类讨论的if里的condition和下方tag发方式列出来,就是类似于伪代码的东西,不然边写代码边写很容易想不清,闷声代码1小时,劲爆调试一晚上。。。
#include const int N = 1000000 + 2333, INF = 0x3f3f3f3f; int n, m, a[N]; struct SegTree { int l, r, add, hadd, set, hset, mx, hmx; } t[N << 2]; void pushup(int p) { t[p].mx = std::max(t[p << 1].mx, t[p << 1 | 1].mx); t[p].hmx = std::max(t[p << 1].hmx, t[p << 1 | 1].hmx); }void pushdown(int p) { //迫真for循环减少码量 for (int i = (p << 1); i <= (p << 1 | 1); i++) { //先把几个历史最大值维护了 t[i].hmx = std::max(t[i].hmx, std::max(t[p].hset, t[p].hadd + t[i].mx)); //用his信息先更新hmax if (t[i].set != -INF) t[i].hset = std::max(t[i].hset, t[i].set + t[p].hadd); //下放掉hadd,儿子有set就更新了hset else t[i].hadd = std::max(t[i].hadd, t[p].hadd + t[i].add); //否则更新hadd t[i].hset = std::max(t[i].hset, t[p].hset); //下放hset if (t[p].add) { //下放add if (t[i].set != -INF) t[i].set += t[p].add; //有set直接叠加 else t[i].add += t[p].add; //没set加给add t[i].mx += t[p].add; } if (t[p].set != -INF) t[i].mx = t[i].set = t[p].set, t[i].add = 0; //set覆盖就完事了,add没用了直接清零 t[i].hset = std::max(t[i].set, t[i].hset); t[i].hadd = std::max(t[i].add, t[i].hadd); } t[p].set = t[p].hset = -INF, t[p].add = t[p].hadd = 0; }void Build(int p, int l, int r) { t[p] = {l, r, 0, 0, -INF, -INF, -INF, -INF}; if (l == r) return (void) (t[p].mx = t[p].hmx = a[l]); int mid = (l + r) >> 1; Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r); t[p].mx = t[p].hmx = std::max(t[p << 1].mx, t[p << 1 | 1].mx); }int query_now(int p, int l, int r) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return t[p].mx; int mid = (t[p].l + t[p].r) >> 1, ret = -INF; if (l <= mid) ret = std::max(ret, query_now(p << 1, l, r)); if (r > mid) ret = std::max(ret, query_now(p << 1 | 1, l, r)); pushup(p); return ret; }int query_history(int p, int l, int r) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return t[p].hmx; int mid = (t[p].l + t[p].r) >> 1, ret = -INF; if (l <= mid) ret = std::max(ret, query_history(p << 1, l, r)); if (r > mid) ret = std::max(ret, query_history(p << 1 | 1, l, r)); pushup(p); return ret; }void add(int p, int l, int r, int d) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return (void) (t[p].add += d, t[p].hadd += d, t[p].mx += d, t[p].hmx = std::max(t[p].hmx, t[p].mx)); int mid = (t[p].l + t[p].r) >> 1; if (l <= mid) add(p << 1, l, r, d); if (r > mid) add(p << 1 | 1, l, r, d); pushup(p); }void change(int p, int l, int r, int d) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return (void) (t[p].set = t[p].mx = t[p].hset = d, t[p].hmx = std::max(t[p].hmx, t[p].mx)); int mid = (t[p].l + t[p].r) >> 1; if (l <= mid) change(p << 1, l, r, d); if (r > mid) change(p << 1 | 1, l, r, d); pushup(p); }signed main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &m); Build(1, 1, n); for (int i = 1; i <= m; i++) { char op[5]; int x, y, z; scanf("%s%d%d", op, &x, &y); if (op[0] == 'Q') printf("%d\n", query_now(1, x, y)); else if (op[0] == 'A') printf("%d\n", query_history(1, x, y)); else if (op[0] == 'P') scanf("%d", &z), add(1, x, y, z); else if (op[0] == 'C') scanf("%d", &z), change(1, x, y, z); } return 0; }

某人嫌弃我的120字符规范,下面是80字符规范版
#include const int N = 1000000 + 2333, INF = 0x3f3f3f3f; int n, m, a[N]; struct SegTree { int l, r, add, hadd, set, hset, mx, hmx; } t[N << 2]; void pushup(int p) { t[p].mx = std::max(t[p << 1].mx, t[p << 1 | 1].mx); t[p].hmx = std::max(t[p << 1].hmx, t[p << 1 | 1].hmx); }void pushdown(int p) { //迫真for循环减少码量 for (int i = (p << 1); i <= (p << 1 | 1); i++) { //先把几个历史最大值维护了 t[i].hmx = std::max(t[i].hmx, std::max(t[p].hset, t[p].hadd + t[i].mx)); if (t[i].set != -INF) t[i].hset = std::max(t[i].hset, t[i].set + t[p].hadd); else t[i].hadd = std::max(t[i].hadd, t[p].hadd + t[i].add); t[i].hset = std::max(t[i].hset, t[p].hset); //下放hset if (t[p].add) { //下放add if (t[i].set != -INF) t[i].set += t[p].add; //有set直接叠加 else t[i].add += t[p].add; //没set加给add t[i].mx += t[p].add; } if (t[p].set != -INF) t[i].mx = t[i].set = t[p].set, t[i].add = 0; t[i].hset = std::max(t[i].set, t[i].hset); t[i].hadd = std::max(t[i].add, t[i].hadd); } t[p].set = t[p].hset = -INF, t[p].add = t[p].hadd = 0; }void Build(int p, int l, int r) { t[p] = {l, r, 0, 0, -INF, -INF, -INF, -INF}; if (l == r) return (void) (t[p].mx = t[p].hmx = a[l]); int mid = (l + r) >> 1; Build(p << 1, l, mid), Build(p << 1 | 1, mid + 1, r); t[p].mx = t[p].hmx = std::max(t[p << 1].mx, t[p << 1 | 1].mx); }int query_now(int p, int l, int r) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return t[p].mx; int mid = (t[p].l + t[p].r) >> 1, ret = -INF; if (l <= mid) ret = std::max(ret, query_now(p << 1, l, r)); if (r > mid) ret = std::max(ret, query_now(p << 1 | 1, l, r)); pushup(p); return ret; }int query_history(int p, int l, int r) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return t[p].hmx; int mid = (t[p].l + t[p].r) >> 1, ret = -INF; if (l <= mid) ret = std::max(ret, query_history(p << 1, l, r)); if (r > mid) ret = std::max(ret, query_history(p << 1 | 1, l, r)); pushup(p); return ret; }void add(int p, int l, int r, int d) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return (void) (t[p].add += d, t[p].hadd += d, t[p].mx += d, t[p].hmx = std::max(t[p].hmx, t[p].mx)); int mid = (t[p].l + t[p].r) >> 1; if (l <= mid) add(p << 1, l, r, d); if (r > mid) add(p << 1 | 1, l, r, d); pushup(p); }void change(int p, int l, int r, int d) { if (t[p].l != t[p].r) pushdown(p); if (l <= t[p].l && r >= t[p].r) return (void) (t[p].set = t[p].mx = t[p].hset = d, t[p].hmx = std::max(t[p].hmx, t[p].mx)); int mid = (t[p].l + t[p].r) >> 1; if (l <= mid) change(p << 1, l, r, d); if (r > mid) change(p << 1 | 1, l, r, d); pushup(p); }signed main() { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &m); Build(1, 1, n); for (int i = 1; i <= m; i++) { char op[5]; int x, y, z; scanf("%s%d%d", op, &x, &y); if (op[0] == 'Q') printf("%d\n", query_now(1, x, y)); else if (op[0] == 'A') printf("%d\n", query_history(1, x, y)); else if (op[0] == 'P') scanf("%d", &z), add(1, x, y, z); else if (op[0] == 'C') scanf("%d", &z), change(1, x, y, z); } return 0; }

转载于:https://www.cnblogs.com/gekoo/p/11240280.html

    推荐阅读