FFT
/*
FFT模板 以此题为例
这道题就是给两个序列a，b
求b序列中有多少个数可以表示为a序列中的一个数，或者两个数之和（可以同一个数）
可以构造两个一样的多项式，a序列有相应的数的项的系数为1，否则为0
因为还有1个数的情况，所以看作a中有一个0。
这样用多项式乘法，就可以得出所有的和。
*/#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 8e5 + 10; //答案多项式次数的两倍 也是limit的理论最大值
const double pi = acos(-1.0);struct Complex
{double x, y;
}a[N], b[N], c[N];
int ans[N], r[N], n, m, l, limit;Complex operator + (Complex a, Complex b) { return Complex{a.x + b.x, a.y + b.y}; }
Complex operator - (Complex a, Complex b) { return Complex{a.x - b.x, a.y - b.y}; }
Complex operator * (Complex a, Complex b) { return Complex{a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x}; }void FFT(Complex *A, int type)
{rep(i, 0, limit)if(i < r[i])swap(A[i], A[r[i]]);for(int mid = 1; mid < limit; mid <<= 1){Complex Wn{cos(pi / mid), type * sin(pi / mid)};for(int R = mid << 1, j = 0; j < limit; j += R){Complex w{1, 0};for(int k = 0; k < mid; k++, w = w * Wn){Complex x = A[j + k], y = w * A[j + mid + k];A[j + k] = x + y;A[j + mid + k] = x - y;}}}
}void solve()
{for(limit = 1, l = 0; limit <= n + m; limit <<= 1, l++); //FFT只能处理2^t的多项式 limit表示最高次数 n + m即答案多项式次数rep(i, 0, limit) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));FFT(a, 1); FFT(b, 1); //FFT 系数表示法转化为点值表示法_for(i, 0, limit) c[i] = a[i] * b[i]; //点值表示法直接相乘FFT(c, -1); //逆FFT 点值表示法转化为系数表示法 最后要多除个limit（下一行）_for(i, 0, n + m) ans[i] = (int)(c[i].x / limit + 0.5);
}int main()
{while(~scanf("%d", &n)){memset(a, 0, sizeof a); //多组数据只用清空a b两个多项式的数组memset(b, 0, sizeof b);a[0].x = b[0].x = 1;_for(i, 1, n){int x; scanf("%d", &x);a[x].x = b[x].x = 1; //a[i].x表示x^i项的系数}m = n = 2e5; //n表示a多项式的次数 m是b多项式的次数solve();int cnt = 0;scanf("%d", &m);while(m--){int x; scanf("%d", &x);cnt += (ans[x] > 0);}printf("%d\n", cnt);}return 0;
}splay
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int N = 1e5 + 10;
int rt, tot, fa[N], ch[N][2], val[N], cnt[N], sz[N];struct Splay
{void maintain(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } //重新计算x的sz值bool get(int x) { return x == ch[fa[x]][1]; } //判断x是不是右儿子void clear(int x) //销毁x节点{ch[x][0] = ch[x][1] = fa[x] = val[x] = sz[x] = cnt[x] = 0;}void rotate(int x) //旋转操作 包含左旋和右旋{int y = fa[x], z = fa[y], chk = get(x);ch[y][chk] = ch[x][chk ^ 1];if(ch[x][chk ^ 1]) fa[ch[x][chk ^ 1]] = y;ch[x][chk ^ 1] = y;fa[y] = x; fa[x] = z;if(z) ch[z][y == ch[z][1]] = x;maintain(y);maintain(x);}void splay(int x) //将x旋转到根 每次访问x后都要splay{for(int f = fa[x]; f = fa[x]; rotate(x))if(fa[f]) rotate(get(x) == get(f) ? f : x);rt = x;}void ins(int k) //插入操作{if(!rt){val[++tot] = k;cnt[tot]++;rt = tot;maintain(rt);return;}int cur = rt, f = 0;while(1){if(val[cur] == k){cnt[cur]++;maintain(cur);maintain(f);splay(cur);break;}f = cur;cur = ch[cur][val[cur] < k];if(!cur){val[++tot] = k;cnt[tot]++;fa[tot] = f;ch[f][val[f] < k] = tot;maintain(tot);maintain(f);splay(tot);break;}}}int rk(int k) //获取k的排名{int res = 0, cur = rt;while(1){if(k < val[cur]) cur = ch[cur][0];else{res += sz[ch[cur][0]];if(k == val[cur]){splay(cur);return res + 1;}res += cnt[cur];cur = ch[cur][1];}}}int kth(int k) //排名第k的是哪一个数{int cur = rt;while(1){if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];else{k -= cnt[cur] + sz[ch[cur][0]];if(k <= 0){splay(cur);return val[cur];}cur = ch[cur][1];}}}int pre() //返回k的前驱 注意函数外要先插入再删除{int cur = ch[rt][0];if (!cur) return cur;while(ch[cur][1]) cur = ch[cur][1];splay(cur);return cur;}int nxt() //返回k的后继 注意函数外要先插入再删除{int cur = ch[rt][1];if (!cur) return cur;while(ch[cur][0]) cur = ch[cur][0];splay(cur);return cur;}void del(int k) //删除k 只删一个{rk(k);if(cnt[rt] > 1){cnt[rt]--;maintain(rt);return;}if(!ch[rt][0] && !ch[rt][1]){clear(rt);rt = 0;return;}if(!ch[rt][0]){int cur = rt;rt = ch[rt][1];fa[rt] = 0;clear(cur);return;}if(!ch[rt][1]){int cur = rt;rt = ch[rt][0];fa[rt] = 0;clear(cur);return;}int cur = rt;int x = pre();fa[ch[cur][1]] = x;ch[x][1] = ch[cur][1];clear(cur);maintain(rt);}
}tree;int main()
{int n;scanf("%d", &n);_for(i, 1, n){int op, x;scanf("%d%d", &op, &x);if (op == 1) tree.ins(x);if (op == 2) tree.del(x);if (op == 3) printf("%d\n", tree.rk(x));if (op == 4) printf("%d\n", tree.kth(x));if (op == 5) tree.ins(x), printf("%d\n", val[tree.pre()]), tree.del(x);if (op == 6) tree.ins(x), printf("%d\n", val[tree.nxt()]), tree.del(x);}return 0;
}文艺平衡树（rope）
rope这个STL可以用来解决一些平衡树的问题
它可以时间区间插入，删除，替换，都是logn
这道题而言就建立两个rope，一个正的一个反的，替换的时候就替换对应区间就可以了
用取子串相加这个操作
#include <bits/stdc++.h>
#include <ext/rope>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;
using namespace __gnu_cxx;rope<int> a, b;
int n, m;void solve(int l, int r)
{int ll = n - 1 - r, rr = n - 1 - l;rope<int> t = a;a = a.substr(a.begin(), a.begin() + l) + b.substr(b.begin() + ll, b.begin() + rr + 1) + a.substr(a.begin() + r + 1, a.end());b = b.substr(b.begin(), b.begin() + ll) + t.substr(t.begin() + l, t.begin() + r + 1) + b.substr(b.begin() + rr + 1, b.end());
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n){a.push_back(i);b.push_back(n - i + 1);}while(m--){int l, r;scanf("%d%d", &l, &r);solve(l - 1, r - 1);}for(int x: a) printf("%d ", x);return 0;
}点分治
#include <bits/stdc++.h>
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;const int N = 1e4 + 10;
const int M = 1e7 + 10;
vector<pair<int, int>> g[N];
int q[N], ans[N], maxp[N], vis[N], siz[N], rt, sum, n, m;
vector<int> ve;
bool judge[M];void getrt(int u, int fa)
{siz[u] = 1; maxp[u] = 0; //注意这里初始化maxpfor(auto x: g[u]){int v = x.first, w = x.second;if(v == fa || vis[v]) continue;getrt(v, u);siz[u] += siz[v];maxp[u] = max(maxp[u], siz[v]);}maxp[u] = max(maxp[u], sum - siz[u]);if(maxp[u] < maxp[rt]) rt = u;
}void getdis(int u, int fa, int d)
{if(d <= 1e7) ve.push_back(d); //询问到1e7 总和会到1e8for(auto x: g[u]){int v = x.first, w = x.second;if(vis[v] || v == fa) continue;getdis(v, u, d + w);}
}void solve(int u)
{vector<int> tmp; //防止memsetfor(auto x: g[u]){int v = x.first, w = x.second;if(vis[v]) continue;ve.clear();getdis(v, u, w);for(int x: ve)_for(i, 1, m)if(q[i] >= x)ans[i] |= judge[q[i] - x];for(int x: ve){judge[x] = true;tmp.push_back(x);}}for(int x: tmp) judge[x] = false;
}void divide(int u)
{vis[u] = 1; //删除usolve(u); //处理经过u的路径for(auto x: g[u]){int v = x.first;if(vis[v]) continue;maxp[rt = 0] = sum = siz[v]; //这里初始化sum是siz[v]getrt(v, 0);getrt(rt, 0);divide(rt);}
}int main()
{scanf("%d%d", &n, &m);_for(i, 1, n - 1){int u, v, w;scanf("%d%d%d", &u, &v, &w);g[u].push_back({v, w});g[v].push_back({u, w});}_for(i, 1, m) scanf("%d", &q[i]);judge[0] = true; //注意要初始化0maxp[rt = 0] = sum = n; //初始化rtgetrt(1, 0); //找重心getrt(rt, 0); //更新正确的siz数组divide(rt);_for(i, 1, m) puts(ans[i] ? "AYE" : "NAY");return 0;
}SAM
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e6 + 10; //字符串总长两倍
int t[N][26], len[N], fa[N], c[N], k[N]; //t为自动机上的边，即fail，fa为parent tree上的边
int siz[N], cnt = 1, last = 1, n; //len表示节点i的类中最长串的长度
vector<int> endpos[N];
char s[N];
ll ans;void add(int c, int pos) //题目不同更新u，r两处 不只有小写字母也要改
{int p = last;int u = last = ++cnt; //u是新建的节点len[u] = len[p] + 1;for(; p && !t[p][c]; p = fa[p]) t[p][c] = u;if(!p) fa[u] = 1;else{int q = t[p][c];if(len[q] == len[p] + 1) fa[u] = q;else{int r = ++cnt; //r是多建的虚空点_for(i, 0, 25) t[r][i] = t[q][i]; //有些题不只是小写字母 注意fa[r] = fa[q];len[r] = len[p] + 1;fa[q] = fa[u] = r;for(; p && t[p][c] == q; p = fa[p])t[p][c] = r;//更新r}}//更新usiz[u] = 1; //注意siz的初始化只有siz[u] = 1 不要写siz[q] = 1endpos[u].push_back(pos); //siz表示有多少个终止位置，也是子串出现次数
}int main()
{scanf("%s", s + 1);n = strlen(s + 1);_for(i, 1, n) add(s[i] - 'a', i);_for(i, 1, cnt) c[len[i]]++; //根据len桶排序 也可以dfs求siz数组_for(i, 1, cnt) c[i] += c[i - 1];_for(i, 1, cnt) k[c[len[i]]--] = i;for(int i = cnt; i >= 1; i--){int id = k[i];siz[fa[id]] += siz[id];for(int x: endpos[id]) endpos[fa[id]].push_back(x);}_for(i, 1, n)if(siz[i] > 1)ans = max(ans, 1LL * siz[i] * len[i]);printf("%lld\n", ans);return 0;
}单调栈
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e6 + 10;
int a[N], ans[N], s[N], top, n;int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);for(int i = n; i >= 1; i--){while(top && a[s[top]] <= a[i]) top--; //注意这里是while 不是 if 维持单调性ans[i] = top ? s[top] : 0; //通过当前栈顶记录答案s[++top] = i; //将当前元素压入栈}_for(i, 1, n) printf("%d ", ans[i]);return 0;
}珂朵莉树模板
应用条件
1.有区间赋值操作
2.数据随机 否则会被构造数据卡成暴力
本质上就是应用set，维护三元组(l, r, v)
因为有区间赋值操作导致区间个数小，保证复杂度
struct node
{int l, r;mutable int v; //注意关键字mutablebool operator < (const node& rhs) const{return l < rhs.l;}
};
set<node> s;
int n;auto split(int x)
{auto it = s.lower_bound({x, 0, 0});if (it != s.end() && it->l == x) return it;--it;int l = it->l, r = it->r, v = it->v;s.erase(it);s.insert({l, x - 1, v});return s.insert({x, r, v}).first;
}void assign(int l, int r, int v)
{auto itr = split(r + 1), itl = split(l); //注意先r后ls.erase(itl, itr);s.insert({l, r, v});
}void add(int l, int r, int x)
{auto itr = split(r + 1), itl = split(l);for(auto it = itl; it != itr; it++) {//做某种操作it->v += x;}
}ST表
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 3e5 + 10;
int stgcd[N][21], stmin[N][21], Log[N], n; int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }int ask_gcd(int l, int r)
{int k = Log[r - l + 1]; //长度位2 ^ kreturn gcd(stgcd[l][k], stgcd[r - (1 << k) + 1][k]);
}int ask_min(int l, int r)
{int k = Log[r - l + 1];return min(stmin[l][k], stmin[r - (1 << k) + 1][k]);
}bool check(int key)
{_for(i, 1, n){int j = i + key;if(j > n) break;int g = ask_gcd(i, j), mi = ask_min(i, j);if(g == mi) return true;}return false;
}void init()
{Log[1] = 0;_for(i, 2, n) Log[i] = Log[i / 2] + 1;_for(j, 1, 20) //注意先枚举j后枚举i 因为每次更新要用到j - 1for(int i = 1; i + (1 << j) - 1 <= n; i++) //注意f[i][j]不要超范围{stgcd[i][j] = gcd(stgcd[i][j - 1], stgcd[i + (1 << (j - 1))][j - 1]);stmin[i][j] = min(stmin[i][j - 1], stmin[i + (1 << (j - 1))][j - 1]);}
}int main()
{ scanf("%d", &n);_for(i, 1, n) {scanf("%d", &stgcd[i][0]);stmin[i][0] = stgcd[i][0];}init();int l = 0, r = n + 1;while(l + 1 < r){int m = l + r >> 1;if(check(m)) l = m;else r = m;}vector<int> ans;_for(i, 1, n){int j = i + l;if(j > n) break;int g = ask_gcd(i, j), mi = ask_min(i, j);if(g == mi) ans.push_back(i);}printf("%d %d\n", ans.size(), l);for(int x: ans) printf("%d ", x);return 0;
}poj3261（后缀数组 + 二分）
同样是二分一个答案，然后根据height来分组
一个组内，如果长度有t次，说明有一个串重复了t次，且长度大于等于ans
这个串就是每一个后缀的前ans个字符 可以画图理解一下
所以只要判断组内的后缀个数大于等于k即可
#include <cstdio>
#include <algorithm>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 2e4 + 10;
const int M = 1e6 + 10;
int s[N], sa[N], rak[N], tp[N], tax[M], height[N], n, m, K; //注意Mvoid Qsort()
{_for(i, 0, m) tax[i] = 0;_for(i, 1, n) tax[rak[i]]++;_for(i, 1, m) tax[i] += tax[i - 1];for(int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i];
}void SuffixSort()
{m = 1e6; //s[i]的元素范围在0~m内_for(i, 1, n) rak[i] = s[i], tp[i] = i;Qsort();for(int w = 1, p = 0; p < n; m = p, w <<= 1){p = 0;_for(i, 1, w) tp[++p] = n - i + 1;_for(i, 1, n) if(sa[i] > w) tp[++p] = sa[i] - w;Qsort(); swap(tp, rak);rak[sa[1]] = p = 1;_for(i, 2, n)rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w]) ? p : ++p;}int k = 0;_for(i, 1, n){if(k) k--;int j = sa[rak[i] - 1];while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;height[rak[i]] = k;}
}bool check(int key)
{int cnt = 1;_for(i, 2, n){if(height[i] >= key) cnt++;else cnt = 1;if(cnt >= K) return true;}return false;
}int main()
{scanf("%d%d", &n, &K);_for(i, 1, n) scanf("%d", &s[i]);SuffixSort();int l = 1, r = n;while(l + 1 < r){int m = l + r >> 1;if(check(m)) l = m;else r = m;}printf("%d\n", l);return 0;
}回文自动机（PAM）
两颗trie树，一颗代表偶数长度回文串，一颗代表奇数长度回文串
一个节点代表一个回文串
fail指针代表当前回文串的最长回文后缀
代码量挺小，可以用来求本质不同的回文串数目，即新建的节点数目cnt-1
可以用来求每个节点出现的次数，每次先sum[last]++
然后再倒序sum[fail[j]] += sum[j] 这样就可以求出
这道题是求每个节点为结尾的回文串数目
每次新建节点的时候，num[cnt] = num[fail[cnt]] + 1
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 5e5 + 10;
int ch[N][26], len[N], fail[N], sum[N], n;
char s[N];int main()
{scanf("%s", s + 1);n = strlen(s + 1);s[0] = '#';fail[0] = 1; len[1] = -1;int last = 0, cnt = 1, pre;_for(i, 1, n){if(i > 1) s[i] = (s[i] - 97 + pre) % 26 + 97;while(s[i] != s[i - len[last] - 1]) last = fail[last];if(!ch[last][s[i] - 'a']){len[++cnt] = len[last] + 2;int j = fail[last];while(s[i] != s[i - len[j] - 1]) j = fail[j];fail[cnt] = ch[j][s[i] - 'a'];sum[cnt] = sum[fail[cnt]] + 1;ch[last][s[i] - 'a'] = cnt;}last = ch[last][s[i] - 'a'];printf("%d ", pre = sum[last]);}return 0;
}CF165E Compatible Numbers（高维前缀和）
对于一个询问，显然有1的地方都不能有1
所以也就是当前的a[i]取反，问有没有元素是它的子集
二进制，子集，可以用高维前缀和
用高维前缀和的思路，处理出每一个数的子集中存不存在题目给的数，存在的话用任意一个数就可以。
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;const int N = 1e6 + 10;
int f[1 << 22], a[N], w = 22, n;int main()
{scanf("%d", &n);_for(i, 1, n){scanf("%d", &a[i]);f[a[i]] = a[i];}rep(i, 0, w)rep(j, 0, 1 << w)if(j & (1 << i) && f[j ^ (1 << i)]) f[j] = f[j ^ (1 << i)];_for(i, 1, n){int cur = ((1 << w) - 1) ^ a[i];printf("%d ", f[cur] ? f[cur] : -1);}return 0;
}CF1092F Tree with Maximum Cost（换根dp）
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int N = 2e5 + 10;
vector<int> g[N];
ll sum[N], d[N], a[N], ans, cur;
int n;void dfs(int u, int fa)
{sum[u] = a[u];for(int v: g[u]){if(v == fa) continue;d[v] = d[u] + 1;dfs(v, u);sum[u] += sum[v];}
}void dfs2(int u, int fa, ll val)
{ans = max(ans, val);for(int v: g[u]){if(v == fa) continue;dfs2(v, u, val - sum[v] + sum[1] - sum[v]);}
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%lld", &a[i]);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);_for(i, 1, n) cur += a[i] * d[i];dfs2(1, 0, cur);printf("%lld\n", ans);return 0;
}