可持久化数据结构
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 催我。

关于 FFT 和 NTT 等多项式科技的学习
Posted Updated Notes15 minutes read (About 2310 words)

关于 FFT 和 NTT 等多项式科技的学习

给大家整个活。

最基础的狒狒贴可以 $O(N \log N)$ 解决多项式乘法。
朴素的就是 $O(N^2)$ 比较低端。

狒狒贴先是把一个用系数表示的多项式转化为点值表示。
然后通过这样的转换搞科技。

首先一个 $n-1$ 次 $n$ 项多项式 $\rightarrow f(x)=\sum\limits_{i=0}^{n-1}a_{i}x^i$， 默认 $a_{0,…,n-1}$。
或者可以表示为 $f(x)={a_0,a_1,…,a_{ n-1}}$。

然后引入一种高级的东西 - 点值表示法。
把一个多项式丢到平面直角坐标系里面，看成一个函数。
然后不同的 $x$ 代进去 $f(x)$ 都会得到不同的 $(x,f(x))$。

然后规定一下 $f(x)$ 用 ${(x_0,f(x_0)),…,(x_{n-1},f(x_{n-1}))}$ 表示，就是点值表示法。

然后如果你要暴力搞的话肯定系数转点值和点值转系数都 $O(N^2)$。
两种朴素算法分别叫做 DFT 和 IDFT，离散傅里叶变换和离散傅里叶逆变换。

首先可以直接将任何一个复数表示到复平面直角坐标系上面变成一个点。
横坐标是实部，单位为 $1$；纵坐标为虚部，单位为 $i=\sqrt{-1}$。
复数运算不多赘述了。

多项式转点值可以找到一个地方突破，就是代入一组特殊的 $x$ 使次方运算减少。
那么就可以直接钦定一个复平面坐标系上以原点为圆心划一个半径为 $1$ 的圆。
例如 $(0,i) \rightarrow (1,0) \rightarrow (0,-i) \rightarrow (-1,0)$ 这样一个圆。
规定一下方便的叫法，这是个单位圆。
那么所有点经过若干次方都可以变成 $1$。

方便起见可以把它分成 $n$ 份代表 $n$ 项式。
从 $(1,0)$ 开始逆时针编号，其实随便怎么标都可以，你开心就好。
令 $\omega_{n}^1$ 代表 $n$ 次单位根。
然后设第 $i$ 个点的复数值为 $\omega_{n}^i$。

然后丢个简单的公式，就是模长相乘，极角相加。
大概就是 $(a,\theta_{1})\times(b,\theta_2)=(ab,\theta_1+\theta_2)$，其中横坐标为实，纵坐标为虚。

这里就可以稍稍拓展一下知道 $\omega_n^{i+j}=\omega_n^i \times \omega_n^j$。
然后由定义显然有 $(\omega_{n}^i)^j=\omega_n^{ij}$。

所以由这个公式知道 $(\omega_{n}^1)^i=\omega_n^i$。
那么每一个 $\omega$ 就可以通过三角函数乘上占的比例求出来。

$$\omega_n^k=\cos\dfrac{k}{n}2\pi+i\sin\dfrac{k}{n}2\pi$$

（这里下标不用 $i$ 了是因为怕跟虚数单位 $i$ 混淆）

那么这一大堆 $\omega$ 就可以当 $x_{0…n-1}$。

推狒狒贴需要用到两个性质，就是可以拿来搞分治的两个性质。

就是 $\omega_n^k=\cos \dfrac{k}{n}2\pi+i\sin\dfrac{k}{n}2\pi=\cos \dfrac{2k}{2n}2\pi+i\sin\dfrac{2k}{2n}2\pi=\omega_{2n}^{2k}$。

以及 $\omega_n^i=-\omega_n^{i+\frac{n}{2}}$，就是类似一个多边形对角线的性质。

因为两个点关于原点对称所以有这个定理，很显然。

那么下面就是整活的推柿子了。

设 $f(n)=\sum\limits_{i=0}^{n-1}a_ix^i=a_0+a_1x+a_2x^2+…+a_{n-1}x^{n-1}$

默认 $n$ 为奇数，方便计算。

那么将 $f(n)$ 按照下标奇偶性分成两半

$=(a_0+a_2x^2+…+a_{n-2}x^{n-2})+(a_1x+a_3x^3+…+a_{n-1}x^{n-1})$
$=(a_0+a_2x^2+…+a_{n-2}x^{n-2})+x(a_1+a_3x^2+…+a_{n-1}x^{n-2})$

然后因为两边非常相似，所以设

$f_1(n)=a_0+a_2x+a_4x^2+…+a_{n-2}x^{\frac{n-2}{2}}$
$f_2(n)=a_1+a_3x+a_5x^2+…+a_{n-1}x^{\frac{n-2}{2}}$

很明显可以把 $f_1$ 和 $f_2$ 代进去。

原式 $=f_1(n^2)+n\times f_2(n^2)$

然后可以开始 DFS / 迭代这样子做，前半段设有 $i<\dfrac{n}{2}$，那么把 $x=\omega_n^i$ 代入原式

$f(\omega_n^i)=f_1((\omega_n^i)^2)+\omega_n^i\times f_2((\omega_n^i)^2)$

然后因为是平方，所以 $2$ 可以乘到上面去，所以有

原式 $=f_1(\omega_n^{2i})+\omega_n^i \times f_2(\omega_n^{2i})=f_1(\omega_{\frac{n}{2}}^i)+\omega_n^i \times f_2(\omega_{\frac{n}{2}}^i)$

后面那个成立是因为 $\omega_{n}^i=\omega_{2n}^{2i}$。

因为分治特别好玩，所以后面那段也要分治。

同理可以推推推，设 $t=\dfrac{n}{2}$（手敲累了）。

$f(\omega_n^{i+t})=f_1(\omega_n^{2i+n})+\omega_n^{i+t}\times f_2(\omega_n^{2i+n})$

因为显然有 $\omega_{n}^{2i+n}=\omega_n^n \times \omega_{n}^{2i}$
所以直接拆开，因为 $\omega_n^n=\omega_n^0=0$，跑路。

原式 $=f_1(\omega_n^{2i})+\omega_n^{i+t} \times f_2(\omega_n^{2i})$

做到这里发现推不动了，直到看到 $\omega_n^i=-\omega_n^{i+\frac{n}{2}}$ 这个玩意我们发现可以代进去。

原式 $=f_1(\omega_n^{2i})-\omega_n^i\times f_2(\omega_n^{2i})$。

然后因为 $\omega_{n}^i=\omega_{2n}^{2i}$ 有原式 $=f_1(\omega_{t}^i)-\omega_n^i \times f_2(\omega_{t}^i)$

最后发现后面那一项，两半分别为相反数。
所以我们知道 $f(\omega_n^i)$ 和 $f(\omega_n^{i+t})$ 只有后面那个地方不同。
换句话说知道了 $f(\omega_{n}^i)$ 就算出了 $f(\omega_n^{i+t})$。

那么就可以这样迭代下去求了。

时间复杂度 $O(\sum\limits_{i=0}^{\log_2N}2^i)=O(N \log N)$。

好耶，没有代码。

听说 DFS 版本的狒狒贴会 TLE。
到时候应该会贴一个迭代版本的狒狒贴上来。

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
#include <math.h>
#include <vector>
#include <stdio.h>
#include <algorithm>
#define rg register

namespace IO {

  const int MAX_LEN = 5e7;
  static char bufin[MAX_LEN], *p1 = bufin;
  #define gc() (*p1++)
  #define isd(ch) (ch>47&&ch<58)

  template <typename T>
  inline static void read(T &ret) {
    ret = 0; rg T f = 1; char ch = gc();
    while (!isd(ch) && ch^'-') ch = gc();
    if (ch=='-') f = -1, ch = gc();
    while (isd(ch)) ret = ret*10+(ch^48), ch = gc();
    return ;
  }

  int cnt, tp;
  static char bf[20], buf[MAX_LEN];

  template <typename T>
  inline static void print(T Num) {
    if (!Num) { buf[cnt++] = '0', buf[cnt++] = ' '; return ; }
    if (Num<0) buf[cnt++] = '-', Num = -Num;
    tp = 0; while (Num)
      bf[tp++] = Num%10^48, Num /= 10;
    while (tp) buf[cnt++] = bf[--tp];
    buf[cnt++] = ' '; return ;
  }

}

namespace Math {

  const int MAX_SIZE = 1e6 + 10;
  int Md, Range, fac[MAX_SIZE];

  template <typename T>
  inline static T qpow(T bas, T pw) {
    T mult = 1;
    while (pw) {
      if (pw&1) mult = mult * bas % Md;
      bas = bas * bas % Md, pw >>= 1;
    } return mult;
  }

  template <typename T>
  inline static T inv(T x) { return qpow(x, Md-2); }
  template <typename T>
  inline static void init() {
    fac[0] = fac[1] = 1;
    for (rg int i=2; i<=Range; ++i)
      fac[i] = 1LL * fac[i-1] * i % Md;
    return ;
  }

}

using namespace IO;
using namespace Math;

const double pi = acos(-1.0);
const int N = 3e6 + 10;

struct cplx {
  double real, im;
  cplx (double real, double im):
    real(real), im(im) {}
  cplx() {}
} x[N], y[N];

// 手写复数太丑了略过

int n, m, Log, Lim = 1;
int status[N];

inline void FFT(cplx *x, int typ) {
  for (int i=0; i<Lim; ++i)
    if (i<status[i]) Swap(x[i], x[status[i]]);
  for (int mid=1; mid<Lim; mid<<=1) {
    cplx omega(cos(pi/mid), typ*sin(pi/mid));
    for (int rig=mid<<1, pos=0; pos<Lim; pos+=rig) {
      cplx pw(1, 0);
      for (int k=0; k<mid; ++k, pw=pw*omega) {
        cplx buf1 = x[pos+k], buf2 = pw * x[pos+k+mid];
        x[pos+k] = buf1 + buf2, x[pos+k+mid] = buf1 - buf2;
      }
    }
  } return ;
}

int main() {
  fread(IO::bufin, 1, 50000000, stdin);
  IO::read(n), IO::read(m);
  for (int i=0; i<=n; ++i) IO::read(x[i].real);
  for (int i=0; i<=m; ++i) IO::read(y[i].real);
  while (Lim<=(n+m)) ++Log, Lim<<=1;
  for (int i=0; i<Lim; ++i)
    status[i] = (status[i>>1]>>1) | ((i&1)<<(Log-1));
  FFT(x, 1), FFT(y, 1);
  for (int i=0; i<=Lim; ++i) x[i] = x[i] * y[i];
  FFT(x, -1); for (int i=0; i<=n+m; ++i)
    IO::print((int)(x[i].real/Lim+.5));
  fwrite(IO::buf, 1, IO::cnt, stdout); return 0;
}

闹太套主要思想就是把毒瘤的狒狒贴复数给换掉
换成一种可以代替复数的、并且能够解决精度问题的东西，原根。

介绍几个专有名词。

阶：如果 $\gcd(a,p)=1$ 并且 $p>1$，
那么对于 $n_{\min}$ 满足 $a^n \equiv 1 \space (\bmod \space p)$，我们称 $n$ 为 $a$ 模 $p$ 的阶，记作 $\delta_p(a)$。

原根：设 $p \in N^*,\space a \in Z$（不会打 $\LaTeX$，轻喷）。
如果 $\delta_p(a)=\phi(p)$，则称 $a$ 为模 $p$ 的一个原根。

原根存在的充要条件是，原根 $d=2,4,x^y,2x^y$（其中 $x$ 为奇素数，$y \ge 1$）。
每一个正整数 $p$ 都有 $\phi(\phi(p))$ 个原根，素数也一样。

闹太套到这里基本上就出来了，也就是最重要的定理：

  • 若 $p$ 为素数且 $g$ 为 $p$ 的原根，那么 $g^i \bmod p$ 的结果两两不同。
    其中$g \in (1,p), \space i \in (0,p)$

这玩意儿可以代替原来的复数来进行狒狒贴，所以有了个新名字，闹太套。
狒狒贴里面不是用到了单位根的几条性质吗，恰好原根也满足这几个性质。
所以原根就可以拿来代替毒瘤的复数了。（

如果有证明欢迎私信，我会蒯走

那么我们直接将 $\omega_i$ 替换为 $g^{\frac{p-1}{i}} \bmod p$ 即可。
$p$ 的取值嘛，听大佬说 $p$ 取 $998244353$ 非常好，原根为 $3$。

关于求原根，这个鸽子咕了 … …
大概求解任意一个质数 $t$ 的原根，只需要把 $t-1$ 分解质因数
变成 $t=\prod\limits_{i=1}^np_i^{k_i}$ 这样的乘积形式
然后如果 $\forall 1 \le i \le n, \space g^{\frac{t-1}{p_i}} \not =1 \space (\bmod\space t)$，那么 $g$ 为 $p$ 原根。

人太懒了没有加 fread 和 fwrite，导致跑得比狒狒贴还慢。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e6 + 10;
const int Mod = 998244353;
int n, m, Lim = 1, Log, status[N];
int a[N], b[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 ;
}

int qpow(int bas, int pw) {
  int mul = 1;
  while (pw) {
    if (pw&1) mul = mul * bas % Mod;
    bas = bas * bas % Mod;
    pw >>= 1;
  } return mul;
}

void NTT(int *x, int typ) {
  for (int i=0; i<Lim; ++i)
    if (i<status[i]) swap(x[i], x[status[i]]);
  for (int mid=1; mid<Lim; mid<<=1) {
    int omega = qpow(typ==1? 3:332748118, (Mod-1)/(mid<<1));
    for (int pos=0; pos<Lim; pos+=(mid<<1)) {
      int pw = 1;
      for (int k=0; k<mid; ++k, pw = (pw*omega)%Mod) {
        int buf1 = x[pos+k], buf2 = pw * x[pos+k+mid] % Mod;
        x[pos+k] = (buf1 + buf2) % Mod;
        x[pos+k+mid] = ((buf1 - buf2) % Mod + Mod) % Mod;
      }
    }
  } return ;
}

signed main() {
  read(n), read(m);
  for (int i=0; i<=n; ++i) read(a[i]);
  for (int i=0; i<=m; ++i) read(b[i]);
  while (Lim<=(n+m)) ++Log, Lim<<=1;
  for (int i=0; i<Lim; ++i)
    status[i] = (status[i>>1]>>1) | ((i&1)<<(Log-1));
  NTT(a, 1), NTT(b, 1);
  for (int i=0; i<Lim; ++i) a[i] = (a[i] * b[i]) % Mod;
  NTT(a, -1); int inv = qpow(Lim, Mod-2);
  for (int i=0; i<=n+m; ++i)
    printf("%lld ", a[i] * inv % Mod);
  return 0;
}
一些卡常的小技巧
咕咕咕的动态淀粉质
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 Notes2 minutes read (About 371 words)

差分约束专题

显然题。

首先有 $x_{c1}-x_{c1’} \le y_1$。
那么有 $x_{c1} \le x_{c1’} + y_1$。
所以看到图论里面的松弛操作，即最终使得 dist[to]<=dist[cur]+e[i].val。

要使得这个成立所以要跑一遍最短路。

那么将 $x$ 视为 dist，c1 视为 to，c1' 视为 cur 即可。

然后因为跑最短路的 dijkstra 需要源点，即单源最短路径。
所以直接造一个源点就可以跑了，并没有什么实际作用（

判负环似乎只需要加上一个统计入队次数的 cnt 即可。
因为显然，有负环就没有合法解。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 5e3 + 10;
int n, m, cnt; bool inq[N];
int head[N<<1], dist[N], vis[N];

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

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 ;
}

bool spfa() {
  queue <int> sp; sp.push(0);
  vis[0] = 1, inq[0] = true;
  memset(dist, 0x3f, sizeof dist);
  dist[0] = 0;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (dist[to] > dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) {
          inq[to] = true, sp.push(to);
          ++vis[to]; if (vis[to]>n) return true;
        }
      }
    }
  }
  return false;
}

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m;
  for (int i=1; i<=m; ++i) {
    int u, v, w; cin >> u >> v >> w;
    addEdge(v, u, w);
  }
  for (int i=1; i<=n; ++i) addEdge(0, i, 0);
  if (spfa()) { puts("NO"); return 0; }
  for (int i=1; i<=n; ++i) cout << dist[i] << ' ';
  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;
}
网络流 24 题 trick 记录（含代码）
Posted Updated Notes19 minutes read (About 2826 words)

网络流 24 题 trick 记录（含代码）

只要默认前面 $m$ 个都是外国的，然后剩下的都是英国的，接着暴力建图跑 Dinic 即可。
貌似只需要弄一个源点 $0$ 和汇点 $n+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
#include <bits/stdc++.h>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 2e4 + 10;
int n, m, cnt = 1;
int head[N], dep[N];
bool vis[N];

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

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 ;
}

bool check() {
  for (int i=0; i<=n+1; ++i) dep[i] = 0;
  dep[0] = 2; queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (!dep[to] && e[i].val) {
        dep[to] = dep[cur] + 1, sp.push(to);
        if (to==n+1) return true;
      }
    }
  }
  return false;
}

int dfs(int cur, int Max) {
  if (cur==n+1) return Max;
  int increase = Max;
  for (int i=head[cur]; i&&increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].val && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].val));
      e[i].val -= res, e[i^1].val += res;
      if (!res) dep[to] = 0;
      increase -= res;
    }
  }
  return Max-increase;
}

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 ;
}

int main() {
  read(m), read(n);
  while (1) {
    int u, v; read(u), read(v);
    if (u==-1 && v==-1) break;
    addEdge(u, v, inf);
    addEdge(v, u, 0);
  }
  for (int i=1; i<=m; ++i)
    addEdge(0, i, 1), addEdge(i, 0, 0);
  for (int i=m+1; i<=n; ++i)
    addEdge(i, n+1, 1), addEdge(n+1, i, 0);
  int ans = 0;
  while(check()) ans += dfs(0, inf);
  cout << ans << endl;
  for (int i=2; i<=cnt; i+=2) {
    if (!e[i^1].val) continue;
    if (!e[i].to || !e[i^1].to) continue;
    if (e[i].to==n+1) continue;
    if (e[i^1].to==n+1) continue;
    printf("%d %d\n", e[i^1].to, e[i].to);
  }
  return 0;
}

这道题最重要的是连边。
那么很显然的拆点技巧，将一天拆成服务和收工两个点，即 i+N 和 i，后前两个点。
那么源点为 0，汇点为 2*N+1。

  • 要购买餐巾

显然从源点处购买，直接建边 add(0,i+N,inf,p)。

  • 偷懒先不洗餐巾

显然直接延到下一天，add(i,i+1,inf,0)。

  • 快洗

显然直接丢到 $m$ 天后，add(i,i+N+m,inf,f)。

  • 慢洗

同理丢到 $n$ 天后，add(i,i+N+n,inf,s)。

然后每一天要跑至少为 r[i] 的流量，直接源点连收工，汇点连服务。

然后跑一遍最小费用最大流即可。

nt 的地方：DFS 要标记 cur，数组不要开小。
要是写对了正解然后数组开小了那就真的是个 zz。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXN = 2e3 + 10;
const int inf = 2e9;

int N, cnt = 1, head[MAXN*12];
int p, m, f, n, s, dist[MAXN*12];
bool inq[MAXN*2], vis[MAXN*2];
int cost;

struct Edge {
  int to, nxt, flow, val;
} e[MAXN*12];

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

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0, e[cnt].val = -w;
  head[v] = cnt; 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 ;
}

bool spfa() {
  for (int i=0; i<=2*N+1; ++i)
    dist[i] = inf, inq[i] = false;
  dist[0] = 0, inq[0] = true;
  queue <int> sp; sp.push(0);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) inq[to] = true, sp.push(to);
      }
    }
  }
  return dist[2*N+1] < inf;
}

int dfs(int cur, int Max) {
  if (cur == 2*N+1) { vis[cur] = true; return Max; }
  int increase = Max; vis[cur] = true;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to] || to==MAXN) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      cost += res * e[i].val, increase -= res;
    }
  }
  return Max-increase;
}

signed main() {
  cin >> N;
  for (int i=1; i<=N; ++i) {
    int r; cin >> r;
    addEdge(0, i, r, 0);
    addEdge(i+N, 2*N+1, r, 0);
  }
  cin >> p >> m >> f >> n >> s;
  // begin point: i
  // ending point: i+N
  for (int i=1; i<=N; ++i) {
    addEdge(0, i+N, inf, p);
    if (i<N) addEdge(i, i+1, inf, 0);
    if (i+m<=N) addEdge(i, i+N+m, inf, f);
    if (i+n<=N) addEdge(i, i+N+n, inf, s);
  }
  while (spfa()) {
    for (int i=0; i<=2*N+1; ++i) vis[i] = false;
    dfs(0, inf);
  }
  cout << cost << endl;
  return 0;
}

这道题为什么要网络流啊。

难道不是直接暴力 BFS 寻找路径吗？

直接状压一下钥匙，然后每一次到达门就看有没有钥匙就可以了。

nt 的地方：x(x), y(y) 写成了 x(x), y(x) … …

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
#include <bits/stdc++.h>
using namespace std;

const int N = 11;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int n, m, p, k, s, door[N][N][N][N];
int cnt[N][N], key[N][N][N];
bool vis[N][N][1<<N];

struct spread {
  int x, y, Key, cost;
  spread(int x, int y, int Key, int cost):
    x(x), y(y), Key(Key), cost(cost) {}
  spread() {}
};

int keyset(int x, int y) {
  int S = 0;
  for (int i=1; i<=cnt[x][y]; ++i)
    S |= (1<<(key[x][y][i]-1));
  return S;
}

bool check(int x, int y, int k, int st) {
  if (x<1 || x>n) return false;
  if (y<1 || y>m) return false;
  if (k<0 || (k && !(st&(1<<(k-1))))) return false;
  return true;
}

int bfs() {
  int x = 1, y = 1;
  int S = keyset(x, y);
  queue <spread> que; que.push(spread(x, y, S, 0));
  vis[x][y][S] = true;
  while (!que.empty()) {
    spread cur = que.front(); que.pop();
    x = cur.x, y = cur.y, S = cur.Key;
    if (x==n && y==m) return cur.cost;
    for (int i=0; i<4; ++i) {
      int tox = x + dx[i], toy = y + dy[i];
      int Door = door[x][y][tox][toy];
      if (!check(tox, toy, Door, S)) continue;
      int to = S|keyset(tox, toy);
      if (vis[tox][toy][to]) continue;
      vis[tox][toy][to] = true;
      que.push(spread(tox, toy, to, cur.cost+1));
    }
  }
  return -1;
}

int main() {
  cin >> n >> m >> p >> k;
  while (k--) {
    int x, y, X, Y, G;
    cin >> x >> y >> X >> Y >> G;
    if (G) door[x][y][X][Y] = door[X][Y][x][y] = G;
    else door[x][y][X][Y] = door[X][Y][x][y] = -1;
  }
  cin >> s;
  while (s--) {
    int x, y, Q; cin >> x >> y >> Q;
    key[x][y][++cnt[x][y]] = Q;
  }
  cout << bfs() << endl;
  return 0;
}

众所周知最小路径覆盖 $=$ 顶点数 $-$ 最大匹配数，这个是很显然的。

Proof：因为对于每一个点一开始都可以作为一条路径，所以一开始就有 $n$ 条路径。因为每一次匹配相当于把两个点合并，所以路径条数相当于减掉了 $1$，所以最大匹配数就是合并的个数，所以最后就是 $n-$最大匹配数。
又因为二分图可以网络流乱搞，所以路径覆盖也可以网络流乱搞。

所以正常的 trick，拆点跑最大流。
路径输出比较正常，直接在 DFS 的时候找到起始点然后记录路径即可。

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
#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;
const int inf = 1e9;

int n, m, s, t, cnt = 1;
int dep[N], head[N]; bool inq[N];
int cost, path[N]; bool vis[N];

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

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

  e[++cnt].to = u;
  e[cnt].nxt = head[v];
  e[cnt].flow = 0; head[v] = cnt;
  return ;
}

bool check() {
  for (int i=0; i<=t; ++i)
    dep[i] = inf, inq[i] = false;
  dep[s] = 0; queue <int> sp;
  sp.push(s); inq[s] = true;
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t] ^ inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) { dep[to] = -1; continue; }
      e[i].flow -=  res, e[i^1].flow += res;
      path[cur] = to; if (cur) vis[to-n] = true;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  cin >> n >> m; t = 2*n+1;
  for (int i=1; i<=m; ++i) {
    int u, v; cin >> u >> v;
    addEdge(u, n+v, 1);
  }
  for (int i=1; i<=n; ++i) addEdge(s, i, 1);
  for (int i=1; i<=n; ++i) addEdge(i+n, t, 1);
  int ans = 0; while (check()) ans += dfs(s, inf);
  for (int i=1; i<=n; ++i) {
    if (vis[i]) continue;
    int cur = i; cout << i;
    while(path[cur] && path[cur]^t)
      cout << ' ' << path[cur]-n, cur = path[cur]-n;
    cout << endl;
  }
  cout << n-ans << endl;
  return 0;
}

听名字还挺高大上的。

其实就是个卡牌游戏啊，只不过每一次只可以交换环上相邻两个。
那么直接断环成链，拿原数减掉最后的固定答案然后前缀和加到 ans。

顺带卡了下常，12ms 最优解 Rank1。

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
#include <stdio.h>
int n, sum, ans, a[110], Sum[110];

int abs(int x) { return x>0? x:-x; }

void qsort(int l, int r) {
  int mid = Sum[(l+r)>>1];
  int i=l, j=r;
  do {
    while (Sum[i]<mid) ++i;
    while (Sum[j]>mid) --j;
    if(i<=j) {
      int u=Sum[i]; Sum[i]=Sum[j]; Sum[j]=u;
      i++, j--;
    }
  } while (i<=j);
  if (l<j) qsort(l, j);
  if (i<r) qsort(i, r);
  return ;
}

int main() {
  scanf("%d", &n);
  for (int i=1; i<=n; ++i)
    scanf("%d", &a[i]), sum += a[i];
  sum /= n;
  for (int i=1; i<=n; ++i)
    Sum[i] = Sum[i-1]+a[i]-sum, a[i] = Sum[i];
  qsort(1, n); int mid = n/2+1;
  for (int i=1; i<=n; ++i)
    ans += abs(Sum[mid]-Sum[i]);
  printf("%d\n", ans);
  return 0;
}

简单题。

首先看到点有限制，直接拆点。

那么因为没有给出单源点和汇点，分别建一个。

接着可以将 * 视为连向源点，所以边权为 $1$。
同理 # 视为连向汇点，边权为限制 $p$。

然后因为 . 只能踩一次，所以拆成两个点，两个点之间的限制为 $1$。
@ 可以踩无数次，所以连 INF。

接着因为周边四个点都可以扩展到（除起始点和水显然不可以扩展）。
所以连容量为 INF 的边。

然后跑一遍最大流。

记得多测 cnt 要赋成 $1$ 而不是 $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
82
83
84
85
86
87
88
89
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
const int inf = 1e9;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, p, s, t, cnt = 1;
int dep[N], head[N]; char ch[40][40];

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

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

bool check(int x, int y) {
  return x<1 || x>n || y<1 || y>m;
}

void init() {
  cnt = 1; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) cin >> ch[i][j];
  memset(head, -1, sizeof head);
  return ;
}

int id(int x, int y) { return (x-1)*m+y; }
bool spfa() {
  for (int i=s; i<=t; ++i) dep[i] = inf;
  dep[s] = 0; queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dep[to]==inf) {
        dep[to] = dep[cur] + 1, sp.push(to);
      }
    }
  }
  return dep[t]^inf;
}

int dfs(int cur, int Max) {
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if (e[i].flow && dep[to]==dep[cur]+1) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res;
    }
  }
  return Max-increase;
}

int main() {
  while (scanf("%d%d%d", &n, &m, &p) != EOF) {
    init(); int siz = n*m;
    for (int i=1; i<=n; ++i) {
      for (int j=1; j<=m; ++j) {
        if (ch[i][j] == '~') continue;
        if (ch[i][j] == '*') addEdge(s, id(i,j), 1);
        if (ch[i][j] == '.') addEdge(id(i,j), id(i,j)+siz, 1);
        if (ch[i][j] == '#') addEdge(id(i,j), t, p);
        for (int k=0; k<4; ++k) {
          int tox = i+dx[k], toy = j+dy[k];
          if (check(tox, toy)) continue;
          if (ch[tox][toy] == '*' || ch[tox][toy] == '~') continue;
          if (ch[i][j] == '.') addEdge(id(i,j)+siz, id(tox, toy), inf);
          else addEdge(id(i,j), id(tox, toy), inf);
        }
      }
    }
    int ans = 0;
    while (spfa()) ans += dfs(s, inf);
    cout << ans << endl;
  }
  return 0;
}

这题也是个拆点模板。
首先 S 连向出点，T 连向入点，默认已经拆完点。
所以因为要使得成为循环格，所以要进行两两之间点的匹配。
即入度、出度均为 $1$。

所以跑二分图匹配最小费用即可。
建边的 value 只需要看当前点实际指的方向是否是枚举的方向。
如果是费用为 $0$，否则为 $1$。

最后要注意：cnt 要赋成 $1$！！11

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
const int inf = 114514;

int n, m, s, t, cnt = 1, cost;
int dist[N], head[N];
bool vis[N], inq[N];
char Map[20][20]; int To[20][20];

const int dx[] = {0, 0, -1, 1};
const int dy[] = {-1, 1, 0, 0};

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

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

bool spfa() {
  for (int i=s; i<=t; ++i)
    inq[i] = false, dist[i] = inf;
  dist[s] = 0, inq[s] = true;
  queue <int> sp; sp.push(s);
  while (!sp.empty()) {
    int cur = sp.front(); sp.pop();
    inq[cur] = false;
    for (int i=head[cur]; ~i; i=e[i].nxt) {
      int to = e[i].to;
      if (e[i].flow && dist[to]>dist[cur]+e[i].val) {
        dist[to] = dist[cur] + e[i].val;
        if (!inq[to]) { inq[to] = true; sp.push(to); }
      }
    }
  }
  return dist[t]^inf;
}

int dfs(int cur, int Max) {
  vis[cur] = true;
  if (cur==t) return Max;
  int increase = Max;
  for (int i=head[cur]; ~i && increase; i=e[i].nxt) {
    int to = e[i].to;
    if ((!vis[to]||to==t) && e[i].flow && dist[to]==dist[cur]+e[i].val) {
      int res = dfs(to, min(increase, e[i].flow));
      if (!res) continue;
      e[i].flow -= res, e[i^1].flow += res;
      increase -= res, cost += res * e[i].val;
    }
  }
  return Max-increase;
}

int id(int x, int y) { return (x-1)*m+y; }

int main() {
  memset(head, -1, sizeof head);
  cin >> n >> m; t = 2*n*m + 1;
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      cin >> Map[i][j];
      if (Map[i][j]=='L') To[i][j] = 0;
      if (Map[i][j]=='R') To[i][j] = 1;
      if (Map[i][j]=='U') To[i][j] = 2;
      if (Map[i][j]=='D') To[i][j] = 3;
    }
  for (int i=1; i<=n; ++i) {
    for (int j=1; j<=m; ++j) {
      for (int k=0; k<4; ++k) {
        int tox = i+dx[k], toy = j+dy[k];
        if (tox<1) tox = n; if (tox>n) tox = 1;
        if (toy<1) toy = m; if (toy>m) toy = 1;
        addEdge(id(i,j)+n*m, id(tox, toy), 1, k!=To[i][j]);
      }
    }
  }
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=m; ++j) {
      addEdge(s, id(i,j)+n*m, 1, 0);
      addEdge(id(i,j), t, 1, 0);
    }
  int ans = 0;
  while (spfa()) {
    for (int i=s; i<=t; ++i) vis[i] = false;
    ans += dfs(s, inf);
  }
  cout << cost << endl;
  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

×

×