mg娱乐电子4355_mg娱乐电子游戏平台
做最好的网站

省选前模板总结

时间:2019-12-01 08:42来源:计算机编程
写在前面 整个项目都托管在了 Github上: 查找更为方便的版本见: 这一节内容可能会用到的库文件有 Quick,同样在 Github 上可以找到。 善用 Ctrl + F 查找题目。 DATA STRUCTURE 习题lt; n, H(

写在前面

整个项目都托管在了 Github 上:
查找更为方便的版本见:
这一节内容可能会用到的库文件有 Quick,同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。

DATA STRUCTURE

习题&题解

1.数据结构

2.3.1

1.1字符串哈希

为后缀计算一个哈希值,满足(H(i)=H(i+1)x+s[i])(其中(0 leq i < n, H(n) = 0)),例如
[H(4)=s[4]]
[H(3)=s[4]x+s[3]]
一般地,(H(i)=s[n-1]x^{n-1-i}+s[n-2]x^{n-2-i}+...+s[i+1]x+s[i])
对于一段长度为L的子串s[i]~s[i+L-1],定义他的哈希值(Hash(i, L) = H(i)-H(i+L)x^L)。
预处理H和(x^L)。注意到hash值很大,我们把他存在unsigned long long中,这样就实现了自然溢出,可以大大减小常数。

题目

按照 Partition() 方法的轨迹的格式给出该方法是如何切分数组 E A S Y Q U E S T I O N 的。

1.2树状数组

解答

mg娱乐电子4355 1

1.2.1普通树状数组

树状数组好写好调,能用树状数组的时候尽量要使用。
树状数组从1开始。

int lowbit(int x) { return x & -x; }
int sum(int x) {
  int ans = 0;
  while (x) {
    ans += bit[x];
    x -= lowbit(x);
  }
  return ans;
}
void add(int i, int x) {
  while (i <= n) {
    bit[i] += x;
    i += lowbit(i);
  }
}

2.3.2

1.2.2支援区间修改的树状数组

假设对于区间([a, b])增加k,令g[i]为加了k以后的数组。
[g[i] = s[i] (i < a)]
[g[i] = s[i] + i*k - k(a-1) (i >= a 且 i <= b)]
[g[i] = s[i] + b*k - k(a-1) (i > b)]
所以我们开设两个树状数组。

题目

按照本节中快速排序所示轨迹的格式给出快速排序是如何将数组 E A S Y Q U E S T I O N 排序的(出于练习的目的,可以忽略开头打乱数组的部分)。

1.2.3二维树状数组

直接扩展就可以了。非常的直观和显然。

//bzoj3132
void change(int id, int x, int y, int val) {
  for (int i = x; i <= n; i += i & -i) {
    for (int j = y; j <= m; j += j & -j) {
      c[id][i][j] += val;
    }
  }
}
int qu(int id, int x, int y) {
  int ans = 0;
  for (int i = x; i > 0; i -= i & -i) {
    for (int j = y; j > 0; j -= j & -j) {
      ans += c[id][i][j];
    }
  }
  return ans;
}
解答

mg娱乐电子4355 2

1.3线段树

2.3.3

1.3.1普通线段树

这个线段树版本来自bzoj1798,代表了一种最基础的线段树类型,支持区间修改,多重标记下传等等操作。

//bzoj1798
void build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  if (r == l) {
    t[k].tag = 1;
    t[k].add = 0;
    scanf("%lld", &t[k].sum);
    t[k].sum %= p;
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  t[k].sum = (t[k << 1].sum + t[k << 1 | 1].sum) % p;
  t[k].add = 0;
  t[k].tag = 1;
}
void pushdown(int k) {
  if (t[k].add == 0 && t[k].tag == 1)
    return;
  ll ad = t[k].add, tag = t[k].tag;
  ad %= p, tag %= p;
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  t[k << 1].tag = (t[k << 1].tag * tag) % p;
  t[k << 1].add = ((t[k << 1].add * tag) % p + ad) % p;
  t[k << 1].sum = (((t[k << 1].sum * tag) % p + (ad * (mid - l + 1) % p)%p)%p) % p;
  t[k << 1 | 1].tag = (t[k << 1 | 1].tag * tag) % p;
  t[k << 1 | 1].add = ((t[k << 1 | 1].add * tag) % p + ad) % p;
  t[k << 1 | 1].sum = (((t[k << 1|1].sum * tag) % p + (ad * (r-mid) % p)%p)%p) % p;
  t[k].add = 0;
  t[k].tag = 1;
  return;
}
void update(int k) { t[k].sum = (t[k << 1].sum%p + t[k << 1 | 1].sum%p) % p; }
void add(int k, int x, int y, ll val) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    t[k].add = (t[k].add + val) % p;
    t[k].sum = (t[k].sum + (val * (r - l + 1) % p) % p) % p;
    return;
  }
  pushdown(k);
  if (x <= mid)
    add(k << 1, x, y, val);
  if (y > mid)
    add(k << 1 | 1, x, y, val);
  update(k);
}
void mul(int k, int x, int y, ll val) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    t[k].add = (t[k].add * val) % p;
    t[k].tag = (t[k].tag * val) % p;
    t[k].sum = (t[k].sum * val) % p;
    return;
  }
  pushdown(k);
  if (x <= mid)
    mul(k << 1, x, y, val);
  if (y > mid)
    mul(k << 1 | 1, x, y, val);
  update(k);
}
ll query(int k, int x, int y) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    return t[k].sum%p;
  }
  pushdown(k);
  ll ans = 0;
  if (x <= mid)
    ans = (ans + query(k << 1, x, y)) % p;
  if (y > mid)
    ans = (ans + query(k << 1 | 1, x, y)) % p;
  update(k);
  return ans%p;
}
题目

对于长度为 N 的数组,在 Quick.sort() 执行时,其最大元素最多会被交换多少次?

1.3.2可持久化线段树

一种可持久化数据结构。
继承一样的节点,只是把修改的重新链接,节省空间。
容易爆空间。
经常与权值线段树和二分答案结合。

int rt[maxn], lc[maxm], rc[maxm], sum[maxm];
void update(int l, int r, int x, int &y, int v) {
  y = ++sz;
  sum[y] = sum[x] + 1;
  if (l == r)
    return;
  lc[y] = lc[x];
  rc[y] = rc[x];
  int mid = (l + r) >> 1;
  if (v <= mid)
    update(l, mid, lc[x], lc[y], v);
  else
    update(mid + 1, r, rc[x], rc[y], v);
}
解答

N / 2
在快速排序中,一个元素要被交换,有以下两种情况
1.该元素是枢轴,在切分的最后一步被交换
2.该元素位于枢轴错误的一侧,需要被交换到另一侧去
注意,以上两种情况在一次切分中只会出现一次

首先来看第一种情况,如果一个元素变成了枢轴
那么在之后的切分中该元素会被排除,不存在后续的交换。
因此我们的目标应该是:
最大的元素总是出现在错误的一侧,同时切分的次数尽可能多。

接下来我们来思考如何构造这样的数组
由于我们针对的是最大的元素,因此「错误的一侧」就是枢轴的左侧。
为了使切分的次数尽可能多,我们需要保持最大值移动的距离尽量短。
但如果每次只移动一位的话,下一次切分时最大值就会变成枢轴
例如 4 10 3 5 6,枢轴为 4,交换后数组变为:
4 3 10 5 6
随后 4 和 3 交换
3 4 10 5 6
下一次切分时 10 会变成枢轴,不再参与后续的切分。
因此我们需要让最大值每次移动两个元素。

考虑下面的数组:
2 10 4 1 6 3 8 5 7 9
第一次切分的时候,枢轴为 2,10 和 1 进行交换
数组变为:
2 1 4 10 6 3 8 5 7 9
随后枢轴交换,数组变为:
1 2 4 10 6 3 8 5 7 9
第二次切分,枢轴为 4,10 和 3 进行交换。
1 2 4 3 6 10 8 5 7 9
随后枢轴交换 数组变为:
1 2 3 4 6 10 8 5 7 9
第三次切分,枢轴为 6,10 和 5 交换
1 2 3 4 6 5 8 10 7 9
随后枢轴交换,数组变为:
1 2 3 4 5 6 8 10 7 9
第四次切分,枢轴为 8,10 和 7 交换
1 2 3 4 5 6 8 7 10 9
枢轴交换,数组变为
1 2 3 4 5 6 7 8 10 9
最后一次切分,枢轴为 10,直接交换
1 2 3 4 5 6 7 8 9 10

我们可以总结出要构造这样的数组的模板
a2 max a3 a1
其中 a1 < a2 < a3 < max
max 每轮切分移动两格,总共切分 N/ 2 次。

1.3.3标记永久化

一种奇怪的姿势,又称李超线段树。
给节点打下的标记不进行下传,而是仅仅在需要的时候进行下传,这就是所谓永久化标记。
mg娱乐电子4355 3

struct line {
  double k, b;
  int id;
  double getf(int x) { return k * x + b; };
};
bool cmp(line a, line b, int x) {
  if (!a.id)
    return 1;
  return a.getf(x) != b.getf(x) ? a.getf(x) < b.getf(x) : a.id < b.id;
}
const int maxn = 50010;
line t[maxn << 2];
line query(int k, int l, int r, int x) {
  if (l == r)
    return t[k];
  int mid = (l + r) >> 1;
  line tmp;
  if (x <= mid)
    tmp = query(k << 1, l, mid, x);
  else
    tmp = query(k << 1 | 1, mid + 1, r, x);
  return cmp(t[k], tmp, x) ? tmp : t[k];
}
void insert(int k, int l, int r, line x) {
  if (!t[k].id)
    t[k] = x;
  if (cmp(t[k], x, l))
    std::swap(t[k], x);
  if (l == r || t[k].k == x.k)
    return;
  int mid = (l + r) >> 1;
  double X = (t[k].b - x.b) / (x.k - t[k].k);
  if (X < l || X > r)
    return;
  if (X <= mid)
    insert(k << 1, l, mid, t[k]), t[k] = x;
  else
    insert(k << 1 | 1, mid + 1, r, x);
}
void Insert(int k, int l, int r, int x, int y, line v) {
  if (x <= l && r <= y) {
    insert(k, l, r, v);
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    Insert(k << 1, l, mid, x, y, v);
  if (y > mid)
    Insert(k << 1 | 1, mid + 1, r, x, y, v);
}
另请参阅

Number of largest element exchanges for quicksort-Stack Overflow

1.4 平衡树

2.3.4

1.4.1 Splay伸展树

mg娱乐电子4355 4
一种最为常用的BBST。

int ch[maxn][2], fa[maxn];
int size[maxn], data[maxn], sum[maxn], la[maxn], ra[maxn], ma[maxn], cov[maxn],
    a[maxn];
bool rev[maxn];
int n, m, sz, rt;
std::stack<int> st;
void update(int x) {
  if (!x)
    return;
  la[x] = std::max(la[l(x)], sum[l(x)] + data[x] + std::max(0, la[r(x)]));
  ra[x] = std::max(ra[r(x)], sum[r(x)] + data[x] + std::max(0, ra[l(x)]));
  ma[x] = std::max(std::max(ma[l(x)], ma[r(x)]),
                   data[x] + std::max(0, ra[l(x)]) + std::max(0, la[r(x)]));
  sum[x] = sum[l(x)] + sum[r(x)] + data[x];
  size[x] = size[l(x)] + size[r(x)] + 1;
}
void reverse(int x) {
  if (!x)
    return;
  std::swap(ch[x][0], ch[x][1]);
  std::swap(la[x], ra[x]);
  rev[x] ^= 1;
}
void recover(int x, int v) {
  if (!x)
    return;
  data[x] = cov[x] = v;
  sum[x] = size[x] * v;
  la[x] = ra[x] = ma[x] = std::max(v, sum[x]);
}
void pushdown(int x) {
  if (!x)
    return;
  if (rev[x]) {
    reverse(ch[x][0]);
    reverse(ch[x][1]);
    rev[x] = 0;
  }
  if (cov[x] != -inf) {
    recover(ch[x][0], cov[x]);
    recover(ch[x][1], cov[x]);
    cov[x] = -inf;
  }
}
void zig(int x) {
  int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
  fa[ch[y][l] = ch[x][r]] = y;
  fa[ch[x][r] = y] = x;
  fa[x] = z;
  if (z)
    ch[z][ch[z][1] == y] = x;
  update(y);
  update(x);
}
void splay(int x, int aim = 0) {
  for (int y; (y = fa[x]) != aim; zig(x))
    if (fa[y] != aim)
      zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
  if (aim == 0)
    rt = x;
  update(x);
}
int pick() {
  if (!st.empty()) {
    int x = st.top();
    st.pop();
    return x;
  } else
    return ++sz;
}
int setup(int x) {
  int t = pick();
  data[t] = a[x];
  cov[t] = -inf;
  rev[t] = false;
  sum[t] = 0;
  la[t] = ra[t] = ma[t] = -inf;
  size[t] = 1;
  return t;
}
int build(int l, int r) {
  int mid = (l + r) >> 1, left = 0, right = 0;
  if (l < mid)
    left = build(l, mid - 1);
  int t = setup(mid);
  if (r > mid)
    right = build(mid + 1, r);
  if (left) {
    ch[t][0] = left, fa[left] = t;
  } else
    size[ch[t][0]] = 0;
  if (right) {
    ch[t][1] = right, fa[right] = t;
  } else
    size[ch[t][1]] = 0;
  update(t);
  return t;
}
int find(int k) {
  int x = rt, ans;
  while (x) {
    pushdown(x);
    if (k == size[ch[x][0]] + 1)
      return ans = x;
    else if (k > size[ch[x][0]] + 1) {
      k -= size[ch[x][0]] + 1;
      x = ch[x][1];
    } else
      x = ch[x][0];
  }
  return -1;
}
void del(int &x) {
  if (!x)
    return;
  st.push(x);
  fa[x] = 0;
  del(ch[x][0]);
  del(ch[x][1]);
  la[x] = ma[x] = ra[x] = -inf;
  x = 0;
}
void print(int x) {
  if (!x)
    return;
  if (ch[x][0])
    print(ch[x][0]);
  std::cout << data[x] << ' ';
  if (ch[x][1])
    print(ch[x][1]);
}
题目

假如跳过开头打乱数组的操作,
给出六个含有 10 个元素的数组,
使得 Quick.sort() 所需的比较次数达到最坏情况。

1.5树套树

解答

每次只让枢轴变为已排序,这就是最坏情况。
这种时候枢轴是当前子数组的最大值 / 最小值。
由于在我们的实现中总是取子数组的第一个元素作为枢轴。
因此一个已排序的数组可以达到最坏情况,比较次数达到 O(n^ 2)。
如果换作取最后一个元素,最坏情况会变成逆序数组。

我们的实现中如果碰到与枢轴相等的元素也会停止循环,
因此如果数组中有重复的元素会减少比较次数。

例如:

1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15

1.5.1 线段树套splay

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

  1. 查询k在区间内的排名
  2. 查询区间内排名为k的值
  3. 修改某一位值上的数值
  4. 查询k在区间内的前驱(前驱定义为小于x,且最大的数)
  5. 查询k在区间内的后继(后继定义为大于x,且最小的数)

    #include #include #include using namespace std; const int maxn = 4e6 + 5; const int inf = 1e9; int ans, n, m, opt, l, r, k, pos, sz, Max; int a[maxn], fa[maxn], ch[maxn][2], size[maxn], cnt[maxn], data[maxn], rt[maxn]; inline int read() { int x = 0, f = 1; char ch = getchar(); while (!isdigit(ch)) {

    if (ch == '-')
      f = -1;
    ch = getchar();
    

    } while (isdigit(ch)) {

    x = x * 10 + ch - '0';
    ch = getchar();
    

    } return x * f; } struct Splay { void clear(int x) {

    fa[x] = ch[x][0] = ch[x][1] = size[x] = cnt[x] = data[x] = 0;
    

    } void update(int x) {

    if (x) {
      size[x] = cnt[x];
      if (ch[x][0])
        size[x] += size[ch[x][0]];
      if (ch[x][1])
        size[x] += size[ch[x][1]];
    }
    

    } void zig(int x) {

    int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
    fa[ch[y][l] = ch[x][r]] = y;
    fa[ch[x][r] = y] = x;
    fa[x] = z;
    if (z)
      ch[z][ch[z][1] == y] = x;
    update(y);
    update(x);
    

    } void splay(int i, int x, int aim = 0) {

    for (int y; (y = fa[x]) != aim; zig(x))
      if (fa[y] != aim)
        zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
    if (aim == 0)
      rt[i] = x;
    

    } void insert(int i, int v) {

    int x = rt[i], y = 0;
    if (x == 0) {
      rt[i] = x = ++sz;
      fa[x] = ch[x][0] = ch[x][1] = 0;
      size[x] = cnt[x] = 1;
      data[x] = v;
      return;
    }
    while (1) {
      if (data[x] == v) {
        cnt[x]++;
        update(y);
        splay(i, x);
        return;
      }
      y = x;
      x = ch[x][v > data[x]];
      if (x == 0) {
        ++sz;
        fa[sz] = y;
        ch[sz][0] = ch[sz][1] = 0;
        size[sz] = cnt[sz] = 1;
        data[sz] = v;
        ch[y][v > data[y]] = sz;
        update(y);
        splay(i, sz);
        rt[i] = sz;
        return;
      }
    }
    

    } void find(int i, int v) {

    int x = rt[i];
    while (1) {
      if (data[x] == v) {
        splay(i, x);
        return;
      } else
        x = ch[x][v > data[x]];
    }
    

    } int pre(int i) {

    int x = ch[rt[i]][0];
    while (ch[x][1])
      x = ch[x][1];
    return x;
    

    } int succ(int i) {

    int x = ch[rt[i]][1];
    while (ch[x][0])
      x = ch[x][0];
    return x;
    

    } void del(int i) {

    int x = rt[i];
    if (cnt[x] > 1) {
      cnt[x]--;
      return;
    }
    if (!ch[x][0] && !ch[x][1]) {
      clear(rt[i]);
      rt[i] = 0;
      return;
    }
    if (!ch[x][0]) {
      int oldroot = x;
      rt[i] = ch[x][1];
      fa[rt[i]] = 0;
      clear(oldroot);
      return;
    }
    if (!ch[x][1]) {
      int oldroot = x;
      rt[i] = ch[x][0];
      fa[rt[i]] = 0;
      clear(oldroot);
      return;
    }
    int y = pre(i), oldroot = x;
    splay(i, y);
    rt[i] = y;
    ch[rt[i]][1] = ch[oldroot][1];
    fa[ch[oldroot][1]] = rt[i];
    clear(oldroot);
    update(rt[i]);
    return;
    

    } int rank(int i, int v) {

    int x = rt[i], ans = 0;
    while (1) {
      if (!x)
        return ans;
      if (data[x] == v)
        return ((ch[x][0]) ? size[ch[x][0]] : 0) + ans;
      else if (data[x] < v) {
        ans += ((ch[x][0]) ? size[ch[x][0]] : 0) + cnt[x];
        x = ch[x][1];
      } else if (data[x] > v) {
        x = ch[x][0];
      }
    }
    

    } int find_pre(int i, int v) {

    int x = rt[i];
    while (x) {
      if (data[x] < v) {
        if (ans < data[x])
          ans = data[x];
        x = ch[x][1];
      } else
        x = ch[x][0];
    }
    return ans;
    

    } int find_succ(int i, int v) {

    int x = rt[i];
    while (x) {
      if (v < data[x]) {
        if (ans > data[x])
          ans = data[x];
        x = ch[x][0];
      } else
        x = ch[x][1];
    }
    return ans;
    

    } } sp; void insert(int k, int l, int r, int x, int v) { int mid = (l + r) >> 1; sp.insert(k, v); if (l == r)

    return;
    

    if (x <= mid)

    insert(k << 1, l, mid, x, v);
    

    else

    insert(k << 1 | 1, mid + 1, r, x, v);
    

    } void askrank(int k, int l, int r, int x, int y, int val) { int mid = (l + r) >> 1; if (x <= l && r <= y) {

    ans += sp.rank(k, val);
    return;
    

    } if (x <= mid)

    askrank(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    askrank(k << 1 | 1, mid + 1, r, x, y, val);
    

    } void change(int k, int l, int r, int pos, int val) { int mid = (l + r) >> 1; sp.find(k, a[pos]); sp.del(k); sp.insert(k, val); if (l == r)

    return;
    

    if (pos <= mid)

    change(k << 1, l, mid, pos, val);
    

    else

    change(k << 1 | 1, mid + 1, r, pos, val);
    

    } void askpre(int k, int l, int r, int x, int y, int val) { int mid = (l + r) >> 1; if (x <= l && r <= y) {

    ans = max(ans, sp.find_pre(k, val));
    return;
    

    } if (x <= mid)

    askpre(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    askpre(k << 1 | 1, mid + 1, r, x, y, val);
    

    } void asksucc(int k, int l, int r, int x, int y, int val) { int mid = (l + r) >> 1; if (x <= l && r <= y) {

    ans = min(ans, sp.find_succ(k, val));
    return;
    

    } if (x <= mid)

    asksucc(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    asksucc(k << 1 | 1, mid + 1, r, x, y, val);
    

    } int main() { #ifdef D freopen("input", "r", stdin); #endif n = read(), m = read(); for (int i = 1; i <= n; i++)

    a[i] = read(), Max = max(Max, a[i]), insert(1, 1, n, i, a[i]);
    

    for (int i = 1; i <= m; i++) {

    opt = read();
    if (opt == 1) {
      l = read(), r = read(), k = read();
      ans = 0;
      askrank(1, 1, n, l, r, k);
      printf("%dn", ans + 1);
    } else if (opt == 2) {
      l = read(), r = read(), k = read();
      int head = 0, tail = Max + 1;
      while (head != tail) {
        int mid = (head + tail) >> 1;
        ans = 0;
        askrank(1, 1, n, l, r, mid);
        if (ans < k)
          head = mid + 1;
        else
          tail = mid;
      }
      printf("%dn", head - 1);
    } else if (opt == 3) {
      pos = read();
      k = read();
      change(1, 1, n, pos, k);
      a[pos] = k;
      Max = std::max(Max, k);
    } else if (opt == 4) {
      l = read();
      r = read();
      k = read();
      ans = 0;
      askpre(1, 1, n, l, r, k);
      printf("%dn", ans);
    } else if (opt == 5) {
      l = read();
      r = read();
      k = read();
      ans = inf;
      asksucc(1, 1, n, l, r, k);
      printf("%dn", ans);
    }
    

    }

另请参阅

Analysis of Quicksort-khanacademy
Worst case for QuickSort - When can it occur?-Stack Overflow

1.6点分治

void getroot(int x, int fa) {
  size[x] = 1;
  f[x] = 0;
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to] && e.to != fa) {
      getroot(e.to, x);
      size[x] += size[e.to];
      f[x] = max(f[x], size[e.to]);
    }
  }
  f[x] = max(f[x], sum - size[x]);
  if (f[x] < f[rt])
    rt = x;
}
void getdeep(int x, int fa) {
  cnt[deep[x]]++;
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to] && e.to != fa) {
      deep[e.to] = (deep[x] + e.weigh) % 3;
      getdeep(e.to, x);
    }
  }
}
int cal(int x, int now) {
  cnt[0] = cnt[1] = cnt[2] = 0;
  deep[x] = now;
  getdeep(x, 0);
  return cnt[1] * cnt[2] * 2 + cnt[0] * cnt[0];
}
void work(int x) {
  ans += cal(x, 0); //统计不同子树通过重心的个数
  vis[x] = 1;
#ifndef ONLINE_JUDGE
  printf("In root %d: %dn", rt, ans);
#endif
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to]) {
      ans -= cal(e.to, e.weigh); //去除在同一个子树中被重复统计的
      rt = 0;
      sum = size[e.to];
      getroot(e.to, 0);
      work(rt); // Decrease and Conquer
    }
  }
}

2.3.5

1.7树链剖分

void dfs1(int x) {
  vis[x] = size[x] = 1;
  for (int i = 1; i <= 17; i++) {
    if (deep[x] < (1 << i))
      break;
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
  }
  for (int i = head[x]; i; i = e[i].next) {
    if (!vis[e[i].to]) {
      deep[e[i].to] = deep[x] + 1;
      fa[e[i].to][0] = x;
      dfs1(e[i].to);
      size[x] += size[e[i].to];
    }
  }
}
void dfs2(int x, int chain) {
  pl[x] = ++sz;
  que[sz] = x;
  belong[x] = chain;
  int k = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (deep[e[i].to] > deep[x] && size[k] < size[e[i].to])
      k = e[i].to;
  if (!k)
    return;
  dfs2(k, chain);
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != k && deep[e[i].to] > deep[x])
      dfs2(e[i].to, e[i].to);
}
void update(int k) {}
void build(int k, int l, int r) {
  t[k].l = l, t[k].r = r, t[k].s = 1, t[k].tag = -1;
  if (l == r) {
    t[k].lc = t[k].rc = value[que[l]];
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  update(k);
}
int lca(int x, int y) {
  if (deep[x] < deep[y])
    std::swap(x, y);
  int t = deep[x] - deep[y];
  for (int i = 0; i <= 17; i++) {
    if (t & (1 << i))
      x = fa[x][i];
  }
  for (int i = 17; i >= 0; i--) {
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  }
  if (x == y)
    return x;
  else
    return fa[x][0];
}
void pushdown(int k) {}
int query(int k, int x, int y) {}//线段树操作
int getcolor(int k, int pos) {}//线段树操作
int solvesum(int x, int f) {
  int sum = 0;
  while (belong[x] != belong[f]) {
    sum += query(1, pl[belong[x]], pl[x]);
    if (getcolor(1, pl[belong[x]]) == getcolor(1, pl[fa[belong[x]][0]]))
      sum--;
    x = fa[belong[x]][0];
  }
  sum += query(1, pl[f], pl[x]);
  return sum;
}
void change(int k, int x, int y, int c) {}//线段树操作
void solvechange(int x, int f, int c) {
  while (belong[x] != belong[f]) {
    change(1, pl[belong[x]], pl[x], c);
    x = fa[belong[x]][0];
  }
  change(1, pl[f], pl[x], c);
}
void solve() {
  dfs1(1);
  dfs2(1, 1);
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    char ch[10];
    scanf("%s", ch);
    if (ch[0] == 'Q') {
      int a, b;
      scanf("%d %d", &a, &b);
      int t = lca(a, b);
      printf("%dn", solvesum(a, t) + solvesum(b, t) - 1);
    } else {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      int t = lca(a, b);
      solvechange(a, t, c);
      solvechange(b, t, c);
    }
  }
}
题目

给出一段代码将已知只有两种主键值的数组排序。

1.8 Link-Cut Tree

对于树上的操作,我们现在已经有了树链剖分可以处理这些问题。然而树链剖分不支持动态维护树上的拓扑结构。所以我们需要Link-Cut Tree(lct)来解决这种动态树问题。顺带一提的是,动态树也是Tarjan发明的。

首先我们介绍一个概念:Preferred path(实边),其他的边都是虚边。我们使用splay来实时地维护这条路径。

lct的核心操作是access。access操作可以把虚边变为实边,通过改变splay的拓扑结构来维护实边。

有了这个数据结构,我们依次来考虑两个操作。

对于链接两个节点,我们需要首先把x节点变为他所在树的根节点,然后直接令fa[x] = y即可。

怎样换根呢?稍微思考一下可以发现,我们直接把从根到他的路径反转即可。

对于第二种操作,我们直接断开拓扑关系即可。

另外实现的时候要注意,splay的根节点的父亲是他的上一个节点。所以zig和splay的写法应该格外注意。

inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
void pushdown(int k) {
  if (rev[k]) {
    rev[k] = 0;
    rev[ch[k][0]] ^= 1;
    rev[ch[k][1]] ^= 1;
    std::swap(ch[k][0], ch[k][1]);
  }
}
void zig(int x) {
  int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
  if (!isroot(y))
    ch[z][ch[z][1] == y] = x;
  fa[ch[y][l] = ch[x][r]] = y;
  fa[ch[x][r] = y] = x;
  fa[x] = z;
}
void splay(int x) {
  stack<int> st;
  st.push(x);
  for (int i = x; !isroot(i); i = fa[i])
    st.push(fa[i]);
  while (!st.empty()) {
    pushdown(st.top());
    st.pop();
  }
  for (int y = fa[x]; !isroot(x); zig(x), y = fa[x])
    if (!isroot(y))
      zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
}
void access(int x) {
  int t = 0;
  while (x) {
    splay(x);
    ch[x][1] = t;
    t = x;
    x = fa[x];
  }
}
void rever(int x) {
  access(x);
  splay(x);
  rev[x] ^= 1;
}
void link(int x, int y) {
  rever(x);
  fa[x] = y;
  splay(x);
}
void cut(int x, int y) {
  rever(x);
  access(y);
  splay(y);
  ch[y][0] = fa[x] = 0;
}
int find(int x) {
  access(x);
  splay(x);
  int y = x;
  while (ch[y][0])
    y = ch[y][0];
  return y;
}
解答

官方实现:

算法 gif 动图
mg娱乐电子4355 5

1.9 KMP

对于字符串S的前i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作next[i]

多用于DP

for (int i = 2; i <= m; i++) {
    while (j > 0 && ch[j + 1] != ch[i])
      j = p[j];
    if (ch[j + 1] == ch[i])
      j++;
    p[i] = j;
  }
代码
namespace Quick
{
    /// <summary>
    /// 用于将只有两种元素的数组排序。
    /// </summary>
    public class Sort2Distinct : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Sort2Distinct() { }

        /// <summary>
        /// 对数组 a 进行排序。
        /// </summary>
        /// <typeparam name="T">数组 a 的元素类型。</typeparam>
        /// <param name="a"></param>
        public override void Sort<T>(T[] a)
        {
            int lt = 0, gt = a.Length - 1;
            int i = 0;
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(a[lt]);
                if (cmp < 0)
                    Exch(a, lt++, i++);
                else if (cmp > 0)
                    Exch(a, i, gt--);
                else
                    i++;
            }
        }
    }
}

1.10 AC自动机

KMP在Trie上的扩展.

void insert(char s[101]) {
  int now = 1, c;
  for (int i = 0; i < strlen(s); i++) {
    c = s[i] - 'A' + 1;
    if (a[now][c])
      now = a[now][c];
    else
      now = a[now][c] = ++sz;
  }
  leaf[now] = 1;
}
void ac() {
  std::queue<int> q;
  q.push(1);
  point[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 1; i <= 26; i++) {
      if (!a[u][i])
        continue;
      int k = point[u];
      while (!a[k][i])
        k = point[k];
      point[a[u][i]] = a[k][i];
      if (leaf[a[k][i]])
        leaf[a[u][i]] = 1;
      q.push(a[u][i]);
    }
  }
}
另请参阅

Quick 库

1.11 后缀数组

void getsa(int sa[maxn], int rank[maxn], int Sa[maxn], int Rank[maxn]) {
  for (int i = 1; i <= n; i++)
    v[rank[sa[i]]] = i;
  for (int i = n; i >= 1; i--)
    if (sa[i] > k)
      Sa[v[rank[sa[i] - k]]--] = sa[i] - k;
  for (int i = n - k + 1; i <= n; i++)
    Sa[v[rank[i]]--] = i;
  for (int i = 1; i <= n; i++)
    Rank[Sa[i]] = Rank[Sa[i - 1]] + (rank[Sa[i - 1]] != rank[Sa[i]] ||
                                     rank[Sa[i - 1] + k] != rank[Sa[i] + k]);
}
void getheight(int sa[maxn], int rank[maxn]) {
  int i, k = 0;
  for (i = 1; i <= n; height[rank[i++]] = k) {
    if (k)
      k--;
    int j = sa[rank[i] - 1];
    while (a[i + k] == a[j + k])
      k++;
  }
}
void da() {
  p = 0, q = 1, k = 1;
  for (int i = 1; i <= n; i++)
    v[a[i]]++;
  for (int i = 1; i <= 2; i++)
    v[i] += v[i - 1];
  for (int i = 1; i <= n; i++)
    sa[p][v[a[i]]--] = i;
  for (int i = 1; i <= n; i++)
    rank[p][sa[p][i]] =
        rank[p][sa[p][i - 1]] + (a[sa[p][i - 1]] != a[sa[p][i]]);
  while (k < n) {
    getsa(sa[p], rank[p], sa[q], rank[q]);
    p ^= 1;
    q ^= 1;
    k <<= 1;
  }
  getheight(sa[p], rank[p]);
}

2.3.6

1.12 后缀自动机

mg娱乐电子4355 6

struct Suffix_Automaton {
  ll fa[maxn], trans[maxn][26], len[maxn], right[maxn];
  ll last, root, sz;
  bool flag[maxn];
  void init() {
    memset(flag, 0, sizeof(flag));
    sz = 0;
    last = root = ++sz;
  }
  void insert(ll x) {
    ll p = last, np = last = ++sz;
    len[np] = len[p] + 1;
    flag[np] = 1;
    right[np] = right[p] + 1;
    for (; !trans[p][x]; p = fa[p])
      trans[p][x] = np;
    if (p == 0)
      fa[np] = root;
    else {
      ll q = trans[p][x];
      if (len[q] == len[p] + 1) {
        fa[np] = q;
      } else {
        ll nq = ++sz;
        fa[nq] = fa[q];
        memcpy(trans[nq], trans[q], sizeof(trans[q]));
        len[nq] = len[p] + 1;
        fa[q] = fa[np] = nq;
        for (; trans[p][x] == q; p = fa[p])
          trans[p][x] = nq;
      }
    }
  }
} sam;
题目

编写一段代码来计算 $ C_N $ 的准确值,
在 $ N=100、1000 $ 和 $10 000 $ 的情况下比较准确值和估计值 $ 2NlnN $ 的差距。

1.13 Manacher

void manacher() {
  int mx = 1, id = 1;
  for (int i = n; i; i--)
    str[i * 2] = '#', str[i * 2 - 1] = str[i];
  n <<= 1;
  for (int i = 1; i <= n; i++) {
    p[i] = std::min(p[id * 2 - i], mx - i);
    while (i - p[i] > 0 && str[i - p[i]] == str[i + p[i]]) {
      int al = (i - p[i]) / 2 + 1;
      int ar = (i + p[i] + 1) / 2;
      // printf("%d %dn", al, ar);
      sam.query(al, ar);
      p[i]++;
    }
    if (i + p[i] > mx)
      mx = i + p[i], id = i;
  }
}
解答

运行结果如下:
mg娱乐电子4355 7

1.14 分块

随便给一个例题吧.

给定一个数列,您需要支持一下两种操作:1.给[l,r]同加一个数. 2.询问[l,r]中有多少数字大于或等于v.

把数据分为(sqrt n)一份,那么对于每一个查询,我们都可以把这个查询分为(sqrt n)个区间,修改的时候也是(O(sqrt n))的级别,所以总的复杂度就是(O(sqrt n log sqrt n))

具体地,对于每一块,我们都存储排序前和排序后的序列,这样我们就解决了这个题。

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
int n, q, m, block;
const int maxn = 1000001;
int a[maxn], b[maxn], pos[maxn], add[maxn];
using std::sort;
using std::min;
inline int read() {}
inline void reset(int x) {
  int l = (x - 1) * block + 1, r = min(x * block, n);
  for (int i = l; i <= r; i++)
    b[i] = a[i];
  sort(b + l, b + r + 1);
}
inline int find(int x, int v) {
  int l = (x - 1) * block + 1, r = min(x * block, n);
  int last = r;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (b[mid] < v)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return last - l + 1;
}
inline void update(int x, int y, int v) {
  if (pos[x] == pos[y]) {
    for (int i = x; i <= y; i++)
      a[i] = a[i] + v;
  } else {
    for (int i = x; i <= pos[x] * block; i++)
      a[i] = a[i] + v;
    for (int i = (pos[y] - 1) * block + 1; i <= y; i++)
      a[i] = a[i] + v;
  }
  reset(pos[x]);
  reset(pos[y]);
  for (int i = pos[x] + 1; i < pos[y]; i++)
    add[i] += v;
}
inline int query(int x, int y, int v) {
  int sum = 0;
  if (pos[x] == pos[y]) {
    for (int i = x; i <= y; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
  } else {
    for (int i = x; i <= pos[x] * block; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
    for (int i = (pos[y] - 1) * block + 1; i <= y; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
    for (int i = pos[x] + 1; i < pos[y]; i++)
      sum += find(i, v - add[i]);
  }
  return sum;
}
int main() {
#ifndef ONLINE_JUDGE
  freopen("input", "r", stdin);
#endif
  n = read(), q = read();
  if (n >= 500000)
    block = 3676;
  else if (n >= 5000) {
    block = 209;
  } else
    block = int(sqrt(n));
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    pos[i] = (i - 1) / block + 1;
    b[i] = a[i];
  }
  if (n % block)
    m = n / block + 1;
  else
    m = n / block;
  for (int i = 1; i <= m; i++)
    reset(i);
  for (int i = 1; i <= q; i++) {
    char ch[5];
    int x, y, v;
    scanf("%s", ch);
    x = read(), y = read(), v = read();
    if (ch[0] == 'M')
      update(x, y, v);
    else
      printf("%dn", query(x, y, v));
  }
}
代码

新建一个 QuickSortAnalyze 类,在 QuickSort 的基础上添加一个 CompareCount 属性,用于记录比较次数。重写 Less 方法,每调用一次就让 CompareCount 增加 1 。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            if (hi - lo == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + hi);
            }
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._6
{
    /*
     * 2.3.6
     * 
     * 编写一段代码来计算 C_N 的准确值,
     * 在 N=100、1000 和 10 000 的情况下比较准确值和估计值 2NlnN 的差距。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Nt准确值t估计值t比值");
            QuickSortAnalyze sort = new QuickSortAnalyze();
            int N = 100;
            int trialTime = 500;
            for (int i = 0; i < 3; i++)
            {
                int sumOfCompare = 0;
                int[] a = new int[N];
                for (int j = 0; j < trialTime; j++)
                {
                    for (int k = 0; k < N; k++)
                    {
                        a[k] = k;
                    }
                    SortCompare.Shuffle(a);
                    sort.Sort(a);
                    sumOfCompare += sort.CompareCount;
                }
                int averageCompare = sumOfCompare / trialTime;
                double estimatedCompare = 2 * N * Math.Log(N);
                Console.WriteLine(N + "t" + averageCompare + "t" + (int)estimatedCompare + "t" + averageCompare / estimatedCompare);
                N *= 10;
            }
        }
    }
}

1.15 莫队算法

如果你知道了[L,R]的答案。你可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的话。就可以使用莫队算法。
对于莫队算法我感觉就是暴力。只是预先知道了所有的询问。可以合理的组织计算每个询问的顺序以此来降低复杂度。要知道我们算完[L,R]的答案后现在要算[L',R']的答案。由于可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案.所以计算[L',R']的答案花的时间为|L-L'|+|R-R'|。如果把询问[L,R]看做平面上的点a(L,R).询问[L',R']看做点b(L',R')的话。那么时间开销就为两点的曼哈顿距离。所以对于每个询问看做一个点。我们要按一定顺序计算每个值。那开销就为曼哈顿距离的和。要计算到每个点。那么路径至少是一棵树。所以问题就变成了求二维平面的最小曼哈顿距离生成树。
关于二维平面最小曼哈顿距离生成树。感兴趣的可以参考胡泽聪大佬的这篇文章

这样只要顺着树边计算一次就ok了。可以证明时间复杂度为(O(n∗sqrt n)).

但是这种方法编程复杂度稍微高了一点。所以有一个比较优雅的替代品。那就是先对序列分块。然后对于所有询问按照L所在块的大小排序。如果一样再按照R排序。然后按照排序后的顺序计算。为什么这样计算就可以降低复杂度呢。

一、i与i+1在同一块内,r单调递增,所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块,r最多变化n,由于有n^0.5块,所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5,跨越一块也不会超过2*n^0.5,不妨看作是n^0.5。由于有n个数,所以时间复杂度是n^1.5
于是就变成了Θ(n1.5)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
const int maxn = 50010;
#define ll long long
ll num[maxn], up[maxn], dw[maxn], ans, aa, bb, cc;
int col[maxn], pos[maxn];
struct qnode {
  int l, r, id;
} qu[maxn];
bool cmp(qnode a, qnode b) {
  if (pos[a.l] == pos[b.l])
    return a.r < b.r;
  else
    return pos[a.l] < pos[b.l];
}
ll gcd(ll x, ll y) {
  ll tp;
  while ((tp = x % y)) {
    x = y;
    y = tp;
  }
  return y;
}
void update(int x, int d) {
  ans -= num[col[x]] * num[col[x]];
  num[col[x]] += d;
  ans += num[col[x]] * num[col[x]];
}
int main() {
  int n, m, bk, pl, pr, id;
#ifndef ONLINE_JUDGE
  freopen("input", "r", stdin);
#endif
  scanf("%d %d", &n, &m);
  memset(num, 0, sizeof(num));
  bk = ceil(sqrt(1.0 * n));
  for (int i = 1; i <= n; i++) {
    scanf("%d", &col[i]);
    pos[i] = (i - 1) / bk;
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &qu[i].l, &qu[i].r);
    qu[i].id = i;
  }
  std::sort(qu, qu + m, cmp);
  pl = 1, pr = 0;
  ans = 0;
  for (int i = 0; i < m; i++) {
    id = qu[i].id;
    if (qu[i].l == qu[i].r) {
      up[id] = 0, dw[id] = 1;
      continue;
    }
    if (pr < qu[i].r) {
      for (int j = pr + 1; j <= qu[i].r; j++)
        update(j, 1);
    } else {
      for (int j = pr; j > qu[i].r; j--)
        update(j, -1);
    }
    pr = qu[i].r;
    if (pl < qu[i].l) {
      for (int j = pl; j < qu[i].l; j++)
        update(j, -1);
    } else {
      for (int j = pl - 1; j >= qu[i].l; j--)
        update(j, 1);
    }
    pl = qu[i].l;
    aa = ans - qu[i].r + qu[i].l - 1;
    bb = (ll)(qu[i].r - qu[i].l + 1) * (qu[i].r - qu[i].l);
    cc = gcd(aa, bb);
    aa /= cc, bb /= cc;
    up[id] = aa, dw[id] = bb;
  }
  for (int i = 0; i < m; i++)
    printf("%lld/%lldn", up[i], dw[i]);
}

### 1.16 整体二分&CDQ分治

另请参阅

Quick 库

GRAPHIC

2.3.7

2.图论

题目

在使用快速排序将 N 个不重复的元素排序时,
计算大小为 0、1 和 2 的子数组的数量。如果你喜欢数学,请推导;
如果你不喜欢,请做一些实验并提出猜想。

2.1图的连通性

解答

我讨厌数学= =

证明:
我们设 $ C_0(n) $ 代表将 $ n $ 个不重复元素排序时大小为 0 的数组的数量。
同理有 $ C_1(n) $ 和 $ C_2(n) $ 代表大小为 1 的数组的数量以及大小为 2 的数组的数量。
设 k 代表切分位置,显然切分位置随机且概率相等,在 1~n 之间均匀分布。
根据条件,$ C_0(n), C_1(n),C_2(n) $ 都满足下式:
[ C(n)= frac{sum_{k=1}^{n}(C(k-1)+C(n-k))}{n} ]
根据快速排序算法, $ sum_{k=1}^{n}C(k-1)=sum_{k=1}^{n}C(n-k) $ ,因此
[ C(n)=frac{2sum_{k=1}^{n}C(k-1)}{n}\ nC(n)=2sum_{k-1}^{n}C(k-1) ]
同理代入 $ n-1 $ 有
[ (n-1)C(n-1)=2sum_{k-1}^{n-1}C(k-1) ]
相减
[ nC(n)-(n-1)C(n-1)=2C(n-1)\ C(n)=frac{n+1}{n}C(n-1) ]
利用累乘法求到通项公式
[ frac{C(n)}{C(n-1)}=frac{n+1}{n} \ frac{C(n)}{C(n-1)}timesfrac{C(n-1)}{C(n-2)}timesdotstimesfrac{C(m+1)}{C(m)}= frac{n+1}{n}timesfrac{n}{n-1}timesdotstimesfrac{m+2}{m+1}\ frac{C(n)}{C(m)}=frac{n+1}{m+1}\ C(n)=C(m)frac{n+1}{m+1},n>m ]
对于 $ C_0(n) $ ,我们有初始条件 $ C_0(0)=1, C_0(1)=0,C_0(2)=C_0(0)+C_0(1)=1 $
[ C_mg娱乐电子4355,0(n)=frac{n+1}{3}, n>2 ]
对于 $ C_1(n) $ ,我们有初始条件 $ C_1(0)=0,C_1(1)=1,C_1(2)=C_1(0)+C_1(1)=1 $
[ C_1(n)=frac{n+1}{3},n>2 ]
对于 $ C_2(n) $ ,我们有初始条件 $ C_2(0)=C_2(1)=0,C_2(2)=1,C_2(3)=frac{2times(C_2(0)+C_2(1)+C_2(2))}{3}=frac{2}{3} $
[ C_2(n)=frac{n+1}{6},n>3 ]
结论
[ C_0(n)=C_1(n)=frac{n+1}{3},n>2 \ C_2(n)=frac{n+1}{6},n>3 ]
实验结果:
mg娱乐电子4355 8

2.1.1 双连通分量

  • 定理: 在无向连通图G的DFS树中, 非根节点u是G的割顶当且仅当u存在一個子节点v, 使得v及其后代都没有反向边连回u的祖先.
  • 设low(u)为u及其后代所能连回的最早的祖先的pre值, 则定理中的条件就是:
  • 节点u存在一个子节点v, 使得low(v) >= pre(u).
  • 对于一个连通图, 如果任意两点存在至少两条"点不重复"的路径, 就说这个图是点-双连通的, 这个要求等价于任意两条边都在同一个简单环中, 即内部无割顶. 类似的定义边-双连通. 对于一张无向图, 点-双连通的极大子图称为双连通分量.
  • 不同双连通分量最多只有一个公共点, 且它一定是割顶. 任意割顶都是两个不同双连通分量的公共点.

    stack S; int dfs(int u, int fa) { int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = 0; i < G[u].size(); i++) {

    int v = G[u][i];
    Edge e = (Edge){u, v};
    if(!pre[v]) {
      S.push(e);
      child++;
      int lowv = dfs(v, u);
      lowu = min(lowu, lowv);
      if(lowv >= pre[u]) {
        iscut[u] = true;
        bcc_cnt++;
        bcc[bcc_cnt].clear();
        for(;;) {
          Edge x = S.top(); S.pop();
          if(bccno[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt;}
          if(bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt;}
          if(x.u == u && x.v == v) break;
        }
      }
    }
    else if(pre[v] < pre[u] && v != fa) {
      S.push(e);
      lowu = min(lowu, pre[v]);
    }
    

    } if(fa < 0 && child == 1) iscut[u] = 0; return lowu; }

  • 边-双连通分量可以使用更简单的方法求出, 分两个步骤, 先做一次dfs标记出所有的桥, 然后再做一次dfs找出边-双连通分量. 因为边-双连通分量是没有公共节点的, 所以只要在第二次dfs的时候保证不经过桥即可.

代码

QuickSortAnalyze 类,添加了三个属性用于计算数组数量。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            if (hi - lo == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + hi);
            }
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._7
{
    /*
     * 2.3.7
     * 
     * 在使用快速排序将 N 个不重复的元素排序时,
     * 计算大小为 0、1 和 2 的子数组的数量。
     * 如果你喜欢数学,请推导;
     * 如果你不喜欢,请做一些实验并提出猜想。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            // 证明
            // 我们设 C0(n) 代表将 n 个不重复元素排序时大小为 0 的数组的数量。
            // 同理有 C1(n) 和 C2(n) 代表大小为 1 的数组的数量和大小为 2 的数组的数量。
            // 设 k 代表切分位置,显然切分位置随机且概率相等,在 1~n 之间均匀分布。
            // 根据条件,三者都满足下式。
            // C(n) = 1/n sum(C(k - 1) + C(n - k)), k=1,2,...,n
            // 显然 sum(C(k - 1)) = sum(C(n - k)), k=1,2,...,n
            // 于是可以化简为
            // C(n) = 2/n sum(C(k - 1)), k=1,2,...,n
            // nC(n) = 2 * sum(C(k-1)), k=1,2,...,n
            // 同理有
            // (n-1)C(n-1) = 2 * sum(C(k-1)), k = 1,2,...,n-1
            // 相减得到递推式
            // nC(n) - (n-1)C(n-1) = 2*C(n-1)
            // C(n) = (n+1)/n * C(n-1)
            // 利用累乘法可以求得通项公式
            // C(n)=C(k)*(n+1)/(k+1), n>k
            // 对于 C0 有 C0(0)=1, C0(1)=0
            // C0(2)=C(0)+C(1)=1
            // C0(n)=(n+1)/3, n>2
            // 对于 C1 有 C1(0)=0, C1(1)=1
            // C1(2)=C1(0)+C1(1)=1
            // C1(n)=(n+1)/3, n>2
            // 对于 C2 有 C2(0)=C2(1)=0, C2(2)=1
            // C2(3)=1/3*2*(C2(0)+C2(1)+C2(2))=2/3
            // C2(n)=C2(3)*(n+1)/4=(n+1)/6, n>3
            // 结论
            // C0(n)=C1(n)=(n+1)/3, C2(n)=(n+1)/6
            int n = 1000;
            QuickSortAnalyze sort = new QuickSortAnalyze();
            Console.WriteLine("nt0t1t2");
            for (int i = 0; i < 5; i++)
            {
                int[] a = new int[n];
                for (int j = 0; j < n; j++)
                {
                    a[j] = j;
                }
                SortCompare.Shuffle(a);
                sort.Sort(a);
                Console.WriteLine(n + "t" + sort.Array0Num + "t" + sort.Array1Num + "t" + sort.Array2Num);
                n *= 2;
            }
        }
    }
}

2.1.2 强连通分量

kosaraju算法.

void dfs(int v) {
  vis[v] = true;
  for (int i = 0; i < G[v].size(); i++) {
    if (!vis[G[v][i]])
      dfs(G[v][i]);
  }
  vs.push_back(v);
}
void rdfs(int v, int k) {
  vis[v] = true;
  cnt[v] = k;
  for (int i = 0; i < rG[v].size(); i++) {
    if (!vis[rG[v][i]])
      rdfs(rG[v][i], k);
  }
  vs.push_back(v);
  sc[k].push_back(v);
}
int scc() {
  memset(vis, 0, sizeof(vis));
  vs.clear();
  for (int v = 1; v <= n; v++) {
    if (!vis[v])
      dfs(v);
  }
  memset(vis, 0, sizeof(vis));
  int k = 0;
  for (int i = vs.size() - 1; i >= 0; i--) {
    if (!vis[vs[i]]) {
      rdfs(vs[i], k++);
    }
  }
  return k;
}
另请参阅

Quick 库
What is the expected number of subarrays of size 0, 1 and 2 when quicksort is used to sort an array of N items with distinct keys?-Stack Overflow

2.2 最短路与最小生成树

2.3.8

2.2.1 SPFA

虽然是NOIp(professional)知识, 但是由于在省选中非常常用, 还是写一下.

最短路算法也会在分层图中考察.

spfa也可以运用在DP中的转移.

void spfa() {
  memset(dist, 0x3f, sizeof(dist));
  dist[s][0] = 0;
  queue<state> q;
  q.push((state){s, 0});
  memset(inq, 0, sizeof(inq));
  inq[s][0] = 1;
  while (!q.empty()) {
    state u = q.front();
    q.pop();
    inq[u.pos][u.k] = 0;
    for (int i = 0; i < G[u.pos].size(); i++) {
      edge &e = G[u.pos][i];
      if (dist[e.to][u.k] > dist[u.pos][u.k] + e.value) {
        dist[e.to][u.k] = dist[u.pos][u.k] + e.value;
        if (!inq[e.to][u.k]) {
          q.push((state){e.to, u.k});
          inq[e.to][u.k] = 1;
        }
      }
      if (u.k < k && dist[e.to][u.k + 1] > dist[u.pos][u.k]) {
        dist[e.to][u.k + 1] = dist[u.pos][u.k];
        if (!inq[e.to][u.k + 1]) {
          q.push((state){e.to, u.k + 1});
          inq[e.to][u.k + 1] = 1;
        }
      }
    }
  }
}

spfa可以用来判负环. 所谓负环就是环上边权和为负的环. 一般使用dfs版本spfa判负环.

double dist[maxn];
inline void spfa(int x) {
  int i;
  vis[x] = false;
  for (i = 0; i < rg[x].size(); i++) {
    edge &e = rg[x][i];
    if (dist[e.to] > dist[x] + e.value)
      if (!vis[e.to]) {
        flag = true;
        break;
      } else {
        dist[e.to] = dist[x] + e.value;
        spfa(e.to);
      }
  }
  vis[x] = true;
}
bool check(double lambda) {
  for (int i = 1; i <= n; i++) {
    rg[i].clear();
    for (int j = 0; j < G[i].size(); j++) {
      rg[i].push_back((edge){G[i][j].to, (double)G[i][j].value - lambda});
    }
  }
  memset(vis, 1, sizeof(vis));
  memset(dist, 0, sizeof(dist));
  flag = false;
  for (int i = 1; i <= n; i++) {
    spfa(i);
    if (flag)
      return true;
  }
  return false;
}
题目

Quick.sort() 在处理 N 个全部重复的元素时大约需要多少次比较?

2.2.2 动态最小生成树

最小生成树算是很常见的考点.

关于最小生成树, 我们有以下结论:

  • 对于连通图中的任意一个环 C :如果C中有边e的权值大于该环中任意一个其它的边的权值,那么这个边不会是最小生成树中的边.
  • 在一幅连通加权无向图中,给定任意的切分,它的横切边中权值最小的边必然属于图的最小生成树。
  • 如果图的具有最小权值的边只有一条,那么这条边包含在任意一个最小生成树中。
  • 次小生成树: 树上倍增+lca
  • 两个点之间的最大权最小路径一定在最小生成森林上(水管局长)
  • 欧几里德最小生成树
    动态最小生成树: 使用Link-Cut Tree维护.

  • 矩阵树定理(Matrix-Tree)

    下面我们介绍一种新的方法——Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前,我们首先明确几个概念:
    1、G的度数矩阵 class="math inline">(D[G])是一个 class="math inline">(n times n)的矩阵,并且满足:当(inot = j)时, class="math inline">(d_{ij}=0);当 class="math inline">(i=j)时, class="math inline">(d_{ij})等于 class="math inline">(v_i)的度数。
    2、G的邻接矩阵 class="math inline">(A[G])也是一个 class="math inline">(n times n)的矩阵, 并且满足:如果(v_i)、 class="math inline">(v_j)之间有边直接相连,则 class="math inline">(a_{ij})=1,否则为0。
    我们定义 class="math inline">(G)的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行、第r列同时去掉后得到的新矩阵,用Cr[G]表示。

  • kruskal 算法: 贪心地选取每一条边

解答

每次切分都会把数组平分,共切分 logN 次(二分法),每次切分比较 N 次(i 和 j 会一位一位地从两边向中间靠拢)。
共比较 NlogN 次。

2.3网络流

2.3.9

2.3.1 预备知识

  • 流网络(G=(V,E))是一个有向图, 其中每条边(<u, v> in E)均为有一非负容量(c(u, v) geqslant 0), 规定: 若(<u,v> not in E), 则(c(u,v)=0). 网络中有两个特殊点(s)和(t).
  • 网络的流是一个实值函数(f):(V times V rightarrow R), 且满足三个性质: 容量限制, 反对称性, 流守恒性.
  • 最大的流是指该网络中流值最大的流.
  • 残留网络由可以容纳更多流的边构成.
  • 增广路径(p)为残留网络上(s)到(t)的一条简单路径.
  • 流网络(G=(V, E))的割([S, T])将点集划分为(S)和(T)两部分, 使得(s in S and t in T). 符号([S, T]={<u,v>|<u,v> in E, u in S, v in T}), 通过割的净流为(f(S,T)), 容量定义为(c(S,T)).
  • 一个网络的最小割就是网络中容量最小的割.
题目

请说明 Quick.sort() 在处理只有两种主键值时的行为,以及在处理只有三种主键值的数组时的行为。

2.3.2 最大流最小割定理与线性规划

首先我们假设读者已经有了线性规划的基本知识.

最大流问题的线性规划描述:
$$
begin{alignat}{2}

maxquad &f_{ts} &{}& tag{LP1} label{eqn - lp}

mbox{s.t.}quad

&f_{u,v}leqslant c_{u,v}, &quad& (u,v)in E

&sum_{v} f_{uv} = sum_v f_{vu}, &{}& u in V
& f_{uv} geqslant 0, &{}& (u,v) in E cup{(t,s)}

end{alignat}
[ 最小割问题的线性规划描述: ]
begin{alignat}{2}

minquad &sum_{(u,v) in E}c_{uv}d_{uv} &{}& tag{LP2}

mbox{s.t.}quad

&d_{u,v}-p_u+p_v &geqslant 0, &quad& (u,v)in E
&p_s-p_t &geqslant 1
&p_u, d_{uv} in {0, 1}

end{alignat}
($ 令)p_u=[u in S]$, (d_{uv}=max{p_u-p_v, 0}).

考虑最大流的对偶: 记由容量限制产生的变量为(d_{uv}), 由点(u)的流量守恒产生的变量为(p_u), 那么对偶问题就是:
$$
begin{alignat}{2}

minquad &sum_{(u,v) in E}c_{uv}d_{uv} &{}& tag{LP3}

mbox{s.t.}quad

&d_{u,v}-p_u+p_v &geqslant 0, &quad& (u,v)in E
&p_s-p_t &geqslant 1
&d_{uv} &geqslant 0, &{}&(u,v)in E

end{alignat}
($ 我们得出结论: (最大流最小割定理)给定一个源为)s(, 汇为)t(的网络, 则)s,t(的最大流等于)s,t$的最小割.

解答

切分时,枢轴左侧都是小于(或等于)枢轴的,
右侧都是大于(或等于)枢轴的
只有两种主键值时,
第一次切分之后,某一侧的元素将全部相同
(如果枢轴选了较大的,那么右侧将全部相同,反之则左侧全部相同)

只有三种主键值时,和一般快速排序并无不同。
但如果第一次切分时选择了中间值作为枢轴,且中间值只有一个
那么只需要一次切分数组便会有序。

2.3.3 最大流算法

2.3.10

2.3.3.1 Dinic算法
int dist[maxn], iter[maxn];
inline void bfs(int s) {
  memset(dist, -1, sizeof(dist));
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < G[u].size(); i++) {
      edge &e = edges[G[u][i]];
      if (e.cap > 0 && dist[e.to] == -1) {
        dist[e.to] = dist[u] + 1;
        q.push(e.to);
      }
    }
  }
}
inline int dfs(int s, int t, int flow) {
  if (s == t)
    return flow;
  for (int &i = iter[s]; i < G[s].size(); i++) {
    edge &e = edges[G[s][i]];
    if (e.cap > 0 && dist[e.to] > dist[s]) {
      int d = dfs(e.to, t, min(e.cap, flow));
      if (d > 0) {
        e.cap -= d;
        edges[G[s][i] ^ 1].cap += d;
        return d;
      }
    }
  }
  return 0;
}
inline int dinic(int s, int t) {
  int flow = 0;
  while (1) {
    bfs(s);
    if (dist[t] == -1)
      return flow;
    memset(iter, 0, sizeof(iter));
    int d;
    while (d = dfs(s, t, inf))
      flow += d;
  }
  return flow;
}
题目

Chebyshev 不等式表明,一个随机变量的标准差距离均值大于 k 的概率小于 1/k^2 。
对于 N=100 万,用 Chebyshev 不等式计算快速排序所使用的比较次数大于 1000 亿次的概率(0.1N^2)。

2.3.3.2 费用流

泛指一种与费用相关的流算法.EK算法比较常用

bool spfa(ll &flow, ll &cost) {
  for (int i = 0; i <= n + 1; i++) {
    dist[i] = -inf;
  }
  memset(inq, 0, sizeof(inq));
  dist[s] = 0, inq[s] = 1, pre[s] = 0, fi[s] = inf;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = 0;
    for (int i = 0; i < G[u].size(); i++) {
      edge &e = E[G[u][i]];
      if (e.cap > e.flow && dist[e.to] < dist[u] + e.cost) {
        dist[e.to] = dist[u] + e.cost;
        pre[e.to] = G[u][i];
        fi[e.to] = min(fi[u], e.cap - e.flow);
        if (!inq[e.to]) {
          q.push(e.to);
          inq[e.to] = 1;
        }
      }
    }
  }
  if (dist[t] <= -inf)
    return false;
  if (cost + dist[t] * fi[t] < 0) { 
    ll temp = cost / (-dist[t]); //temp:还能够增加的流
    flow += temp;
    return false;
  }
  flow += fi[t];
  cost += dist[t] * fi[t];
  int u = t;
  while (u != s) {
    E[pre[u]].flow += fi[t];
    E[pre[u] ^ 1].flow -= fi[t];
    u = E[pre[u]].from;
  }
  return true;
}
ll mcmf(int s, int t) {
  ll flow = 0;
  ll cost = 0;
  while (spfa(flow, cost))
    ;
  return flow;
}
解答

切比雪夫不等式(Chebyshev’s inequality)
[ P(|X-mu|geq ksigma)leq frac{1}{k^2} ]
其中,$ mu $ 代表期望,$ sigma $ 代表标准差。
对于快速排序的比较次数来说,$ mu = 2Nln N $ ,$ sigma=0.65N $。
(这两个结论见 2.3 节的命题 K 和命题 L)
题目中要求比较次数大于 $ 0.1N^2 $ ,可以求得 $ k $ 的值。
[ 0.65kN=0.1N^2 \ k=frac{2N}{13} ]
将 $ N=1,000,000 $ 代入
[ P(|X-27,631,021|geq 100,000,000,000)leq 0.00000000004225 ]

2.3.4 建模方法

另请参阅

切比雪夫不等式到底是个什么概念? - 马同学的回答 - 知乎

2.3.4.1 基本建模
  • 多个源点和汇点(超级源点, 超级汇点)
  • 无向图: 拆成两条边
  • 顶点容量限制: 拆点
  • 不相交的两条路径: 拆点
  • 上下界网络流:mg娱乐电子4355 9
  • 上下界费用流:mg娱乐电子4355 10
  • 图部分发生变化: 重复利用之前的结果
  1. 容量增加, 直接跑最大流
  2. 容量减少, 如果(f(e) leq c(e)-1), 那么不用动, 否则退流

    for (int i = 1; i <= n; i++) {
      int now = cc[i].id;
      int u = now, v = now + n;
      bfs(u);
      if (dist[v] != -1)
        continue;
      rec[tot++] = now;
      dinic(t, v);
      dinic(u, s);
      edges[(now - 1) * 2].cap = edges[(now - 1) * 2 + 1].cap = 0;
    }
    
  • 容量为负数: 适当变形
  • 费用为负数的情况:
  1. 消负圈
  2. 通过适当的变形. 比如说, 如果每次增广所用的边数都是相同的(记做m), 那么把所有边的费用都加上常数(k), 然后从最短路减去(mk)就得到了原图最短路的长度
  3. mg娱乐电子4355 11

2.3.11

2.3.4.2 最大流建模
  • 与棋盘有关的题目可以考虑最大流
题目

假如在遇到和切分元素重复的元素时我们继续扫描数组而不是停下来,
证明使用这种方法的快速排序在处理只有若干种元素值的数组时运行时间是平方级别的。

2.3.4.3 最小割建模
  • 用容量为(infty)的边表示冲突
  • 从两点关系的角度进行最小割建模
解答

只有若干种元素值意味着大量的连续重复。
(由于存在打乱这一步骤,不存在连续重复的可能性是很低的)
接下来我们考虑这样的连续重复在修改后的快排下的性能。
1 1 1 1 1 1 1
对于这样的数组,枢轴选为 1,j 将会在 j = lo 处终止。
因此最后的结果将是每次只有数组的第一个元素被排序
已知每次切分都是 O(k - 1) 的(i 和 j 都将走完整个子数组)
因此这样的快速排序所需时间 = $ 2 (N - 1 + N - 2 + cdots + 1) = (N - 1)N $
因此对于值相同的子数组,这样的快排运行时间是平方级别的
那么当数组中这样的连续重复内容越多,运行时间就越接近平方级别。

2.3.4.4 费用流建模

2.3.12

2.3.4.5 流量平衡思想
题目

按照代码所示轨迹的格式给出信息量最佳的快速排序第一次是如何切分
数组 B A B A B A B A C A D A B R A 的。

2.4二分图

  • 二分图, 指顶点可以分为两个不相交的几个(U)和(V)((U and V)皆为独立集), 使得在同一个集内的顶点不相邻的图.
  • 无向图G为二分图(Leftrightarrow)G至少有两个顶点, 且所有回路的长度均为偶数(Leftrightarrow)没有奇圈
  • 最大边独立集的基数等于最大独立集的基数
  • 最大独立集的基数和最大匹配基数之和, 等于顶点数目.
  • 对于连通的二分图: 最小顶点覆盖集的基数等于最大匹配的基数
  • Hall定理是一个用于判定二分图是否具有最大匹配的定理。
    首先对于二分图G=(X∪Y,E),点集被分为了XX和YY两部分。
    是否具有最大匹配,首先一个最基本的条件就是|X|=|Y||X|=|Y|。
    Hall定理则在此基础上给出了一个更强的条件。
    首先对于一个点集T⊆X,定义Γ(T)Γ(T)如下:
    Γ(T)={v∣u→v∈E,u∈T,v∈Y}
    Γ(T)={v∣u→v∈E,u∈T,v∈Y}
    即表示TT中所有点能够直接到达的YY中的点的集合。
    mg娱乐电子4355 12
    上图中,Γ({1,3})={4,5,6}Γ({1,3})={4,5,6}。
    那么Hall条件则用于判断一个二分图是否存在最大匹配。Hall条件如下:
    对于任意的点集T⊆X,均存在:
    |T|≤|Γ(T)|
    |T|≤|Γ(T)|
    那么此二分图必定存在最大匹配。
解答

mg娱乐电子4355 13

2.5 其他常用结论

  • 对于不存在孤立点的图,|最大匹配|+|最小边覆盖| = |V|

  • 最大独立集合 + 最小顶点覆盖 = V

  • 对于二分图:|最大匹配| = |最小顶点覆盖|

  • 平面圖的頂點個數、邊數和面的個數之間有一個以歐拉命名的公式:mg娱乐电子4355 14

其中,V是頂點的数目,E是邊的數目,F是面的數目,C是组成圖形的連通部分的數目。當圖是單連通圖的時候,公式簡化為: mg娱乐电子4355 15

  • 任何一个平面图的对偶图仍然是平面图

2.3.13

MATHEMATICS

题目

在最佳、平均和最坏情况下,快速排序的递归深度分别是多少?
这决定了系统为了追踪递归调用所需的栈的大小。
在最坏情况下保证递归深度为数组大小的对数级的方法请见练习 2.3.20。

3.数学知识

解答

快速排序先将数组分为 (小于枢轴)枢轴(大于枢轴)三部分,然后再分别递归的排序左右两部分数组。
在这里,我们可以将快速排序的递归树看作是一棵二叉搜索树(BST, Binary Search Tree)。
枢轴作为根结点,左子树即为左数组构造的 BST,右子树即为右数组构造的 BST。
这样题目中所求的递归深度即为所构造的 BST 的高度。

最坏情况,每次都只有枢轴和大于枢轴两部分,BST 退化为链表,高度为 $ n-1 $。

最好情况,每次枢轴都正好平分数组,构造一棵完全二叉树,高度为 $ log n $。

平均情况,问题转化为:一个由 $ n $ 个元素随机构造的 BST 的平均高度是多少?
《算法导论》给出的结论是 $ log n $ ,具体证明如下:
设由 $ n $ 个结点随机构成的 BST 的高度为 $ h_n $,那么有:
[ h_n=1+max(h_{l}+h_{r}) ]
其中,$ h_l $ 和 $ h_r $ 分别代表左数组和右数组构造的 BST 的高度。
设枢轴位置为 $ i $,上式可简化为:
[ h_n=1+max(h_{i-1}, h_{n-i}) ]
由于枢轴位置可以在 1~n 之间任意取值且概率相等,因此 BST 的平均高度(即高度的期望)为:
[ E(h_n)=frac{1}{n}sum_{i=1}^{n}lbrack 1+max(h_{i-1}, h_{n-i}) rbrack ]
我们令 $ Y_n=2^{h_n} $,可得:
[ Y_n=2timesmax(Y_{i-1},Y_{n-i}) ]
我们把 $ Y_n $ 代入,可得:
[ begin{align*} E(Y_n) &=sum_{i=1}^{n}frac{1}{n}Elbrack2timesmax(Y_{i-1}, Y_{n-i})rbrack\ &=frac{2}{n}sum_{i=1}^{n}Elbrackmax(Y_{i-1},Y_{n-i})rbrack\ end{align*} ]
接下来我们去掉最大值运算,根据最大值的性质,下式显然成立:
[ Elbrackmax(X,Y)rbrackle Elbrackmax(X,Y)+min(X,Y)rbrack=Elbrack X+Yrbrack=Elbrack Xrbrack+Elbrack Yrbrack ]
代入可得:
[ E(Y_n) lefrac{2}{n}sum_{i=1}^{n}(Elbrack Y_{i-1}rbrack + Elbrack Y_{n-i} rbrack) =frac{2}{n}sum_{i=0}^{n-1}2Elbrack Y_irbrack =frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack ]
大小为 0 的数组构成的 BST 的高度显然为 0,我们设 $ Y_0=0 $ 。接下来用一个组合数公式来构造上界:
[ begin{align*} 0&=Y_0=Elbrack Y_0 rbrackle frac{1}{4}begin{pmatrix}3\3end{pmatrix}=frac{1}{4}\ 1&=Y_1=Elbrack Y_1 rbracklefrac {1}{4}begin{pmatrix}3+1\3end{pmatrix}=1 \ vdots \ Y_i &=Elbrack Y_irbracklefrac{1}{4}begin{pmatrix}i+3\3end{pmatrix} end{align*} ]
注意这里的组合数公式为:
[ begin{pmatrix}n\rend{pmatrix}=frac{r!}{r!(n-r)!} ]
代入可得:
[ begin{align*} E(Y_n) &le frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack \ &lefrac{4}{n}sum_{i=0}^{n-1}frac{1}{4}begin{pmatrix}i+3\3end{pmatrix} \ &=frac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix} end{align*} ]
接下来我们去掉求和符号,首先根据组合数的性质,有以下等式成立
[ begin{align*} begin{pmatrix}n\kend{pmatrix}&=begin{pmatrix}n-1\k-1end{pmatrix}+begin{pmatrix}n-1\kend{pmatrix} \ begin{pmatrix}n\nend{pmatrix}&=1 end{align*} ]
我们把求和式展开得到:
[ begin{align*} sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix} &=begin{pmatrix}3\3end{pmatrix} + begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix} \ &=begin{pmatrix}4\4end{pmatrix} + begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix} \ &=begin{pmatrix}n+3\4end{pmatrix} end{align*} ]
代入可得:
[ begin{align*} E(Y_n) &lefrac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}\ &=frac{1}{n}begin{pmatrix}n+3\4 end{pmatrix} \ &=frac{1}{n}cdotfrac{(n+3)!}{4!(n-1)!} \ &=frac{1}{4}cdotfrac{(n+3)!}{3!n!} \ &=frac{(n+1)(n+2)(n+3)}{24} \ &=frac{n^3+6n^2+11n+6}{24} end{align*} ]
由于 (Y_n=2^{h_n}) ,因此 (Elbrack Y_n rbrack=Elbrack 2^{h_n} rbrack)。
由于 (f(x)=2^x) 是个凸函数,可以应用延森不等式(凸函数的割线一定在函数上方),即 (2^{Elbrack h_nrbrack}le Elbrack Y_nrbrack)。
于是得到结论:
[ 2^{Elbrack h_nrbrack} le frac{n^3+6n^2+11n+6}{24} \ Elbrack h_n rbrackle log(frac{n^3+6n^2+11n+6}{24}) ]

3.1数论

另请参阅

快速排序的递归树可以视为 BST 的结论可以在下面这个 PPT 的第 5 页找到。
QuickSort-纽约大学
《算法导论》中关于随机 BST 高度的证明(P321 Theorem12.4)
Introduction to Algorithms
也可以参考下面这个链接获得更详细的解释。
Proof that a randomly built binary search tree has logarithmic height-StackExchange

3.1.1扩展欧几里德算法

首先我们有欧几里德算法:

[gcd(a, b) = gcd(a mod b, b)]

扩展欧几里德算法解决了这样的问题:

[ ax + by = gcd(a,b)]

我们先考察一种特殊的情况:

当(b=0)时,我们直接可以有解:
[ begin{eqnarray} left{ begin{array}{lll} x = 1 \ y = 0 end{array} right. end{eqnarray} ]
一般地,我们令(c = a mod b),递归地解下面的方程:

[bx^{'}+cy^{'}=gcd(b,c)]

根据欧几里德算法,有

[bx^{'}+cy^{'}=gcd(a,b)]

根据(mod)的定义我们可以有

[c = a - blfloorfrac{a}{b}rfloor]

带入原式

[bx^{'}+(a - blfloorfrac{a}{b}rfloor)y^{'}=gcd(a,b)]

为了体现与(a,b)的关系

[ay^{'}+b(x^{'}-lfloorfrac{a}{b}rfloor y^{'})=gcd(a,b)]

所以这样就完成了回溯。

这个算法的思想体现在了下面的程序里。

void gcd(int a, int b, int &d, int &x, int &y) {
  if(!b) {d = a; x = 1; y = 0; }
  else { gcd(b, a%b, d, y, x); y -= x * (a/b); }
}

2.3.14

3.1.2线性筛与积性函数

题目

证明在用快速排序处理大小为 N 的不重复数组时,
比较第 i 大和第 j 大元素的概率为 2/(j - i + 1),并用该结论证明命题 K。

3.1.2.1线性筛素数

首先给出线性筛素数的程序。

void get_su(int n) {
  tot = 0;
  for(int i = 2; i <= n; i++) {
    if(!check[i]) prime[tot++] = i;
    for(int j = 0; j < tot; j++) {
      if(i * prime[j] > n) break;
      check[i * prime[j]] = true;
      if(i % prime[j] == 0) break;
    }
  }
}

可以证明的是,每个合数都仅仅会被他的最小质因数筛去,这段代码的时间复杂度是(Theta (n))的,也就是所谓线性筛。

证明:设合数 class="math inline">(n)最小的质因数为 class="math inline">(p),它的另一个大于 class="math inline">(p)的质因数为 class="math inline">(p^{'}),另 class="math inline">(n = pm=p^{'}m^{'})。 观察上面的程序片段,可以发现 class="math inline">(j)循环到质因数 class="math inline">(p)时合数n第一次被标记(若循环到 class="math inline">(p)之前已经跳出循环,说明 class="math inline">(n)有更小的质因数),若也被 class="math inline">(p^{'})标记,则是在这之前(因为 class="math inline">(m^{'}<m)),考虑 class="math inline">(i)循环到 class="math inline">(m^{'}),注意到 class="math inline">(n=pm=p^{'}m^{'})且 class="math inline">(p,p^{'})为不同的质数,因此 class="math inline">(p|m^{'}),所以当j循环到质数p后结束,不会循环到 class="math inline">(p^{'}),这就说明 class="math inline">(n)不会被 class="math inline">(p^{'})筛去。

解答

中文版题目有误,详见官方勘误页面:

假设 $ i < j $ 。
首先,在快速排序中,如果两个元素要发生交换,意味着其中一个元素被选为枢轴。
而且数组中的元素各不相同,那么两个特定的元素的比较最多发生一次。

那么先考虑一个特殊情况,$ i = 1, j = n $ ,即求最大值和最小值比较的概率。
此时,一旦枢轴不是这两个元素之一,
最大值和最小值会被分到两个不同的子数组,无法发生比较。
因此在这种特例下第 $ i $ 大的元素和第 $ j $ 大的元素发生比较的概率为 $ frac{2}{n} = frac{2}{j-i+1} $ 。

接下来考虑一般情况,如果枢轴选择了第 $ i $ 到第 $ j $ 大之外的元素,
那么第 $ i $ 大和第 $ j $ 大的元素会被分到同一个子数组里,重复上述过程。
因此我们所求的概率只和从第 $ i $ 大到第 $ j $ 大之间的元素有关,概率为 (frac{2}{j-i+1})。
(举个例子,一个箱子里有 2 个红球、1个蓝球和 7 个白球,现在摸球而不放回。
如果摸到白球可以再摸一次,直到摸到红球或蓝球为止。
显然在这样的规则下摸到红球或蓝球的概率为 1,即白球对概率没有影响。)

现在我们已经得到了某两个元素比较的概率 (E(X_{ij})),接下来我们求每两个元素比较的概率 $ E(X) $。
[ begin{align*} E(X) &= sum_{i=1}^{n}sum_{j=i+1}^{n}E(X_{ij})\ &=sum_{i=1}^{n}2(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1}) \ &=2n(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1}) end{align*} ]
根据调和级数的性质($ ln (n) < 1+ frac{1}{2}+ cdots + frac{1}{n} < 1+ln(n) $),可以得到结论:
[ E(X) le 2n ln(n) ]

3.1.2.2积性函数
  • 考虑一个定义域为(mathbb{N}^{+})的函数(f)(数论函数),对于任意两个互质的正整数(a,b),均满足

[f(ab) = f(a)f(b)],则函数f被称为积性函数。

  • 如果对于任意两个正整数(a,b),都有(f(ab)=f(a)f(b)),那么就被称作完全积性函数。

容易看出,对于任意积性函数,(f(1)=1)。

  • 考虑一个大于1的正整数(N),设(N = prod p_{i}^{a_i}),那么

[f(N)=f(prod p_i^{a_i})=prod f(p_i^{a_i})],如果(f)还满足完全积性,那么

[f(N)=prod f(p_i)^{a_i}]

  • 如果(f)是一个任意的函数,它使得和式(g(m) = sum_{d|m}f(d))为积性函数,那么(f)也一定是积性函数。
  • 积性函数的Dirichlet前缀和也是积性函数。这个定理是上面定理的反命题。
  • 两个积性函数的Dirichlet卷积也是积性函数。
另请参阅

下面这个链接里的 3.4.2 节给出了解法。
lect0906 - 卡内基梅隆大学
如果还是不能理解为什么多次切分不影响概率,可以参考三门问题的解释:
蒙提霍尔问题 - 维基百科
蒙提霍尔问题(又称三门问题、山羊汽车问题)的正解是什么?- 知乎

3.1.2.3欧拉函数(varphi)
  • (varphi(n))表示(1..n)中与(n)互质的整数个数。
  • 我们有欧拉定理:

[n^{varphi(m)}equiv 1 pmod m nperp m]

可以使用这个定理计算逆元。

  • 如果(m)是一个素数幂,则容易计算(varphi(m)),因为有$n perp p^{k} Leftrightarrow p nmid n $ 。在({0,1,...,p^k-1})中的(p)的倍数是({0, p, 2p, ..., p^k-p}),从而有(p^{k-1})个,剩下的计入(varphi(p^k))

[varphi(p^k) = p^k-p^{k-1}=(p-1)p^{k-1}]

  • 由上面的推导我们不难得出欧拉函数一般的表示:

[varphi(m) = prod_{p|m}(p^{m_p}-p^{m_p-1}) = m prod_{p|m}(1-frac{1}{p})=prod(p-1)p^{m_p-1}]

  • 运用Mobius反演,不难得出(sum_{d|n}varphi(d) = n)。
  • 当(n>1)时,(1..n)中与(n)互质的整数和为(frac{nvarphi(n)}{2})
  • 降幂大法[A^B mod C=A^{B mod varphi(C)+varphi(C)} mod C]

2.3.15

3.1.2.4线性筛法求解积性函数
  • 积性函数的关键是如何求(f(p^k))。
  • 观察线性筛法中的步骤,筛掉n的同时还得到了他的最小的质因数(p),我们希望能够知道(p)在(n)中的次数,这样就能够利用(f(n)=f(p^k)f(frac{n}{p^k}))求出(f(n))。
  • 令(n=pm),由于(p)是(n)的最小质因数,若(p^2|n),则(p|m),并且(p)也是(m)的最小质因数。这样在筛法的同时,记录每个合数最小质因数的次数,就能算出新筛去合数最小质因数的次数。
  • 但是这样还不够,我们还要能够快速求解(f(p^k)),这时一般就要结合(f)函数的性质来考虑。
  • 例如欧拉函数(varphi),(varphi(p^k)=(p-1)p^{k-1}),因此进行筛法求(varphi(p*m))时,如果(p|m),那么(p*m)中(p)的次数不为1,所以我们可以从(m)中分解出(p),那么(varphi(p*m) = varphi(m) * p),否则(varphi(p * m) =varphi(m) * (p-1))。

  • 再例如默比乌斯函数(mu),只有当(k=1)时(mu(p^k)=-1),否则(mu(p^k)=0),和欧拉函数一样根据(m)是否被(p)整除判断。

    void Linear_Shaker(int N) { phi[1] = mu[1] = 1; for (int i = 2; i <= N; i++) {

    if (!phi[i]) {
      phi[i] = i - 1;
      mu[i] = -1;
      prime[cnt++] = i;
    }
    for (int j = 0; j < cnt; j++) {
      if (prime[j] * i > N)
        break;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        mu[i * prime[j]] = 0;
        break;
      } else {
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        mu[i * prime[j]] = -mu[i];
      }
    }
    

    } for (int i = 2; i <= N; i++) {

    phi[i] += phi[i - 1];
    mu[i] += mu[i - 1];
    

    } }

题目

螺丝和螺帽。(G.J.E.Rawlins)
假设有 N 个螺丝和 N 个螺帽混在一堆,你需要快速将它们配对。
一个螺丝只会匹配一个螺帽,一个螺帽也只会匹配一个螺丝。
你可以试着把一个螺丝和一个螺帽拧在一起看看谁大了,但不能直接比较两个螺丝或者两个螺帽。
给出一个解决这个问题的有效方法。

3.1.2.5线性筛逆元

令(f(i))为(i)在(mod p)意义下的逆元。显然这个函数是积性函数,我们可以使用线性筛求。但是其实没有那么麻烦。

我们设(p = ki+r),那么(ki+r equiv 0 (mod p)),两边同时乘(i^{-1}r^{-1}),有(kr^{-1}+i^{-1}equiv 0),那么(i^{-1} equiv -kr^{-1}=-lfloor frac {p}{i} rfloor * (p mod i)^{-1}),这样就可以递推了。

void getinv(int n) {
  inv[1] = 1;
  for(int i = 2; i <= x; i++)
    inv[i] = (long long)(p - p/i)*inv[p % i] % p;
}

有了逆元,我们就可以预处理阶乘的逆元

[n!^{-1} equiv prod_{k=1}^n k^{-1} mod p]

解答

事实上只需要修改快速排序的切分方法,分两次进行切分。
首先选第一个螺母作为枢轴,找到对应的螺丝($ O(n) $)放到第一位,对螺丝数组进行切分。
然后再用找到的螺丝对螺母数组进行切分。

螺母类,实现了对螺丝类的 IComparable 接口

/// <summary>
/// 螺母类。
/// </summary>
public class Nut<T> : IComparable<Bolt<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺母的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺母的构造函数。
    /// </summary>
    /// <param name="value">螺母的值。</param>
    public Nut(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺母只能和螺丝比较。
    /// </summary>
    /// <param name="other">需要比较的螺丝。</param>
    /// <returns></returns>
    public int CompareTo(Bolt<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

类似的有螺丝类。

/// <summary>
/// 螺丝类。
/// </summary>
public class Bolt<T> : IComparable<Nut<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺丝的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺丝的默认构造函数。
    /// </summary>
    /// <param name="value">螺丝的值。</param>
    public Bolt(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺丝只能和螺母比较。
    /// </summary>
    /// <param name="other">需要比较的螺母。</param>
    /// <returns></returns>
    public int CompareTo(Nut<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

3.1.3默比乌斯反演与狄利克雷卷积

代码

修改后的排序方法。

using System;

namespace _2._3._15
{
    /// <summary>
    /// 用快排的方式解决螺母和螺帽的问题。
    /// </summary>
    public class BoltsAndNuts
    {
        private readonly Random random = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public BoltsAndNuts() { }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts) where T : IComparable<T>
        {
            if (bolts.Length != nuts.Length)
                throw new ArgumentException("数组长度必须一致");

            Shuffle(bolts);
            Shuffle(nuts);
            Sort(bolts, nuts, 0, bolts.Length - 1);
        }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int j = Partition(bolts, nuts, lo, hi);
            Sort(bolts, nuts, lo, j - 1);
            Sort(bolts, nuts, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        /// <returns>切分位置。</returns>
        private int Partition<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            Bolt<T> pivotB = bolts[lo];
            // 找到对应螺丝
            for (int k = lo; k <= hi; k++)
            {
                if (nuts[k].CompareTo(pivotB) == 0)
                {
                    Exch(nuts, k, lo);
                    break;
                }
            }
            // 先用螺母去套螺丝
            while (true)
            {
                while (nuts[++i].CompareTo(pivotB) < 0)
                    if (i == hi)
                        break;
                while (pivotB.CompareTo(nuts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;
                Exch(nuts, i, j);
            }
            Exch(nuts, lo, j);

            // 再用螺丝去比较螺母
            Nut<T> pivotN = nuts[j];
            i = lo;
            j = hi + 1;
            while (true)
            {
                while (bolts[++i].CompareTo(pivotN) < 0)
                    if (i == hi)
                        break;
                while (pivotN.CompareTo(bolts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;

                Exch(bolts, i, j);
            }
            Exch(bolts, lo, j);

            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + this.random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 交换两个元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="a">需要交换的第一个元素。</param>
        /// <param name="b">需要交换的第二个元素。</param>
        private void Exch<T>(T[] a, int lo, int hi)
        {
            T t = a[lo];
            a[lo] = a[hi];
            a[hi] = t;
        }
    }
}
3.1.3.1初等积性函数(mu)

(mu)就是容斥系数。
[ mu(n) = begin{cases} 0, & text{if $exists x^2|n$} \ (-1)^k&n=prod_limits{i=1}^{k}p_i \ end{cases} ]
(mu)函数也是一个积性函数。

下面的公式可以从容斥的角度理解。
[ sum_{d|n}mu(d)=[n=1] ]

另请参阅

下面这个网站给出了这道题的解法,还给出了另一种确定性算法(非随机的算法)的论文链接。
Matching Nuts and Bolts - Solution

3.1.3.2默比乌斯反演

首先给出Mobius反演的公式:

[ F(n)=sum_{d|n}f(d) Rightarrow f(n)=sum_{d|n}mu(frac{n}{d})F(d) ]
有两种常见的证明,一种是运用Dirichlet卷积,一种是使用初等方法。

证明:
[ sum_{d|n}mu(d)F(frac{n}{d}) = sum_{d|n}mu(frac{n}{d})F(d)=sum_{d|n}mu(frac{n}{d})sum_{k|d}f(k)\=sum_{d|n}sum_{k|d}mu(frac{n}{d})f(k)=sum_{k|n}sum_{d|frac{n}{k}}mu(frac{n}{kd})f(k)\ =sum_{k|n}sum_{d|frac{n}{k}}mu(d)f(k)=sum_{k|n}[frac{n}{k} = 1]f(k)=f(n) ]
默比乌斯反演的另一种形式:
[ F(n)=sum_{n|d}f(d)Rightarrow f(n)=sum_{n|d}mu(frac{d}{n})F(d) ]
这个式子的证明与上式大同小异,我在这里写一下关键步骤
[ sum_{n|d}sum_{d|k}mu(frac{d}{n})f(k)=sum_{n|k}sum_{d|frac{k}{n}}mu(d)f(k)=f(n) ]
对于一些函数(f(n)),如果我们很难直接求出他的值,而容易求出倍数和或者因数和(F(n)),那么我们可以通过默比乌斯反演来求得(f(n))的值

2.3.16

3.1.3.3狄利克雷卷积

定义两个数论函数(f(x)),(g(x))的(Dirichlet)卷积
[ (f*g)(n)=sum_{d|n}f(d)g(frac nd) ]
Dirichlet卷积满足交换律,结合律,分配律,单位元。

运用狄利克雷卷积不难证明默比乌斯反演。

题目

最佳情况。
编写一段程序来生成使算法 2.5 中的 sort() 方法表现最佳的数组(无重复元素):
数组大小为 N 且不包含重复元素,每次切分后两个子数组的大小最多差 1
(子数组的大小与含有 N 个相同元素的数组的切分情况相同)。
(对于这道练习,我们不需要在排序开始时打乱数组。)

3.1.4积性函数求和与杜教筛

解答

官方实现见:

类似于快速排序的结构,只要中点的两边都是最佳情况,那么整个数组就是最佳情况了。
具体方法是:
首先构造一个有序数组,
然后找到中点(作为枢轴),
对中点左右两侧子数组进行构造,
将选择的枢轴放到开始处(a[lo])。

3.1.4.1概述

如果能通过狄利克雷卷积构造一个更好计算前缀和的函数,且用于卷积的另一个函数也易计算,则可以简化计算过程。

设(f(n))为一个数论函数,需要计算(S(n)=sum_{i=1}^n f(i))。

根据函数(f(n))的性质,构造一个(S(n))关于(S(lfloor frac ni rfloor))的递推式,如下例:

找到一個合适的数论函数(g(x))
[ sum_{i=1}^nsum_{d|i}f(d)g(frac id)=sum_{i=1}^ng(i)S(lfloorfrac nirfloor) ]
可以得到递推式
[ g(1)S(n)=sum_{i=1}^n(f*g)(i)-sum_{i=2}^ng(i)S(lfloor frac{n}{i}rfloor) ]
在递推计算(S(n))的过程中,需要被计算的(S(lfloor frac ni rfloor))只有(O(sqrt n))种。

代码

用于构造最佳数组的类。

namespace Quick
{
    /// <summary>
    /// 构建快速排序最佳情况的类。
    /// </summary>
    public class QuickBest
    {
        /// <summary>
        /// 构造函数,这个类不应该被实例化。
        /// </summary>
        private QuickBest() { }

        /// <summary>
        /// 构造适用于快速排序的最佳数组。
        /// </summary>
        /// <param name="n">数组长度。</param>
        /// <returns></returns>
        public static int[] Best(int n)
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = i;
            }
            Best(a, 0, n - 1);
            return a;
        }

        /// <summary>
        /// 递归的构造数组。
        /// </summary>
        /// <param name="a">需要构造的数组。</param>
        /// <param name="lo">构造的起始下标。</param>
        /// <param name="hi">构造的终止下标。</param>
        private static void Best(int[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Best(a, lo, mid - 1);
            Best(a, mid + 1, hi);
            Exch(a, lo, mid);
        }

        /// <summary>
        /// 交换数组中的两个元素。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">包含要交换元素的数组。</param>
        /// <param name="x">需要交换的第一个元素下标。</param>
        /// <param name="y">需要交换的第二个元素下标。</param>
        private static void Exch(int[] a, int x, int y)
        {
            int t = a[x];
            a[x] = a[y];
            a[y] = t;
        }
    }
}

用于测试的方法

using System;
using Quick;

namespace _2._3._16
{
    /*
     * 2.3.16
     * 
     * 最佳情况。
     * 编写一段程序来生成使算法 2.5 中的 sort() 方法表现最佳的数组(无重复元素):
     * 数组大小为 N 且不包含重复元素,
     * 每次切分后两个子数组的大小最多差 1
     * (子数组的大小与含有 N 个相同元素的数组的切分情况相同)。
     * (对于这道练习,我们不需要在排序开始时打乱数组。)
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortAnalyze quick = new QuickSortAnalyze
            {
                NeedShuffle = false,            // 关闭打乱
                NeedPath = true                 // 显示排序轨迹
            };
            int[] a = QuickBest.Best(10);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
            quick.Sort(a);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
        }
    }
}
3.1.4.1欧拉函数求前缀和

利用(varphi * I=id)的性质,可以有:
[ S(n)=sum_{i=1}^ni-sum_{i=2}^nS(lfloor frac nirfloor) ]

另请参阅

Quick 库

3.1.4.2默比乌斯函数前缀和

利用(mu * I = e)的性质,可以有:
[ S(n)=1-sum_{i=2}^nS(lfloorfrac nirfloor) ]

2.3.17

3.1.4.3模板
ll get_p(int x) { return (x <= m) ? phi[x] : p[n / x]; };
ll get_q(int x) { return (x <= m) ? mu[x] : q[n / x]; };
void solve(ll x) {
  if (x <= m)
    return;
  int i, last = 1, t = n / x;
  if (vis[t])
    return;
  vis[t] = 1;
  p[t] = ((x + 1) * x) >> 1;
  q[t] = 1;
  while (last < x) {
    i = last + 1;
    last = x / (x / i);
    solve(x / i);
    p[t] -= get_p(x / i) * (last - i + 1);
    q[t] -= get_q(x / i) * (last - i + 1);
  }
}
//注:本代码为了避免数组过大,p[]和q[]记录的是分母的值。
题目

哨兵。
修改算法 2.5,去掉内循环 while 中的边界检查。
由于切分元素本身就是一个哨兵(v 不可能小于 a[lo]),左侧边界检查是多余的。
要去掉另一个检查,可以在打乱数组后将数组的最大元素方法 a[length - 1] 中。
该元素永远不会移动(除非和相等的元素交换),可以在所有包含它的子数组中成为哨兵。
注意:在处理内部子数组时,右子数组中最左侧的元素可以作为左子数组右边界的哨兵。

3.1.5中国剩余定理

中国剩余定理给出了以下的一元线性同余方程组有解的判定条件:
[ left{ begin{array}{c} x equiv a_1 pmod {m_1}\ x equiv a_2 pmod {m_2}\ vdots \ x equiv a_n pmod {m_n} end{array} right. ]
中国剩余定理指出,如果模数两两互质,那么方程组有解,并且通解可以构造得到:

  1. 设(M = prod_{i=1}^n m_i),并设(M_i=frac{M}{m_i})。
  2. 设(t_i=M_i^{-1} pmod {m_i})。
  3. 那么通解(x = sum_{i=1}^n a_it_iM_i)。
解答

按照题意修改代码即可,在调用 Suffle() 之后添加一段用于寻找最大值的方法($ O(n) $)。

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);

    // 把最大元素放到最后一位
    int maxIndex = 0;
    for (int i = 0; i < a.Length; i++)
    {
        if (Less(a[maxIndex], a[i]))
            maxIndex = i;
    }
    Exch(a, maxIndex, a.Length - 1);

    Sort(a, 0, a.Length - 1);
    Debug.Assert(IsSorted(a));
}

3.1.6高斯消元

Gauss消元法就是使用初等行列式变换把原矩阵转化为上三角矩阵然后回套求解。给定一个矩阵以后,我们考察每一个变量,找到它的系数最大的一行,然后根据这一行去消除其他的行。

double a[N][N]
void Gauss(){
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)
            if(abs(a[j][i])>abs(a[r][i])) r=j;
        if(r!=i) for(int j=1;j<=n+1;j++) swap(a[i][j],a[r][j]);

        for(int j=i+1;j<=n;j++){
            double t=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*t;
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=n;j>i;j--) a[i][n+1]-=a[j][n+1]*a[i][j];
        a[i][n+1]/=a[i][i];
    }
}

对于xor运算,我们可以使用同样的方法消元。

另外,xor的话可以使用bitset压位以加速求解。

代码

修改后的快速排序类。

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._17
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortX : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortX() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);

            // 把最大元素放到最后一位
            int maxIndex = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (Less(a[maxIndex], a[i]))
                    maxIndex = i;
            }
            Exch(a, maxIndex, a.Length - 1);

            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
             //     if (i == hi)
             //         break;
                while (Less(v, a[--j])) ;
             //     if (j == lo)
             //         break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

主方法。

using System;
using Quick;

namespace _2._3._17
{
    /*
     * 2.3.17
     * 
     * 哨兵。
     * 修改算法 2.5,去掉内循环 while 中的边界检查。
     * 由于切分元素本身就是一个哨兵(v 不可能小于 a[lo]),
     * 左侧边界检查是多余的。
     * 要去掉另一个检查,可以在打乱数组后将数组的最大元素方法 a[length - 1] 中。
     * 该元素永远不会移动(除非和相等的元素交换),
     * 可以在所有包含它的子数组中成为哨兵。
     * 注意:在处理内部子数组时,
     * 右子数组中最左侧的元素可以作为左子数组右边界的哨兵。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quick = new QuickSort();
            QuickSortX quickSortX = new QuickSortX();
            int arrayLength = 1000000;
            int[] a = SortCompare.GetRandomArrayInt(arrayLength);
            int[] b = new int[arrayLength];
            a.CopyTo(b, 0);

            double time1 = SortCompare.Time(quick, a);
            double time2 = SortCompare.Time(quickSortX, b);
            Console.WriteLine("QSorttQSort with Sentinelst");
            Console.WriteLine(time1 + "t" + time2 + "t");
        }
    }
}

3.1.7大步小步BSGS算法

大步小步算法用于解决:

已知(A,B,C),求(x)使得, 其中(C is a prime).
[ A^xequiv Bpmod C ]
我们令(x=itimes m-frac{j}{m}=lceil sqrt C rceil, i in [1,m], j in [0,m])

那么原式就变成了[A^{im}=A^jtimes B] .我们先枚举(j),把(A^j times B)加入哈希表,然后枚举(i),在表中查找(A^{im}),如果找到了,就找到了一个解。时间复杂度为(Theta (sqrt n))。

ll BSGS(ll A, ll B, ll C) {
    mp.clear();
    if(A % C == 0) return -2;
    ll m = ceil(sqrt(C));
    ll ans;
    for(int i = 0; i <= m; i++) {
        if(i == 0) {
            ans = B % C;
            mp[ans] = i;
            continue;
        }
        ans = (ans * A) % C;
        mp[ans] = i;
    }
    ll t = pow(A, m, C); 
    ans = t;
    for(int i = 1; i <= m; i++) {
        if(i != 1)ans = ans * t % C;
        if(mp.count(ans)) {
            int ret = i * m % C - mp[ans] % C;
            return (ret % C + C)%C;
        }
    }
    return -2;
} 
另请参阅

Quick 库

3.2组合数学

编辑:计算机编程 本文来源:省选前模板总结

关键词: