芋艿酱的 ACM 板子
老模板已经过时,现在是新模板时代~
文件模板
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x...) fprintf(stderr, x);
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(char c, T x, Args... args) { print(x), putc(c), print(args...); }
int main() {
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}
=
数学
高斯消元 1
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x...) fprintf(stderr, x);
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(char c, T x, Args... args) { print(x), putc(c), print(args...); }
constexpr int N = 107;
constexpr double eps = 1e-7;
int n;
double a[N][N], f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%lf", &a[i][j]);
}
scanf("%lf", f + i);
}
for (int i = 1; i <= n; ++i) {
int p = i;
for (int j = i + 1; j <= n; ++j) {
if (abs(f[p])) p = j;
}
if (p != i) {
for (int j = 1; j <= n; ++j) swap(a[p][i], a[i][j]);
swap(f[i], f[p]);
}
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
double d = a[j][i] / a[i][i];
for (int k = 1; k <= n; ++k) {
a[j][k] -= a[i][k] * d;
}
f[j] -= f[i] * d;
}
}
bool fl = 0;
for (int i = 1; i <= n; ++i) {
int cnt = 0;
for (int j = 1; j <= n; ++j) {
cnt += abs(a[i][j]]) > eps;
}
if (cnt != 1) fl = 1;
if (a[i][i]) f[i] /= a[i][i];
}
if (fl) {
puts("No Solution");
} else {
for (int i = 1; i <= n; ++i) {
printf("%.2lf\n", f[i]);
}
}
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}
高斯消元 2
fl = 0 无数解,fl = -1 无解。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x...) fprintf(stderr, x);
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(char c, T x, Args... args) { print(x), putc(c), print(args...); }
constexpr int N = 107;
constexpr double eps = 1e-7;
int n;
double a[N][N], f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
scanf("%lf", &a[i][j]);
}
scanf("%lf", f + i);
}
for (int i = 1; i <= n; ++i) {
int p = i;
for (int j = 1; j <= n; ++j) {
if (abs(a[j][j]) > eps && j < i) continue;
if (abs(a[j][i]) > abs(a[p][i])) {
p = j;
}
}
for (int j = 1; j <= n; ++j) {
swap(a[p][j], a[i][j]);
}
swap(f[i], f[p]);
if (abs(a[i][i]) <= eps) continue;
for (int j = 1; j <= n; ++j) {
if (i == j) continue;
double d = a[j][i] / a[i][i];
for (int k = 1; k <= n; ++k) {
a[j][k] -= a[i][k] * d;
}
f[j] -= f[i] * d;
}
}
int fl = 1;
for (int i = 1; i <= n; ++i) {
if (abs(a[i][i]) <= eps) {
if (abs(f[i]) > eps) {
fl = -1;
} else if (fl != -1) {
fl = 0;
}
}
}
if (fl < 1) printf("%d", fl);
else {
for (int i = 1; i <= n; ++i) {
printf("x%d=%.2lf\n", i, abs(f[i] / a[i][i]) <= eps ? 0 : f[i] / a[i][i]);
}
}
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}
二元一次不定方程
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (!b) return x = 1, y = 0, a;
ll g = exgcd(b, a % b, y, x);
return y = y - a / b * x, g;
}
中国剩余定理
要求模数互质
// P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪
// 125 MB 1000 ms
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define mst(a, k) memset(a, k, sizeof a)
#define minv(a, b) a = min(a, b)
#define maxv(a, b) a = max(a, b)
#define gcd(a, b) __gcd((ll)a, (ll)b)
#define lcm(a, b) (a / gcd(a, b) * b)
#define gc(x) getchar(x)
#define pc(x) putchar(x)
#define put(x) printf("%d\n", x)
#define putl(x) printf("%lld\n", x)
#define mts() int t; scanf("%d", &t); while (t--) solve()
#define dbg(x...) fprintf(stderr, x)
#define dbgv(a, l, r) rep (i, l, r) fprintf(stderr, "%lld", (ll)a[i])
#define inf 0x3f3f3f3f
#define infl ((ll)1e18)
using namespace std;
using db = double;
using ll = __int128;
using ull = unsigned long long;
template<int size = 1 << 20>
struct IO {
char in[size], out[size], *p1, *p2, *pp;
IO() : p1(in), p2(in), pp(out) {}
~IO() { fwrite(out, 1, pp - out, stdout); }
inline char gc() { if (p1 == p2) p2 = (p1 = in) + fread(in, 1, size, stdin); return p1 == p2 ? ' ' : *p1++; }
inline bool blank(char ch) { return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t'; }
template<class T> inline void read(T& x) { double tmp = 1; bool sign = 0; x = 0; char ch = gc(); for (; !isdigit(ch); ch = gc()) sign |= ch == 45; for (; isdigit(ch); ch = gc()) x = x * 10 + ch - 48; if (ch == '.') for (ch = gc(); isdigit(ch); ch = gc()) tmp /= 10.0, x += tmp * (ch - '0'); if (sign) x = -x; }
inline void read(char& c) { while (!blank(c)) c = gc(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
inline void push(const char& c) { if (pp - out == size) fwrite(out, 1, size, stdout), pp = out; *pp++ = c; }
inline void write(char c) { push(c); }
template<class T>
inline void write(T x) { if (x < 0) x = -x, push('-'); static T sta[35]; T top = 0; do sta[top++] = x % 10, x /= 10; while (x); while (top) push(sta[--top] + '0'); }
template<class T> inline void write(T x, char c) { write(x), push(c); }
template<typename T, typename... Args> inline void write(const T x, const Args... args) { write(x), write(args...); }
};
IO<> io;
struct dsu {
vector<int> f;
dsu(int n) { f.resize(n + 1); iota(f.begin() + 1, f.end(), 1); }
int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }
bool merge(int x, int y) {
x = find(x), y = find(y);
return x == y ? 0 : f[x] = y, 1;
}
void clear() { iota(f.begin(), f.end(), 1); }
};
struct bit {
int n;
vector<ll> c;
bit(int x) : c(n + 1) { n = x; }
void add(int x, ll y) {
for (; x <= n; x += (x & -x)) c[x] += y;
}
ll _ask(int x) {
ll ans = 0;
for (; x; x -= (x & -x)) ans += c[x];
return ans;
}
ll ask(int l, int r) { return _ask(r) - _ask(l - 1); }
};
ll exgcd(ll a, ll b, ll& x, ll& y) {
if (!b) return x = 1, y = 0, a;
ll g = exgcd(b, a % b, y, x);
return y = y - a / b * x, g;
}
constexpr int N = 1e5 + 7;
ll n, a[N], b[N];
int main() {
// mts();
io.read(n);
rep (i, 1, n) io.read(a[i], b[i]);
ll M = 1, ans = 0;
rep (i, 1, n) M *= a[i];
rep (i, 1, n) {
ll m = M / a[i], B, y;
exgcd(m, a[i], B, y);
ans = (ans + b[i] * m * B % M) % M;
}
io.write((ans % M + M) % M);
return 0;
}
字符串
Trie
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 3e6 + 7;
int t[N][65], cnt, end[N];
char a[N];
int id(char c) {
if (c >= 'A' && c <= 'Z') return c - 'A';
else if (c >= 'a' && c <= 'z') return c - 'a' + 26;
else return c - '0' + 52;
}
void clear() {
for (int i = 0; i <= cnt; ++i)
for (int j = 0; j <= 63; ++j)
t[i][j] = 0;
for (int i = 0; i <= cnt; ++i)
end[i] = 0;
cnt = 0;
}
void insert(char* s) {
int len = strlen(s);
int p = 0;
for (int i = 0; i < len; ++i) {
int x = id(s[i]);
if (!t[p][x]) t[p][x] = ++cnt;
p = t[p][x];
++end[p];
}
}
int ask(char *s) {
int len = strlen(s);
int p = 0;
for (int i = 0; i < len; ++i) {
int x = id(s[i]);
if (!t[p][x]) return 0;
p = t[p][x];
}
return end[p];
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
clear();
int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) {
scanf("%s", a);
insert(a);
}
for (int i = 1; i <= q; ++i) {
scanf("%s", a);
printf("%d\n", ask(a));
}
}
return 0;
}
01Trie
#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;
char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) putchar_unlocked(x)
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(T x, Args... args) { print(x), print(args...); }
constexpr int N = 3e5 + 7;
int n;
struct edge {
int to, ne, w;
} e[N << 1];
int cnt, head[N];
void add(int x, int y, int z) { e[++cnt] = {y, head[x], z}, head[x] = cnt; }
int val[N];
void dfs(int x, int fa) {
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to, w = e[i].w;
if (tn == fa) continue;
val[tn] = val[x] ^ w;
dfs(tn, x);
}
}
int nxe[N << 5][2], tot;
void insert(int x) {
int p = 0;
for (int i = 30; i >= 0; --i) {
int k = x >> i & 1;
if (!nxe[p][k]) nxe[p][k] = ++tot;
p = nxe[p][k];
}
}
int calc(int x) {
int ans = 0, p = 0;
for (int i = 30; i >= 0; --i) {
int k = x >> i & 1;
if (nxe[p][k ^ 1]) p = nxe[p][k ^ 1], ans = ans << 1 | (k ^ 1);
else p = nxe[p][k], ans = ans << 1 | k;
}
return ans;
}
signed main() {
read(n);
for (int i = 1, u, v, w; i < n; ++i)
read(u, v, w), add(u, v, w), add(v, u, w);
dfs(1, 0);
for (int i = 1; i <= n; ++i) insert(val[i]);
int res = 0;
for (int i = 1; i <= n; ++i) res = max(res, val[i] ^ calc(val[i]));
print(res);
return 0;
}
KMP
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1e6 + 7;
char a[N], b[N];
auto main()->int {
#ifndef fastio
std::cin.tie(nullptr)->sync_with_stdio(false);
#endif
// freopen("log.txt", "w", stderr);
scanf("%s\n%s", a + 1, b + 1);
int n = strlen(a + 1), m = strlen(b + 1);
std::vector<int> ne(m + 1, 0);
for (int i = 2, j = 0; i <= m; ++i) {
while (j && b[i] != b[j + 1]) {
j = ne[j];
}
if (b[i] == b[j + 1]) {
++j;
}
ne[i] = j;
}
std::vector<int> f(n + 1, 0);
for (int i = 1, j = 0; i <= n; ++i) {
while (j && a[i] != b[j + 1]) {
j = ne[j];
}
if (a[i] == b[j + 1]) {
++j;
}
f[i] = j;
if (f[i] == m) {
j = ne[j];
}
}
for (int i = 1; i <= n; ++i) {
if (f[i] == m) {
printf("%d\n", i - m + 1);
}
}
for (int i = 1; i <= m; ++i) {
printf("%d ", ne[i]);
}
return 0;
}
Manacher
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1.1e7 + 7;
char s[N << 1];
int p[N << 1], cnt = 1, ans;
void read() {
char c = getchar();
s[0] = '~', s[1] = '|';
for (; c < 'a' && c > 'z'; c = getchar());
for (; c >= 'a' && c <= 'z'; c = getchar()) {
s[++cnt] = c, s[++cnt] = '|';
}
}
int main() {
read();
for (int i = 1, r = 0, mid = 0; i <= cnt; ++i) {
if (i <= r) {
p[i] = std::min(p[mid * 2 - i], r - i + 1);
}
for (; s[i - p[i]] == s[i + p[i]]; ++p[i]);
if (p[i] + i > r) {
r = p[i] + i - 1, mid = i;
}
ans = std::max(ans, p[i]);
}
printf("%d\n", ans - 1);
return 0;
}
图论
SPFA 判负环
bool spfa() {
for (int _ = 1; _ <= n; ++_) {
bool fl = 0;
for (int x = 1; x <= n; ++x) {
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to, w = e[i].w;
if (d[i] > d[tn] + w) {
d[i] = d[tn] + w, fl = 1;
}
}
}
if (!fl) break;
}
for (int x = 1; x <= n; ++x) {
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to, w = e[i].w;
if (d[x] > d[tn] + w) return 0;
}
}
return 1;
}
Tarjan缩点
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll read() {
ll x = 0;
#define gc getchar
char c = getchar();
int f = 0;
for (; !isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
#undef gc
return f ? -x : x;
}
template<typename T> void read(T& x) { x = read(); }
template<typename T, typename... Args> void read(T& x, Args&... args) { read(x), read(args...); }
constexpr int N = 1e4 + 7;
constexpr int M = 1e5 + 7;
int n, m;
struct edge {
int fr, to, ne;
} e[M], ee[M];
int cnt, head[N];
void add(int x, int y) {
e[++cnt] = {x, y, head[x]}, head[x] = cnt;
}
int cnte, heade[N];
void adde(int x, int y) {
ee[++cnte] = {x, y, heade[x]}, heade[x] = cnte;
}
int a[N], b[N], low[N], dfn[N], stk[N], top, scc[N], sc, v[N], tot;
void tarjan(int x) {
low[x] = dfn[x] = ++tot, stk[++top] = x, v[x] = 1;
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (!dfn[tn]) {
tarjan(tn);
low[x] = min(low[x], low[tn]);
} else if (v[tn]) {
low[x] = min(low[x], dfn[tn]);
}
}
if (dfn[x] == low[x]) {
++sc;
while (stk[top] != x) {
v[stk[top]] = 0;
b[sc] += a[stk[top]];
scc[stk[top]] = sc;
--top;
}
v[x] = 0;
b[sc] += a[x];
scc[x] = sc;
--top;
}
}
int deg[N], dis[N];
void topo() {
queue<int> q;
for (int i = 1; i <= sc; ++i) if (!deg[i]) q.push(i);
for (int i = 1; i <= sc; ++i) dis[i] = b[i];
while (!q.empty()) {
int x = q.front(); q.pop();
for (int i = heade[x]; i; i = ee[i].ne) {
int tn = ee[i].to;
dis[tn] = max(dis[tn], dis[x] + b[tn]);
if (!--deg[tn]) q.push(tn);
}
}
printf("%d\n", *max_element(dis + 1, dis + n + 1));
}
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(a[i]);
for (int i = 1; i <= m; ++i) {
int u, v;
read(u, v);
add(u, v);
}
for (int i = 1; i <= n; ++i) if (!dfn[i]) tarjan(i);
for (int i = 1; i <= n; ++i)
for (int j = head[i]; j; j = e[j].ne) {
int x = scc[i], y = scc[e[j].to];
if (x != y) adde(x, y), ++deg[y];
}
topo();
return 0;
}
数据结构
分块
int n, m, a[N], pos[N], L[N], R[N];
ll add[N], sum[N];
void init() {
int t = sqrt(n);
for (int i = 1; i <= t; ++i)
L[i] = (i - 1) * sqrt(n) + 1, R[i] = i * sqrt(n);
if (R[t] < n) ++t, L[t] = R[t - 1] + 1, R[t] = n;
for (int i = 1; i <= t; ++i)
for (int j = L[i]; j <= R[i]; ++j)
pos[j] = i, sum[i] += a[j];
}
void upd(int l, int r, ll x) {
int p = pos[l], q = pos[r];
if (p == q) {
for (int i = l; i <= r; ++i) a[i] += x;
sum[p] += x * (r - l + 1);
}
else {
for (int i = p + 1; i <= q - 1; ++i) add[i] += x;
for (int i = l; i <= R[p]; ++i) a[i] += x;
sum[p] += x * (R[p] - l + 1);
for (int i = L[q]; i <= r; ++i) a[i] += x;
sum[q] += x * (r - L[q] + 1);
}
}
ll ask(int l, int r) {
int p = pos[l], q = pos[r]; ll ans = 0;
if (p == q) {
for (int i = l; i <= r; ++i) ans += a[i];
ans += add[p] * (r - l + 1);
} else {
for (int i = p + 1; i <= q - 1; ++i)
ans += sum[i] + add[i] * (R[i] - L[i] + 1);
for (int i = l; i <= R[p]; ++i) ans += a[i];
ans += add[p] * (R[p] - l + 1);
for (int i = L[q]; i <= r; ++i) ans += a[i];
ans += add[q] * (r - L[q] + 1);
}
return ans;
}
树链剖分
如果需要边权转点权:a[tn] = w 询问的最后一行改成 query(1, 1, tot, loc[x] + 1, loc[y])
#include <bits/stdc++.h>
#define int ll
using namespace std;
using ll = long long;
int n, m, r, P, a[100007];
struct edge{
int to, ne;
} e[200007];
int cnt, head[100007];
void add(int x, int y) {
e[++cnt] = {y, head[x]}, head[x] = cnt;
}
int f[100007], dep[100007], sz[100007], son[100007];
void dfs1(int x, int fa) {
dep[x] = dep[f[x] = fa] + (sz[x] = 1);
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (tn == fa) continue;
dfs1(tn, x);
sz[x] += sz[tn];
if (sz[son[x]] < sz[tn]) son[x] = tn;
}
}
int loc[100007], tot, id[100007], top[100007];
void dfs2(int x, int tp) {
top[x] = tp, id[loc[x] = ++tot] = x;
if (!son[x]) return;
dfs2(son[x], tp);
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (tn == son[x] || tn == f[x]) continue;
dfs2(tn, tn);
}
}
int su[400007], ad[400007];
void pushup(int p) {
su[p] = (su[p << 1] + su[p << 1 | 1]) % P;
}
void pushdown(int p, int l, int r) {
if (!ad[p]) return;
int mid = l + r >> 1;
ad[p << 1] += ad[p], ad[p << 1 | 1] += ad[p];
su[p << 1] += ad[p] * (mid - l + 1);
su[p << 1 | 1] += ad[p] * (r - mid);
ad[p] = 0;
}
void build(int p, int l, int r) {
if (l == r) {
su[p] = a[id[l]] % P;
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
pushup(p);
}
void modify(int p, int l, int r, int L, int R, int v) {
if (L <= l && R >= r) {
(ad[p] += v) %= P;
(su[p] += v * (r - l + 1)) %= P;
return;
}
pushdown(p, l, r);
int mid = l + r >> 1;
if (L <= mid) modify(p << 1, l, mid, L, R, v);
if (R > mid) modify(p << 1 | 1, mid + 1, r, L, R, v);
pushup(p);
}
int query(int p, int l, int r, int L, int R) {
if (L <= l && R >= r) return su[p] % P;
pushdown(p, l, r);
int mid = l + r >> 1, ans = 0;
if (L <= mid) (ans += query(p << 1, l, mid, L, R)) %= P;
if (R > mid) (ans += query(p << 1 | 1, mid + 1, r, L, R)) %= P;
return ans % P;
}
void upd(int x, int y, int v) {
while (top[x] != top[y]) {
if (dep[f[top[x]]] < dep[f[top[y]]]) swap(x, y);
modify(1, 1, tot, loc[top[x]], loc[x], v);
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
modify(1, 1, tot, loc[x], loc[y], v);
}
int sum(int x, int y) {
int res = 0;
while (top[x] != top[y]) {
if (dep[f[top[x]]] < dep[f[top[y]]]) swap(x, y);
(res += query(1, 1, tot, loc[top[x]], loc[x])) %= P;
x = f[top[x]];
}
if (dep[x] > dep[y]) swap(x, y);
(res += query(1, 1, tot, loc[x], loc[y])) %= P;
return res;
}
int lca(int x, int y) {
while (top[x] != top[y]) {
if (dep[top[x]] < dep[top[y]]) swap(x, y);
x = f[top[x]];
}
return dep[x] < dep[y] ? x : y;
}
signed main() {
// freopen("1.in", "r", stdin);
scanf("%lld %lld %lld %lld", &n, &m, &r, &P);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1, u, v; i < n; ++i) {
scanf("%lld %lld", &u, &v);
add(u, v), add(v, u);
}
dfs1(r, 0), dfs2(r, r);
build(1, 1, tot);
for (int i = 1, opt, x, y, z; i <= m; ++i) {
scanf("%lld", &opt);
if (opt == 1) {
scanf("%lld %lld %lld", &x, &y, &z);
upd(x, y, z);
} else if (opt == 2) {
scanf("%lld %lld", &x, &y);
printf("%lld\n", sum(x, y));
} else if (opt == 3) {
scanf("%lld %lld", &x, &z);
modify(1, 1, tot, loc[x], loc[x] + sz[x] - 1, z % P);
} else {
scanf("%lld", &x);
printf("%lld\n", query(1, 1, tot, loc[x], loc[x] + sz[x] - 1) % P);
}
}
return 0;
}
离散二维数点
求序列的区间 [l, r] 内小于等于 x 的数的个数
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char buf[1 << 20], *p1 = buf, *p2 = buf, obuf[1 << 20], *p3 = obuf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
#define putc(x) (p3 - obuf < (1 << 20) ? (*p3++ = x) : (fwrite(obuf, p3 - obuf, 1, stdout), p3 = obuf, *p3++=x))
inline ll read() {
ll x = 0, sgn = 0; char s = getc();
while(!isdigit(s)) sgn |= s == '-', s = getc();
while(isdigit(s)) x = x * 10 + s - '0', s = getc();
return sgn ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if (x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(T x, Args... args) { print(x), print(args...); }
constexpr int N = 2e6 + 7;
struct qq {
int id, k, x, val;
bool operator<(qq r) const { return k < r.k; }
} q[N << 1];
int n, m, a[N], mx, c[N], ans[N], cnt;
void add(int x) {
for (; x <= mx; x += x & -x) ++c[x];
}
int qry(int x) {
int ans = 0;
for (; x; x -= x & -x) ans += c[x];
return ans;
}
int main() {
read(n, m);
for (int i = 1; i <= n; ++i) read(a[i]), mx = max(a[i], mx);
for (int i = 1, l, r, x; i <= m; ++i) {
read(l, r, x);
q[++cnt] = {i, l - 1, x, -1};
q[++cnt] = {i, r, x, 1};
mx = max(x, mx);
}
sort(q + 1, q + cnt + 1);
for (int i = 1, pos = 1; i <= cnt; ++i) {
for (; pos <= q[i].k; ++pos) add(a[pos]);
ans[q[i].id] += q[i].val * qry(q[i].x);
}
for (int i = 1; i <= m; ++i) print(ans[i]), putc('\n');
fwrite(obuf, p3 - obuf, 1, stdout);
return 0;
}
莫队
区间询问数字出现次数平方和
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k, B, res, ans[50007], a[50007], cnt[50007];
struct Q {
int id, l, r;
bool operator<(Q x) {
return (l / B == x.l / B) ? (r == x.r ? 0 : ((l / B) & 1) ^ (r < x.r)) : l < x.l;
}
} que[50007];
void add(int val) {
res -= cnt[val] * cnt[val];
++cnt[val];
res += cnt[val] * cnt[val];
}
void del(int val) {
res -= cnt[val] * cnt[val];
--cnt[val];
res += cnt[val] * cnt[val];
}
int main() {
scanf("%d %d %d", &n, &m, &k);
B = sqrt(m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &que[i].l, &que[i].r);
que[i].id = i;
}
sort(que + 1, que + m + 1);
for (int i = 1, l = 1, r = 0; i <= m; ++i) {
while (l > que[i].l) add(a[--l]);
while (r < que[i].r) add(a[++r]);
while (l < que[i].l) del(a[l++]);
while (r > que[i].r) del(a[r--]);
ans[que[i].id] = res;
}
for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
return 0;
}
带修莫队
单点修改, 询问区间去重后数的个数
注意块长
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
char buf[1 << 20], *p1 = buf, *p2 = buf;
#define getc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
char obuf[1 << 20], *O = obuf;
#define putc(x) *O++ = x
ll read() {
ll x = 0;
char c = getc();
int f = 0;
for (; !isdigit(c); c = getc()) f |= c == '-';
for (; isdigit(c); c = getc()) x = x * 10 + c - '0';
return f ? -x : x;
}
template<typename T> inline void read(T& x) { x = read(); }
template<typename T, typename... Args> inline void read(T& x, Args&... args) { read(x), read(args...); }
template<typename T> inline void print(T x) { if (x < 0) x = -x, putc('-'); if(x >= 10) print(x / 10); putc(x % 10 + '0'); }
template<typename T, typename... Args> inline void print(T x, Args... args) { print(x), print(args...); }
constexpr int N = 2e6 + 7;
int n, m, B;
struct que {
int l, r, t, id;
bool operator<(que x) {
return l / B == x.l / B ? (r / B == x.r / B ? t < x.t : r < x.r) : l < x.l;
}
} q[N];
struct mod {
int p, col;
} c[N];
int a[N], res[N], ans, cnt[N];
char op[5];
void add(int val) {
ans += !cnt[val]++;
}
void del(int val) {
ans -= !--cnt[val];
}
void modify(int x, int ti) {
if (c[ti].p >= q[x].l && c[ti].p <= q[x].r) {
del(a[c[ti].p]);
add(c[ti].col);
}
swap(a[c[ti].p], c[ti].col);
}
int main() {
scanf("%d %d", &n, &m);
B = pow(n, 2.0 / 3.0);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
int tq = 0, tc = 0;
for (int i = 1; i <= m; ++i) {
scanf("%s", op);
if (op[0] == 'Q') {
++tq;
scanf("%d %d", &q[tq].l, &q[tq].r);
q[tq].t = tc, q[tq].id = tq;
} else {
++tc;
scanf("%d %d", &c[tc].p, &c[tc].col);
}
}
sort(q + 1, q + tq + 1);
for (int i = 1, l = 1, r = 0, ti = 0; i <= tq; ++i) {
while (l > q[i].l) add(--l);
while (r < q[i].r) add(++r);
while (l < q[i].l) del(a[l++]);
while (r > q[i].r) del(a[r--]);
while (ti < q[i].t) modify(i, ++ti);
while (ti > q[i].t) modify(i, ti--);
res[q[i].id] = ans;
}
for (int i = 1; i <= tq; ++i) printf("%d\n", res[i]);
fwrite(obuf, O - obuf, 1, stdout);
return 0;
}
DSU on tree
求树上两点之间出现最多的颜色
// LUOGU_RID: 130257582
#include <bits/stdc++.h>
#define int ll
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (b); i >= (a); ++i)
#define go(x) for (int i = head[x], tn = e[i].to; i; i = e[i].ne, tn = e[i].to)
using ll = long long;
struct edge {
int to, ne;
};
signed main() {
// freopen("log.txt", "w", stderr);
int n;
scanf("%lld", &n);
std::vector<int> col(n + 1, 0);
rep (i, 1, n) scanf("%lld", &col[i]);
int _cnt = 0;
std::vector<edge> e = {{0, 0}};
std::vector<int> head(n + 1, 0);
auto add = [&](int x, int y) {
e.push_back({y, head[x]}), head[x] = ++_cnt;
};
rep (i, 1, n - 1) {
int x, y;
scanf("%lld %lld", &x, &y);
add(x, y), add(y, x);
}
int dfn = 0;
std::vector<int> sz(n + 1, 0), son(n + 1, 0);
std::vector<int> L(n + 1, 0), R(n + 1, 0), loc(n + 1, 0);
auto preDfs = [&](auto self, int x, int fa) -> void {
L[x] = ++dfn;
loc[dfn] = x;
sz[x] = 1;
go(x) {
if (tn == fa) continue;
self(self, tn, x);
sz[x] += sz[tn];
if (!son[x] || sz[son[x]] < sz[tn]) son[x] = tn;
}
R[x] = dfn;
};
preDfs(preDfs, 1, -1);
std::vector<int> cnt(n + 1, 0);
std::vector<int> res(n + 1, 0);
int ans = 0, mx = 0;
auto ad = [&](int u) {
++cnt[col[u]];
if (cnt[col[u]] == mx) ans += col[u];
else if (cnt[col[u]] > mx)
mx = cnt[col[u]], ans = col[u];
};
auto de = [&](int u) {
if (cnt[col[u]] == mx) ans -= col[u];
--cnt[col[u]];
};
auto calc = [&]() {
return ans;
};
auto dfs = [&](auto self, int x, int fa, bool ke) -> void {
go(x) {
if (tn == fa || tn == son[x]) continue;
self(self, tn, x, false);
}
if (son[x]) self(self, son[x], x, true);
go(x) {
if (tn == fa || tn == son[x]) continue;
rep (i, L[tn], R[tn]) ad(loc[i]);
}
ad(x);
res[x] = calc();
if (!ke) {
rep (i, L[x], R[x]) de(loc[i]);
ans = mx = 0;
}
};
dfs(dfs, 1, -1, false);
rep (i, 1, n) printf("%lld ", res[i]);
return 0;
}
线段树合并
给定一棵树,每次操作:给两点之间的所有点的集合加上一个数,或者询问
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct node {
int l, r;
int val, id;
#define l(p) tr[p].l
#define r(p) tr[p].r
#define val(p) tr[p].val
#define id(p) tr[p].id
} tr[100007 * 300];
int n, m, tot, root[100007];
int insert(int now, int x, int v, int l = 1, int r = 1e5) {
int p = ++tot;
tr[p] = tr[now];
if (l == r) {
val(p) += v;
id(p) = l;
return p;
}
int mid = l + r >> 1;
if (x <= mid) l(p) = insert(l(now), x, v, l, mid);
else r(p) = insert(r(now), x, v, mid + 1, r);
if (val(l(p)) >= val(r(p))) val(p) = val(l(p)), id(p) = id(l(p));
else val(p) = val(r(p)), id(p) = id(r(p));
return p;
}
int merge(int a, int b, int l = 1, int r = 1e5) {
if (!a) return b;
if (!b) return a;
if (l == r) {
val(a) += val(b);
id(a) = l;
return a;
}
int mid = l + r >> 1;
l(a) = merge(l(a), l(b), l, mid);
r(a) = merge(r(a), r(b), mid + 1, r);
if (val(l(a)) >= val(r(a))) val(a) = val(l(a)), id(a) = id(l(a));
else val(a) = val(r(a)), id(a) = id(r(a));
return a;
}
struct edge {
int to, ne;
} e[100007 * 2];
int cnt, dfn, eul[100007 * 2], loc[100007], f[100007], dep[100007], head[100007];
void preDfs(int x, int fa) {
eul[++dfn] = x, loc[x] = dfn, f[x] = fa, dep[x] = dep[fa] + 1;
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (tn == fa) continue;
preDfs(tn, x);
eul[++dfn] = x;
}
}
int mn[100007 * 8];
void build(int p, int l, int r) {
if (l == r) {
mn[p] = eul[l];
return;
}
int mid = l + r >> 1;
build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
mn[p] = dep[mn[p << 1]] < dep[mn[p << 1 | 1]] ? mn[p << 1] : mn[p << 1 | 1];
}
int ask(int l, int r, int p = 1, int L = 1, int R = dfn) {
if (L > r || R < l) return -1;
if (L >= l && R <= r) return mn[p];
int mid = L + R >> 1;
int lans = ask(l, r, p << 1, L, mid);
int rans = ask(l, r, p << 1 | 1, mid + 1, R);
if (lans == -1 || rans == -1) return lans + rans + 1;
return dep[lans] < dep[rans] ? lans : rans;
}
int lca(int x, int y) {
int l = loc[x], r = loc[y];
if (l > r) swap(l, r);
return ask(l, r);
}
int ans[100007];
void dfs(int x, int fa) {
for (int i = head[x]; i; i = e[i].ne) {
int tn = e[i].to;
if (tn == fa || dep[tn] <= dep[x]) continue;
dfs(tn, x);
root[x] = merge(root[x], root[tn]);
}
if (val(root[x])) ans[x] = id(root[x]);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, x, y; i < n; ++i) {
scanf("%d %d", &x, &y);
e[++cnt] = {y, head[x]}, head[x] = cnt;
e[++cnt] = {x, head[y]}, head[y] = cnt;
}
preDfs(1, 0);
build(1, 1, dfn);
for (int i = 1, x, y, z; i <= m; ++i) {
scanf("%d %d %d", &x, &y, &z);
int lc = lca(x, y);
root[x] = insert(root[x], z, 1), root[y] = insert(root[y], z, 1);
root[lc] = insert(root[lc], z, -1);
if (f[lc]) root[f[lc]] = insert(root[f[lc]], z, -1);
}
dfs(1, 0);
for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
return 0;
}
科技
集合哈希
ha/hb/hc 表示前 k 个元素组成的集合的哈希值
struct randomhash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
class SetHasher {
unordered_map<int, ull, randomhash> elemHash;
mt19937_64 rng;
public:
SetHasher():rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull getelemhash(const int &elem) {
if (!elemHash.count(elem)) {
elemHash[elem] = rng();
}
return elemHash[elem];
}
ull computexorhash(const vector<int> &elem) {
ull x = 0;
for (const auto &e: elem) {
x ^= getelemhash(e);
}
return x;
}
ull add(ull curhash, const int &elem) {
return curhash ^ getelemhash(elem);
}
};
void solve(){
SetHasher sh;
int n; cin >> n;
vector<int> a(n + 1, 0), b(n + 1, 0), c(n + 1,0);
vector<int> ma, mb, mc;
ma.reserve(n);
mb.reserve(n);
mc.reserve(n);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
for (int i = 1; i <= n; i++) cin >> c[i];
int cnt = 0;
ull ha = 0, hb = 0, hc = 0;
for (int i = 1; i <= n; i++){
ha = sh.add(ha, a[i]);
hb = sh.add(hb, b[i]);
hc = sh.add(hc, c[i]);
if(ha == hb || ha == hc || hb == hc){
cnt++;
}
}
cout << cnt << '\n';
}
防卡 unordered_map
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
区间最远互质点对
for (ll len = r - l; len >= 0; --len)
for (ll i = l; i <= r - len; ++i)
if (__gcd(i, i + len) == 1)