bzoj 1171: 大sz的游戏, bzoj 2892: 强袭作战

标记永久化，线段树套单调队列。

标记永久化的好处在于可以减少下传标记的时间。

如果有些标记很难下传，但是打标记的顺序对结果没有影响，就可以用标记永久化

比如说 支持矩阵加、矩阵求和就可以用带标记永久化的二维线段树来做——> 用第二维线段树维护第一维线段树上的标记

标记永久化具体做法：维护两种值，A、B。

修改：如果区间覆盖了一个节点，修改A，返回。如果经过一个节点，修改B，递归修改两个子树

查询：如果区间覆盖了一个节点，返回B。如果经过了一个节点，递归查询子树并加上当前节点的A值

另：（大雾

一维：返回一个变量的值

二维：区间求和

三维：矩形求和

四维：矩形加、矩形求和

五维：矩形加、矩形求和，带撤销

六维：矩形加、矩形求和，可持久化

七维：？

#include <bits/stdc++.h>
#define N 1001000
#define M 6000000
#define mp make_pair
#define fr first
#define sc second
#define pI pair <int, int>
#define INF 1000000000
#define int unsigned
using namespace std;
int n, L;
int lb[M], rb[M], lc[M], rc[M];
list <pI> tg[M], su[M];
int xi[N], yi[N], li[N], px[N];
int tot, ss, tim;
int build(int l, int r)
{int nw = ++ ss;lb[nw] = l; rb[nw] = r;if (l != r)lc[nw] = build(l, (l + r) / 2),rc[nw] = build((l + r) / 2 + 1, r);return nw;
}
void add(int t, int l, int r, pI s)
{if (l <= lb[t] && rb[t] <= r){while (!tg[t].empty() && tg[t].back().sc >= s.sc) tg[t].pop_back();tg[t].push_back(s);return;}while (!su[t].empty() && su[t].back().sc >= s.sc) su[t].pop_back();su[t].push_back(s);if (l <= rb[lc[t]]) add(lc[t], l, r, s);if (r >= lb[rc[t]]) add(rc[t], l, r, s);
}
int sum(int t, int l, int r)
{int s;while (!tg[t].empty() && tg[t].front().fr < tim)tg[t].pop_front();if (!tg[t].empty()) s = tg[t].front().sc;else s = INF;while (!su[t].empty() && su[t].front().fr < tim)su[t].pop_front();if (l <= lb[t] && rb[t] <= r){if (!su[t].empty()) s = min(s, su[t].front().sc);return s;}if (l <= rb[lc[t]]) s = min(s, sum(lc[t], l, r));if (r >= lb[rc[t]]) s = min(s, sum(rc[t], l, r));    return s;
}
int f[N];
signed main()
{scanf("%d%d", &n, &L);for (int i = 2; i <= n; ++ i)scanf("%d%d%d", &xi[i], &yi[i], &li[i]),px[++ tot] = xi[i],px[++ tot] = yi[i];sort(px + 1, px + tot + 1);xi[1] = px[1]; yi[1] = px[tot];tot = unique(px + 1, px + tot + 1) - px - 1;for (int i = 1; i <= n; ++ i)xi[i] = lower_bound(px + 1, px + tot + 1, xi[i]) - px,yi[i] = lower_bound(px + 1, px + tot + 1, yi[i]) - px;build(1, tot);//printf("%d\n", ss);add(1, 1, tot, mp(L, 0));for (int i = 2; i <= n; ++ i){//if (i == 182796)//    puts("233");tim = li[i];f[i] = sum(1, xi[i], yi[i]) + 1;add(1, xi[i], yi[i], mp(li[i] + L, f[i])); printf("%d\n", f[i] > n? -1: f[i]);}
}

转载于:.html

bzoj 1171: 大sz的游戏, bzoj 2892: 强袭作战

标记永久化，线段树套单调队列。

标记永久化的好处在于可以减少下传标记的时间。

如果有些标记很难下传，但是打标记的顺序对结果没有影响，就可以用标记永久化

比如说 支持矩阵加、矩阵求和就可以用带标记永久化的二维线段树来做——> 用第二维线段树维护第一维线段树上的标记

标记永久化具体做法：维护两种值，A、B。

修改：如果区间覆盖了一个节点，修改A，返回。如果经过一个节点，修改B，递归修改两个子树

查询：如果区间覆盖了一个节点，返回B。如果经过了一个节点，递归查询子树并加上当前节点的A值

另：（大雾

一维：返回一个变量的值

二维：区间求和

三维：矩形求和

四维：矩形加、矩形求和

五维：矩形加、矩形求和，带撤销

六维：矩形加、矩形求和，可持久化

七维：？

#include <bits/stdc++.h>
#define N 1001000
#define M 6000000
#define mp make_pair
#define fr first
#define sc second
#define pI pair <int, int>
#define INF 1000000000
#define int unsigned
using namespace std;
int n, L;
int lb[M], rb[M], lc[M], rc[M];
list <pI> tg[M], su[M];
int xi[N], yi[N], li[N], px[N];
int tot, ss, tim;
int build(int l, int r)
{int nw = ++ ss;lb[nw] = l; rb[nw] = r;if (l != r)lc[nw] = build(l, (l + r) / 2),rc[nw] = build((l + r) / 2 + 1, r);return nw;
}
void add(int t, int l, int r, pI s)
{if (l <= lb[t] && rb[t] <= r){while (!tg[t].empty() && tg[t].back().sc >= s.sc) tg[t].pop_back();tg[t].push_back(s);return;}while (!su[t].empty() && su[t].back().sc >= s.sc) su[t].pop_back();su[t].push_back(s);if (l <= rb[lc[t]]) add(lc[t], l, r, s);if (r >= lb[rc[t]]) add(rc[t], l, r, s);
}
int sum(int t, int l, int r)
{int s;while (!tg[t].empty() && tg[t].front().fr < tim)tg[t].pop_front();if (!tg[t].empty()) s = tg[t].front().sc;else s = INF;while (!su[t].empty() && su[t].front().fr < tim)su[t].pop_front();if (l <= lb[t] && rb[t] <= r){if (!su[t].empty()) s = min(s, su[t].front().sc);return s;}if (l <= rb[lc[t]]) s = min(s, sum(lc[t], l, r));if (r >= lb[rc[t]]) s = min(s, sum(rc[t], l, r));    return s;
}
int f[N];
signed main()
{scanf("%d%d", &n, &L);for (int i = 2; i <= n; ++ i)scanf("%d%d%d", &xi[i], &yi[i], &li[i]),px[++ tot] = xi[i],px[++ tot] = yi[i];sort(px + 1, px + tot + 1);xi[1] = px[1]; yi[1] = px[tot];tot = unique(px + 1, px + tot + 1) - px - 1;for (int i = 1; i <= n; ++ i)xi[i] = lower_bound(px + 1, px + tot + 1, xi[i]) - px,yi[i] = lower_bound(px + 1, px + tot + 1, yi[i]) - px;build(1, tot);//printf("%d\n", ss);add(1, 1, tot, mp(L, 0));for (int i = 2; i <= n; ++ i){//if (i == 182796)//    puts("233");tim = li[i];f[i] = sum(1, xi[i], yi[i]) + 1;add(1, xi[i], yi[i], mp(li[i] + L, f[i])); printf("%d\n", f[i] > n? -1: f[i]);}
}

转载于:.html