2.22（倍增）
P3865 【模板】ST表（RMQ）
首先是RMQ问题，静态查询区间最值，也就是不修改
用ST算法，其实蛮简单的
相比于线段树，ST算法代码少好写
初始化nlogn，每次查询O（1）
时间复杂度比线段树优秀
核心是处理出一个数组f[i][j]表示从i开始长2^j的最值
求这个数组就模仿求LCA那个数组，第一层循环是j第二层是i
然后对于每一段查询，找出最大的k使得2^k小于区间长度
这个k也就是log区间长度，要预处理一下log数组
然后取两段的最值，一段左端为l，右端为r
这两段并集就是一整段
理解思想就很容易写出代码了，要理解算法原理
ST算法和线段树不同的地方在于询问区间的分解方式
ST算法的分解是两个区间的并集
所以只能维护一些重叠部分不影响的信息，比如最值，最大公因数
如果是不修改而且查询最值就用ST算法
很好写，无非是预处理个f数组
#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 MAXN = 1e6 + 10;
int f[MAXN][20], Log[MAXN], n, m;void init()
{Log[1] = 0;_for(i, 2, n) Log[i] = Log[i >> 1] + 1;for(int j = 1; (1 << j) <= 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 main()
{scanf("%d%d", &n, &m);_for(i, 1, n) scanf("%d", &f[i][0]);init();while(m--){int l, r;scanf("%d%d", &l, &r);int k = Log[r - l + 1];printf("%d\n", max(f[l][k], f[r - (1 << k) + 1][k]));}return 0;
}
【模板】最近公共祖先（LCA）
算是复习了模板
有几个地方容易错
lca的过程中要用到d数组和up数组
那么开始就要dfs一遍初始化这个数组
这里有一个坑
就是默认树根的父亲是0号节点，且0号节点和树根深度不同
所以初始化代码要写到dfs的最开始地方，才可以把0这个节点包括进去
dfs一开始就要初始化这两个数组了
#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 MAXN = 5e5 + 10;
const int MAXM = 20;
int up[MAXN][MAXM], d[MAXN], n, m, s;
vector<int> g[MAXN];void dfs(int u, int fa)
{d[u] = d[fa] + 1; up[u][0] = fa;REP(j, 1, MAXM) up[u][j] = up[up[u][j-1]][j-1];for(auto v: g[u]){if(v == fa) continue;dfs(v, u);}
}int lca(int u, int v)
{if(d[u] < d[v]) swap(u, v);for(int j = MAXM - 1; j >= 0; j--)if(d[up[u][j]] >= d[v])u = up[u][j];if(u == v) return u;for(int j = MAXM - 1; j >= 0; j--)if(up[u][j] != up[v][j])u = up[u][j], v = up[v][j];return up[u][0];
}int main()
{scanf("%d%d%d", &n, &m, &s);_for(i, 1, n - 1){int u, v;scanf("%d%d", &u, &v);g[u].push_back(v);g[v].push_back(u);}dfs(s, 0);while(m--){int u, v;scanf("%d%d", &u, &v);printf("%d\n", lca(u, v));}return 0;
}P1967 [NOIP2013 提高组] 货车运输（生成树建图+lca拓展）
这题蛮好的
首先题目给的不是一个树，而我们求路径的时候用lca前提是一棵树
所以我们要生成树
根据题意是最大生成树
然后这题时求路径上边的最小值
那么我们模仿up数组，lca跳的时候顺便更新一个k数组，记录当前点到up的那个点的路径上边的最小值
#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 MAXN = 1e4 + 10;
struct node { int v, w; };
vector<node> g[MAXN];
int f[MAXN], n, m, q;
int up[MAXN][20], k[MAXN][20], d[MAXN];struct Edge
{ int u, v, w; bool operator < (const Edge& rhs) const{return w > rhs.w;}
};
vector<Edge> e;int find(int x)
{if(f[x] == x) return x;return f[x] = find(f[x]);
}void dfs(int u, int fa, int w)
{k[u][0] = w;up[u][0] = fa; d[u] = d[fa] + 1;REP(j, 1, 20) up[u][j] = up[up[u][j-1]][j-1];REP(j, 1, 20) k[u][j] = min(k[u][j-1], k[up[u][j-1]][j-1]);for(auto x: g[u]){if(x.v == fa) continue;dfs(x.v, u, x.w);}
}int ans(int u, int v)
{int res = 1e9;if(d[u] < d[v]) swap(u, v);for(int j = 19; j >= 0; j--)if(d[up[u][j]] >= d[v])res = min(res, k[u][j]), u = up[u][j];if(u == v) return res;for(int j = 19; j >= 0; j--)if(up[u][j] != up[v][j]){res = min(res, min(k[u][j], k[v][j]));u = up[u][j], v = up[v][j];} return min(res, min(k[u][0], k[v][0]));
}int main()
{scanf("%d%d", &n, &m);while(m--){int u, v, w;scanf("%d%d%d", &u, &v, &w);e.push_back(Edge{u, v, w});}sort(e.begin(), e.end());_for(i, 1, n) f[i] = i;REP(i, 0, e.size()){int u = e[i].u, v = e[i].v, w = e[i].w;if(find(u) != find(v)){f[find(u)] = find(v);g[u].push_back(node{v, w});g[v].push_back(node{u, w});}}_for(i, 1, n)if(f[i] == i) dfs(i, 0, 1e9);scanf("%d", &q);while(q--){int u, v;scanf("%d%d", &u, &v);if(find(u) != find(v)) puts("-1");else printf("%d\n", ans(u, v));}return 0;
}归并排序
下面一道题要用到归并排序。归并排序是个挺简单的知识点，理解就好
思想就是分治
先分，把数列切一半分，一直分到只剩下一个元素
然后治。把两段有序数列合并成一个有序数列，非常简单，一个个比较就好，其中一个数列完了，另一个数列剩下全部填上就好
可以在O（n）的时间内把两段有序有序数列合并成一个有序数列
学算法要学思想
#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 MAXN = 1e4 + 10;
int a[MAXN], t[MAXN], n;void merge_sort(int l, int r)
{if(l == r) return;int mid = (l + r) >> 1;merge_sort(l, mid); merge_sort(mid + 1, r);int i = l, j = mid + 1, p = 0;while(i <= mid && j <= r){if(a[i] < a[j]) t[++p] = a[i++];else t[++p] = a[j++];}while(i <= mid) t[++p] = a[i++];while(j <= r) t[++p] = a[j++];p = 0; _for(k, l, r) a[k] = t[++p];
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);merge_sort(1, n);_for(i, 1, n) printf("%d ", a[i]);puts("");return 0;
}hihoCoder 1384（倍增思想+归并排序）
这题挺精彩的
显然一格一格一格拓展会超时
那么就用倍增的思想，走1格，走2格，走4格，超了再减半
复杂度从n到logn，但常数会大一点
这里有个关键，就是排序的时候前面一部分已经是排好的了
所以可以只排后一部分然后归并排序
比直接全部排要优
然后这里我用了速读
速读挺简单的，无非是先处理非数字部分再处理数字部分
#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 MAXN = 5e5 + 10;
ll a[MAXN], b[MAXN], t[MAXN], k;
int n, m;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void readll(ll& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}int merge_sort(int l, int mid, int r)
{_for(i, l, r) b[i] = a[i];sort(b + mid + 1, b + r + 1);int p = 0, i = l, j = mid + 1;while(i <= mid && j <= r){if(b[i] < b[j]) t[++p] = b[i++];else t[++p] = b[j++];}while(i <= mid) t[++p] = b[i++];while(j <= r) t[++p] = b[j++];return p;
}bool check(int l, int mid, int r)
{int p = merge_sort(l, mid, r);ll sum = 0;int cnt = m, L = 1, R = p;while(L < R && cnt--){sum += (t[L] - t[R]) * (t[L] - t[R]);L++; R--;if(sum > k) return false;}p = 0; _for(i, l, r) a[i] = t[++p];return true;
}int main()
{int T; read(T);while(T--){read(n); read(m); readll(k);_for(i, 1, n) readll(a[i]);int ans = 0, l = 1, p, r;while(l <= n){ans++;r = l;p = 1;while(p){if(r + p <= n && check(l, r, r + p)){r += p;p <<= 1; } else p >>= 1;}l = r + 1;}printf("%d\n", ans);}return 0;
}P1311 [NOIP2011 提高组] 选择客栈（ST算法+思维）
我AC后发现我的解法貌似和洛谷里面的题解都不一样……
首先把每个颜色的标号用vector存一下
对于一种颜色
我发现只要最小的区间，也就是相邻的两个点，它们的最小值小于等于p，那么所有包含它的区间都小于等于p
所以我们可以判断每一个最小区间最小值是不是小于等于p（用ST算法O（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;typedef long long ll;
const int N = 2e5 + 10;
int f[N][20], Log[N], n, k, p, a;
vector<int> c[60]; void init()
{Log[1] = 0;_for(i, 2, n) Log[i] = Log[i >> 1] + 1;_for(j, 1, Log[n])for(int i = 1; i + (1 << j) - 1 <= n; i++) f[i][j] = min(f[i][j-1], f[i + (1 << (j - 1))][j-1]);
}int query(int l, int r)
{int k = Log[r - l + 1];return min(f[l][k], f[r - (1 << k) + 1][k]);
}int main()
{scanf("%d%d%d", &n, &k, &p);_for(i, 1, n){scanf("%d%d", &a, &f[i][0]);c[a].push_back(i);}init();ll ans = 0;REP(i, 0, k){int m = c[i].size();ll sum = 0, t = 0;REP(j, 0, m - 1){if(query(c[i][j], c[i][j + 1]) > p) t++;else{sum += t * (t + 1) / 2;t = 0;}}sum += t * (t + 1) / 2;ans += m * (m - 1) / 2 - sum;}printf("%lld\n", ans);return 0;
}2.23（树状数组与线段树）
虽然学过，但发现自己学的还不是很深，继续学
离散化
只要元素相对大小关系时用离散化
用unique函数离散化
注意unique返回值就是长度+1
所以要多减一个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 = 1e5 + 10;
int a[N], lsh[N], n, m;void deal()
{_for(i, 1, n) lsh[i] = a[i];int m = unique(lsh + 1, lsh + n + 1) - lsh - 1;sort(lsh + 1, lsh + m + 1);_for(i, 1, n) a[i] = lower_bound(lsh + 1, lsh + m + 1, a[i]) - lsh;
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);deal();_for(i, 1, n) printf("%d\n", a[i]);return 0;
}poj 2528（线段树区间染色+特殊离散化）
线段树可以维护区间信息，其实主要是懒标记起了加速作用
这里是区间染色，就可以用线段树
这里离散化有个坑
离散化只保留了数相对大小的关系
但是这道题还需要数与数之间有空隙这个信息
所以我们要补上这个信息（数据弱，不补上也能过）
那么当数与数之间的差大于1时，我们就要加进去一个数作为空隙
注意空间大小也要相应的变大
#include<cstdio>
#include<algorithm>
#include<cstring>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 = 4e4 + 10;
struct node
{int l, r, w, f;int mid() { return (l + r) >> 1; }
}t[N << 2];
int L[N], R[N], lsh[N], ans[N], n, m;void deal()
{_for(i, 1, n) lsh[i] = L[i];_for(i, n + 1, 2 * n) lsh[i] = R[i - n];m = unique(lsh + 1, lsh + 2 * n + 1) - lsh - 1;sort(lsh + 1, lsh + m + 1);int t = 0;_for(i, 1, m)if(lsh[i + 1] - lsh[i] > 1){t++;lsh[m + t] = lsh[i] + 1;}m += t;sort(lsh + 1, lsh + m + 1); _for(i, 1, n) {L[i] = lower_bound(lsh + 1, lsh + m + 1, L[i]) - lsh;R[i] = lower_bound(lsh + 1, lsh + m + 1, R[i]) - lsh;}
}void lazy(int k, int p)
{t[k].f = t[k].w = p;
}void down(int k)
{if(!t[k].f) return; lazy(l(k), t[k].f);lazy(r(k), t[k].f);t[k].f = 0;
}void up(int k)
{if(t[l(k)].w == t[r(k)].w) t[k].w = t[l(k)].w ;else t[k].w = -1;
}void build(int k, int l, int r)
{t[k].l = l, t[k].r = r, t[k].w = t[k].f = 0;if(l == r) return;int mid = t[k].mid();build(l(k), l, mid);build(r(k), mid + 1, r);up(k);
}void change(int k, int l, int r, int p)
{if(l <= t[k].l && t[k].r <= r){lazy(k, p);return;}down(k);int mid = t[k].mid();if(l <= mid) change(l(k), l, r, p);if(r > mid) change(r(k), l, r, p);up(k);
}void query(int k)
{if(!t[k].w) return;if(t[k].w > 0) {ans[t[k].w] = 1;return;}query(l(k)); query(r(k));
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d", &n);_for(i, 1, n) scanf("%d%d", &L[i], &R[i]);deal();build(1, 1, m);int color = 0;_for(i, 1, n) change(1, L[i], R[i], ++color);memset(ans, 0, sizeof(ans));query(1);int sum = 0;_for(i, 1, color) sum += ans[i];printf("%d\n", sum);}return 0;
}poj 2777（区间染色）
与上一题类似，比上一题还简单一点
颜色少可以用二进制来存储状态，很方便的用一个int表示了当前的状态
比我用-1表示多种颜色，要继续往下要快一些
#include<cstdio>
#include<algorithm>
#include<cstring>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 = 1e5 + 10;
struct node
{int l, r, w, f;int mid() { return (l + r) >> 1; }
}t[N << 2];
int ans[50], n, T, m;void lazy(int k, int p)
{t[k].f = t[k].w = p;
}void down(int k)
{if(!t[k].f) return; lazy(l(k), t[k].f);lazy(r(k), t[k].f);t[k].f = 0;
}void up(int k)
{if(t[l(k)].w == t[r(k)].w) t[k].w = t[l(k)].w ;else t[k].w = -1;
}void build(int k, int l, int r)
{t[k].l = l, t[k].r = r, t[k].w = 1, t[k].f = 0;if(l == r) return;int mid = t[k].mid();build(l(k), l, mid);build(r(k), mid + 1, r);up(k);
}void change(int k, int l, int r, int p)
{if(l <= t[k].l && t[k].r <= r){lazy(k, p);return;}down(k);int mid = t[k].mid();if(l <= mid) change(l(k), l, r, p);if(r > mid) change(r(k), l, r, p);up(k);
}void query(int k, int L, int R)
{if(L <= t[k].l && t[k].r <= R && t[k].w != -1) {ans[t[k].w] = 1;return;}down(k);int mid = t[k].mid();if(L <= mid) query(l(k), L, R);if(R > mid) query(r(k), L, R);
}int main()
{scanf("%d%d%d", &n, &T, &m);build(1, 1, n);while(m--){char op[5];int l, r, c;scanf("%s%d%d", op, &l, &r);if(l > r) swap(l, r);if(op[0] == 'C'){scanf("%d", &c);change(1, l, r, c);}else {memset(ans, 0, sizeof(ans));query(1, l, r);int sum = 0;_for(i, 1, T) sum += ans[i];printf("%d\n", sum);}}return 0;
}「一本通 4.3 练习 2」花神游历各国（观察性质+特殊标记）
这题的突破口在于发现同一个数开跟多次后就是1了
所以为1的时候可以标记一下，以后修改区间的时候可以不理它了，改了也是白改
所以多写一个f表示当前这个区间还需不需要修改
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 = 1e5 + 10;
struct node
{int l, r, f; ll w;int m() { return (l + r) >> 1; }
}t[N << 2];
int n, m;void up(int k)
{t[k].w = t[l(k)].w + t[r(k)].w;t[k].f = t[l(k)].f & t[r(k)].f;
}void build(int k, int l, int r)
{t[k].l = l, t[k].r = r;if(l == r){scanf("%lld", &t[k].w);t[k].f = t[k].w <= 1;return;}int m = t[k].m();build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void change(int k, int L, int R)
{if(t[k].f) return;if(t[k].l == t[k].r){t[k].w = sqrt(t[k].w);if(t[k].w <= 1) t[k].f = 1;return;}int m = t[k].m();if(L <= m) change(l(k), L, R);if(R > m) change(r(k), L, R);up(k);
}ll query(int k, int L, int R)
{if(L <= t[k].l && t[k].r <= R) return t[k].w;ll res = 0;int m = t[k].m();if(L <= m) res += query(l(k), L, R);if(R > m) res += query(r(k), L, R);return res;
}int main()
{scanf("%d", &n);build(1, 1, n);scanf("%d", &m);while(m--){int x, l, r;scanf("%d%d%d", &x, &l, &r);if(x == 1) printf("%lld\n", query(1, l, r));else change(1, l, r);}return 0;
}P2574 XOR的艺术（线段树维护区间信息）
有点水这道题。其实深刻理解算法原理，很多拓展题就迎刃而解了，无非时利用了算法的思想
这题依然是用线段树维护区间信息
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 = 2e5 + 10;
struct node
{int l, r, w, f;int m() { return (l + r) >> 1; }int len() { return r - l + 1; }
}t[N << 2];
int n, m;void up(int k)
{t[k].w = t[l(k)].w + t[r(k)].w;
}void lazy(int k)
{ t[k].f ^= 1; t[k].w = t[k].len() - t[k].w;
}void down(int k)
{if(!t[k].f) return;lazy(l(k)); lazy(r(k)); t[k].f = 0;
}void build(int k, int l, int r)
{t[k].l = l; t[k].r = r; t[k].f = 0;if(l == r){scanf("%1d", &t[k].w);return;}int m = t[k].m();build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void change(int k, int L, int R)
{if(L <= t[k].l && t[k].r <= R){lazy(k);return;}down(k);int m = t[k].m();if(L <= m) change(l(k), L, R);if(R > m) change(r(k), L, R);up(k);
}int query(int k, int L, int R)
{if(L <= t[k].l && t[k].r <= R) return t[k].w;down(k);int res = 0, m = t[k].m();if(L <= m) res += query(l(k), L, R);if(R > m) res += query(r(k), L, R);return res;
}int main()
{scanf("%d%d", &n, &m);build(1, 1, n);while(m--){int op, l, r;scanf("%d%d%d", &op, &l, &r);if(op == 1) printf("%d\n", query(1, l, r));else change(1, l, r);}return 0;
}[TJOI2018]数学计算（思维+线段树前缀积）
这题其实思路很简单，但是很难想到
我看到除法想到逆元，但是逆元要互质，除数和mod不一定互质
然后就懵逼了，一直没什么思路
看了题解发现是线段树维护前缀积
区间呢，元素呢？？这么就线段树了？？
这题难在思维跨度大
这里有个抽象的过程，把每次操作看作一个点，就变成一个数轴了
那么维护前缀积就好了
懂了就很简单，但真的挺难想到这是一道线段树的题目
代码实现也不难，这题难在思维
#include<bits/stdc++.h>
#define l(k) (k << 1)
#define r(k) (k << 1 | 1)
#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 = 1e5 + 10;
struct node
{int l, r, w;int m() { return (l + r) >> 1; }
}t[N << 2];
int n, mod;void up(int k)
{t[k].w = 1ll * t[l(k)].w * t[r(k)].w % mod;
}void build(int k, int l, int r)
{t[k].l = l; t[k].r = r; t[k].w = 1;if(l == r) return;int m = t[k].m();build(l(k), l, m);build(r(k), m + 1, r);up(k);
}void change(int k, int x, int p)
{if(t[k].l == t[k].r){t[k].w = p;return;}int m = t[k].m();if(x <= m) change(l(k), x, p);else change(r(k), x, p);up(k);
}int main()
{int T; scanf("%d", &T);while(T--){scanf("%d%d", &n, &mod);build(1, 1, n);_for(i, 1, n){int op, x;scanf("%d%d", &op, &x);if(op == 1) change(1, i, x);else change(1, x, 1);printf("%d\n", t[1].w);}}return 0;
}P1966 [NOIP2013 提高组] 火柴排队（树状数组求逆序对+离散化+思维）
先离散化一波
首先要观察出，只要每个位置上对应的大小排名相同就ok
也就是说任何一个位置都需要都是第k大的
那么要把b排成a那样
那就用a数组的大小来cmp
即把a数组每个数设置一个id， id为1 2 3……
然后b数组每个数就取这个id
然后做离散化就好
#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 = 1e5 + 10;
const int MOD = 1e8 - 3;
int f[N], a[N], b[N], lsh[N], id[N], n;void deal(int t[])
{_for(i, 1, n) lsh[i] = t[i];sort(lsh + 1, lsh + n + 1);_for(i, 1, n) t[i] = lower_bound(lsh + 1, lsh + n + 1, t[i]) - lsh;
}int lowbit(int x) { return x & (-x); }void add(int x, int p)
{for(; x <= n; x += lowbit(x))f[x] += p;
}int sum(int x)
{int res = 0;for(; x; x -= lowbit(x))res += f[x];return res;
}int main()
{scanf("%d", &n);_for(i, 1, n) scanf("%d", &a[i]);_for(i, 1, n) scanf("%d", &b[i]);deal(a); deal(b);int ans = 0;_for(i, 1, n) id[a[i]] = i;_for(i, 1, n){ans = (ans + i - 1 - sum(id[b[i]])) % MOD;add(id[b[i]], 1);}printf("%d\n", ans);return 0;
}今天真的效率挺高
越做越快乐
我觉得核心在于题目难度都很合适，都是比我的水平高一些的题目
真的爱上acm，喜欢刷题
想很久最后ac那一次真的太tm爽了
加油加油
独立思考，尽量不看题解
知道了方法，接下来就是疯狂刷题学习了
发现洛谷那些题单都挺不错的，我现在多做蓝题一下的题目
蓝题就是比我水平高一些那样
加油
2.24(组合数学)
继续奋斗
acm是我真正热爱的事情，是我愿意为之付出的事情
没有acm的生活真的空虚无聊
加油
卡特兰数
1.这是一类问题答案的总结
这类问题都类似于下面这个问题
有n种操作1，n种操作2
一个数列是合法的如果任意前k个数都满足操作1次数的总和大于等于操作2次数的总和
那么合法的数列个数答案就是卡特兰数
2.数列为1 1 2 5 14 42
找规律看到这个就知道是卡特兰数
3.计算公式
h(n) = c(2n, n) - c(2n, n - 1)
P1044 [NOIP2003 普及组] 栈(卡特兰数模板)
#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 = 40;
ll c[N][N];void init()
{REP(i, 0, N) c[i][0] = 1;REP(i, 1, N)_for(j, 1, i)c[i][j] = c[i-1][j] + c[i-1][j-1];
}int main()
{init();int n; scanf("%d", &n);printf("%d\n", c[2 * n][n] - c[2 * n][n - 1]);return 0;
}求组合数方法
1.用定义。也就是预处理阶乘，用逆元
2.用递推公式。n方复杂度
3.当n与m很大时，上面两种方法肯定不行了
求这种比较大的组合数的时候要用到Lucas定理
其实Lucas定理蛮简单的，无非就是一个公式
当p为质数时
C(n, m) = C(n % p, m % p) * C(n / p, m / p)
这个公式挺有规律的
可以看成n和m化为p进制的每一位，然后都乘起来
当模了p之后，就变成了一个相对较小的组合数
这时就可以用前面两种方法求这个相对较小的组合数
后面一部分除以p的就继续递归下去
递归出口是m = 0时返回1
这里注意%p之后可能导致m > n这个时候返回0
「一本通 6.6 例 3」组合（Lucas模板）
这题有一点要注意，就是求C的时候可能会超时
题目有个限制条件非常有用，就是m比较小且m小于p
所以这时就可以用直接乘的方式来算C，且这个时候存在逆元，因为m小于p
某个数存在逆元的前提是这个数和模数p互质，当p为质数时可以用费马小定理
然后这里有个简化代码的技巧，就是一般数论题容易爆int。这里输入的数据不爆int，但中间过程可能爆int
那就些个mul函数使得中间过程为long long。这样写不用每次都写mod p，而且不用全部改成long long
#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;int p;int mul(int a, int b) { return 1ll * a * b % p; }int binpow(int a, int b)
{int res = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, a);a = mul(a, a);}return res;
}int inv(int a) { return binpow(a, p - 2); }int cal(int a, int b)
{int res = 1;_for(i, a, b) res = mul(res, i);return res;
}int C(int n, int m)
{if(m > n) return 0;return mul(cal(n - m + 1, n), inv(cal(1, m)));
}int Lucas(int n, int m)
{if(m == 0) return 1;return mul(C(n % p, m % p), Lucas(n / p, m / p));
}int main()
{int T; scanf("%d", &T);while(T--){int n, m;scanf("%d%d%d", &n, &m, &p);printf("%d\n", Lucas(n, m)); }return 0;
}#10230. 「一本通 6.6 练习 1」牡牛和牝牛（推公式+组合数）
不要畏难，最起码想它一个小时再放弃，要敢于挑战难题
想难题的过程中就在提升
这种精神要保持
这题就可以枚举有多少公牛
然后先删去要隔着的母牛再用组合数就好了
预处理阶乘，套公式求组合数就ok了
#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 MOD = 5000011;
const int N = 1e5 + 10;
int f[N];int add(int a, int b) { return (a + b) % MOD; }
int mul(int a, int b) { return 1ll * a * b % MOD; }int binpow(int a, int b)
{int res = 1;for(; b; b >>= 1){if(b & 1) res = mul(res, a);a = mul(a, a);}return res;
}void init()
{f[0] = f[1] = 1;REP(i, 2, N) f[i] = mul(f[i - 1], i);
}int inv(int a) { return binpow(a, MOD - 2); }int C(int n, int m)
{return mul(f[n], mul(inv(f[m]), inv(f[n - m])));
}int main()
{init();int n, k;scanf("%d%d", &n, &k);int ans = 1;for(int i = 1; n - (i - 1) * k >= i; i++)ans = add(ans, C(n - (i - 1) * k, i)); printf("%d\n", ans);return 0;
}后来又写了两道题，都没做出来，明天再看吧
看了支付宝的爱心捐赠，发现这个世界还有太多太多太多处于水深火热的人了，还有太多太多需要帮助的人了
我要变得强大，帮助他们
2.25（数论）
快速乘
当a*bmodp爆long long时用快速乘
和快速幂思想类似，在快速幂的代码下改一下就好
#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 MOD = 1e5 + 3;int add(int a, int b) { return (a + b) % MOD; }
int mul(int a, int b) { return 1ll * a * b % MOD; }int cal(int a, int b)
{int res = 0;for(; b; b >>= 1){if(b & 1) res = add(res, a); //乘换成加 a = mul(a, 2); //平方换成乘以2 }return res;
}int main()
{int a, b;while(~scanf("%d%d", &a, &b))printf("%d\n", cal(a, b));return 0;
}P1350 车的放置（组合数+数学）
独立做出一道蓝题，还行
首先考虑在一个矩形里面，方案数为c[n] [k]* c[m][k] * k!
注意要乘k！我就是在这里卡了巨久
然后给的那个图形就是三个矩形
那就枚举这三个矩形中每个矩形有多少辆车，然后算就完事了
注意矩形之间会有同一行和同一列，然后把公式改一下就好了
#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 MOD = 1e5 + 3;
const int N = 1e3 + 10;
int C[N][N], f[N];int add(int a, int b) { return (a + b) % MOD; }
int mul(int a, int b) { return 1ll * a * b % MOD; }void init()
{REP(i, 0, N) C[i][0] = 1;REP(i, 1, N)_for(j, 1, i)C[i][j] = add(C[i-1][j], C[i-1][j-1]);f[0] = f[1] = 1;REP(i, 2, N) f[i] = mul(f[i - 1], i);
}int main()
{init();int a, b, c, d, k;scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);int ans = 0;_for(n, 0, a){int m = k - n;if(m > c || m > d) continue;_for(y, 0, min(d, n)){int x = n - y, t = 1;t = mul(t, mul(C[a][x], C[b][x])); t = mul(t, f[x]);t = mul(t, mul(C[a - x][y], C[d][y])); t = mul(t, f[y]);t = mul(t, mul(C[c][m], C[d - y][m])); t = mul(t, f[m]);ans = add(ans, t);}}printf("%d\n", ans);return 0;
}欧拉函数
欧拉函数是小于等于n的数与n互质的数 phi[1] = 1
欧拉函数是积性函数，即a b互质时 f(ab) = f(a)f(b)
a^phi[p] = 1(mod p)
在快速幂，指数很大的时候可以用欧拉函数
在欧拉筛求素数的过程，改一改代码就可以线性求欧拉函数
#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 = 1e5 + 10;
int phi[N];
bool vis[N];
vector<int> p;void init()
{vis[0] = vis[1] = true;phi[1] = 1;REP(i, 2, N){if(!vis[i]) {p.push_back(i);phi[i] = i - 1; //质数就是i-1 }REP(j, 0, p.size()){if(i * p[j] >= N) break;vis[i * p[j]] = true;if(i % p[j] == 0){phi[i * p[j]] = phi[i] * p[j]; //不互质，p[j]为最小质因子，互质的数不变 break;}phi[i * p[j]] = phi[i] * phi[p[j]]; //互质就用积性函数性质 }}
}int main()
{init();_for(i, 1, 20)printf("%d %d\n", i, phi[i]);return 0;
}「CQOI2014」数三角形（思维）
想了好久，终于做出
先算总数，减去在横线和竖线的，难的是斜线的
把三个点的两端的点作为矩形的两点
那么中间的点数就是gcd(长，宽)-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;typedef long long ll;ll f(ll a)
{return (a - 2) * a * (a - 1) / 6;
}ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }int main()
{ll n, m;scanf("%lld%lld", &n, &m);n++; m++;ll ans = f(n * m);ans -= f(n) * m + f(m) * n;n--; m--;ll sum = 0;_for(a, 1, n)_for(b, 1, m)sum += (gcd(a, b) - 1) * (n - a + 1) * (m - b + 1);printf("%lld\n", ans - sum * 2); return 0;
}今天把昨天卡住的两道题做出来了，数学题还是比较费脑子的
还可以啦
接下来三天有其他社团的集训，就休息休息