JZTXT

线段树

发布时间 2023-04-27 18:31:28作者: jkc999

 

1.基础算法

1.1快读快写

template <typename T> inline void read(T& t) {
​
  int f = 0, c = getchar(); t = 0; 
​
  while (!isdigit(c)) f |= c == '-', c = getchar();
​
  while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
​
  if (f) t = -t;
​
}
​
 
​
template <typename T> void print(T x) {
​
  if (x < 0) x = -x, putchar('-');
​
  if (x > 9) print(x / 10);
​
  putchar(x % 10 + 48);
​
}

 

1.2二分、三分

区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用

int bsearch_1(int l, int r)
​
{
​
  while (l < r)
​
  {
​
     int mid = l + r >> 1;
​
     if (check(mid)) r = mid; 
​
     else l = mid + 1;
​
  }
​
  return l;
​
}
​
//区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用
​
int bsearch_2(int l, int r)
​
{
​
  while (l < r)
​
  {
​
     int mid = l + r + 1 >> 1;
​
     if (check(mid)) l = mid;
​
     else r = mid - 1;
​
  }
​
  return l;
​
}
​
double bsearch_3(double l, double r)
​
{
​
  const double eps = 1e-6;  eps //表示精度，取决于题目对精度的要求
​
  while (r - l > eps)
​
  {
​
     double mid = (l + r) / 2;
​
     if (check(mid)) r = mid;
​
     else l = mid;
​
  }
​
  return l;
​
}
​
 
​
//三分法
​
double l, r;
​
const double eps
​
while(r - l > eps) {
​
  double mid1 = l + (r - l) / 3.0;
​
  double mid2 = r - (r - l) / 3.0;
​
  double fx = check(mid1), fy = check(mid2);
​
  if(fx > fy) l = mid1;
​
  else r = mid2;
​
}

 

1.3前缀和

 

//一维前缀和：快速查询区间和
​
s[i] = s[i-1]+a[i]
​
a[l] + ... + a[r] = s[r] - s[l - 1]
​
 
​
//二维前缀和：子矩阵和
​
//s[i, j] = 第i行j列格子左上部分所有元素的和
​
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
​
s[x2, y2] - s[x1 - 1, y2] - s[x2, y1 - 1] + s[x1 - 1, y1 - 1]
​
 
​
//s[i]处理：
​
for(int i = 1; i <= n; i++) {
​
  for(int j = 1; j <= m; j++) {
​
     s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
​
  }
​
}
​
 
​
//一维差分
​
//区间[l, r]中的每个数加上c：b[l] += c, b[r + 1] -= c
​
//前缀和的逆运算就是差分
​
void insert(int l, int r, int x) {
​
  b[l] += x;
​
  b[r + 1] -= x;
​
}
​
//二维差分
​
//以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
​
s[x1, y1] += c, s[x2 + 1, y1] -= c, s[x1, y2 + 1] -= c, s[x2 + 1, y2 + 1] += c
​
 
​
void insert(int x1, int y1, int x2, int y2, int c) {
​
  b[x1][y1] += c;
​
  b[x2 + 1][y1] -= c;
​
  b[x1][y2 + 1] -= c;
​
  b[x2 + 1][y2 + 1] += c;
​
}
​
//差分处理原数组 
​
for(int i = 1; i <= n; i++) {
​
  for(int j = 1; j <= m; j++) {
​
     insert(i, j, i, j, a[i][j]);
​
  }
​
}
​
//还原
​
for(int i = 1; i <= n; i++) {
​
  for(int j = 1; j <= m; j++) {
​
     b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
​
  }
​
}

 

1.4离散化

/*
​
 *第一种方式：stl函数（绝对的大小关系）
​
 *n 原数组大小 
​
 *num 原数组中的元素 lsh 离散化的数组 cnt 离散化后的数组大小 
​
 */
​
int lsh[MAXN], cnt, num[MAXN], n;
​
for(int i = 1; i <= n; i++) {
​
  scanf("%d", &num[i]);
​
  lsh[i] = num[i];
​
}
​
sort(lsh + 1, lsh + n + 1);
​
 
​
cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1;
​
for(int i = 1; i <= n; i++)
​
num[i] = lower_bound(lsh + 1, lsh + cnt + 1, num[i]) - lsh;
​
 
​
/*
​
 *第二种方式：记录下标，排序后放回原数组 
​
 */
​
#include<algorithm>
​
struct Node {
​
  int data, id;
​
  bool operator < (const Node &a) const {
​
    return data < a.data; //如果有位置要求 记得加
​
  }
​
};
​
Node num[MAXN];
​
int rank[MAXN], n;
​
for(int i = 1; i <= n; i++) {
​
  scanf("%d", &num[i].data);
​
  num[i].id = i;
​
}
​
sort(num + 1, num + n + 1);
​
for(int i = 1; i <= n; i++)
​
  rank[num[i].id] = i;

 

1.5高精度

 

/*

 *加法 

 */

\#include <bits/stdc++.h>

using namespace std;

vector<int> add(vector<int> &a, vector<int> &b) {

  vector<int> c;

  int t = 0;

  for(int i = 0; i < a.size() || i < b.size(); i++) {

    if(i < a.size()) t += a[i];

    if(i < b.size()) t += b[i];

    c.push_back(t % 10);

    t /= 10;

  }

  if(t) c.push_back(1);

  return c;

}

int main() {

  vector<int> A, B;

  string a, b;

  cin >> a >> b;

  for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

  for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

  auto ok = add(A, B);

  for(int i = ok.size() - 1; i >= 0; i--) {

    cout << ok[i];

  }

  return 0;

}

/*

 *减法C = A - B, 满足A >= B, A >= 0, B >= 0

 */

bool cmp(vector<int> &a, vector<int> &b) {

  if(a.size() != b.size()) return a.size() > b.size();

 

  for(int i = a.size() - 1; i >= 0; i--) {

    if(a[i] != b[i]) return a[i] > b[i];

 

  }

  return true;

}

vector<int> sub(vector<int> &A, vector<int> &B) {

  vector<int> C;

  for (int i = 0, t = 0; i < A.size(); i ++ ) {

    t = A[i] - t;

    if (i < B.size()) t -= B[i];

    C.push_back((t + 10) % 10);

    if (t < 0) t = 1;

    else t = 0;

  }

 

  while (C.size() > 1 && C.back() == 0) C.pop_back();

  return C;

}

signed main() {

  string a, b;

  cin >> a >> b;

  vector<int> A, B;

  for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

  for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

  if(cmp(A, B)) {

    auto c = sub(A, B);

    for(int i = c.size() - 1; i >= 0; i--) {

      cout << c[i];

    }

  } else {

    auto c = sub(B, A);

    cout << "-";

    for(int i = c.size() - 1; i >= 0; i--) {

      cout << c[i];

    }

  }

  return 0;

}

 

/*

 *除法  A / b = C ... r, A >= 0, b > 0

 */

vector<int> div(vector<int> &A, int b, int &r) {

  vector<int> C;

  r = 0;

  for (int i = A.size() - 1; i >= 0; i -- ) {

    r = r * 10 + A[i];

    C.push_back(r / b);

    r %= b;

  }

  reverse(C.begin(), C.end());

  while (C.size() > 1 && C.back() == 0) C.pop_back();

  return C;

}

signed main() {

  string a;

  int b;

  int r = 0;

  cin >> a >> b;

  vector<int> A;

  for(int i = a.size() - 1; i >= 0; i--) {

    A.push_back(a[i] - '0');

  }

  auto c = div(A, b, r);

  for(int i = c.size() - 1; i >= 0; i--) {

    cout << c[i];

  }

  puts("");

  cout << r;

  return 0;

}

 

/*

 *乘法

 */

#include <iostream>

#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B) {

  vector<int> C(A.size() + B.size());

  for (int i = 0; i < A.size(); i++)

    for (int j = 0; j < B.size(); j++)

      C[i + j] += A[i] * B[j];

  for (int i = 0, t = 0; i < C.size() || t; i++) {

    t += C[i];

    if (i >= C.size()) C.push_back(t % 10);

    else C[i] = t % 10;

    t /= 10;

  }

  while (C.size() > 1 && C.back() == 0) C.pop_back();

  return C;

}

int main() {

  string a, b;

  cin >> a >> b;

  vector<int> A, B;

  for (int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');

  for (int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

  vector<int> C = mul(A, B);

  for (int i = C.size() - 1; i >= 0; i--) cout << C[i];

  return 0;

}

 

1.6尺取法

/*

 *尺取法 适用于l增大时侯r跟着增大取到一些合法的区间时使用

 */

int ans = INF, l = 1, r = 1, cnt = 0;

for(; ;)

{

  while(r <= n && cnt < sum) cnt += a[r++]; //直到符合总数

  if(cnt < sum) break; //再也无法满足

  ans = min(ans, r - l); //更新答案

  cnt -= a[l++]; //尝试进步

}

 

1.7归并排序

int n, a[N], b[N]; //b为辅助数组

void merge_dfs(int l, int mid, int r)

{

  int i = l, j = mid + 1, k = l;

  while(i <= mid && j <= r)

  {

    b[k++] = (a[i] < a[j] ? a[i++] : a[j++]); //排序

  }

  while(i <= mid) b[k++] = a[i++];

  while(j <= r) b[k++] = a[j++];

  RE(i, l, r) a[i] = b[i]; //还原

}

void dfs(int l, int r)

{

  if(l == r) return;

  int mid = l + r >> 1;

  dfs(l, mid);

  dfs(mid + 1, r);

  merge_dfs(l, mid, r);

}

 

2. 数据结构

2.1单调栈

/*

 *top = 0 栈空

 *st[++top] = x 插入

 *st[top] 栈顶 

 */

int top, st[N]; //指针 数组栈

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

   if(top == 0) st[++top] = i;//为空入栈

   //维护单调性 b[]存储答案

   hile(top != 0 && a[i] > a[st[top]]) b[st[top]] = i, top--;

   st[++top] = i;

}

 

 

2.2单调队列

/*

 *head 队头 tail队尾 

 *head <= tail 队列不为空

 *head++ 出队

 *q[++tail] = x 入队

 */

int head, tail, q[N], idx[N];

head = 1, tail = 0;

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

   while(head <= tail && a[i] > q[tail]) tail--;

   q[++tail] = a[i];

   idx[tail] = i;

   if(idx[head] <= i - k) head++;//队头元素过时

   if(i >= k) cout << q[head] << " ";

}

 

2.3 ST表

struct rmq {

  int f[N][50], lg[N] = {-1};

  void init() {

    for(int i = 1; i <= n; ++i) f[i][0] = a[i];

    for(int i = 1; i <= n; ++i) lg[i] = lg[i >> 1] + 1;

    for(int j = 1; j <= lg[n]; ++j)

      for(int i = 1; i + (1 << j) - 1 <= n; ++i)

        f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

  }

  int query(int x, int y) {

    int s = lg[y - x + 1];

    return max(f[x][s], f[y - (1 << s) + 1][s]);

  }

} st;

 

2.4树状数组

/*

 *单点修改 区间查询

 */

int lowbit(int x) {

  return x & -x;

}

void change(int i, int x) {

  for(; i <= n; i += lowbit(i)) c[i] += x;

}

//查询[1, i],

int query(int i) {

  int res = 0;

  for(; i; i -= lowbit(i)) res += c[i];

  return res;

}

 

/*

 *单点查询 区间修改

 *函数模板均跟第一个一样，读入a[]数组，以及区间修改时使用到差分 

 */

add(i, a[i] - a[i - 1]); //初始化

cin >> l >> r >> x;

add(l, x)， add(r + 1, -x); //差分更新

 

 

/*

 *树状数组上二分求第k大：

 *假设有n个数, 求第k大等价于求(n - k + 1)小

 *可将权值用树状数组维护，二分查找第k大。

 */

scanf("%d", &k);

k = num - k + 1;//num是实际存在的数的个数

int l = 1, r = n;//值域

while(l < r) {

  int mid = l + r >> 1;

  if(query(mid) >= k) r = mid;

  else l = mid + 1;

}

cout << l;

 

2.5线段树

2.5.1线段树结构 

/*

 *线段树主要考虑区间维护的信息

 *以及如何设计lazy

 *区间修改区间查询模板

 */

struct tnode {

  int l, r; //区间边界

  int sum, lazy; //需要维护的信息

};

struct segment_tree {

  tnode t[N << 2];

  void build(int k, int l, int r) { //建树

    t[k].l = l, t[k].r = r;

    if(l == r) {

      t[k].sum = a[l];

      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; //push_up

  }

  void push_down(int k, int l, int r) { //下放懒标记

    if(t[k].lazy) { //lazy值存在

      int mid = l + r >> 1;

      t[k << 1].lazy += t[k].lazy; //union_lazy

      t[k << 1 | 1].lazy += t[k].lazy;

      t[k << 1].sum += t[k].lazy * (mid - l + 1); //cal_lazy

      t[k << 1 | 1].sum += t[k].lazy * (r - mid);

      t[k].lazy = 0;

    }

  }

  void change(int k, int l, int r, int val) {

    if(t[k].l >= l && t[k].r <= r) {

      t[k].lazy += val; //union_lazy

      t[k].sum += (t[k].r - t[k].l + 1) * val; //cal_lazy

      return;

    }

    push_down(k, t[k].l, t[k].r);

    int mid = (t[k].l + t[k].r) >> 1;

    if(r <= mid) change(k << 1, l, r, val);

    else if(l > mid) change(k << 1 | 1, l, r, val);

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

    t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum; //push_up

  }

  int query(int k, int l, int r) {

    if(t[k].l >= l && t[k].r <= r) {

      return t[k].sum;

    }

    push_down(k, t[k].l, t[k].r);

    int mid = t[k].l + t[k].r >> 1;

    if(r <= mid) return query(k << 1, l, r);

    else if(l > mid) return query(k << 1 | 1, l, r);

    else return query(k << 1, l, mid) + query(k << 1 | 1, mid + 1, r);
      
  }

};

 

2.5.2线段树优化建图

/*

 *某点到区间建边，不需要虚点

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 2e6 + 10;

int cnt, head[N];

struct edge {

  int to, nex, w;

} e[N << 1];

inline void add(int u, int v, int w) {

  e[++cnt].to = v;

  e[cnt].w = w;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

int n, m, s;

int tot, Ls[N], Rs[N], In, Out;

//入树 实现 u -> [L, R] 自上往下连边

void buildIn(int &k, int l, int r) {

  if(l == r) {

    k = l;

    return;

  }

  k = ++tot;

  int mid = l + r >> 1;

  buildIn(Ls[k], l, mid);

  buildIn(Rs[k], mid + 1, r);

  add(k, Ls[k], 0);

  add(k, Rs[k], 0);

}

//出树 实现 [L, R] -> u 自下往上连边

void buildOut(int &k, int l, int r) {

  if(l == r) {

    k = l;

    return;

  }

  k = ++tot;

  int mid = l + r >> 1;

  buildOut(Ls[k], l, mid);

  buildOut(Rs[k], mid + 1, r);

  add(Ls[k], k, 0);

  add(Rs[k], k, 0);

}

void addIn(int k, int l, int r, int L, int R, int tag, int w) {

  if(l >= L && r <= R) {

    add(tag, k, w);

    return;

  }

  int mid = l + r >> 1;

  if(L <= mid) addIn(Ls[k], l, mid, L, R, tag, w);

  if(R > mid) addIn(Rs[k], mid + 1, r, L, R, tag, w);

}

void addOut(int k, int l, int r, int L, int R, int tag, int w) {

  if(l >= L && r <= R) {

    add(k, tag, w);

    return;

  }

  int mid = l + r >> 1;

  if(L <= mid) addOut(Ls[k], l, mid, L, R, tag, w);

  if(R > mid) addOut(Rs[k], mid + 1, r, L, R, tag, w);

}

signed main() {

  cin >> n >> m >> s; //n点m条边源点

  tot = n;//线段树结点标号从n+1开始

  buildIn(In, 1, n);

  buildOut(Out, 1, n);

  int op, l, r, u, v, w;

  while(m-- && cin >> op) {

    if(op == 1) {

      cin >> u >> v >> w;

      add(u, v, w);

    } else if(op == 2) {

      cin >> u >> l >> r >> w;

      addIn(In, 1, n, l, r, u, w);

    } else {

      cin >> u >> l >> r >> w;

      addOut(Out, 1, n, l, r, u, w);

    }

  }

  dijstra();

  return 0;

}

 

/*

 *区间到区间建图，需要虚点p，q

 */

#include <bits/stdc++.h>

#define ll long long

using namespace std;

template <typename T> inline void read(T& t) {

  int f = 0, c = getchar();

  t = 0;

  while (!isdigit(c)) f |= c == '-', c = getchar();

  while (isdigit(c)) t = t * 10 + c - 48, c = getchar();

  if (f) t = -t;

}

const int N = 5e6 + 10;

int cnt, head[N];

struct edge {

  int to, nex, w;

} e[N << 1];

inline void add(int u, int v, int w) {

  e[++cnt].to = v;

  e[cnt].w = w;

  e[cnt].nex = head[u];

  head[u] = cnt++;

}

int n, m, s;

int tot, Ls[N], Rs[N], In, Out;

//入树 自上而下建边

void buildIn(int &k, int l, int r) {

  if(l == r) {

    k = l;

    return;

  }

  k = ++tot;

  int mid = l + r >> 1;

  buildIn(Ls[k], l, mid);

  buildIn(Rs[k], mid + 1, r);

  add(k, Ls[k], 0);

  add(k, Rs[k], 0);

}

//出树 自下而上建边

void buildOut(int &k, int l, int r) {

  if(l == r) {

    k = l;

    return;

  }

  k = ++tot;

  int mid = l + r >> 1;

  buildOut(Ls[k], l, mid);

  buildOut(Rs[k], mid + 1, r);

  add(Ls[k], k, 0);

  add(Rs[k], k, 0);

}

void addOut(int k, int l, int r, int L, int R, int idx) {

  if(l >= L && r <= R) {

    add(k, idx, 0);

    return;

  }

  int mid = l + r >> 1;

  if(L <= mid) addOut(Ls[k], l, mid, L, R, idx);

  if(R > mid) addOut(Rs[k], mid + 1, r, L, R, idx);

}

void addIn(int k, int l, int r, int L, int R, int idx) {

  if(l >= L && r <= R) {

    add(idx, k, 0);

    return;

  }

  int mid = l + r >> 1;

  if(L <= mid) addIn(Ls[k], l, mid, L, R, idx);

  if(R > mid) addIn(Rs[k], mid + 1, r, L, R, idx);

}

void insertt(int a, int b, int c, int d) {

  int p = ++tot;

  addOut(Out, 1, n, a, b, p);

  int q = ++tot;

  addIn(In, 1, n, c, d, q);

  add(p, q, 1);

}

signed main() {

  read(n), read(m), read(s);

  tot = n;

  buildIn(In, 1, n);

  buildOut(Out, 1, n);

  int a, b, c, d;

  while(m--) {

    read(a);

    read(b);

    read(c);

    read(d);

    insertt(a, b, c, d);

    insertt(c, d, a, b);

  }

  dijstra();

  return 0;

}

 

2.5.3维护GCD

#include <bits/stdc++.h>

#define go continue

#define int long long

#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fory(i,a,b) for(int i = a; i <= b; ++i)

using namespace std;

const int N = 5e5 + 10;

int n, m, a[N];

inline int gcd(int a, int b) {

  return b ? gcd(b, a % b) : a;

}

struct node {

  int l, r, sum, d;

};

struct segment_tree {

  node t[N << 2];

  int mp[N];

  inline void help_push(node& a, node& b, node& c) {

    a.sum = b.sum + c.sum;

    a.d = gcd(b.d, c.d);

  }

  inline void push_up(int root) {

    int ch = root << 1;

    help_push(t[root], t[ch], t[ch + 1]);

  }

  inline void build(int root, int l, int r) {

    t[root].l = l;

    t[root].r = r;

    if(l != r) {

      int ch = root << 1;

      int mid = (l + r) >> 1;

      build(ch, l, mid);

      build(ch + 1, mid + 1, r);

      push_up(root);

    } else {

      int tmp = a[l] - a[l - 1];

      t[root].d = tmp;

      t[root].sum = tmp;

      mp[l] = root;

    }

  }

  inline void change(int root, int x, int y) {

    x = mp[x];

    t[x].d = t[x].sum + y;

    t[x].sum += y;

 

    while(x >>= 1) push_up(x);

  }

  inline node query(int root, int l, int r) {

    if(t[root].l >= l && t[root].r <= r) {

      return t[root];

    } else {

      int ch = root << 1;

      int mid = (t[root].l + t[root].r) >> 1;

 

      if(mid >= r) return query(ch, l, r);

      else if(l > mid) return query(ch + 1, l, r);

      else {

        node left = query(ch, l, mid);

        node right = query(ch + 1, mid + 1, r);

        node res;

        help_push(res, left, right);

        return res;

      }

    }

  }

} st;

int l, r, x;

char op[2];

signed main() {

  read(n), read(m);

  fory(i, 1, n) read(a[i]);

  st.build(1, 1, n);

  while(m--) {

    scanf("%s%lld%lld", op, &l, &r);

    if(*op == 'C') {

      read(x);

      st.change(1, l, x);

      if(r + 1 <= n) st.change(1, r + 1, -x);

    } else {

      node ll = st.query(1, 1, l);

      node rr = {0, 0, 0, 0};

      if(l + 1 <= r) rr = st.query(1, l + 1, r);

      printf("%lld\n", abs(gcd(ll.sum, rr.d)));

    }

  }

  return 0;

}

 

2.5.4区间第K小

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int cnt, root[N];

int sum[N << 5], lc[N << 5], rc[N << 5];

int n, m, a[N], b[N], p;

void build(int& t, int l, int r) {

  t = ++cnt;

  if(l == r) return;

  int mid = l + r >> 1;

  build(lc[t], l, mid);

  build(rc[t], mid + 1, r);

}

int change(int pre, int l, int r) {

  int now = ++cnt;

  lc[now] = lc[pre];

  rc[now] = rc[pre];

  sum[now] = sum[pre] + 1;

  if(l == r) return now;

  int mid = l + r >> 1;

  if(p <= mid) lc[now] = change(lc[now], l, mid);

  else rc[now] = change(rc[now], mid + 1, r);

  return now;

}

int query(int L, int R, int l, int r, int k) {

  if(l == r) return l;

  int mid = l + r >> 1;

  int x = sum[lc[R]] - sum[lc[L]];

   if(x >= k) return query(lc[L], lc[R], l, mid, k);

  else return query(rc[L], rc[R], mid + 1, r, k - x);

}

signed main() {

  ios::sync_with_stdio(false), cin.tie(0);

  cin >> n >> m;

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

     cin >> a[i];

     b[i] = a[i];

  }

  sort(b + 1, b + 1 + n);

  int l, r, k, q;

  q = unique(b + 1, b + 1 + n) - b - 1;

  build(root[0], 1, q);

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

     p = lower_bound(b + 1, b + 1 + q, a[i]) - b;

      root[i] = change(root[i - 1], 1, q);

  }

  while(m--) {

     cin >> l >> r >> k;

     cout << b[query(root[l - 1], root[r], 1, q, k)] << "\n";

  }

  return 0;

}

 

2.6 LCA

/*

 *倍增法求LCA

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int head[N], cnt;

struct node {

  int to, nex;

} e[N << 1];

void add_edge(int u, int v) {

  e[++cnt].to = v;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

int dep[N], f[N][30], clg[N];

void dfs(int u, int fa) {

  f[u][0] = fa;

  dep[u] = dep[fa] + 1;

  for(int i = 1; i <= clg[dep[u]]; ++i) {

     f[u][i] = f[f[u][i - 1]][i - 1];

  }

  for(int i = head[u]; i; i = e[i].nex) {

     if(e[i].to != fa) dfs(e[i].to, u);

  }

}

int lca(int x, int y) {

  if(dep[x] < dep[y]) swap(x, y);

  while(dep[x] > dep[y]) x = f[x][clg[dep[x] - dep[y]] - 1];

  if(x == y) return x;

  for(int i = clg[dep[x]] - 1; i >= 0; --i) {

     if(f[x][i] != f[y][i]) {

       x = f[x][i];

       y = f[y][i];

     }

  }

  return f[x][0];

}

int n, m, s;

signed main() {

  cin >> n >> m >> s;

  int x, y;

  for(int i = 1; i <= n - 1; ++i) {

     cin >> x >> y;

     add_edge(x, y);

     add_edge(y, x);

  }

  for(int i = 1; i <= n; ++i) clg[i] = clg[i - 1] + (1 << clg[i - 1] == i);

  dfs(s, 0);

  while(m--) {

     cin >> x >> y;

     cout << lca(x, y) << "\n";

  }

  return 0;

}

 

/*

 *树上任意两点距离

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 4e4 + 100;

int cnt, head[N];

struct node {

  int to, nex, w;

} e[N << 1];

void add_edge(int u, int v, int w) {

  e[++cnt].to = v;

  e[cnt].w = w;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

int dep[N], clg[N], f[N][30], dis[N];

void dfs(int u, int fa) {

  f[u][0] = fa;

  dep[u] = dep[fa] + 1;

  for(int i = 1; i <= clg[dep[u]]; ++i) {

     f[u][i] = f[f[u][i - 1]][i - 1];

  }

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v != fa) {

       dis[v] = dis[u] + e[i].w;

       dfs(v, u);

     }

  }

}

int lca(int x, int y) {

  if(dep[x] < dep[y]) swap(x, y);

  while(dep[x] > dep[y]) x = f[x][clg[dep[x] - dep[y]] - 1];

  if(x == y) return x;

  for(int i = clg[dep[x]] - 1; i >= 0; --i) {

     if(f[x][i] != f[y][i]) {

       x = f[x][i];

       y = f[y][i];

     }

  }

  return f[x][0];

}

//公式

int cal_dis(int u, int v) {

  return dis[u] + dis[v] - 2 * dis[lca(u, v)];

}

int n, q, u, v, w;

signed main() {

  for(int i = 1; i < N; ++i) clg[i] = clg[i - 1] + (1 << clg[i - 1] == i);

  int t;

  cin >> t;

  while(t--) {

     cnt = 0;

     memset(head, -1, sizeof head);

     dis[1] = dep[1] = 0;

     cin >> n >> q;

     for(int i = 1; i <= n - 1; ++i) {

       cin >> u >> v >> w;

       add_edge(u, v, w);

       add_edge(v, u, w);

     }

     dfs(1, 0);

     while(q-- && cin >> u >> v) cout << cal_dis(u, v) << "\n";

  }

  return 0;

}

 

2.7莫队

/*

 *询问[l, r]之间有多少个不同的数字

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m;

int a[N], pos[N], ans[N], cnt;

map<int, int> mp;

struct qnode {

  int l, r, id;

} q[N];

void add(int n) {

  if(mp[a[n]]) mp[a[n]]++;

  else {

     mp[a[n]] = 1;

     cnt++;

  }

}

void sub(int n) {

  mp[a[n]]--;

  if(mp[a[n]] == 0) cnt--;

}

signed main() {

  ios::sync_with_stdio(false), cin.tie(0);

  cin >> n;

  int siz = sqrt(n);

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

     cin >> a[i];

     pos[i] = i / siz;

  }

  cin >> m;

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

     cin >> q[i].l >> q[i].r;

     q[i].id = i;

  }

  sort(q + 1, q + 1 + m, [](qnode x, qnode y) {

     return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];

  });

  int l = 1, r = 0;

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

     while(q[i].l < l) add(--l);

     while(q[i].r > r) add(++r);

     while(q[i].l > l) sub(l++);

     while(q[i].r < r) sub(r--);

     ans[q[i].id] = cnt;

  }

  for(int i = 1; i <= m; ++i) cout << ans[i] << "\n";

  return 0;

}

 

/*

 *离线区间查询mex

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 100;

int n, m, a[N], mp[N];

int val[N], cnt[N], L[N], R[N], pos[N], tot;

int ok[N];

struct qnode {

  int l, r, id;

} q[N];

bool cmp(qnode& a, qnode& b) {

  return (pos[a.l] == pos[b.l]) ? a.r < b.r : pos[a.l] < pos[b.l];

}

int Q() {

  int idx = 1;

  while(val[idx] == R[idx] - L[idx] + 1) idx++;

  for(int i = L[idx]; i <= R[idx]; ++i) if(!cnt[i]) return i;

}

void add(int x) {

  if(cnt[x] == 0) val[pos[x]]++;

  cnt[x]++;

}

void sub(int x) {

  if(cnt[x] == 1) val[pos[x]]--;

  cnt[x]--;

}

signed main() {

  read(n), read(m);

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

     read(a[i]);

     if(a[i] > n) a[i] = n + 1;

  }

  int siz = sqrt(n);

  for(int i = 0; i <= n; ++i) pos[i] = i / siz + 1;

  for(int i = 0; i <= n; i += siz) {

     L[++tot] = i, R[tot] = i + siz - 1;

  }

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

     read(q[i].l), read(q[i].r);

     q[i].id = i;

  }

  sort(q + 1, q + 1 + m, cmp);

  int l = 1, r = 0;

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

     while(l < q[i].l) sub(a[l++]);

     while(l > q[i].l) add(a[--l]);

     while(r > q[i].r) sub(a[r--]);

     while(r < q[i].r) add(a[++r]);

     ok[q[i].id] = Q();

  }

  for(int i = 1; i <= m; ++i) printf("%d\n", ok[i]);

  return 0;

}

 

/*

 *带修莫队

 *询问[L, R]多少种不同颜色

 *修改某个位置的颜色

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, ans;

int a[N], ok[N], mp[N];

struct qnode {

  int l, r, pre, id, bkl, bkr;

} q[N];

int qnum, cnum;

struct cnode {

  int pos, val;

} c[N];

void change(int now, int i) {

  if(c[now].pos >= q[i].l && c[now].pos <= q[i].r) {

     if(--mp[a[c[now].pos]] == 0) ans--;

      if(++mp[c[now].val] == 1) ans++;

  }

  swap(c[now].val, a[c[now].pos]);

}

void add(int x) {

  if(++mp[x] == 1) ans++;

}

void sub(int x) {

  if(--mp[x] == 0) ans--;

}

inline bool cmp(register qnode a, register qnode b) {

  return a.bkl != b.bkl ? a.bkl < b.bkl : (a.bkr != b.bkr ? a.bkr < b.bkr : a.pre < b.pre);

}

void moqueue() {

  int l = 1, r = 0, now = 0;

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

     while(l < q[i].l) sub(a[l++]);

     while(l > q[i].l) add(a[--l]);

     while(r < q[i].r) add(a[++r]);

     while(r > q[i].r) sub(a[r--]);

     while(now < q[i].pre) now++, change(now, i);

     while(now > q[i].pre) change(now, i), now--;

     ok[q[i].id] = ans;

  }

  for(int i = 1; i <= qnum; ++i) cout << ok[i] << "\n";

}

signed main() {

  read(n), read(m);

  int siz = pow(n, 2.0 / 3.0);

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

     read(a[i]);

  }

  char op[N];

  while(m--) {

     scanf("%s", op);

     if(*op == 'Q') {

       read(q[++qnum].l);

       read(q[qnum].r);

       q[qnum].pre = cnum;

       q[qnum].id = qnum;

       q[qnum].bkl = (q[qnum].l - 1) / siz + 1;

       q[qnum].bkr = (q[qnum].r - 1) / siz + 1;

     } else {

       read(c[++cnum].pos);

       read(c[cnum].val);

     }

  }

  sort(q + 1, q + 1 + qnum, cmp);

  moqueue();

  return 0;

}

 

2.8树链剖分（重链）

/*

 *1 x y z 树从 x 到 y 结点最短路径上所有节点的值都加上 z

 *2 x y 求树从 x 到 y 结点最短路径上所有节点的值之和

 *3 x z 表示将以 x 为根节点的子树内所有节点值都加上 z

 *4 x 表示求以 x 为根节点的子树内所有节点值之和

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int cnt, head[N];

struct edge {

  int to, nex;

} e[N << 1];

inline void add_edge(int u, int v) {

  e[++cnt].to = v;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

int n, m, root, mod;

int a[N], w[N]; //初始点权, dfs序后的点权

int dfn[N], siz[N], son[N], f[N], top[N], dep[N], tim; //时间戳 子树大小 重儿子 父亲 当前链顶端节点

struct segment_tree {

  struct tnode {

     int l, r, sum, lazy;

  };

  tnode t[N << 2];

  inline void push_down(int root) {

     if(t[root].lazy != 0) {

       t[root].sum += (t[root].lazy * (t[root].r - t[root].l + 1)) % mod;

       if(t[root].l != t[root].r) {

         int ch = root << 1;

         t[ch].lazy += t[root].lazy;

         t[ch + 1].lazy += t[root].lazy;

       }

       t[root].lazy = 0;

     }

  }

  inline void push_up(int root) {

     int ch = root << 1;

     push_down(ch);

     push_down(ch + 1);

     t[root].sum = (t[ch].sum + t[ch + 1].sum) % mod;

  }

  inline void build(int root, int l, int r) {

     t[root].l = l, t[root].r = r;

     if(l != r) {

       int ch = root << 1;

       int mid = l + r >> 1;

       build(ch, l, mid);

       build(ch + 1, mid + 1, r);

       push_up(root);

     } else {

       t[root].lazy = 0;

       t[root].sum = w[l] % mod;

     }

  }

  void change(int root, int l, int r, int k) {

     push_down(root);

     if(t[root].l >= l && t[root].r <= r) {

       t[root].lazy += k;

       return;

     }

     int ch = root << 1;

     int mid = t[root].l + t[root].r >> 1;

     if(r <= mid) change(ch, l, r, k);

     else if(l > mid) change(ch + 1, l, r, k);

     else change(ch, l, mid, k), change(ch + 1, mid + 1, r, k);

     push_up(root);

  }

  int query(int root, int l, int r) {

     push_down(root);

     if(t[root].l >= l && t[root].r <= r) {

       return t[root].sum % mod;

     }

     int ch = root << 1;

     int mid = t[root].l + t[root].r >> 1;

     if(r <= mid) return query(ch, l, r) % mod;

     else if(l > mid) return query(ch + 1, l, r) % mod;

     else return (query(ch, l, mid) % mod + query(ch + 1, mid + 1, r) % mod) % mod;

  }

} st;

void dfs1(int u, int fa) {

  f[u] = fa;

  dep[u] = dep[fa] + 1;

  siz[u] = 1;

  int maxsize = -1;

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v == fa) continue;

     dfs1(v, u);

     siz[u] += siz[v];

     if(siz[v] > maxsize) {

       maxsize = siz[v];

       son[u] = v;

     }

  }

}

void dfs2(int u, int t) {

  dfn[u] = ++tim;

  top[u] = t;

  w[tim] = a[u];

  if(!son[u]) return;

  dfs2(son[u], t);

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v == f[u] || v == son[u]) continue;

     dfs2(v, v);

  }

}

inline void op1(int x, int y, int k) {

  k %= mod;

  while(top[x] != top[y]) {

     if(dep[top[x]] < dep[top[y]]) swap(x, y);

     st.change(1, dfn[top[x]], dfn[x], k);

     x = f[top[x]];

  }

  if(dep[x] > dep[y]) swap(x, y);

  st.change(1, dfn[x], dfn[y], k);

}

inline int op2(int x, int y) {

  int cnt = 0;

  while(top[x] != top[y]) {

     if(dep[top[x]] < dep[top[y]]) swap(x, y);

     cnt += st.query(1, dfn[top[x]], dfn[x]);

     x = f[top[x]];

  }

  if(dep[x] > dep[y]) swap(x, y);

  cnt += st.query(1, dfn[x], dfn[y]) % mod;

  return cnt % mod;

}

inline void op3(int x, int k) {

  st.change(1, dfn[x], dfn[x] + siz[x] - 1, k);

}

inline int op4(int x) {

  return st.query(1, dfn[x], dfn[x] + siz[x] - 1);

}

 

signed main() {

  ios::sync_with_stdio(false), cin.tie(0);

  cin >> n >> m >> root >> mod;

  for(int i = 1; i <= n; ++i) cin >> a[i];

  int x, y;

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

     cin >> x >> y;

     add_edge(x, y);

     add_edge(y, x);

  }

  dfs1(root, root);

  dfs2(root, root);

  st.build(1, 1, n);

  while(m--) {

     int op, z;

     cin >> op;

     if(op == 1) {

       cin >> x >> y >> z;

       op1(x, y, z);

     } else if(op == 2) {

       cin >> x >> y;

       cout << op2(x, y) << "\n";

     } else if(op == 3) {

       cin >> x >> y;

       op3(x, y);

     } else {

       cin >> x;

       cout << op4(x) << "\n";

     }

  }

  return 0;

}

 

2.9 dsu on tree

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int cnt, head[N];

struct E {

  int to, nex;

} e[N << 1];

inline void add_edge(int u, int v) {

  e[++cnt].to = v, e[cnt].nex = head[u], head[u] = cnt;

}

int siz[N], son[N];

void dfs(int u, int fa) {

  siz[u] = 1;

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v == fa) continue;

     dfs(v, u);

     siz[u] += siz[v];

     if(siz[v] > siz[son[u]]) son[u] = v;

  }

}

int a[N], ok[N], cot[N], sum;

void cal(int u, int fa, int val) { //统计函数

  cot[a[u]] += val;

  if(val == 1 && cot[a[u]] == 1) sum++;

  if(val == -1 && cot[a[u]] == 0) sum--;

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v != fa) cal(v, u, val);

  }

}

void dsu(int u, int fa, bool flag) {

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(v != fa && v != son[u]) dsu(v, u, true);//往轻儿子方向走

  }

  if(son[u] != 0) dsu(son[u], u, false);//往重儿子方向走

  cot[a[u]]++;

  if(cot[a[u]] == 1) sum++;//计算自己的贡献

  for(int i = head[u]; i; i = e[i].nex) { //计算轻儿子的贡献

     int v = e[i].to;

     if(v != fa && v != son[u]) cal(v, u, 1);

  }

  ok[u] = sum;

  if(flag) cal(u, fa, -1);//释放掉cot数组 清空其他信息

}

int n, m;

signed main() {

  ios::sync_with_stdio(false), cin.tie(0);

  cin >> n;

  for(int i = 1, u, v; i < n; ++i) {

     cin >> u >> v;

     add_edge(u, v), add_edge(v, u);

  }

  for(int i = 1; i <= n; ++i) cin >> a[i];

  dfs(1, 0);

  dsu(1, 0, 0);

  cin >> m;

  int x;

  while(m-- && cin >> x) cout << ok[x] << "\n";

  return 0;

}

 

2.10 字典树

struct {

   int cnt, son[26];

}c[N];

int idx;

inline void insertt(string& s) {

   int p = 0;

   for(auto x : s) {

       x -= 'a';

       if(!c[p].son[x]) c[p].son[x] = ++idx;

       p = c[p].son[x];

       ++c[p].cnt;

   }

}

 

inline int query(string& s) {

   int p = 0, ok = 0;

   for(auto x : s) {

       x -= 'a';

       if(!c[p].son[x]) return 0;

       p = c[p].son[x];

   }

   return c[p].cnt;

}

 

3. 数论

 

3.1质数

/*

 *质数：严格大于1 的整数，只有自己和1两个因子。

 *算术基本定理：任何一个大于 1的自然数N，N不为质数，可以唯一被分解有

 *限个质数的乘积：N = p1^a1 * p2^a2 * .. * pn^an

 *且最多有一个大于sqrt(n)的质因子

 *试除法判断质数：o(sqrt(n))

 */

bool is_prime(int x) {

  if (x < 2) return false;

  for (int i = 2; i <= x / i; i ++ )

     if (x % i == 0)

       return false;

  return true;

}

/*

 *分解质因数

 */

void divide(int x) {

  for (int i = 2; i <= x / i; i ++ )

     if (x % i == 0) {

       int s = 0;

       while (x % i == 0) x /= i, s++;

       cout << i << ' ' << s << endl;

     }

  if (x > 1) cout << x << ' ' << 1 << endl;

  cout << endl;

}

/*

 ***线性筛法**

 */

int primes[N], cnt;

bool st[N];

void get_primes(int n) {

  for (int i = 2; i <= n; ++i) {

     if (!st[i]) primes[cnt++] = i;

     for (int j = 0; primes[j] <= n / i; ++j) {

       st[primes[j] * i] = true;

       if (i % primes[j] == 0) break;

     }

  }

}

 

3.2约数

/*

 *一个数的约数集合

 */

vector<int> get_divisors(int x) {

  vector<int> res;

  for (int i = 1; i <= x / i; ++i)

     if (x % i == 0) {

       res.push_back(i);

       if (i != x / i) res.push_back(x / i);

     }

  sort(res.begin(), res.end());

  return res;

}

/*

 *约数个数：

 *由算术基本定理、组合数原理

 *N = p1^a1 + p2^a2 + .. + pn^an

 *设K为约数，sum为约数个数

 *K = p1^b1 * p2^b2 * ... * pn ^bn (0 <= bi <= ai)

 *sum = (a1 + 1) * (a2 + 1) * .. * (an + 1)

 */

//多个数相乘得到的约数个数，统计指数最后再计算即可

unordered_map<int, int> primes;

  while (n--) {

     int x;

     cin >> x;

     for (int i = 2; i <= x / i; ++i)

       while (x % i == 0) {

         x /= i;

         primes[i]++;

       }

     if (x > 1) primes[x]++;

  }

  LL res = 1;

  for (auto p : primes) res = res * (p.second + 1) % mod;

cout << res << endl;

/*

 *约数之和：

 *(p1^0 + p1^1 + ... + p1^a1) * (p2^0 + p2^1 + ... + p2^a2) * ...

 *(pn^0 + pn^1 + ... + pn^an)

 */

unordered_map<int, int> primes;

  while (n--) {

     int x;

     cin >> x;

     for (int i = 2; i <= x / i; i++)

       while (x % i == 0) {

         x /= i;

         primes[i]++;

       }

     if (x > 1) primes[x]++;

  }

  LL res = 1;

  for (auto p : primes) {

     LL a = p.first, b = p.second;

     LL t = 1;

     while (b--) t = (t * a + 1) % mod;

     res = res * t % mod;

  }

cout << res << endl;

 

3.3组合数

/*

 *打表方式组合数，数据范围较小

 *c[i][j] 代表i个里面选j个

 */

int c[N][N]; //c[i][j] 代表i个里面选j个

inline void init(){

  for(int i = 0; i < N; ++i)

  for(int j = 0; j <= i; ++j){

     if(!j) c[i][j] = 1;

     else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

  }

}

 

/*

 *数据范围预处理on到1e7，计算o1

 */

const int N = 2e5 + 10;

const int mod = 1e9 + 7;

int fac[N], inv[N];

int qk(int a, int b) {

  int ans = 1;

  while(b) {

     if(b & 1) ans = ans * a % mod;

     a = a * a % mod;

     b >>= 1;

  }

  return ans;

}

void init() {

  fac[0] = 1;

  for(int i = 1; i < N; ++i) fac[i] = fac[i - 1] * i % mod;

  inv[N - 1] = qk(fac[N - 1], mod - 2);

  for(int i = N - 2; i >= 0; --i) inv[i] = inv[i + 1] * (i + 1) % mod;

}

int C(int a, int b){

  if(b < 0 || b > a) return 0;

  return fac[a] * inv[a - b] % mod * inv[b] % mod; //组合数定义

}

 

/*

 *卢卡斯定理 适合n， m1e18级别， p1e5

 *时间复杂度20*N*log(p)N*lgP

 */

int n, m, p;

int qk(int a, int b, int mod) {

  int res = 1;

  while(b) {

     if(b & 1) res = res * a % mod;

     a = a * a % mod;

     b >>= 1;

  }

  return res;

}

int C(int a, int b, int p) {

  int res = 1;

  for(int i = 1, j = a; i <= b; i++, j--) {

     res = res * j % p;

     res = res * qk(i, p - 2, p) % p;

  }

  return res;

}

int lucas(int a, int b, int p) {

  if(a < p && b < p) return C(a, b, p);

  return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;

}

 

3.3欧拉函数

/*

f(n) : 1 - n 中与n互质的个数(gcd(a, b) = 1)

n = p1^a1.p2^a2...pn^an

f(n) = n * (1 - 1/p1)(1 - 1/p2)...(1 - 1/pn)

*/

int div_ola(int x) {

  int res = x;

  for(int i = 2; i <= x / i; ++i) {

     if(x % i == 0) {

       res = res / i * (i - 1);

       while(x % i == 0) x /= i;

     }

  }

  if(x > 1) res = res / x * (x - 1);

  return res;

}

/*

 *筛法

 */

const int N = 1e5 + 10;

int cnt, p[N], st[N], e[N];

void div_ola(int n) {

  e[1] = 1;

  for(int i = 2; i <= n; ++i) {

     if(!st[i]) {

       p[cnt++] = i;

       e[i] = i - 1;

     }

     for(int j = 0; p[j] <= n / i; ++j) {

       int t = p[j] * i;

       st[t] = true;

       if(i % p[j] == 0) {

         e[t] = e[i] * p[j];

         break;

       }

       e[t] = e[i] * (p[j] - 1);

     }

  }

}

signed main() {

  div_ola(100);

  for(int i = 1; i <= 100; ++i) cout << e[i] << " ";

  return 0;

}

 

3.4SG函数

/*

 *打表版本

 */

int sg[N], vis[N], f[N];

void cal_sg(int n) {

  for(int i = 1; i <= n; ++i) { //从1开始 sg[0] = 0

     memset(vis, 0, sizeof vis); //清空后继状态

     for(int j = 1; f[j] <= i; ++j) { //f[i]保证有序且预处理的最大权值>=n

       vis[sg[i - f[j]]] = 1;

     }

     for(int j = 0; ; ++j) if(!vis[j]) {

         sg[i] = j;

         break;

       }

  }

}

 

/*

 *dfs版本 用于不好打表的情况

 */

int sg[N][N], f[N];

int dfs(int x) {

  if(sg[x]) return sg[x];

  int vis[N] = {0};

  for(int i = 0; i < n; ++i) { //种类数

     if(x >= f[i]) { //如果合法

       dfs(x - f[i]);

       vis[sg[x - f[i]] = 1

     }

  }

  for(int i = 0; ; ++i) if(!vis[i]) {

       return sg[x] = i;

     }

}

 

 

4. 动态规划

4.1背包问题

4.1.1 01背包

/*

 *01背包基础写法

 */

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

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

     if(j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);

     else f[i][j] = f[i - 1][j];

  }

}

/*

 *回滚优化 优化空间

 */

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

  for(int j = m; j >= v[i]; --j) { //一定是从后往前跑

     f[j] = max(f[j], f[j - v[i]] + w[i]);

  }

}

/*

 *有些01变形不好使用回滚，再加个辅助数组帮助优化空间

 */

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

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

     if(j < v[i]) f[j][0] = f[j][1];

     else f[j][0] = max(f[j][1], f[j - v[i]][1] + w[i]);

  }

  for(int j = 1; j <= m; ++j) f[j][1] = f[j][0];

}

cout << f[m][0];

/*

 *求刚好装满的最大值，初始化均为负值，f[0] = 0

 */

for(int i = 0; i < mx; i++) f[i] = -inf;//一个极小负值

f[0] = 0;

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

  cin >> v[i] >> w[i];

}

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

  for (int j = m; j >= v[i]; j--) {

     f[j] = max(f[j], f[j - v[i]] + w[i]);

     if (f[j] < 0) f[j] = -inf;

  }

}

if(f[m] > 0) cout << f[m];

else    cout << "no";

/*

 *求n个物品，具有重量和价值，价值max，不超过背包容量的方案总数。

 */

cin >> n >> m;

for(int i = 0; i <= m; ++i) cnt[i] = 1;

for(int i = 1; i <= n; ++i) 

  cin >> v >> w;

  for(int j = m; j >= v; --j) {

     int val = f[j - v] + w;

     if(val > f[j]) { //当前值更大，替换最优方案数

       f[j] = val;

       cnt[j] = cnt[j - v];

     } else if(val == f[j]) cnt[j] = (cnt[j] + cnt[j - v]) % mod;

     //出现了一个相同的最大值，叠加

  }

}

cout << cnt[m];

/*

 *n个整数，从中任意选出若干个组成m的方案数

 */

f[0] = 1;

int x;

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

  cin >> x;

  for(int j = m; j >= x; --j) f[j] += f[j - x];

}

cout << f[m];

 

4.1.2完全背包

/*

 *物品可重复选取

 */

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

  cin >> v >> w;

  for(int j = v; j <= m; ++j) { //正着跑

     f[j] = max(f[j], f[j - v] + w);

  }

}

cout << f[m];

/*

 *方案数

 */

f[0] = 1;

int x;

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

  cin >> x;

  for(int j = x; j <=m; ++j) f[j] += f[j - x];

}

cout << f[m];

 

4.1.3多重背包

/*

 *每种物品数量不定，二进制枚举优化

 */

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

  cin >> a >> b >> s;

  int k = 1;

  while(s - k >= 0) {

     s -= k;

     v[++cnt] = a * k;

     w[cnt] = b * k;

     k <<= 1;

  }

  if(s > 0) {

     v[++cnt] = a * s;

     w[cnt] = b * s;

  }

}

n = cnt;

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

  for(int j = m; j >= v[i]; --j) {

     f[j] = max(f[j], f[j - v[i]] + w[i]);

  }

}

cout << f[m];

 

 

4.1.4分组背包

/*

 *每组物品只能选一种

 */

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

  cin >> s[i];

  for(int j = 1; j <= s[i]; ++j) cin >> v[i][j] >> w[i][j];

}

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

  for(int j = m; j > 0; --j) {

     for(int k = 1; k <= s[i]; ++k) {

       if(v[i][k] <= j)

         f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);

     }

  }

}

cout << f[m];

 

4.2数位DP

int dfs(int pos, bool limit, bool lead)

{

   if (pos == cnt)

       return 1;

   int ans = 0;

   if (dp != -1)return dp;

   for (int v = 0; v <= (limit ? A[pos] : 9); v++) // 根据是否limit决定循环上界

   {

       ans += dfs(pos + 1, limit && v == A[pos], lead && v == 0);

   }

   return dp = ans;

}

int f(int x) {

   if (x == 0)return 0;

   cnt = 0;

   memset(A, 0, sizeof(A));

   memset(dp, -1, sizeof(dp)); // 初始化dp数组为-1

   while (x)

       A[cnt++] = x % 10, x /= 10;

   reverse(A, A + cnt);

   return dfs(0, true, true); 

}

 

4.3区间DP

f[i][j]: [i, j]区间的dp值

len = (n << 1)

rep(L, 2, n) { //长度

  for(int i = 1; i <= len - L + 1; ++i) { //起点

     int j = i + L - 1; //终点

     for(int k = i; k < j; ++k) { //枚举中点

       //更新

     }

     //更新

  }

}

 

5. 图论

5.1最短路

/*

 *弗洛伊德多源点最短路

 */

RE(i, 1, n)

RE(j, 1, n) {

  g[i][j] = i == j ? 0 : INF;

}

RE(k, 1, n) 

RE(i, 1, n) 

RE(j, 1, n) {

  g[i][j] = min(g[i][j], g[i][k] + g[k][j]);

}

/**\

单源最短路

输入: n m s t 接下来m行 u, v, w表示u -> v 有一条权值为w的无向边

input:

3 3 1 2

1 2 3

2 3 4

1 3 5

output:

3

\**/

\#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

struct node {

  int to, w, next;

} e[N << 1];

int cnt = 0, head[N];

inline void add_edge(int u, int v, int w) {

  e[++cnt].to = v;

  e[cnt].w = w;

  e[cnt].next = head[u];

  head[u] = cnt;

}

inline void init() {

  cnt = 0;

  memset(head, -1, sizeof head);

}

int n, m, s, t;

struct v {

  int x, dis;

  bool operator < (const v& a) const {

     return dis > a.dis; //stl默认大顶堆

  }

};

int dis[N];

bool vis[N];

/**\

dijstra

1、从源点开始每次选取一个离点集距离最近的点t 添加到集合中

2、利用t点对集合中的点进行松弛操作，进行更新

3、使用堆进行1找点的操作降低时间复杂度

4、不能在有负边权的图中使用

\**/

const int inf = 2147483647;

int cnt, head[N];

struct E {

     int to, nex, w;

}e[N << 1];

void add(int u, int v, int w) {

     e[++cnt].nex = head[u], e[cnt].w = w, e[cnt].to = v, head[u] = cnt;

}

int n, m, s;

int dis[N];

bool vis[N];

void dst(int s) {

     for(int i = 1; i <= n; ++i) dis[i] = inf;

     dis[s] = 0;

     using pii = pair<int, int>;

     priority_queue<pii, vector<pii >, greater<pii >> q;

     q.push({0, s});

     while(q.size()) {

        int u = q.top().second;

        q.pop();

        if(vis[u]) continue;

        vis[u] = 1;

        for(int i = head[u]; i; i = e[i].nex) {

            int v = e[i].to;

            if(dis[v] > dis[u] + e[i].w) {

               dis[v] = dis[u] + e[i].w;

               q.push({dis[v], v});

            }

        }

     }

     for(int i = 1; i <= n; ++i) cout << dis[i] << " ";

}

/**\

spfa算法思路:

1、每次迭代,取出队头点v,依次枚举从v出发的边,v->u,设边的长度为w

判断dis[v] + w 是否小于dis[u], 小于则更新值,

2、由于s-u的距离变短了,有可能u能改变其他点,使用vis数组判断是否在队列,没有则放入

3、若一个点的入队次数超过n,则存在负环

\**/

queue<int> q1;

inline void spfa(int s, int t) {

  memset(dis, 0x3f, sizeof dis);

  memset(vis, 0, sizeof vis);

  dis[s] = 0;

  vis[s] = 1;

  q1.push(s);

  while(!q1.empty()) {

     int x = q1.front();

     q1.pop();

     vis[x] = 0;

     for(int i = head[x]; i != -1; i = e[i].next) {

       int y = e[i].to;

       if(dis[y] > dis[x] + e[i].w) {

         dis[y] = dis[x] + e[i].w;

         if(!vis[y]) {

           q1.push(y);

           vis[y] = 1;

         }

       }

     }

  }

  if(dis[t] >= 0x3f3f3f3f) cout << -1;

  else cout << dis[t];

}

inline void solve() {

  init();

  cin >> n >> m >> s >> t;

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

     int x, y, z;

     cin >> x >> y >> z;

     add_edge(x, y, z);

     add_edge(y, x, z);

  }

  //dijstra(s, t);

  spfa(s, t);

}

signed main() {

  solve();

  return 0;

}

 

5.2拓扑排序

/**\

拓扑排序:每次找到入度为0的点删掉

判断一个有向图中是否有环，无环的图都能进行拓扑排序

\**/

const int N = 1e5 + 10;

int inr[N]; //记录入度的数组

struct node {

  int t, next;

} e[N << 1];

int cnt = 0;

int head[N];

int n, m;

void add_edge(int x, int y) {

  e[++cnt].t = y;

  e[cnt].next = head[x];

  head[x] = cnt;

}

void topo() {

  queue<int> q;

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

     if(inr[i] == 0) q.push(i);

  }

  int idx = 0, ans[N];

  while(!q.empty()) {

     int x = q.front();

      ans[++idx] = x;

     q.pop();

     for(int i = head[x]; i != -1; i = e[i].next) {

       inr[e[i].t]--;

       if(inr[e[i].t] == 0) q.push(e[i].t);

     }

  }

  if(idx != n) cout << -1;

  else {

     for(int i = 1; i <= idx; ++i) cout << ans[i] << " ";

  }

}

signed main() {

  scanf("%d %d", &n, &m);

  memset(head, -1, sizeof head);

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

     int x, y;

     scanf("%d %d", &x, &y);

     inr[y]++;

     add_edge(x, y);

  }

  topo();

  return 0;

}

 

 

 

5.3二分图

/*

 *染色法判断二分图

 *二分图性质：至少两个点，回路长度均为偶数

 */

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int cnt, head[N];

struct edge {

  int to, nex;

} e[N << 1];

inline void add_edge(int u, int v) {

  e[++cnt].to = v;

  e[cnt].nex = head[u];

  head[u] = cnt;

}

int n, m, col[N];

vector<int> v1, v2;

bool dfs(int u) {

  for(int i = head[u]; i; i = e[i].nex) {

     int v = e[i].to;

     if(!col[v]) {

       col[v] = 3 - col[u];

       if(!dfs(v)) return false;

     }

     if(col[v] == col[u]) return false;

  }

  return true;

}

signed main() {

  ios::sync_with_stdio(false), cin.tie(0);

  cin >> n >> m;

  int u, v;

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

     cin >> u >> v;

     add_edge(u, v);

     add_edge(v, u);

  }

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

     if(col[i]) continue;

     if(!col[i]) {

       col[i] = 1;

       if(!dfs(i)) {

          cout << "-1\n";

         return 0;

       }

     }

  }

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

     if(col[i] == 1) v1.push_back(i);

     else v2.push_back(i);

  }

  cout << v1.size() << "\n";

  for(int i = 0; i < v1.size(); ++i) cout << v1[i] << " \n"[i == v1.size() - 1];

  cout << v2.size() << "\n";

  for(int i = 0; i < v2.size(); ++i) cout << v2[i] << " \n"[i == v2.size() - 1];

  return 0;

}

 

/**\

https://www.luogu.com.cn/problem/P3386

二分图最大匹配匈牙利算法:

假设左部是男孩,右部是女孩

1、对于一个男孩子,如果他喜欢女孩y,女孩y没有配偶,就在一起

2、如果y有配偶了,x还是想去挖一手墙脚,y也不是什么好女人,

如果y发现他的配偶z能换一个对象(这里dfs),y就主动抛弃z(z能换一个对象),跟x在一起

这样就多了一对配偶

\**/

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, e;//左部 右部 边数

int g[N][N], vis[N], link[N];

//dfs搜索的起点是左集合, link[]代表右集合

int dfs(int x) {

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

     if(!g[x][i] || vis[i]) continue; //如果没有边 或者已经被邀请过了 就跳过

     vis[i] = 1;

     if(link[i] == 0 || dfs(link[i])) { //如果没有配偶,或者能让自己的配偶找到配偶(找到增广路),就在一起

       link[i] = x;

       return 1;

     }

  }

  return 0;

}

signed main() {

  int ok = 0;

  cin >> n >> m >> e;

  for(int i = 1, x, y; i <= e; ++i) {

      cin >> x >> y;

     g[x][y] = 1;

  }

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

     memset(vis, 0, sizeof vis);

     if(dfs(i)) ok++;//如果能匹配成功,边数++

  }

  printf("%lld\n", ok);

  return 0;

}

 

/*

 *二分图最大权完美匹配

 */

#include<bits/stdc++.h>

using namespace std;

int n, m; //左右点均为n m条边

long long edge[505][505];

int matched[505];//记录右部点所匹配的左部点

int visy[505];

int lx[505], ly[505]; //lx表示左部点的顶标，ly表示右部点的顶标

int pre[505];

long long slack[505];

void bfs(int want_match) {

  int now, new_match = 0;

  int x = 0; //0点初始化

  memset(pre, 0, sizeof pre); //重新建立交错树（因为每一次要重新找增广路）

  memset(slack, 0x3f, sizeof slack); //初始化松弛量

  matched[x] = want_match; //初始化0点匹配到了u这个左部点

  do {

     now = matched[x]; //找到当前寻找匹配的左部点

     long long delta = 1e18; //delta记录寻找的增广路路径的松弛量

     visy[x] = true;

     //标记本轮已经在这个点找过增广路，和匈牙利算法中vis数组同理

     for(register int i = 1; i <= n; i++) { //枚举右部点

       if(!visy[i]) { //找到了一个还没有尝试找增广路的右部点

         if(slack[i] > lx[now] + ly[i] - edge[now][i]) {

           //找到了一个匹配点

           //优化DFS进行的find操作

           slack[i] = lx[now] + ly[i] - edge[now][i];

           pre[i] = x; //记录交错树(BFS对DFS的优化)

         }

         if(slack[i] < delta) {

           delta = slack[i]; //更新delta

           new_match = i;

         }

       }

     }

     for(register int i = 0; i <= n; i++) { //因为初始化的是0，所以说必须从0开始修改顶标

       if(visy[i]) {

         lx[matched[i]] -= delta; //i点匹配到的左部点的顶标减去delta

         ly[i] += delta; //i点的顶标加上delta

          //和DFS版本同理

       } else slack[i] -= delta; //进行松弛操作

     }

     x = new_match; //下一个访问的左部点即刚才取出的右部点的匹配点

     //此处x指代找到的右部点

  } while(matched[x]);

  while(x) matched[x] = matched[pre[x]], x = pre[x]; //交错树还原操作

}

long long KM() {

  memset(matched, 0, sizeof matched);

  memset(lx, 0, sizeof lx);

  memset(ly, 0, sizeof ly);

  for(register int i = 1; i <= n; i++) {

     memset(visy, 0, sizeof visy); //每次重新进行增广

     bfs(i);

  }

  long long ans = 0;

  for(register int i = 1; i <= n; i++)

     ans += (long long)edge[matched[i]][i]; //正常的统计答案

  return ans;

}

int main() {

  n = read(), m = read();

  memset(edge, -0x3f, sizeof edge); //赋初值为负无穷，因为题目边权有负数

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

     int u = read(), v = read(), w = read();

     edge[u][v] = max(edge[u][v], (long long)w);

  }

  printf("%lld\n", KM());

  for(register int i = 1; i <= n; i++)

     printf("%d ", matched[i]);

   return 0;

}

 

5.4网络流

5.4.1最大流dinic

#include <bits/stdc++.h>

using namespace std;

const int N = 1e4 + 10, M = 2e5 + 10;

int n, m, S, T;

int head[N], ver[M], edge[M], Next[M], idx;

int deep[N], cur[M];

void add(int a, int b, int c) {

  ver[idx] = b, edge[idx] = c, Next[idx] = head[a], head[a] = idx++;

  ver[idx] = a, edge[idx] = 0, Next[idx] = head[b], head[b] = idx++;

}

bool bfs() {

  queue<int> q;

  memset(deep, 0, sizeof deep);

  q.push(S);

  cur[S] = head[S];

  deep[S] = 1;

  while (q.size()) {

     int t = q.front();

     q.pop();

     for (int i = head[t]; i != -1; i = Next[i]) {

       int e = ver[i];

       if (deep[e] == 0 && edge[i]) {

         deep[e] = deep[t] + 1;

         cur[e] = head[e];

         if (e == T)

           return 1;

         q.push(e);

       }

     }

  }

  return 0;

}

int find(int fa, int limit) {

  if (fa == T)

     return limit;

  int flow = 0;

  for (int i = cur[fa]; i != -1 && flow < limit; i = Next[i]) {

     cur[fa] = i;

     int e = ver[i];

     if (deep[e] == deep[fa] + 1 && edge[i]) {

       int t = find(e, min(edge[i], limit - flow));

       if (!t) {

         deep[e] = 0;

         continue;

       }

       edge[i] -= t, edge[i ^ 1] += t, flow += t;

     }

  }

  return flow;

}

 

int dinic() {

  int maxflow = 0, flow;

  while (bfs())

     while (flow = find(S, INT_MAX))

       maxflow += flow;

  return maxflow;

}

int main() {

  cin >> n >> m >> S >> T;

  memset(head, -1, sizeof head);

  while (m--) {

     int a, b, c;

     cin >> a >> b >> c;

     add(a, b, c);

  }

  cout << dinic();

}

 

5.4.2最小费用最大流

#include <bits/stdc++.h>

using namespace std;

const int N = 5e3 + 10, M = 1e5 + 10;

int n, m, S, T;

int head[N], ver[M], edge[M], w[M], Next[M], idx;

int dist[N], pre[N], incf[N];

bool vis[N];

void add(int a, int b, int c, int d) {

  ver[idx] = b, edge[idx] = c, w[idx] = d, Next[idx] = head[a], head[a] = idx++;

  ver[idx] = a, edge[idx] = 0, w[idx] = -d, Next[idx] = head[b], head[b] = idx++;

}

bool spfa() {

  queue<int> q;

  memset(dist, 0x3f, sizeof dist);

  memset(incf, 0, sizeof incf);

  incf[S] = INT_MAX, dist[S] = 0;

  q.push(S);

  while (q.size()) {

     int t = q.front();

     q.pop();

     vis[t] = false;

     for (int i = head[t]; i != -1; i = Next[i]) {

       int e = ver[i];

       if (edge[i] && dist[e] > dist[t] + w[i]) {

         dist[e] = dist[t] + w[i];

         pre[e] = i;

         incf[e] = min(edge[i], incf[t]);

         if (!vis[e]) {

           q.push(e);

           vis[e] = 1;

         }

       }

     }

  }

  return incf[T] > 0;

}

void EK(int &flow, int &cost) {

  flow = cost = 0;

  while (spfa()) {

     int t = incf[T];

     flow += t, cost += t * dist[T];

     for (int i = T; i != S; i = ver[pre[i] ^ 1]) {

       edge[pre[i]] -= t;

       edge[pre[i] ^ 1] += t;

     }

  }

}

signed main() {

  cin >> n >> m >> S >> T;

  memset(head, -1, sizeof head);

  while (m--) {

     int a, b, c, d;

     cin >> a >> b >> c >> d;

     add(a, b, c, d);

  }

  int flow, cost;

  EK(flow, cost);

  cout << flow << " " << cost;

}

 

6. 字符串

长度为n的字符串

1、有n(n+1)/2 +1个子串；

2、非空子串：n（n+1）/2；

3、非空真子串：n（n+1）/2– 1。

6.5哈希

/*

 *双哈希统计多少个相同的字符串 可以利用ull的自动取模

 */

#define ull unsigned long long

const int N = 1e5 + 10;

const int mod = 1e9 + 7;

const int P = 131, PP = 1331;

ull p[N], pp[N], hs1[N], hs2[N];

char s[N];

set<pair<ull, ull> > st;

ull get1(int l, int r) {

  return (hs1[r] - hs1[l - 1] * p[r - l + 1] % mod + mod) % mod;

}

ull get2(int l, int r) {

  return (hs2[r] - hs2[l - 1] * pp[r - l + 1] % mod + mod) % mod;

}

void cal_hash(int l, int r) {

  ull t1 = get1(l, r), t2 = get2(l, r);

  st.insert({t1, t2});

}

signed main() {

  int T;

  scanf("%d", &T);

  while(T-- && scanf("%s", s + 1)) {

     int n = strlen(s + 1);

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

       p[i] = (p[i - 1] * P) % mod;

       pp[i] = (pp[i - 1] * PP) % mod;

       hs1[i] = (hs1[i - 1] * P % mod + s[i]) % mod;

       hs2[i] = (hs2[i - 1] * PP % mod + s[i]) % mod;

     }

     cal_hash(1, n);

  }

  printf("%d\n", st.size());

  return 0;

}

 

/*

 *n,m的矩阵，查询有q个大小a,b的矩阵出现

 */

#define ull unsigned long long

using namespace std;

const int N = 1e3 + 10;

char ch;

ull h[N][N];

ull p[N], pp[N];

unordered_map<ull, int> mp;

ull get(int x1, int y1, int x2, int y2) {

  return h[x2][y2] - h[x2][y1 - 1] * p[y2 - y1 + 1] - h[x1 - 1][y2] * pp[x2 - x1 + 1]

       \+ h[x1 - 1][y1 - 1] * p[y2 - y1 + 1] * pp[x2 - x1 + 1];

}

int n, m, a, b, q;

signed main() {

  cin >> n >> m >> a >> b;

  p[0] = pp[0] = 1;

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

     p[i] = p[i - 1] * 131;

     pp[i] = pp[i - 1] * 233;

  }

  for(int i = 1; i <= n; ++i)

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

       cin >> ch;

       h[i][j] = h[i][j - 1] * 131 + ch;

     }

 

  for(int i = 1; i <= n; ++i)

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

       h[i][j] = h[i][j] + h[i - 1][j] * 233;

     }

  for(int i = 1; i <= n - a + 1; ++i)

     for(int j = 1; j <= m - b + 1; ++j) {

       ull z = get(i, j, i + a - 1, j + b - 1);

       mp[z]++;

     }

  cin >> q;

  while(q--) {

     for(int i = 1; i <= a; ++i)

       for(int j = 1; j <= b; ++j) {

         cin >> ch;

         h[i][j] = h[i][j - 1] * 131 + ch;

       }

     for(int i = 1; i <= a; ++i)

       for(int j = 1; j <= b; ++j) {

         h[i][j] = h[i][j] + h[i - 1][j] * 233;

       }

     cout << (mp[h[a][b]] ? 1 : 0) << endl;

  }

}

 

#include <bits/stdc++.h>

#define int long long 

#define rep(i, a, b) for(int i = a; i <= b; ++i)

 

using namespace std;

const int N = 2e6 + 10;

const int mod1 = 1e9 + 7, mod2 = 1e9 + 9;

 

struct pii {

   int p1, p2;

   pii() {}

   pii(int p1_, int p2_) : p1(p1_), p2(p2_) {}

   pii operator + (pii t) {

       t.p1 = (this->p1 + t.p1) % mod1;

       t.p2 = (this->p2 + t.p2) % mod2;

       return t;

   }

   pii operator - (pii t) {

       t.p1 = (this->p1 - t.p1 + mod1) % mod1;

       t.p2 = (this->p2 - t.p2 + mod2) % mod2;

       return t;

   }

   pii operator * (pii t) {

       t.p1 = (this->p1 * t.p1) % mod1;

       t.p2 = (this->p2 * t.p2) % mod2;

       return t;

   }

   bool operator == (pii t) {

       if(t.p1 == this->p1 && t.p2 == this->p2) return true;

       return false;

   }

}p[N], pre[N], suf[N];

signed main() {

   int n;//拼凑的长度

   string s;

   cin >> n >> s;

   pii P = {131, 13331};

   p[0] = {1, 1};

   rep(i, 1, (n << 1)) {

       p[i] = p[i - 1] * P;

       pii tt = {s[i - 1] - 'a', s[i - 1] - 'a'};

       pre[i] = pre[i - 1] * P + tt;

   }

   for(int i = (n << 1); i >= 0; --i) {

       pii tt = {s[i - 1] - 'a', s[i - 1] - 'a'};

       suf[i] = suf[i + 1] * P + tt;

   }

   rep(i, 0, n) {

       pii sum1 = (pre[i] * p[n - i]) + (pre[(n << 1)] - pre[i + n] * p[n - i]);

       pii sum2 = suf[i + 1] - suf[i + n + 1] * p[n];

       if(sum1 == sum2) {

          cout << s.substr(0, i) << s.substr(i + n) << "\n" << i << "\n";

          return 0;

       }

   }

   cout << "-1\n";

   return 0;

}

 

 

6.5 Kmp

int n, m;

char s[N], p[N];

int ne[N];

signed main() {

  cin >> s + 1 >> p + 1;

  n = strlen(s + 1), m = strlen(p + 1);

  for(int i = 2, j = 0; i <= m; ++i) {

     while(j && p[i] != p[j + 1]) j = ne[j];

     if(p[i] == p[j + 1]) ++j;

     ne[i] = j; //更新ne值

  }

  for(int i = 1, j = 0; i <= n; ++i) {

     while(j && s[i] != p[j + 1]) j = ne[j];

     if(s[i] == p[j + 1]) ++j;

     if(j == m) {

       cout << i - m + 1 << "\n"; //第一个字符的位置

       j = ne[j];

     }

  }

}

 

6.6 Manacher

/*

 *p[i] 回文半径 p[i] - 1即是回文串长度

 *(i - p[i] + 1) / 2 为原回文串长度为p[i] - 1的起点

 */

char s[N], t[N << 1];

int n, p[N << 1];

void manacher() {

  int L = 0;

  t[++L] = '$', t[++L] = '#';

  for(int i = 1; i <= n; ++i) t[++L] = s[i], t[++L] = '#';

  int mx = 0, id, ans = -1;

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

     if(mx >= i) p[i] = min(mx - i, p[2 * id - i]);

     else p[i] = 1;

     while(t[i - p[i]] == t[i + p[i]]) ++p[i];

     if(i + p[i] > mx) mx = i + p[i], id = i;

     if(ans < p[i]) ans = p[i];

  }

  cout << ans - 1;

}

/*

 *判断某个区间是否是回文

 */

bool check(int L, int R) {

  int mid = L + R + 1;

  return 2 * p[mid] - 1 >= 2 * (R - L);

}

 

6.7 后缀数组

/*

 *sa[i]：排名为i的后缀开始

 *hel[i]：sa[i]与sa[i - 1] 的最长公共前缀lcp

 *某个字符串的本质不同的子串是n * (n + 1) / 2 - sum(hel[i])

 */

int n, m; //m 值域

char s[N];

int sa[N], hel[N];

int h1[N], h2[N], rk[N], c[N];

void SA() {

  int *x = h1, *y = h2;

  for(int i = 1; i <= n; ++i) c[x[i] = s[i]]++;

  for(int i = 2; i <= m; ++i) c[i] += c[i - 1];

  for(int i = n; i; --i) sa[c[x[i]]--] = i; //第一关键字排序

  for(int k = 1; k <= n; k <<= 1) {

     int num = 0;

     for(int i = n - k + 1; i <= n; ++i) y[++num] = i;

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

       if(sa[i] > k) y[++num] = sa[i] - k;

     }

     for(int i = 1; i <= m; ++i) c[i] = 0;

     for(int i = 1; i <= n; ++i) c[x[i]]++;

     for(int i = 2; i <= m; ++i) c[i] += c[i - 1];

     for(int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;

     swap(x, y);

     x[sa[1]] = 1, num = 1;

     for(int i = 2; i <= n; ++i)

       x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) == 1 ? num : ++num;

     if(num == n) break;

     m = num;

  }

  for(int i = 1; i <= n; i++) rk[sa[i]] = i;

  for(int i = 1, k = 0; i <= n; i++) {

     if(rk[i] == 1) continue;

     if(k) k--;

     int j = sa[rk[i] - 1];

     while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;

     hel[rk[i]] = k;

  }

}

/*

 *2个串求公共最长子串

 *len1为第一个串的长度

 */

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

  if((sa[i] <= len1) != (sa[i - 1] <= len1)) {

     if(hel[i] > ans) ans = hel[i];

  }

}