Posted 2021-09-04Updated 2021-09-04Notes7 minutes read (About 980 words)

可持久化数据结构

可持久化线段树 1

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

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

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

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

可持久化线段树 2

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

如果我们要找到区间第 $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$ 了。

#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 2021-08-31Updated 2021-09-04Notes15 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。
到时候应该会贴一个迭代版本的狒狒贴上来。

#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，导致跑得比狒狒贴还慢。

#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 2021-08-20Updated 2021-09-04Notesa minute read (About 154 words)

一些卡常的小技巧

Here's something encrypted, password is required to continue reading.

Posted 2021-08-13Updated 2021-09-04Notes5 minutes read (About 775 words)

咕咕咕的动态淀粉质

膜拜动态淀粉质。

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

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

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

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

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

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

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

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

淀粉质 AC 代码。

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

Posted 2021-08-09Updated 2021-09-04Notes20 minutes read (About 2993 words)

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

SP1043 GSS1

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

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

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

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

SP1716 GSS3

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

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

SP2713 GSS4

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

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

LOJ6277 数列分块1

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

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

LOJ6278 数列分块2

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

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

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

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

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

LOJ6279 数列分块3

区间加法，区间前驱。

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

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

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

LOJ6280 数列分块4

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

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

LOJ6281 数列分块5

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

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

LOJ6282 数列分块6

单点插入，单点查询。

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

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

LOJ6283 数列分块7

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

#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 2021-08-07Updated 2021-09-04Notesa minute read (About 168 words)

比较奇妙的小错误

Here's something encrypted, password is required to continue reading.

Posted 2021-08-04Updated 2021-09-04Notes10 minutes read (About 1480 words)

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

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

P1908 逆序对

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

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

那么代码如下。

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

#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

P3313 旅行

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

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

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

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

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

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

然后就没了。

似乎并不毒瘤？

#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 2021-08-04Updated 2021-08-05Sol10 minutes read (About 1456 words)

CF961G Solution

CF961G Partitions

这题好神啊 … 我发现我一直 WA5 的原因是开始统计和的时候没有取模（
然后就想着写篇题解记录一下 …

首先题目不是要求一个和吗。

那么通过人类智慧发现很显然所有数出现的次数都是一样的。
也就是说最后的和式必然是 $…\times \sum\limits_{i=1}^nw_i$ 这样的形式。

那么不妨将前面的系数设为 $p$。

我们对于这个问题其实可以用 DP 的思想来解决。
我们对于求整个柿子的系数，直接考虑枚举子集大小。
然后就可以发现我们当前选了 $i$ 个，然后算出自己集合的方案和别的集合的方案即可。
最后相乘累加就是答案，其中运用的是第二类斯特林数的思想。

第二类斯特林数就解决的是这样一类问题：

$n$ 个物品放入 $m$ 个不同集合中，求集合非空的总方案数。

想要研究的同学可以自行研究，这里不再赘述。

所以就可以得到系数 $p$ 变成了下面的柿子。

$$p=\sum\limits_{i=1}^ni\binom{n-1}{i-1}S_2(n-i,k-1)$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\dfrac{1}{(k-1)!}\sum\limits_{j=0}^{k-1}(-1)^j\binom{k-1}{j}(k-j-1)^{n-i}$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\dfrac{1}{(k-1)!}\sum\limits_{j=0}^{k-1}(-1)^j\dfrac{(k-1)!}{j!\times(k-j-1)!}(k-j-1)^{n-i}$$
$$=\sum\limits_{i=1}^ni\binom{n-1}{i-1}\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j(k-j-1)^{n-i}}{j!\times(k-j-1)!}$$
$$=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}\sum\limits_{i=1}^ni\binom{n-1}{i-1}(k-j-1)^{n-i}$$

注意上面将 $j$ 的和式提前了，这显然是正确的。
因为分母相同相加分母不变，然后 $-1$ 的系数显然只和 $j$ 有关。
但是分子剩下的部分 $(k-j-1)^{n-i}$ 显然和 $i$ 和 $j$ 都有关。
所以为了方便后面的推导，这里直接将 $j$ 提前作为后面那一堆和的系数。
这里说的 方便推导 其实也没有什么非常清晰的界定，只是这部分可以简单解决。
当然不排除有暴力老哥直接卷的情况。（
其实我也不知道可不可以卷，因为我没学多项式（（

所以看到一大堆阶乘，在保证答案正确性的情况下，直接从一大堆柿子里面拎出来是必要的。

然后后面那个 $(k-j-1)$ 看起来特别丑，弄成 $s$。

$$\sum\limits_{i=1}^ni\binom{n-1}{i-1}s^{n-i}$$
$$=\sum\limits_{i=1}^ni\times s^{n-i}\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$

为了约分上面的组合数拆开了。

然后有一个 trick，
看到分母有一个 $i-1$，看到前面的系数 $i$，
所以把那个 $i$ 给拆掉，拆成 $i=i-1+1$。

所以有

$$=\sum\limits_{i=1}^ns^{n-i}\times(i-1+1)\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$
$$=\sum\limits_{i=1}^ns^{n-i}[(i-1)\times \dfrac{(n-1)!}{(i-1)! \times (n-i)!}+\dfrac{(n-1)!}{(i-1)! \times (n-i)!}]$$
$$=\sum\limits_{i=1}^ns^{n-i}(i-1)\dfrac{(n-1)!}{(i-1)! \times (n-i)!}+\sum\limits_{i=1}^ns^{n-i}\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$

然后约掉共同的 $i-1$。

$$=\sum\limits_{i=1}^ns^{n-i}\dfrac{(n-1)!}{(i-2)! \times (n-i)!}+\sum\limits_{i=1}^n\dfrac{(n-1)!}{(i-1)! \times (n-i)!}$$

再重新写成方便的组合数形式。

$$=\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{i-2}+\sum_{i=1}^ns^{n-i}\binom{n-1}{i-1}$$

由于这个上下不统一所以把 $(n-1)$ 提出来。

$$=(n-1)\sum\limits_{i=1}^ns^{n-i}\binom{n-2}{i-2}+\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{i-1}$$

然后发现这个玩意儿好像很不好算，
所以变成下面这样，因为 $\binom{n}{m}=\binom{n}{n-m}$。

$$=(n-1)\sum\limits_{i=1}^ns^{n-i}\binom{n-2}{n-i}+\sum\limits_{i=1}^ns^{n-i}\binom{n-1}{n-i}$$

然后根据那个什么柿子的展开，就是杨辉三角的系数，
观察到 $n-i$ 的共同部分可以运用上这个公式，
可以发现这个可以直接把组合数拆开变成幂。

实际上那个 $\sum\limits_{i=1}^n$ 有一些项应该是不能算的，因为组合数其实等于 $0$。
所以根据 $(a+b)^n$ 的系数其实就是组合数，可以直接代进去。

即 $(a+b)^n=\sum\limits_{i=0}^n\binom{n}{i}a^{n-i}b^i$。

应该长成这样吧，不太确定有没有问题。

所以又可以化简成下面那样。

$$=(n-1)(s+1)^{n-2}+(s+1)^{n-1}$$
$$=(s+1)^{n-2}(s+1+n-1)$$
$$=(s+1)^{n-2}(s+n)$$

然后就可以代回去了。

$$p=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}[(n-1)(k-j)^{n-2}+(k-j)^{n-1}]$$
$$=\sum\limits_{j=0}^{k-1}\dfrac{(-1)^j}{j!\times(k-j-1)!}(k-j)^{n-2}(n+k-j-1)$$

所以就可以得出代码了。
我的时间复杂度比较劣，代码还是参考别人的吧。

时间复杂度 $\Theta(k \log \text{Mod})$。

不要问我为什么后面是 $\text{Mod}$ 而不是 $n$（
问就是逆元没有线性求，直接 qpow(x,mod-2)（（（

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
int n, k, cnt, sum, a, jc[N];

void init() {
  jc[0] = jc[1] = 1ll;
  for (int i=2; i<=k; ++i)
    jc[i] = jc[i-1] * i % MOD;
    // 预处理阶乘
  return ;
}

int qpow(int bas, int pw) {
  int mult = 1ll;
  while (pw) {
    if (pw & 1ll) mult = mult * bas % MOD;
    bas = bas * bas % MOD;
    pw /= 2;
    // 貌似是个 UB，不能写 >>=1ll
  } return mult;
}

int inv(int x) { return qpow(x, MOD-2); }

signed main() {
//   freopen("sum.in", "r", stdin);
  // freopen("sum.out", "w", stdout);
  scanf("%lld%lld", &n, &k); init();
  for (int i=1; i<=n; ++i)
    scanf("%lld", &a), cnt = (cnt + a) % MOD;
  int Sum = 0;
  for (int i=0; i<k; ++i) {
    int cur = inv(jc[i]);
    cur = cur * inv(jc[k-i-1]) % MOD;
    int f = i&1? -1 : 1;
    cur = f * cur % MOD, cur = (cur % MOD + MOD) % MOD;
    cur = cur * qpow(k-i, n-2) % MOD;
    cur = cur * (n+k-i-1) % MOD;
    Sum = (Sum + cur) % MOD;
    // 对于分母求逆元再乘分子，基本操作
  }
  cout << Sum * cnt % MOD << endl;
  return 0;
}

Posted 2021-08-04Updated 2021-08-05Sol9 minutes read (About 1326 words)

P2150 Solution

P2150 寿司晚宴

Simplification for the Question

有 $[2,n]$ 总共 $n-1$ 个数。
从中挑选一些不重复的数字（可以不全选），组成集合 $S$ 和 $T$。
求使得 $\forall x \in S,y \in T,\gcd(x,y)=1$ 的方案总数。

Part 1 - 30pts Algorithm

首先看到最简单的 30pts 算法，最暴力的部分总能给我们启示。

对于这 30pts，观察到 $n \le 30$。

那么这意味着什么呢？对，就是暴力。

首先看到 $\gcd$，求最大公约数，由唯一分解定理可知每一个数都可以由若干质数或质数的幂的连乘积构成，那么显然问题转化为：求使得 $\forall x\in S,y \in T$，设 $x$ 包含的质数集合为 $P$，设 $y$ 包含的质数集合为 $P’$，有 $P∩P’=\varnothing$，像这样的方案总数。

由于一个数的整数因数一定 $\le$ 它本身，所以说最大的质数一定 $\le n$，即 $p \le n \le 30$。
其中 $p$ 表示当前情况的质数集合。

很显然，经过枚举，我们发现 $30$ 以内有 $10$ 个质数（

所以直接暴力状压 DP，将质数的包含情况作为状态，包含为 $1$，否则为 $0$。

那么这个就是 30pts 的暴力算法了，时间复杂度 $\Theta(2^{2p}N)$，其中 $p$ 为质数个数。

Part 2 - ? pts Algorithm

我也不知道中间那两档分是用来干什么的。
所以直接看正解算了吧。/kel

Part 3 - 100pts Algorithm

首先我们判一个数是否是质数，最暴力的是这样判的。

试除法

大概就长这样

function (int n)
if n:0 / n:1 -> back(0)
for i in range(2,sqrt(n))
  if !(n mod i) -> back(0)
back(1)

那么看到这个 $\sqrt{n}$，这个就是解题的重点。

首先 $\sqrt{n} \times \sqrt{n}=n$。

接着，分两种情况讨论质数 $p$。

$p\ge\sqrt{n}$

那么设 $p \times k=n$，则显然 $k \le \sqrt{n}$。

又因为因数不大于这个数本身，所以 $\ge\sqrt{n}$ 的数最多只有两个，即 $>\sqrt{n}$ 的数最多只有一个。

$p<\sqrt{n}$

这个不用讲了吧。

那么又看到我们之前的暴力。

我们搞暴力，就是处理 $20$ 以内的质数。

但是现在我们发现 $>\sqrt{n}$ 的数最多只有一个，那么只要处理 $\le \sqrt{n}$ 的数，并且新开一个记录这个 $>\sqrt{n}$ 的数即可。

然后我们又看到 $n \le 500$。

而 $\sqrt{500}=22.360679775…$

所以说这个暴力就是个铺垫嘛，处理 $22$ 反而只有八个质数。

所以我们就想到了正解，也就是，同样枚举八个质数的情况，然后再根据大质数来判断是否可选即可。

但是我们怎么能保证大质数呢？

很显然，直接大质数从小到大结构体排个序即可。
然后对于两个人取的 DP 数，直接暴力处理然后合并即可。

注意合并的时候要容斥，因为统计会同时处理两个人都不选的情况，所以在合并的时候要减掉一个原来的数值。

恭喜你，你又 A 掉了一道黑题。

时间复杂度优化为恒定 $\Theta(2^{16}N)$

其中有一个地方要注意一下，就是在判断一开始预处理的质数情况时，贡献一定要加到对面去而不是自己的地方，因为如果加到自己的地方，无法保证对面和自己没有重复的元素，但是因为我们已经判断过这个质数和自己的关系，所以即使这个质数情况与对面有重复，加到一起仍然与自己合法，因为一定不会有重复的地方。

#include <bits/stdc++.h>
#define ri register int
using namespace std;

const int N = 5e2 + 10;
const int M = 1<<8;
const int pr[8] = {2,3,5,7,11,13,17,19};
int n, Mod, dp[M][M];
int Mer1[M][M], Mer2[M][M];
// Merge after dealing with, to DP

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

struct Number {
  int value;
  int MaxiPrime;
  int OtherPrime;
  void dealwith() {
    // deal with possible primes
    int cur = value;
    for (ri i=0; i<8; ++i) {
      // choose the primes
      if (cur % pr[i]) continue;
      // can't be devided with no left
      OtherPrime |= (1<<i);
      while (!(cur % pr[i])) cur /= pr[i];
    }
    if (cur > 1) MaxiPrime = cur;
    return ;
  }

  bool operator <(const Number &X) const {
    return MaxiPrime < X.MaxiPrime;
  }
} a[N];

void init() {
  read(n), read(Mod);
  for (ri i=2; i<=n; ++i)
    a[i-1].value = i, a[i-1].dealwith();
  sort(a+1, a+n), dp[0][0] = 1;
  return ;
}

void Merge(ri &x, ri y) {
  x = (x + y) % Mod;
  return ;
}

int main() {
  init();
  // predict:
    // Rolling Array, Back-to-Head Scan!
  for (ri i=1; i<n; ++i) {
    if (i == 1 || a[i].MaxiPrime ^ a[i-1].MaxiPrime || !a[i].MaxiPrime)
      memcpy(Mer1, dp, sizeof Mer1),
      memcpy(Mer2, dp, sizeof Mer2);
    // just copy from dp to Merge

    for (ri j=M-1; j>=0; --j)
      for (ri k=M-1; k>=0; --k) {
        // enumarate each possible situation
        // which is of the two people
        if (j&k) continue;
        // has the same elements
        if (!(j&a[i].OtherPrime))
          Merge(Mer1[j][k|a[i].OtherPrime], Mer1[j][k]);
        if (!(k&a[i].OtherPrime))
          Merge(Mer2[j|a[i].OtherPrime][k], Mer2[j][k]);
          # 需要注意的就是这里，不要写反了
      }

    if (i == n-1 || a[i].MaxiPrime ^ a[i+1].MaxiPrime || !a[i].MaxiPrime)
      for (ri j=0; j<M; ++j)
        for (ri k=0; k<M; ++k) {
          if (j&k) continue;
          // has the same elements
          ri to = Mer1[j][k] + Mer2[j][k] - dp[j][k];
          to %= Mod, dp[j][k] = to;
          dp[j][k] = (dp[j][k] + Mod) % Mod;
        }
  }
  ri ans = 0;
  for (ri i=0; i<M; ++i)
    for (ri j=0; j<M; ++j)
      if (!(i&j)) Merge(ans, dp[i][j]);
  cout << ans << endl;
  return 0;
}

Posted 2021-08-03Updated 2021-09-04Notes2 minutes read (About 371 words)

差分约束专题

P5960 差分约束算法

显然题。

首先有 $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 即可。
因为显然，有负环就没有合法解。

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

可持久化数据结构

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

一些卡常的小技巧

咕咕咕的动态淀粉质

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

比较奇妙的小错误

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

CF961G Solution

P2150 Solution

Simplification for the Question

Part 1 - 30pts Algorithm

Part 2 - ? pts Algorithm

Part 3 - 100pts Algorithm

差分约束专题

Links

Categories

Recents

Archives

Tags

Subscribe for updates

follow.it

Your browser is out-of-date!