可持久化数据结构
Posted Updated Notes7 minutes read (About 980 words)

可持久化数据结构

历史版本修改和查询，每一次操作生成一个历史版本。

知道可持久化思想就不难了。
大概就是对于每一个点可以丢到线段树上的叶子节点。
然后对于每一个历史版本，确定了根和每一个节点的左右节点那就知道了整棵树。
所以可以直接拿一个 root 数组来作为历史版本的信息存储。
然后显而易见地，发现对于每一个修改操作都会修改不超过 $\log n$ 个点。
形式化地，就是修改了当前节点到根节点路径上的所有节点。
所有信息都可以合并一下，然后更新 root 节点。

大概就没了，时间复杂度和空间复杂度均为 $N \log N$（猜的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int MAXN = 2e7 + 10;

struct seg { int l, r, val; } t[MAXN];
int n, Q, tot, a[N], rt[N];
int basic, opt, pos, val;

inline int New(int x) { t[++tot] = t[x]; return tot; }
inline int build(int x, int l, int r) {
  x = ++tot;
  if (l==r) { t[x].val = a[l]; return tot; }
  int mid = (l+r) >> 1;
  t[x].l = build(t[x].l, l, mid);
  t[x].r = build(t[x].r, mid+1, r);
  return x;
}

inline int upd(int x, int l, int r, int pos, int v) {
  x = New(x);
  if (l==r) { t[x].val = v; return x; }
  int mid = (l+r) >> 1;
  if (pos<=mid) t[x].l = upd(t[x].l, l, mid, pos, v);
  else t[x].r = upd(t[x].r, mid+1, r, pos, v);
  return x;
}

inline int query(int x, int l, int r, int pos) {
  if (l==r) return t[x].val;
  int mid = (l+r) >> 1;
  if (pos<=mid) return query(t[x].l, l, mid, pos);
  return query(t[x].r, mid+1, r, pos);
}

inline void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void print(int x) {
  if (x<0) { putchar('-'); x = -x; }
  if (x>9) print(x/10);
  putchar(x%10^48); return ;
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i) read(a[i]);
  rt[0] = build(0, 1, n);
  for (int i=1; i<=Q; ++i) {
    read(basic), read(opt), read(pos);
    if (opt==1) read(val), rt[i] = upd(rt[basic], 1, n, pos, val);
    else print(query(rt[basic], 1, n, pos)), puts(""), rt[i] = rt[basic];
  } return 0;
}

主席树入门题（？
这主席树还是静态的，那么我们可以乱搞了。
首先分块老哥靠边（

如果我们要找到区间第 $k$ 小那么是不是可以直接维护区间内某些值的个数
如果一段前缀某些数的个数和 $<k$ 那么可以直接遍历另外一半
所以直接想到了线段树的左儿子和右儿子 然后直接遍历搞

因为你这样显然是要建一个值域的是吧
然后因为值域你开不下啊，所以离散化一样，不改变相对关系
最后在询问值得时候代回去就可以了

重点是我们怎么维护前缀某些数个数和
你现在有一堆结构体 tree[N]
然后 $\forall \space 1 \le i \le n$，tree[i] 代表了一段前缀的信息

信息的具体处理方式可以参考这样：3 3 4 6 9 1 1 4 1

然后你离散化每一个位置维护的值就应该是其出现的次数
那么就变成这样了 3[1] 2[3] 2[4] 1[6] 1[9]
但是你每个前缀都建一颗线段树，时间复杂度抛开不说，你空间跑不了啊
然后发现每一个前缀都和前面处理的信息有极大的重复
所以参考上面的方法 直接共用一大堆节点，新建相当于 $\log N$ 了。

所以时间复杂度和空间复杂度都是 $N \log N$ 了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, Q, tot, a[N], b[N], tmp[N];
struct seg { int l, r, val; } t[N*20];

inline void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

inline int build(int l, int r) {
  int rt = ++tot; t[rt].val = 0;
  if (l<r) {
    int mid = (l+r) >> 1;
    t[rt].l = build(l, mid);
    t[rt].r = build(mid+1, r);
  } return rt;
}

inline int upd(int pre, int l, int r, int pos) {
  int rt = ++tot;
  t[rt].l = t[pre].l, t[rt].r = t[pre].r;
  t[rt].val = t[pre].val + 1;
  if (l<r) {
    int mid = (l+r) >> 1;
    if (pos<=mid) t[rt].l = upd(t[pre].l, l, mid, pos);
    else t[rt].r = upd(t[pre].r, mid+1, r, pos);
  } return rt;
}

inline int query(int x, int y, int l, int r, int rk) {
  if (l>=r) return l;
  int val = t[t[y].l].val - t[t[x].l].val;
  int mid = (l+r) >> 1;
  if (val>=rk) return query(t[x].l, t[y].l, l, mid, rk);
  else return query(t[x].r, t[y].r, mid+1, r, rk-val);
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i)
    read(a[i]), b[i] = a[i];
  sort(b+1, b+1+n);
  int Len = unique(b+1, b+1+n)-b-1;
  tmp[0] = build(1, Len);
  for (int i=1; i<=n; ++i) {
    int cur = lower_bound(b+1, b+1+Len, a[i])-b;
    tmp[i] = upd(tmp[i-1], 1, Len, cur);
  }
  while (Q--) {
    int l, r, k; read(l), read(r), read(k);
    int id = query(tmp[l-1], tmp[r], 1, Len, k);
    printf("%d\n", b[id]);
  } return 0;
}

tmp 维护的就是上述的根，然后常规处理。

好的，这些就是暂时的可持久化博客了。
Flag：树套树，懒标记专题，线性基，如果咕了 QQ 催我。

咕咕咕的动态淀粉质
Posted Updated Notes5 minutes read (About 775 words)

咕咕咕的动态淀粉质

膜拜动态淀粉质。

首先动态淀粉质主要处理的是树上路径问题的修改与查询。对于某一个点 $rt$ 来说，其子树中的简单路径可以分成两种情况。（无根树）

  • 经过 $rt$ 的，即可以理解为由 $rt$ 发散出去一条或两条路径。
  • 不经过 $rt$，可以通过处理 $rt$ 的子树来进行处理。

所以我们现在只需要考虑第一种情况。

所以我们可以寻找当前处理的树的分治中心 $x$。
对于每一个分治中心，我们都可以将其所有子树视为几个连通块，然后删掉当前的节点 $rt$，递归分别处理，这样递归，构成一棵点分树。

那么很显然点分树每一层代表的节点个数都是 $\Theta(N)$ 级别的。

然后最深的递归层数显然是这棵树的深度。
那么很显然对于无根树我们把其根赋值为重心即可。

假设最深深度为 $d$，那么点分树建出来时间复杂度为 $\Theta(Nd)$。
那么使得 $d$ 最小就应该将分治中心设为每一个树上连通块的重心。
此时时间复杂度理论上最小，为 $\Theta(N \log N)$ 级别。

然后就这样递归乱搞就可以了。

淀粉质 AC 代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int M = 1e7 + 10;

int n, m, cnt, rt, totsiz, tot, head[N<<1];
int Maxi[N], siz[N], dist[N], Dis[N];
bool Exist[M], vis[N], hasret[N];
struct Edge { int to, nxt, val; } e[N<<1];
int query[N], MaxQue;

void addEdge(int u, int v, int w) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  e[cnt].val = w;
  head[u] = cnt; return ;
}

void calcsiz(int cur, int fa) {
  siz[cur] = 1, Maxi[cur] = 0;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    calcsiz(to, cur);
    Maxi[cur] = max(Maxi[cur], siz[to]);
    siz[cur] += siz[to];
  }
  Maxi[cur] = max(Maxi[cur], totsiz - siz[cur]);
  if (Maxi[cur] < Maxi[rt]) rt = cur;
  return ;
}

void calcdist(int cur, int fa) {
  Dis[++tot] = dist[cur];
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    dist[to] = dist[cur] + e[i].val;
    calcdist(to, cur);
  } return ;
}

queue <int> stat;
void dfs(int cur, int fa) {
  Exist[0] = vis[cur] = true; stat.push(0);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    dist[to] = e[i].val;
    calcdist(to, cur);
    for (int j=1; j<=m; ++j)
      for (int k=1; k<=tot; ++k)
        if (query[j]>=Dis[k])
          hasret[j] |= Exist[query[j]-Dis[k]];
    for (int j=1; j<=tot; ++j)
      if (Dis[j]<M)
        stat.push(Dis[j]), Exist[Dis[j]] = true;
    tot = 0;
  }
  while (!stat.empty())
    Exist[stat.front()] = false, stat.pop();
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa || vis[to]) continue;
    totsiz = siz[to], rt = 0;
    Maxi[0] = INT_MAX;
    calcsiz(to, cur), calcsiz(rt, -1);
    dfs(rt, cur);
  } return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(n), read(m);
  for (int i=1; i<n; ++i) {
    int u, v, w; read(u), read(v), read(w);
    addEdge(u, v, w), addEdge(v, u, w);
  }
  for (int i=1; i<=m; ++i)
    read(query[i]), MaxQue = max(MaxQue, query[i]);
  Maxi[0] = INT_MAX, totsiz = n;
  calcsiz(1, -1); calcsiz(rt, -1); dfs(rt, -1);
  for (int i=1; i<=m; ++i)
    puts(hasret[i]? "AYE" : "NAY");
  return 0;
}
比较纯粹的分块线段树等 DS 趣题
Posted Updated Notes20 minutes read (About 2993 words)

比较纯粹的分块线段树等 DS 趣题

要你求一个区间的最大子段和。
那么，显然地，我们可以维护区间最大前缀和和后缀和。
即根据左区间后缀和加上右区间前缀和可以等于最大子段和这个性质。

那么如何维护最大前缀和和最大后缀和呢？

显然一段区间分成两块，最大前缀和有可能是左区间的最大前缀和，也有可能是左区间的 Sum 加上右区间的最大前缀和，那么这样想，右区间也就没有疑问了。
然后正常操作即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4 + 10;
int n, m, a[N];

struct seg {
  int Lmax, Rmax, all, sum;
} t[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  t[rt].sum = t[ls].sum + t[rs].sum;
  // deal with Maximum Lmax
  t[rt].Lmax = max(t[ls].Lmax, t[ls].sum + t[rs].Lmax);
  // deal with Maximum Rmax
  t[rt].Rmax = max(t[rs].Rmax, t[rs].sum + t[ls].Rmax);
  // deal with the all Max
  t[rt].all = t[ls].Rmax + t[rs].Lmax;
  t[rt].all = max(t[rt].all, max(t[ls].all, t[rs].all));
  return ;
}

seg pushup_ret(seg l, seg r) {
  seg Root; Root.sum = l.sum + r.sum;
  // deal with Maximum Lmax
  Root.Lmax = max(l.Lmax, l.sum + r.Lmax);
  // deal with Maximum Rmax
  Root.Rmax = max(r.Rmax, r.sum + l.Rmax);
  // deal with the all Max
  Root.all = l.Rmax + r.Lmax;
  Root.all = max(Root.all, max(l.all, r.all));
  return Root;
}

void build(int rt, int l, int r) {
  if (l==r) {
    t[rt].all = t[rt].sum = a[l];
    t[rt].Lmax = t[rt].Rmax = a[l];
    return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt];
  int mid = (l+r) >> 1, tag = 0; seg ans1, ans2;
  if (L<=mid) ++tag, ans1 = query(ls, l, mid, L, R);
  if (R>mid) tag += 2, ans2 = query(rs, mid+1, r, L, R);
  if (tag==1) return ans1; if (tag==2) return ans2;
  return pushup_ret(ans1, ans2);
}

signed main() {
  read(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  build(1, 1, n);
  read(m); while (m--) {
    int l, r; read(l), read(r);
    printf("%lld\n", query(1, 1, n, l, r).all);
  }
  return 0;
}

带修区间最大子段和。
。没什么好说的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int n, m, a[N];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

struct seg {
  int Lmax, Rmax, sum, all;
  seg(int Lmax, int Rmax, int sum, int all):
    Lmax(Lmax), Rmax(Rmax), sum(sum), all(all) {}
  seg() {}
} t[N<<2];

void pushup(int rt) {
  t[rt].sum = t[ls].sum + t[rs].sum;
  t[rt].Lmax = max(t[ls].Lmax, t[ls].sum+t[rs].Lmax);
  t[rt].Rmax = max(t[rs].Rmax, t[rs].sum+t[ls].Rmax);
  t[rt].all = max(t[ls].all, t[rs].all);
  t[rt].all = max(t[rt].all, t[ls].Rmax+t[rs].Lmax);
  return ;
}

seg pushup_ret(seg l, seg r) {
  seg ans; ans = seg(0, 0, 0, 0);
  ans.sum = l.sum + r.sum;
  ans.Lmax = max(l.Lmax, l.sum+r.Lmax);
  ans.Rmax = max(r.Rmax, r.sum+l.Rmax);
  ans.all = max(l.all, r.all);
  ans.all = max(ans.all, l.Rmax+r.Lmax);
  return ans;
}

void build(int rt, int l, int r) {
  if (l==r) { t[rt] = seg(a[l], a[l], a[l], a[l]); return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void upd(int rt, int l, int r, int pos, int f) {
  if (l==r) { t[rt] = seg(f, f, f, f); return; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(ls, l, mid, pos, f);
  else upd(rs, mid+1, r, pos, f);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt];
  int mid = (l+r) >> 1, tag = 0; seg ans1, ans2;
  if (L<=mid) ++tag, ans1 = query(ls, l, mid, L, R);
  if (R>mid) tag += 2, ans2 = query(rs, mid+1, r, L, R);
  if (tag==1) return ans1; if (tag==2) return ans2;
  return pushup_ret(ans1, ans2);
}

int main() {
  read(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  build(1, 1, n);
  read(m); while (m--) {
    int opt, l, r; read(opt);
    read(l), read(r);
    if (!opt) upd(1, 1, n, l, r);
    else printf("%d\n", query(1, 1, n, l, r).all);
  }
  return 0;
}

Update 区间开方，Query 区间和。
那么根据某上帝造题的套路，因为 $\sqrt{1}=1$，所以可以维护一个区间 Max。
如果当前区间 Max = 1，那么直接退出循环，停止修改。
然后 pushdown 的时候 lazytag 下传一下。
没别的了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;
int n, m, cnt, a[N];

struct seg {
  int sum, Max;
} t[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  t[rt].Max = max(t[ls].Max, t[rs].Max);
  t[rt].sum = t[ls].sum + t[rs].sum;
  return ;
}

void upd(int rt, int l, int r, int L, int R) {
  if (t[rt].Max<=1) return ;
  if (l==r) {
    t[rt].sum = sqrt(t[rt].sum);
    t[rt].Max = t[rt].sum; return ;
  }
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R);
  if (R>mid) upd(rs, mid+1, r, L, R);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return t[rt].sum;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void build(int rt, int l, int r) {
  if (l==r) {
    t[rt].sum = a[l];
    t[rt].Max = t[rt].sum; return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

signed main() {
  while (cin >> n) {
    for (int i=1; i<=n; ++i) read(a[i]);
    build(1, 1, n); read(m);
    printf("Case #%lld:\n", ++cnt);
    while (m--) {
      int opt, l, r; read(opt);
      read(l), read(r); if (l>r) swap(l, r);
      if (!opt) upd(1, 1, n, l, r);
      else printf("%lld\n", query(1, 1, n, l, r));
    } puts("");
  }
  return 0;
}

区修单查。
直接维护一个块内加法的 tag 和零散块的 tag 即可。
零散块为了方便可以直接加在原数组里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
int n, a[N], tag[N], bel[N];
int Len, beg[N], End[N];

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void upd(int l, int r, int f) {
  if (bel[l] == bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  return ;
}

void init() {
  read(n); Len = sqrt(n);
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Len; ++i) {
    beg[i] = (i-1) * Len + 1;
    End[i] = i * Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i;
  }
  if (Len*Len == n) return ;
  beg[Len+1] = Len * Len + 1, End[Len+1] = n;
  for (int i=beg[Len+1]; i<=n; ++i) bel[i] = Len + 1;
  return ;
}

int query(int pos) {
  return a[pos] + tag[bel[pos]];
}

int main() {
  init();
  while (n--) {
    int opt, l, r, c;
    read(opt), read(l), read(r), read(c);
    if (!opt) upd(l, r, c);
    else printf("%d\n", query(r));
  }
}

区间修改，区间查询 $<k$ 的数的个数。

不难想到直接块内排个序就没了。
这个时候就要考虑零散块了。
因为排了序，所以原来的下标都换了位置。
那么我们可以暴力一点，直接在输入的数组里面进行修改，在这之后把零散块所在的区间全部重新赋值一遍，然后再块内排个序即可。可以保证这个是正确的，因为区间 tag 是区间统一加上，所以原来的相对关系都没有变，所以是对的！

那么要注意的是，query 的时候查询零散块要查询输入数组而非块内已排序的数组。
为什么？还是那个 id 变化的问题，下标不一样嘛。

我才不会告诉你就是这个问题卡了我好久

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;
const int M = 233;

int n, a[N], tag[M], bel[N];
int Num, Len, beg[M], End[M];

struct seg { int val[M]; } t[M];

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void upd(int l, int r, int f) {
  if (bel[l] == bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i) {
      int y = (i-1) % Len + 1;
      t[bel[l]].val[y] = a[i];
    }
    int segm = End[bel[l]] - beg[bel[l]] + 1;
    sort(t[bel[l]].val+1, t[bel[l]].val+1+segm);
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i) {
    int y = (i-1) % Len + 1;
    t[bel[l]].val[y] = a[i];
  }
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i) {
    int y = (i-1) % Len + 1;
    t[bel[r]].val[y] = a[i];
  }
  int segml = End[bel[l]] - beg[bel[l]] + 1;
  sort(t[bel[l]].val+1, t[bel[l]].val+1+segml);
  int segmr = End[bel[r]] - beg[bel[r]] + 1;
  sort(t[bel[r]].val+1, t[bel[r]].val+1+segmr);
  return ;
}

void init() {
  read(n); Len = sqrt(n); Num = n/Len;
  for (int i=1; i<=n; ++i) {
    int x = (i-1) / Len + 1, y = (i-1) % Len + 1;
    read(t[x].val[y]); a[i] = t[x].val[y];
  }
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1) * Len + 1;
    End[i] = i * Len;
    for (int j=beg[i]; j<=End[i]; ++j) bel[j] = i;
  }
  if (End[Num]==n) return ; else ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=n; ++i) bel[i] = Num;
  return ;
}

int query(int l, int r, int Lim) {
  // checking for updates
  if (bel[l] == bel[r]) {
    int cnt = 0;
    for (int i=l; i<=r; ++i)
      if (a[i] + tag[bel[l]] < Lim) ++cnt;
    return cnt;
  }
  int ans = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i)
    ans += ((lower_bound(t[i].val+1, t[i].val+1+Len, Lim-tag[i])-t[i].val)-1);
  for (int i=l; i<=End[bel[l]]; ++i)
    if (a[i] + tag[bel[l]] < Lim) ++ans;
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (a[i] + tag[bel[r]] < Lim) ++ans;
  return ans;
}

int main() {
  // freopen("fk2.in", "r", stdin);
  // freopen("fk2.out", "w", stdout);
  init();
  for (int i=1; i<=Num; ++i) {
    int segm = End[i] - beg[i] + 1;
    sort(t[i].val+1, t[i].val+segm+1);
  }
  while (n--) {
    int opt, l, r, c;
    read(opt), read(l), read(r), read(c);
    if (!opt) upd(l, r, c);
    else printf("%d\n", query(l, r, c*c));
  }
  return 0;
}

区间加法，区间前驱。

简单题。每一次区间加法直接加到 tag 里面去。
然后区间前驱对于每一个块都扫一遍 lower_bound。
接着零散块暴力扫。取一个 Max 即可。

注意零散块扫的是原来的数组，update 完之后要重新更新左右两个块。
以及不要忘记在求前驱的时候加上 tag。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;

int n, Len, Num, beg[M], End[M];
int a[N], tag[M], bel[N];
int Length[M], seg[M][M];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = Len*(i-1)+1, End[i] = Len*i;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, seg[i][(j-1)%Len+1] = a[j];
    Length[i] = Len;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, seg[Num][(i-1)%Len+1] = a[i];
  Length[Num] = End[Num] - beg[Num] + 1;
  return ;
}

void upd(int l, int r, int f) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += f;
    for (int i=beg[bel[l]]; i<=End[bel[r]]; ++i)
      seg[bel[l]][(i-1)%Len+1] = a[i];
    sort(seg[bel[l]]+1, seg[bel[l]]+1+Length[bel[l]]);
    return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i) tag[i] += f;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += f;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += f;
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
    seg[bel[l]][(i-1)%Len+1] = a[i];
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i)
    seg[bel[r]][(i-1)%Len+1] = a[i];
  sort(seg[bel[l]]+1, seg[bel[l]]+1+Length[bel[l]]);
  sort(seg[bel[r]]+1, seg[bel[r]]+1+Length[bel[r]]);
  return ;
}

int query(int l, int r, int x) {
  if (bel[l]==bel[r]) {
    int Max = -1e18;
    for (int i=l; i<=r; ++i)
      if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
    return (Max==-1e18)? -1:Max;
  }
  int Max = -1e18;
  for (int i=bel[l]+1; i<bel[r]; ++i) {
    int cur = lower_bound(seg[i]+1, seg[i]+1+Length[i], x-tag[i])-seg[i]-1;
    if (!cur) continue; Max = max(Max, seg[i][cur]+tag[i]);
  }
  for (int i=l; i<=End[bel[l]]; ++i)
    if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (a[i]+tag[bel[i]]<x) Max = max(Max, a[i]+tag[bel[i]]);
  return (Max==-1e18)? -1:Max;
}

signed main() {
  // freopen("fk3.in", "r", stdin);
  // freopen("fk3.out", "w", stdout);
  init();
  for (int i=1; i<=Num; ++i)
    sort(seg[i]+1, seg[i]+1+Length[i]);
  while (n--) {
    int opt, L, R, c; read(opt);
    read(L), read(R), read(c);
    if (!opt) upd(L, R, c);
    else printf("%lld\n", query(L, R, c));
  }
  return 0;
}

区间加法，区间求和。
直接记录一下块内的和 Sum 即可。
然后维护一个 tag，和原数组 a，查询暴力查询即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 5e4 + 10;
const int M = 233;

int n, Len, Num, a[N], tag[M], add[M];
int beg[M], End[M], Length[M], bel[N];

void init() {
  read(n); Len = sqrt(n); Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len, Length[i] = Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, add[i] += a[j];
  }
  if (Len*Num==n) return; ++Num;
  beg[Num] = End[Num-1]+1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, add[Num] += a[i];
  return ;
}

void upd(int l, int r, int x) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) a[i] += x;
    add[bel[l]] += x*(r-l+1); return ;
  }
  for (int i=bel[l]+1; i<bel[r]; ++i)
    tag[i] += x, add[i] += x*Len;
  for (int i=l; i<=End[bel[l]]; ++i) a[i] += x;
  for (int i=beg[bel[r]]; i<=r; ++i) a[i] += x;
  add[bel[l]] += x*(End[bel[l]]-l+1);
  add[bel[r]] += x*(r-beg[bel[r]]+1);
  /* cout << "TAG: "; for (int i=1; i<=Num; ++i) cout << tag[i] << ' ';
  cout << endl << "ADD: "; for (int i=1; i<=Num; ++i) cout << add[i] << ' ';
  cout << endl; */
  return ;
}

int query(int l, int r, int Mod) {
  if (bel[l]==bel[r]) {
    int sum = 0;
    for (int i=l; i<=r; ++i) sum += (a[i] + tag[bel[l]]);
    return (sum%Mod + Mod) % Mod;
  }
  int sum = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i)
    sum = (sum+add[i]) % Mod;
  for (int i=l; i<=End[bel[l]]; ++i)
    sum = (sum+tag[bel[l]]+a[i]) % Mod;
  for (int i=beg[bel[r]]; i<=r; ++i)
    sum = (sum+tag[bel[r]]+a[i]) % Mod;
  return (sum%Mod + Mod) % Mod;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R, x);
    else printf("%lld\n", query(L, R, x+1));
  }
  return 0;
}

区间开方，区间求和。
因为一个数最多被开方多少多少次（懒得算），所以直接类比线段树做法。
对于每一个块如果 Max $\le 1$ 了直接跳过，根本不需要开方。
否则直接暴力修改整个块，更新 Sum 数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 5e4 + 10;
const int M = 233;

int n, Len, Num, beg[M], End[N], Max[M];
int Length[M], a[N], add[M], bel[N];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=n; ++i) read(a[i]);
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len;
    for (int j=beg[i]; j<=End[i]; ++j)
      bel[j] = i, add[i] += a[j], Max[i] = max(Max[i], a[j]);
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    bel[i] = Num, add[Num] += a[i], Max[Num] = max(Max[Num], a[i]);
  return ;
}

void upd(int l, int r) {
  if (bel[l]==bel[r]) {
    for (int i=l; i<=r; ++i) {
      int to = sqrt(a[i]);
      add[bel[l]] += to - a[i], a[i] = to;
    }
    Max[bel[l]] = 0;
    for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
      Max[bel[l]] = max(Max[bel[l]], a[i]);
    return ;
  }
  for (int i=l; i<=End[bel[l]]; ++i) {
    int to = sqrt(a[i]);
    add[bel[l]] += to - a[i], a[i] = to;
  }
  for (int i=beg[bel[l]]; i<=End[bel[l]]; ++i)
    Max[bel[l]] = max(Max[bel[l]], a[i]);
  for (int i=beg[bel[r]]; i<=r; ++i) {
    int to = sqrt(a[i]);
    add[bel[r]] += to - a[i], a[i] = to;
    Max[bel[r]] = max(Max[bel[r]], to);
  }
  for (int i=beg[bel[r]]; i<=End[bel[r]]; ++i)
    Max[bel[r]] = max(Max[bel[r]], a[i]);
  for (int i=bel[l]+1; i<bel[r]; ++i) {
    if (Max[i]<=1) continue; Max[i] = 0;
    for (int j=beg[i]; j<=End[i]; ++j) {
      int to = sqrt(a[j]);
      add[i] += to - a[j], a[j] = to;
      Max[i] = max(Max[i], to);
    }
  } return ;
}

int query(int l, int r) {
  if (bel[l]==bel[r]) {
    int sum = 0;
    for (int i=l; i<=r; ++i) sum += a[i];
    return sum;
  }
  int sum = 0;
  for (int i=bel[l]+1; i<bel[r]; ++i) sum += add[i];
  for (int i=l; i<=End[bel[l]]; ++i) sum += a[i];
  for (int i=beg[bel[r]]; i<=r; ++i) sum += a[i];
  return sum;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R);
    else printf("%lld\n", query(L, R));
  }
  return 0;
}

单点插入，单点查询。

对于每一个块维护一个 vector 和 siz。
然后对于每一个插入操作，直接插入 vector 即可，siz 更新。
单点查询只要将查询的 id 遍历一遍减掉 siz 看什么时候满足当前 siz 即可。
插入操作也是一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;

vector <int> seg[M];
int n, Len, Num, bel[N], beg[M];
int End[M], Length[M];

#define pb push_back
#define ins insert

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len + 1, End[i] = i*Len;
    for (int j=beg[i]; j<=End[i]; ++j) {
      int x; read(x); seg[i].pb(x);
      bel[j] = i;
    } Length[i] = Len;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i) {
    int x; read(x); seg[Num].pb(x);
    bel[i] = Num;
  } Length[Num] = n - beg[Num] + 1;
  return ;
}

void upd(int pos, int x) {
  for (int i=1; i<=Num; ++i) {
    if (pos<=Length[i]) {
      seg[i].ins(seg[i].begin()+pos-1, x);
      ++Length[i]; return ;
    }
    pos -= Length[i];
  } return ;
}

int query(int pos) {
  for (int i=1; i<=Num; ++i) {
    if (pos<=Length[i]) return seg[i][pos-1];
    pos -= Length[i];
  }
}

int main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (!opt) upd(L, R);
    else printf("%d\n", query(R));
  }
  return 0;
}

区间加，区间乘，单点查询。
直接参考线段树加法乘法操作即可。
首先优先级肯定乘法大于加法，所以考虑维护两个 tag。
即 addtag 和 multag。
然后区间加和区间乘最重要的就是类似于 pushdown 之类的东西。
就是根据优先级直接将当前区间标记下放乱搞即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

const int N = 1e5 + 10;
const int M = 350;
const int Mod = 1e4 + 7;

int n, Len, Num, a[N], bel[N];
int addtag[M], multag[M];
int beg[M], End[M], Length[M];

void init() {
  read(n); Len = sqrt(n), Num = n / Len;
  for (int i=1; i<=Num+1; ++i) multag[i] = 1;
  for (int i=1; i<=Num; ++i) {
    beg[i] = (i-1)*Len+1, End[i] = i*Len;
    Length[i] = End[i] - beg[i] + 1;
    for (int j=beg[i]; j<=End[i]; ++j)
      read(a[j]), bel[j] = i;
  }
  if (End[Num]==n) return ; ++Num;
  beg[Num] = End[Num-1] + 1, End[Num] = n;
  for (int i=beg[Num]; i<=End[Num]; ++i)
    read(a[i]), bel[i] = Num;
  return ;  
}

void reset(int x) {
  for (int i=beg[x]; i<=End[x]; ++i)
    a[i] = (a[i] * multag[x] + addtag[x]) % Mod;
  multag[x] = 1, addtag[x] = 0;
  return ;
}

void upd(int l, int r, int x, bool opt) {
  if (bel[l]==bel[r]) {
    reset(bel[l]);
    for (int i=l; i<=r; ++i)
      if (!opt) a[i] = (a[i] + x) % Mod;
      else a[i] = (a[i] * x) % Mod;
    return ;
  }
  reset(bel[l]), reset(bel[r]);
  for (int i=bel[l]+1; i<bel[r]; ++i)
    if (!opt) addtag[i] = (addtag[i] + x) % Mod;
    else addtag[i] = (addtag[i] * x) % Mod,
        multag[i] = (multag[i] * x) % Mod;
  for (int i=l; i<=End[bel[l]]; ++i)
    if (!opt) a[i] = (a[i] + x) % Mod;
    else a[i] = (a[i] * x) % Mod;
  for (int i=beg[bel[r]]; i<=r; ++i)
    if (!opt) a[i] = (a[i] + x) % Mod;
    else a[i] = (a[i] * x) % Mod;
  return ;
}

int query(int x) {
  return (a[x] * multag[bel[x]] + addtag[bel[x]]) % Mod;
}

signed main() {
  init();
  while (n--) {
    int opt, L, R, x; read(opt);
    read(L), read(R), read(x);
    if (opt==2) printf("%lld\n", query(R));
    else upd(L, R, x, opt);
  }
  return 0;
}
关于动态开点线段树的应用
Posted Updated Notes10 minutes read (About 1480 words)

关于动态开点线段树的应用

自己瞎取的名字，就是动态开点线段树。
大概思想当空间不够用的时候，随时可以删点和新建点，比较灵活。
下面是几个例子，有的是值域线段树，有的是普通坐标的线段树。

本来是树状数组水题，现在变成了奇怪的动态开点值域线段树模板题。
其实不用值域线段树也可以。
普通线段树就要离散化然后按照单调递增的顺序加 value，再 query。
多麻烦啊，所以一个值域线段树解决问题。

因为最大值 MAX 为 $10^9$，所以 inf 设为 $10^9$。
因为每一次查询的是当前点往右的点数，所以要特判 l>r 的情况。
因为 inf=1e9，所以查询 1e9+1 就会炸掉，所以要特判。
其实把 inf 变成 1e9+10 不是一样的吗

那么代码如下。

因为线段树平均链深度为 $\log$ 级别。
所以开 $N \log N$ 大小的线段树。
动态开点线段树的优势在这道题还真没体现出来（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e7 + 10;
const int inf = 1e9 + 10;

int n, cnt, root, tree[N];
int a[N], ls[N], rs[N];

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void upd(int &rt, int l, int r, int val, int f) {
  if (!rt) rt = ++cnt;
  if (l==r) { tree[rt] += f; return ; }
  int mid = (l+r) >> 1;
  if (val<=mid) upd(ls[rt], l, mid, val, f);
  else upd(rs[rt], mid+1, r, val, f);
  tree[rt] = tree[ls[rt]] + tree[rs[rt]];
  return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (!rt) return 0;
  if (L<=l && r<=R) return tree[rt];
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls[rt], l, mid, L, R);
  if (R>mid) ans += query(rs[rt], mid+1, r, L, R);
  return ans;
}

int main() {
  read(n); ll ans = 0;
  for (int i=1; i<=n; ++i) {
    int x; read(x);
    ans += (ll)query(root, 1, inf, x+1, inf);
    upd(root, 1, inf, x, 1);
  }
  printf("%lld\n", ans);
  return 0;
}

跑了 4s 多，还不如写普通线段树（bu

虽然是个紫题，但是是个水紫。

首先问题可以简化成树上染色问题，四个 option 变成下面这样。

  • 某个节点被重新染色
  • 节点权值被修改
  • 求路径上某种颜色权值和
  • 求路径上某种颜色最大权值

那么考虑对于每一个颜色开一棵动态开点线段树。
然后直接树链剖分乱搞。（轻重链剖分）
对于 option 3 和 4 随便乱搞都可以过。

但是对于 option 1，可以转化为在树中删点，再丢到另一棵树里。
option 2 直接修改当前权值即可。

所以想到 pushup 操作。
可以将节点的 MAX 和 SUM 直接变成 0。
接着删点（就这么做！）跑路。
然后在另一棵树里面新建节点，只需要丢进去即可。
然后修改颜色（即要修改节点所属树根）。
或者是修改当前的权值。注意要 remove 和 update 之后做。

然后就没了。

似乎并不毒瘤？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int MAXN = 1e5 + 10;
const int MAX_SIZE = 2e7;

int n, Q, cnt, tot/*build-cnt*/, idx;
int w[MAXN], c[MAXN], wl[MAXN], wc[MAXN];
int dep[MAXN], siz[MAXN], fa[MAXN], son[MAXN];
int tp[MAXN], root[MAXN], id[MAXN];
char opt[3]; int head[MAXN<<1];

struct Edge { int to, nxt; } e[MAXN<<1];
void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  fa[cur] = f, siz[cur] = 1;
  dep[cur] = dep[f] + 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa[cur] || to==son[cur]) continue;
    dfs2(to, to);
  } return ;
}

struct seg { int ls, rs, Max, val; } tree[MAX_SIZE];
void pushup(int rt) {
  tree[rt].val = tree[tree[rt].ls].val + tree[tree[rt].rs].val;
  tree[rt].Max = max(tree[tree[rt].ls].Max, tree[tree[rt].rs].Max);
  return ;
}

void upd(int &rt, int l, int r, int pos, int W) {
  if (!rt) rt = ++tot;
  if (l==r) { tree[rt].val = tree[rt].Max = W; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(tree[rt].ls, l, mid, pos, W);
  else upd(tree[rt].rs, mid+1, r, pos, W);
  pushup(rt); return ;
}

void remv(int rt, int l, int r, int pos) {
  if (l==r) { tree[rt].val = tree[rt].Max = 0; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) remv(tree[rt].ls, l, mid, pos);
  else remv(tree[rt].rs, mid+1, r, pos);
  pushup(rt); return ;
}

int querys(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt].val;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += querys(tree[rt].ls, l, mid, L, R);
  if (R>mid) ans += querys(tree[rt].rs, mid+1, r, L, R);
  return ans;
}

int querym(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt].Max;
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans = max(ans, querym(tree[rt].ls, l, mid, L, R));
  if (R>mid) ans = max(ans, querym(tree[rt].rs, mid+1, r, L, R));
  return ans;
}

int qus(int l, int r, int rel) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans += querys(root[rel], 1, n, id[tp[l]], id[l]);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += querys(root[rel], 1, n, id[l], id[r]);
  return ans;
}

int qum(int l, int r, int rel) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans = max(ans, querym(root[rel], 1, n, id[tp[l]], id[l]));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = max(ans, querym(root[rel], 1, n, id[l], id[r]));
  return ans;
}

int main() {
  read(n), read(Q);
  for (int i=1; i<=n; ++i)
    read(w[i]), read(c[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  for (int i=1; i<=n; ++i)
    upd(root[c[i]], 1, n, id[i], w[i]);
  while (Q--) {
    cin >> opt+1;
    int u, v; read(u), read(v);
    if (opt[2] == 'C') {
      remv(root[c[u]], 1, n, id[u]);
      upd(root[v], 1, n, id[u], w[u]);
      c[u] = v;
    } else if (opt[2] == 'W') {
      remv(root[c[u]], 1, n, id[u]);
      upd(root[c[u]], 1, n, id[u], v);
      w[u] = v;
    } else if (opt[2] == 'S') printf("%d\n", qus(u, v, c[u]));
    else if (opt[2] == 'M') printf("%d\n", qum(u, v, c[u]));
  }
  return 0;
}
树链剖分专题
Posted Updated Notes26 minutes read (About 3949 words)

树链剖分专题

显然的板子题。

那么我们只需要干这样一件事情，就是按照重儿子的顺序来进行 DFS，那么这样我们就可以通过 DFS 序这样一个东西来进行子树的查询和更改，同时也可以通过跳链顶，类似 LCA 的操作，来进行路径的修改和查询。这都非常容易实现。

所以代码会长下面这样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int n, m, root, Mod, cnt, idx;
int w[N], wl[N], val[N<<2], head[N<<1];
int dep[N], id[N], fa[N], son[N];
int lazy[N<<2], tp[N], siz[N];

struct Edge {
  int to, nxt;
} e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

void pushup(int rt) {
  val[rt] = (val[ls] + val[rs]) % Mod;
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  lazy[ls] %= Mod, lazy[rs] %= Mod;
  val[ls] = (val[ls] + (mid-l+1) * lazy[rt]) % Mod;
  val[rs] = (val[rs] + (r-mid) * lazy[rt]) % Mod;
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    val[rt] += (r-l+1) * f, val[rt] %= Mod;
    lazy[rt] += f, lazy[rt] %= Mod;
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans % Mod;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  siz[cur] = 1, fa[cur] = f;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to]>heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp; if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur] || to==fa[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  f %= Mod;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int qu(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans = (ans + query(1, 1, n, id[tp[l]], id[l])) % Mod;
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = (ans + query(1, 1, n, id[l], id[r])) % Mod;
  return ans;
}

void upsub(int x, int f) { upd(1, 1, n, id[x], id[x]+siz[x]-1, f); }
int qusub(int x) { return query(1, 1, n, id[x], id[x]+siz[x]-1); }

signed main() {
  read(n), read(m);
  read(root), read(Mod);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(root, root);
  dfs2(root, 0); build(1, 1, n);
  while (m--) {
    int opt, x, y, z;
    read(opt);
    if (opt==1) {
      read(x), read(y), read(z);
      up(x, y, z);
    } else if (opt==2) {
      read(x), read(y);
      printf("%lld\n", qu(x, y) % Mod);
    } else if (opt==3) {
      read(x), read(z);
      upsub(x, z);
    } else { read(x); printf("%lld\n", qusub(x) % Mod); }
  }
  return 0;
}

更简单了，甚至不需要 lazytag。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <stdio.h>
#include <iostream>
#define isdigit(ch) (ch>47&&ch<58)

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch ^ '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } ret *= f; return ;
}

void out(int ret) {
  if (ret<0) { ret = -ret, putchar('-'); }
  if (ret>9) out(ret/10);
  putchar(ret%10 ^ 48); return ;
}

const int N = 3e4 + 10;
int n, Q, cnt, dfn;
int w[N], v[N], head[N];

int val[N<<2], siz[N], Maxi[N<<2];
int id[N], fa[N], tp[N], son[N], dep[N];
char str[10];

int max(int x, int y) { return x>y? x:y; }
void swap(int &x, int &y) { x ^= y ^= x ^= y; }

struct Edge {
  int to, nxt;
} e[N<<1];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
  return ;
}

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  Maxi[rt] = max(Maxi[ls], Maxi[rs]);
  return ;
}

void build(int rt, int l, int r) {
  if (l == r) { val[rt] = Maxi[rt] = v[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void upd(int rt, int l, int r, int pos, int f) {
  if (l == r) { val[rt] = Maxi[rt] = f; return ; }
  int mid = (l+r) >> 1;
  if (pos<=mid) upd(ls, l, mid, pos, f);
  if (pos>mid) upd(rs, mid+1, r, pos, f);
  pushup(rt); return ;
}

int querys(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += querys(ls, l, mid, L, R);
  if (R>mid) ans += querys(rs, mid+1, r, L, R);
  return ans;
}

int querym(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return Maxi[rt];
  int mid = (l+r) >> 1, Max = -1e9;
  if (L<=mid) Max = max(Max, querym(ls, l, mid, L, R));
  if (R>mid) Max = max(Max, querym(rs, mid+1, r, L, R));
  return Max;
}

void dfs1(int cur, int Fa) {
  dep[cur] = dep[Fa] + 1;
  fa[cur] = Fa, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == Fa) continue;
    dfs1(to, cur);
    siz[cur] += siz[to];
    if (siz[to] > heavyson)
      son[cur] = to, heavyson = siz[to];
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++dfn;
  v[dfn] = w[cur], tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int qus(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querys(1, 1, n, id[tp[l]], id[l]);
    ans += cur, l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += querys(1, 1, n, id[l], id[r]);
  return ans;
}

int qum(int l, int r) {
  int ans = -1e9;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    int cur = querym(1, 1, n, id[tp[l]], id[l]);
    ans = max(ans, cur), l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans = max(ans, querym(1, 1, n, id[l], id[r]));
  return ans;
}

int main() {
//   freopen("P2590.in", "r", stdin);
//   freopen("P2590.out", "w", stdout);
  read(n);
  for (int i=1; i<n; ++i) {
    int x, y; read(x), read(y);
    addEdge(x, y), addEdge(y, x);
  }
  for (int i=1; i<=n; ++i) read(w[i]);

  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);

  read(Q);
  while (Q--) {
    std::cin >> str+1;
    int l, r; read(l), read(r);
    if (str[1] == 'C') upd(1, 1, n, id[l], r);
    else if (str[2] == 'M') out(qum(l, r)), puts("");
    else if (str[2] == 'S') out(qus(l, r)), puts("");
  }
  return 0;
}

简单 trick。

只需要将依赖关系转化为树上关系就可以了。
然后就是要区分 0 和 unedited，完全不一样。
所以可以直接将 unedited 设置为 -1 然后乱搞即可。

注意是赋值而不是加法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

const int N = 1e5 + 10;
int n, Q, cnt, idx, head[N];
int val[N<<2], lazy[N<<2];
int id[N], tp[N], siz[N], dep[N];
char opt[20]; int fa[N], son[N];

struct Edge { int to, nxt; } e[N];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void pushdown(int rt, int l, int r) {
  if (lazy[rt]<0) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rt], lazy[rs] = lazy[rt];
  val[ls] = lazy[rt] * (mid-l+1);
  val[rs] = lazy[rt] * (r-mid);
  lazy[rt] = -1; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) {
    lazy[rt] = f; val[rt] = f * (r-l+1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, ans = 0;
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx; tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

void up(int l, int r, int f) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], f);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], f);
  return ;
}

int main() {
//   freopen("P2146.in", "r", stdin);
  memset(lazy, -1, sizeof lazy);
  read(n);
  for (int i=2; i<=n; ++i) {
    int v; read(v);
    addEdge(v+1, i);
  }
  dfs1(1, 1), dfs2(1, 1), read(Q);
  while (Q--) {
    cin >> opt+1;
    int v; read(v); ++v;
    int cur = query(1, 1, n, 1, n);
    if (opt[1]=='i') up(1, v, 1);
    else if (opt[1]=='u') upd(1, 1, n, id[v], id[v]+siz[v]-1, 0);
    int to = query(1, 1, n, 1, n);
    printf("%d\n", abs(cur-to));
  }
  return 0;
}

也是个简单题，就是不要被 from 和 to 骗了，双向边肯定要连的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <bits/stdc++.h>
#define int long long
using namespace std;

void read(int &ret) {
  ret = 0; char ch = getchar(); int f = 1;
  while (!isdigit(ch) && ch^'-') ch = getchar();
  if (ch=='-') f = -1, ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  }
  ret *= f; return ;
}

const int N = 1e5 + 10;

int n, m, cnt, idx;
int dep[N], son[N], fa[N], siz[N];
int head[N<<1], tp[N], w[N], wl[N], id[N];
struct Edge { int to, nxt; } e[N<<1];

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

int lazy[N<<2], val[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  val[rt] = val[ls] + val[rs];
  return ;
}

void build(int rt, int l, int r) {
  if (l==r) { val[rt] = wl[l]; return ; }
  int mid = (l+r) >> 1;
  build(ls, l, mid);
  build(rs, mid+1, r);
  pushup(rt); return ;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
  val[ls] += (mid-l+1) * lazy[rt];
  val[rs] += (r-mid) * lazy[rt];
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int f) {
  if (L<=l && r<=R) { lazy[rt] += f; val[rt] += f * (r-l+1); return ; }
  int mid = (l+r) >> 1; pushdown(rt, l, r);
  if (L<=mid) upd(ls, l, mid, L, R, f);
  if (R>mid) upd(rs, mid+1, r, L, R, f);
  pushup(rt); return ;
}

int query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return val[rt];
  int ans = 0, mid = (l+r) >> 1;
  pushdown(rt, l, r);
  if (L<=mid) ans += query(ls, l, mid, L, R);
  if (R>mid) ans += query(rs, mid+1, r, L, R);
  return ans;
}

void dfs1(int cur, int f) {
  fa[cur] = f, siz[cur] = 1;
  dep[cur] = dep[f] + 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==f) continue;
    dfs1(to, cur); siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  }
  return ;
}

void dfs2(int cur, int Tp) {
  id[cur] = ++idx, wl[idx] = w[cur];
  tp[cur] = Tp;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to==fa[cur] || to==son[cur]) continue;
    dfs2(to, to);
  }
  return ;
}

int que(int l, int r) {
  int ans = 0;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    ans += query(1, 1, n, id[tp[l]], id[l]);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  ans += query(1, 1, n, id[l], id[r]);
  return ans;
}

signed main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v);
    addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    int opt, x, a; read(opt), read(x);
    if (opt==1) {
      read(a);
      upd(1, 1, n, id[x], id[x], a);
    } else if (opt==2) {
      read(a);
      upd(1, 1, n, id[x], id[x]+siz[x]-1, a);
    } else printf("%lld\n", que(1, x));
  }
  return 0;
}

毒瘤出题人搞边不搞点。

看到题目首先想到树链剖分。
首先变为重边的操作不难，直接普通树链剖分即可。
查询路径上包含所有重边也很简单，只需要标记为 1 然后统计和。

但是 ex 的在于将点 $x$ 的所有连边变为轻边。

所以应该怎么弄呢？
那么很容易想到树链剖分的染色。

可以这样做：每一次路径变为重边就可以看成是给路径上所有点染一种 新的 颜色。
那么这个时候，看到所有其他连边连向的点都和当前路径上点的颜色不一样。
这个时候就可以默认其变为了轻边。

所以这样就可以得出判断轻边的条件了。
就是一条边，如果它两端颜色相同就为重边。
证明显然。

然后就是关于区间修改的问题了。
因为当前是求区间两端颜色相同边的个数，所以考虑树链剖分，将一段路径拆成若干区间，每一次合并区间都可以加上子区间答案，并保证其正确性，显而易见这样是不会假掉的。
要注意的就是如果子区间中间连接的两点颜色相同答案要加上 $1$。

那路径修改呢？这样还是有很大区别的。
因为两点之间路径可以视作从一个点剖开变成两条路径。
所以考虑两条路径分别维护。

那么我们可以对于每一个跳链顶的过程，记录当前 update 的是以 $u$ 为起点的路径还是以 $v$ 为起点的路径（$u \rightarrow v$ 为路径），每一次看维护两个指针 L 和 R 是否交换即可，最后还要合并答案，这里还是要详细讲一下。

不考虑整条路径两个指针 L，R 的实际位置，只考虑相对位置。
那么有两种情况。

  • L 跳到了但是 R 没有跳到。

显然这个时候 dep[L]<dep[R]。
又因为 L 跳到了，所以上一次更新的是 L 路径，本次就要更新 R 路径了。
所以本轮不用交换 L 和 R，L 路径和 R 路径的 tag 仍然指向 L。
这里就是容易弄混的地方，指向 L 的 tag 在这时要更新 R 路径。

  • R 跳到了但是 L 没有跳到。

显然这个时候 dep[L]>dep[R]。
又因为 R 跳到了，所以上面的 tag 指向 R，本次更新 L 路径。
因为当前这样所以要交换 L 和 R，tag 反转之后指向当前 R，所以相当于更新交换之后的 R 路径，本质还是 L 路径。（我自己都晕了）
反正不偷懒的写法会好理解一些，手动模拟比较好一点。

大概就是分 L 先到和 R 先到的情况吧。
其实手玩一下也是没有问题的，手玩完之后再写暴力更新的代码。

另外一点，我这里默认 L 路径在左边，其 dep[l]>dep[r]。
而 R 路径默认在右边，其 dep[l]<dep[r]。

lc 和 rc 分别是 leftcolor，rightcolor。

注意一开始如果全部没有染色那默认全都为 $0$，那么重边的条数就变成 $n-1$ 了，which is totally wrong。所以一开始就要染奇奇怪怪的颜色。
接着注意边数等于点数减一，在 pushdown 和 update 的时候要注意。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int T, n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) ++tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) ++cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  // lazy[rt] -> stores the color
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], mid-l); // (mid-l+1)-1
  tree[rs] = seg(lazy[rt], lazy[rt], r-mid-1); // (r-mid)-1
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, r-l); // (r-l+1)-1
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; else if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx;
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == son[cur] || to == fa[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = seg(0, 0, 0), ans[1] = ans[0];
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val+(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val+(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(T);
  while (T--) {
    read(n), read(m);
    cnt = idx = 0;
    for (int i=1; i<=n; ++i) {
      siz[i] = dep[i] = son[i] = 0;
      id[i] = tp[i] = fa[i] = head[i] = 0;
      tree[i*4-3] = tree[i*4-2] = tree[i*4-1] = tree[i*4] = NUL;
      lazy[i*4-3] = lazy[i*4-2] = lazy[i*4-1] = lazy[i*4] = 0;
    }
    for (int i=1; i<n; ++i) {
      int u, v; read(u), read(v);
      addEdge(u, v), addEdge(v, u);
    }
    dfs1(1, 1), dfs2(1, 1);
    for (int i=1; i<=n; ++i) upd(1, 1, n, id[i], id[i], -i);
    while (m--) {
      int opt, u, v; read(opt), read(u), read(v);
      if (opt == 1) up(u, v, m);
      else printf("%d\n", qu(u, v));
    }
  }
  return 0;
}

什么时候 NOI 能出一些不重复的题目啊 …（指 NOI2021 D1T1）
这个 trick 和上面一题几乎一致，但是这个时候初始贡献为 $1$。
每一次 update 的区间贡献都为 $1$，判断 ls.rc=rs.lc 那么贡献 $-1$。

代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, cnt, idx, lazy[N<<2];
int head[N<<1], dep[N], siz[N];
int tp[N], son[N], fa[N], id[N];
int w[N], wl[N];

struct Edge { int to, nxt; } e[N<<1];
struct seg {
  int lc, rc, val;
  seg(int lc, int rc, int val):
    lc(lc), rc(rc), val(val) {}
  seg() {}
} tree[N<<2];

#define ls ((rt)<<1)
#define rs ((rt)<<1|1)

void pushup(int rt) {
  tree[rt].lc = tree[ls].lc;
  tree[rt].rc = tree[rs].rc;
  tree[rt].val = tree[ls].val + tree[rs].val;
  if (tree[ls].rc == tree[rs].lc) --tree[rt].val;
  return ;
}

seg Merge(seg L, seg R) {
  seg cur; cur.lc = L.lc, cur.rc = R.rc;
  cur.val = L.val + R.val;
  if (L.rc == R.lc) --cur.val;
  return cur;
}

void pushdown(int rt, int l, int r) {
  if (!lazy[rt]) return ;
  int mid = (l+r) >> 1;
  lazy[ls] = lazy[rs] = lazy[rt];
  tree[ls] = seg(lazy[rt], lazy[rt], 1);
  tree[rs] = seg(lazy[rt], lazy[rt], 1);
  lazy[rt] = 0; return ;
}

void upd(int rt, int l, int r, int L, int R, int col) {
  if (L<=l && r<=R) {
    lazy[rt] = col;
    tree[rt] = seg(col, col, 1);
    return ;
  }
  pushdown(rt, l, r);
  int mid = (l+r) >> 1;
  if (L<=mid) upd(ls, l, mid, L, R, col);
  if (R>mid) upd(rs, mid+1, r, L, R, col);
  pushup(rt); return ;
}

seg query(int rt, int l, int r, int L, int R) {
  if (L<=l && r<=R) return tree[rt];
  pushdown(rt, l, r);
  int mid = (l+r) >> 1, tag = 0;
  seg ans1, ans2;
  if (L<=mid) ans1 = query(ls, l, mid, L, R), ++tag;
  if (R>mid) ans2 = query(rs, mid+1, r, L, R), tag += 2;
  if (tag == 1) return ans1; if (tag == 2) return ans2;
  return Merge(ans1, ans2);
}

void addEdge(int u, int v) {
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt; return ;
}

void dfs1(int cur, int f) {
  dep[cur] = dep[f] + 1;
  fa[cur] = f, siz[cur] = 1;
  int heavyson = -1;
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == f) continue;
    dfs1(to, cur), siz[cur] += siz[to];
    if (siz[to] > heavyson)
      heavyson = siz[to], son[cur] = to;
  } return ;
}

void dfs2(int cur, int Tp) {
  tp[cur] = Tp, id[cur] = ++idx, wl[idx] = w[cur];
  if (!son[cur]) return ;
  dfs2(son[cur], Tp);
  for (int i=head[cur]; i; i=e[i].nxt) {
    int to = e[i].to;
    if (to == fa[cur] || to == son[cur]) continue;
    dfs2(to, to);
  } return ;
}

void up(int l, int r, int col) {
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) swap(l, r);
    upd(1, 1, n, id[tp[l]], id[l], col);
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) swap(l, r);
  upd(1, 1, n, id[l], id[r], col);
  return ;
}

const seg NUL = seg(0, 0, 0);
int qu(int l, int r) {
  int belong = 0; seg ans[2];
  ans[0] = ans[1] = NUL;
  while (tp[l] ^ tp[r]) {
    if (dep[tp[l]] < dep[tp[r]]) {
      belong = 1 - belong;
      swap(l, r);
    }
    seg cur = query(1, 1, n, id[tp[l]], id[l]);
    if (belong) ans[1] = Merge(cur, ans[1]);
    else ans[0] = seg(ans[0].lc, cur.lc,
    ans[0].val+cur.val-(ans[0].rc==cur.rc));
    l = fa[tp[l]];
  }
  if (dep[l] > dep[r]) {
    belong = 1 - belong;
    swap(l, r);
  }
  seg cur = query(1, 1, n, id[l], id[r]);
  if (!belong) ans[1] = Merge(cur, ans[1]);
  else ans[0] = seg(ans[0].lc, cur.lc,
  ans[0].val+cur.val-(ans[0].rc==cur.rc));
  return Merge(ans[0], ans[1]).val;
}

void build(int rt, int l, int r) {
  if (l==r) {
    tree[rt].val = 1;
    tree[rt].lc = tree[rt].rc = wl[l];
    return ;
  }
  int mid = (l+r) >> 1;
  build(ls, l, mid), build(rs, mid+1, r);
  pushup(rt); return ;
}

void read(int &ret) {
  ret = 0; char ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) {
    ret = (ret<<1) + (ret<<3) + (ch^48);
    ch = getchar();
  } return ;
}

int main() {
  read(n), read(m);
  for (int i=1; i<=n; ++i) read(w[i]);
  for (int i=1; i<n; ++i) {
    int u, v; read(u), read(v);
    addEdge(u, v), addEdge(v, u);
  }
  dfs1(1, 1), dfs2(1, 1);
  build(1, 1, n);
  while (m--) {
    char opt; cin >> opt;
    int u, v, color;
    read(u), read(v);
    if (opt == 'C') read(color), up(u, v, color);
    else printf("%d\n", qu(u, v));
  }
  return 0;
}
Follow

Links

Categories

Recents

Archives

Tags

DS5
Graph1
Math1
Network Flows1
Number Theory2
Others2
State Compression1

Subscribe for updates

follow.it

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×

×