Template
DoctorBobo · · 个人记录
1. 头部&宏定义
#include<bits/stdc++.h>
#define rg register
#define For(i, a, b) for(int (i) = (a); (i) <= (b); (i)++)
#define FOR(i, a, b) for(int (i) = (a); (i) >= (b); (i)--)
#define acl() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define fix(i) cout << fixed << setprecision(i)
#define pb push_back
#define lson (p << 1)
#define rson (p << 1 | 1)
using namespace std;
using i64 = long long;
using d64 = long double;
using pii = std::pair<int, int>;
using pll = std::pair<i64, i64>;
inline int read(){
int x = 0, f = 0;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = 1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + c - 48;
c = getchar();
}
return f ? -x : x;
}
void solve();
int main() {
acl();
int t = 1;
//cin >> t;
while(t--) solve();
return 0;
}2.链式前行星建边和删边
struct Edge {int nxt, to, w, *from;};
cin >> n >> m; tot = 1;//tot starts from 2
std::vector<Edge> e(m * 2 + 2);
std::vector<int> head(n + 1, 0);
auto add_edge = [&](int u, int v, int w)->void {
e[++tot] = {head[u], v, w, &head[u]};
if(head[u]) e[head[u]].from = &e[tot].nxt;
head[u] = tot;
};
auto dlt_edge = [&](int u)->void {
*e[u].from = e[u].nxt;
if(e[u].nxt) e[e[u].nxt].from = e[u].from;
e[u].from = NULL;
};3.用链式前向星跑欧拉回路（存在欧拉回路）
std::vector<int> st, head(n + 1, 0);
auto Euler = [&](auto self, int u)->void {
for(int i = head[u]; e[i].from != NULL; i = head[u]) {
head[u] = e[i].nxt;
int v = e[i].to;
dlt_edge(i), dlt_edge(i ^ 1);
self(self, v);
} st.pb(u);
//self loop : while(sum[u]) st.pb(u), sum[u]--;
};Euler(Euler, 1);
cout << "YES\n" << st.size() - 1 << '\n';
reverse(st.begin(), st.end());
for(int i = 0 ; i < (ll)st.size(); i++)
cout << st[i] << " \n"[i == st.size() - 1];4.二分图匹配的匈牙利算法
int n, m, e, ans = 0;
std::vector<int> dfn(n + 1, 0), match(m + 1, 0);
cin >> n >> m >> e;
for(int i = 1; i <= e; i++) {
int u, v;
cin >> u >> v;
edge[u].pb(v);
}
auto dfs = [&](auto self, int u, const int tag)->bool {
if(dfn[u] == tag) return false;
dfn[u] = tag;
for(auto v : edge[u]) if(!match[v] || self(self, match[v], tag)) {
match[v] = u;
return true;
} return false;
};
for(int i = 1; i <= n; i++) ans += dfs(dfs, i, i);
cout << ans;5.权值线段树动态开点
namespace VST {
using ll = long long;
struct vst {int v, ls, rs; ll s;};
int tot = 0;//value-SegmentTree, s = sum
void push_up(std::vector<vst> &tree, int p) {
tree[p].v = tree[tree[p].ls].v + tree[tree[p].rs].v;
}
void change(std::vector<vst> &tree, int lp, int &p, int l, int r, int q, int v) {
if(!p) p = ++tot;// build nodes dynamically
if(l == r) {
tree[p].v += v;
return;
}
int mid = l + r >> 1;
if(q <= mid) {
tree[p].rs = tree[lp].rs;
tree[p].ls = ++tot;
tree[tree[p].ls] = tree[tree[lp].ls];
change(tree, tree[lp].ls, tree[p].ls, l, mid, q, v);
}
else {
tree[p].ls = tree[lp].ls;
tree[p].rs = ++tot;
tree[tree[p].rs] = tree[tree[lp].rs];
change(tree, tree[lp].rs, tree[p].rs, mid + 1, r, q, v);
}
push_up(tree, p);
}
void update(std::vector<vst> &tree, int &p, int l, int r, int q, int v) {
if(!p) p = ++tot;// build nodes dynamically
tree[p].v += v;
tree[p].s += v * q;
if(l == r) return;
int mid = l + r >> 1;
if(q <= mid) change(tree, tree[p].ls, l, mid, q, v);
else change(tree, tree[p].rs, mid + 1, r, q, v);
push_up(tree, p);
}
int query_kth(std::vector<vst> &tree, int p1, int p2, int l, int r, int q) {
if(l == r) return l;
int mid = l + r >> 1, tmp = tree[tree[p2].ls].v - tree[tree[p1].ls].v;
if(q <= tmp) return query_kth(tree, tree[p1].ls, tree[p2].ls, l, mid, q);
else return query_kth(tree, tree[p1].rs, tree[p2].rs, mid + 1, r, q - tmp);
}
int query_sum(std::vector<vst> &tree, int p, int l, int r, ll sum) {
if(l == r) return (sum <= 0 ? 0 : (sum + l - 1) / l);
int mid = l + r >> 1;
if(tree[tree[p].rs].s >= sum)
return query_sum(tree, tree[p].rs, mid + 1, r, sum);
else
return query_sum(tree, tree[p].ls, l, mid, sum - tree[tree[p].rs].s) + tree[tree[p].rs].v;
}
void insert(std::vector<vst> &tree, std::vector<int> &node, std::vector<int> &rank, int &root, int n, int cnt) {
std::sort(rank.begin() + 1, rank.begin() + 1 + cnt);
cnt = std::unique(rank.begin(), rank.begin() + 1 + cnt) - rank.begin() - 1;
for(int i = 1; i <= n; i++) {
node[i] = std::lower_bound(rank.begin() + 1, rank.begin() + 1 + cnt, node[i]) - rank.begin();
change(tree, root, 1, cnt, node[i], 1);
}
}
}6.ST表
namespace ST {
using i64 = long long;
void prepare_gcd(int n, std::vector<int> &a, std::vector<int> &Log, std::vector<vector<int>> &st) {
for(int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
for(int j = 0; j <= Log[n]) st[j].resize(2 * n + 2);
st[0] = a;
for(int j = 1; j <= Log[n]; j++) for(int i = 1; i <= n; i++)
st[j][i] = __gcd(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int query_gcd(i64 l, i64 r, std::vector<int> &Log, std::vector<vector<int>> &st) {
int k = Log[r - l + 1];
return __gcd(st[k][l], st[k][r - (1 << k) + 1]);
}
void prepare_min(int n, std::vector<int> &a, std::vector<int> &Log, std::vector<vector<int>> &st) {
for(int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
for(int j = 0; j <= Log[n]) st[j].resize(2 * n + 2);
st[0] = a;
for(int j = 1; j <= Log[n]; j++) for(int i = 1; i <= n; i++)
st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}
int query_min(i64 l, i64 r, std::vector<int> &Log, std::vector<vector<int>> &st) {
int k = Log[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
}7.数学
using i64 = long long;
using i128 = __int128;
namespace MATH {
using std::gcd;
using std::lcm;
using std::min;
using std::max;
using i64 = long long;
using d64 = long double;
using i128 = __int128;
using pii = std::pair<int, int>;
using pII = std::pair<std::vector<int>, std::vector<int>>;
using pll = std::pair<i64, i64>;
using pLL = std::pair<std::vector<i64>, std::vector<i64>>;
using fdd = std::function<double(double)>;
constexpr int MAXN = 1e8 + 10;
constexpr int maxn = 1e6 + 10;
constexpr int mod = 998244353;
constexpr int N = 2e5 + 10000;
constexpr double eps = 1e-9;
constexpr d64 EPS = 1e-18;
std::vector<int> phi, prime, ind;
i64 qpow(i64 a, i64 b, i64 p) {
i64 ans = 1ll % p;
for(; b != 0; b >>= 1) {
if(b & 1) ans = (i128)ans * a % p;
a = (i128)a * a % p;
}
return ans;
}
i64 qmul(i64 x, i64 y, i64 p) {
i64 ans = 0; x %= p, y %= p;
for(; y != 0; y >>= 1) {
if(y & 1) ans = (ans + x) % p;
x = (x + x) % p;
}
return ans;
}
i64 qmod(i64 x, i64 p) {
if(x >= p) return x - p;
else return x;
}
i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) {
if(!b) return x = 1, y = 0, a;
i64 g = exgcd(b, a % b, y, x);
y = y - (a / b) * x; return g;
}
i64 congruence(i64 a, i64 b, i64 m) { // ax≡b(mod m)
i64 x, y, d = exgcd(a, m, x, y);
if(b % d) return -1;
else m = m / d;
return ((i128)x * (b / d) % m + m) % m;
}
i64 invmod(i64 a, i64 p) {
return congruence(a, 1ll, p);
}
i64 CRT(std::vector<i64> &r, std::vector<i64> &a) {
i128 n = 1, ans = 0;
int k = a.size();
for(auto x : r) n *= x;
for(int i = 0; i < k; i++) {
i128 m = n / r[i]; i64 R, y;
exgcd(m % r[i], r[i], R, y);
ans = (ans + (i128)a[i] * m % n * R % n) % n;
}
i64 res = (ans % n + n) % n;
return res;
}
i64 exCRT(std::vector<i64> &r, std::vector<i64> &a) {
i128 A = a[0]; i64 R = r[0];
for(int i = 1; i < (int)r.size(); i++) {
i64 p = a[i], q = r[i];
i64 x = congruence(R, (p - A) % q, q);
if(x == -1) return -1;
A += (i128)R * x;
R = std::lcm(R, q);
A %= R; if(A < 0) A += R;
}
return (A % R + R) % R;
}
i64 getphi(int n) { // phi(n)
i64 ans = 1;
for(int i = 2; i * i <= n; ++i) {
if(n % i != 0) continue;
ans *= i - 1, n /= i;
while(!(n % i)) ans *= i, n /= i;
}
if(n > 1) return ans * (n - 1);
else return ans;
}
i64 exEuler(i64 a, std::string b, i64 m) {
// a^b mod m = a^(b mod phim + phim) mod m (b >= phim)
i64 f = 0, phim = getphi(m), B = 0; // B = b mod m
for(auto &c : b) {
B = 10ll * B + c - '0';
if(B >= phim) f = 1, B %= phim; // f == 1 -> b >= phim
}
B += f ? phim : 0;
return qpow(a, B, m);
}
void EulerSieve(int n) {
phi.clear(), prime.clear();
std::vector<int> vis(n + 2, 0);
phi.resize(n + 2), prime.resize(n + 1);
int cnt = 0; phi[1] = 1;
for(int i = 2; i <= n + 1; i++) {
if(!vis[i]) prime[++cnt] = i, phi[i] = i - 1;
for(int j = 1; i * prime[j] <= n + 1 && j <= cnt; j++) {
vis[i * prime[j]] = true;
if(i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else phi[i * prime[j]] = phi[i] * phi[prime[j]];
}
}
}
int MPR(int n, int p, int l = 1, int r = 50) { // minimum primitive root
int q = p; // EulerSieve first, p = phi[n]
std::vector<int> pri;
for(int i = 2; i * i <= q; i++) {
if(q % i == 0) pri.push_back(i);
while(q % i == 0) q /= i;
} if(q > 1) pri.push_back(q);
auto check = [&](int i) -> bool {
if(MATH::qpow(i, p, n) != 1) return 0;
for(auto j : pri)
if(MATH::qpow(i, p / j, n) == 1)
return 0;
return 1;
};
for(int i = l; i <= r; i++) // n^0.25
if(check(i)) return i;
return 0;
}
i64 BSGS(i64 a, i64 b, i64 p) { // a^x ≡ b (mod p) x = min
a %= p, b %= p;
if(b == 1) return 0ll;
i64 m = ceil(sqrt(p));
std::unordered_map<i64, i64> hash;
for(i64 j = 0; j < m; j++) {
hash[b] = j; // non-decreasing
b = (i128)b * a % p;
} // x = m * i - j, (a^m)^i ≡ ba^j (mod p)
i64 M = qpow(a, m, p), A = 1ll; // M = a^m, A = (a^m)^i
for(i64 i = 1; i <= m; i++) {
A = (i128)A * M % p;
if(hash.count(A)) {
i64 ans = i * m - hash[A];
if(ans >= 0) return ans;
}
}
return -1;
}
i64 exBSGS(i64 a, i64 b, i64 p) { // gcd(a,p)!=1
a %= p, b %= p;
if(b == 1 || p == 1) return 0;
i64 k = 0, d, A = 1ll;
while((d = gcd(a, p)) != 1) {
if(b % d) return -1;
++k, b /= d, p /= d;
A = (i128)A * (a / d) % p; // (a^k)/D
if(A == b) return k;
}
b = (i128)b * invmod(A, p) % p;
i64 ans = BSGS(a, b, p);
if(ans == -1) return -1;
else return ans + k;
}
void IndSieve(i64 g, i64 p) { // g has to be p's primitive root
i64 B = sqrt(p * sqrt(p) / log(p)); // Block size
std::unordered_map<i64, i64> hash;
i64 w = invmod(qpow(g, B, p), p);
i64 n = sqrt(p) + 1, Phi = p - 1; // p is prime
prime.clear(); prime.resize(n + 2);
ind.clear(); ind.resize(n + 2);
std::vector<i64> vis(n + 2, 0);
for(i64 i = 0ll, j = 1ll; i < B; i++) {
hash[j] = i, j = (i128)j * g % p;
}
auto bsgs = [&](i64 a) -> i64 { // BSGS
for(int i = 0; i <= p / B; i++) {
if(hash.count(a)) return i * B + hash[a];
a = (i128)a * w % p;
}
return -1;
};
ind[1] = 0, ind[0] = bsgs(p - 1);
for(int i = 2, cnt = 0; i <= n; i++) {
if(!vis[i]) prime[++cnt] = i, ind[i] = bsgs(i);
for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
i64 k = prime[j]; vis[i * k] = 1;
ind[i * k] = qmod(ind[i] + ind[k], Phi);
if(i % k == 0) break;
}
}
}
i64 Ind(i64 a, i64 p) { // Discrete Log
i64 lim = sqrt(p) + 1;
if(a <= lim) return ind[a];
i64 b = p / a, c = p % a, Phi = p - 1;
if(c < a - c) return qmod(qmod(ind[0] + Ind(c, p), Phi) - ind[b] + Phi, Phi);
else return qmod(Ind(a - c, p) - ind[b + 1] + Phi, Phi);
}
i64 conv(i64 a, i64 h, i64 p) { // convert to base h:ind_h(a)
// M = getphi(p), t = ind_g(a), k = ind_g(h)
i64 M = p - 1; // prime || p^(k-1)(p-1)
i64 t = Ind(a, p);
i64 k = Ind(h, p);
return congruence(k, t, M);
}
i64 DSM(i64 n, i64 k, int flag = 0) {
// Divisor Summatory Method
// sum(i*floor(n/i),i=1~n,k=n)=sum(f(i),i=1~n), f(i)=sum(divisors of i)
// f(x)+f(x+1)+...f(y)=DSM(y,y)-DSM(x-1,x-1)=(1~y)-(1~(x-1))
i64 l, r, t, ans = 0ll;
if(flag == 0) for(l = 1; l <= n; l = r + 1) {
t = k / l; if(!t) break;
r = min(n, k / t);
ans += t * (l + r) * (r - l + 1) / 2ll;
}
if(flag == 1) for(l = 1; l <= n; l = r + 1) { // sum(floor(k/i),i=1~n)
t = k / l; if(!t) break;
r = min(n, k / t);
ans += t * (r - l + 1);
}
/*
// sum(C*floor(n1/i)*floor(n2/i)...*floor(nk/i),i=1~min({nj},j=1~k))
for(l = 1; l <= min{n_1,n_2...n_k}; l = r + 1) {
i = 1~k, t_i = n_i / l; if(!t_i) break;
i = 1~k, r = min({n_i / t_i});
ans += prod(t_i,i=1~k) * (sum of coefficients)
}
*/
return ans;
}
double newton(fdd f, fdd df, double x0) {
// function f(x)=y
// f(x) = f(x0) + f'(x0)(x - x0) + o = 0
// x = x0 - f(x0) / f'(x0)
double x = x0; int maxIter = 1000;
for(int i = 0; i < maxIter; i++) {
double fx = f(x);
double dfx = df(x);
if(fabs(fx) < eps) break;
if(fabs(dfx) < eps) return nan("");
x = x - fx / dfx;
}
return x;
}
double fixn(double tar, int n = 2) {
d64 p = std::pow(10.0L, n);
d64 v = (d64)tar * p + ((tar > 0) ? 0.5L : -0.5L);
i64 iv = (i64)(v);
d64 res = (d64)iv / p;
return (double)res;
}
struct matrix { // 1-based index(start from 1 not 0)
static const int MOD = 1e9 + 7;
std::vector<std::vector<int>> G; int N;
matrix(int n = 0) {N = n; G.assign(n + 1, std::vector<int>(n + 1, 0));}
matrix(const matrix &other) {
N = other.N;
G = other.G;
}
inline void clear() {for(auto &row : G) fill(row.begin(), row.end(), 0);}
inline int size() const {return (int)G.size() - 1;}
friend matrix operator * (const matrix &a, const matrix &b) {
int n = a.N; matrix c(n);
for(int i = 1; i <= n; i++) for(int k = 1; k <= n; k++)
if(a.G[i][k]) for(int j = 1; j <= n; j++)
c.G[i][j] = (c.G[i][j] + 1ll * a.G[i][k] * b.G[k][j] % MOD) % MOD;
return c;
}
friend bool operator == (const matrix &a, const matrix &b) {
int n = a.N, m = b.N;
if(n != m) return false;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
if(a.G[i][j] != b.G[i][j]) return false;
}
return true;
}
friend bool operator != (const matrix &a, const matrix &b) {
return !(a == b);
}
friend matrix operator + (const matrix &a, const matrix &b) {
int n = a.N; matrix c(n);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++)
c.G[i][j] = (a.G[i][j] + b.G[i][j]) % MOD;
return c;
}
friend matrix operator - (const matrix &a, const matrix &b) {
int n = a.N; matrix c(n);
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
c.G[i][j] = (a.G[i][j] - b.G[i][j]) % MOD;
if(c.G[i][j] < 0) c.G[i][j] += MOD;
}
return c;
}
matrix& operator = (const matrix &other) {
if(this != &other) G = other.G;
return *this;
}
friend std::istream & operator >> (std::istream &in, matrix &m) {
int n = m.N;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
in >> m.G[i][j];
m.G[i][j] %= MOD;
}
}
return in;
}
friend std::ostream & operator << (std::ostream &out, const matrix &m) {
int n = m.N;
for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) {
out << m.G[i][j] << (j == n ? '\n' : ' ');
}
return out;
}
inline matrix mpow(i64 p) {
int n = N; matrix res(n);
for(int i = 1; i <= n; i++) res.G[i][i] = 1;
matrix base = *this;
while(p != 0) {
if(p & 1) res = res * base;
base = base * base;
p >>= 1;
}
return *this = res;
}
matrix inv() const {
int n = N; matrix A = *this, I(n), U(0);
for(int i = 1; i <= n; i++) I.G[i][i] = 1;
for(int i = 1; i <= n; i++) {
int pivot = i;
for(int j = i; j <= n; j++) if(A.G[j][i] != 0) {
pivot = j; break;
}
if(A.G[pivot][i] == 0) {
std::cout << "No Solution\n";
return U;
}
if(pivot != i) {
std::swap(A.G[i], A.G[pivot]);
std::swap(I.G[i], I.G[pivot]);
}
i64 inv_pivot = qpow(A.G[i][i], MOD - 2, MOD);
for(int j = 1; j <= n; j++) {
A.G[i][j] = 1LL * A.G[i][j] * inv_pivot % MOD;
I.G[i][j] = 1LL * I.G[i][j] * inv_pivot % MOD;
}
for(int r = 1; r <= n; r++) {
if(r == i || A.G[r][i] == 0) continue;
i64 factor = A.G[r][i];
for(int c = 1; c <= n; c++) {
A.G[r][c] = (A.G[r][c] - 1LL * factor * A.G[i][c]) % MOD;
if(A.G[r][c] < 0) A.G[r][c] += MOD;
I.G[r][c] = (I.G[r][c] - 1LL * factor * I.G[i][c]) % MOD;
if(I.G[r][c] < 0) I.G[r][c] += MOD;
}
}
}
return I;
}
};
std::vector<double> gauss(matrix A, std::vector<int> b) {
int n = A.N;
std::vector<std::vector<double>> M(n, std::vector<double>(n));
std::vector<double> B(n);
for(int i = 0; i < n; i++) B[i] = (double)b[i + 1];
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
M[i][j] = (double)A.G[i + 1][j + 1];
int rank = 0;
for(int i = 0; i < n; i++) {
int pivot = -1;
for(int j = rank; j < n; j++) {
if(fabs(M[j][i]) > EPS) {
pivot = j;
break;
}
}
if(pivot == -1) continue;
std::swap(M[rank], M[pivot]);
std::swap(B[rank], B[pivot]);
double div = M[rank][i];
for(int k = i; k < n; k++) M[rank][k] /= div;
B[rank] /= div;
for(int j = 0; j < n; j++) {
if(j == rank) continue;
if(fabs(M[j][i]) > EPS) {
double factor = M[j][i];
for(int k = i; k < n; k++) {
M[j][k] -= factor * M[rank][k];
}
B[j] -= factor * B[rank];
}
}
rank++;
}
for(int i = rank; i < n; i++)
if(fabs(B[i]) > EPS) return {-1}; // no answer
if(rank < n) return {0}; // inf answers
std::vector<double> x(n + 1, 1);
for(int i = 1; i <= n; i++) x[i] = B[i - 1];
return x;
}
i64 mxor(std::vector<i64> a) {
int n = a.size(), k = 0;
auto Gauss = [&]() -> void {
for(int i = 63; i >= 0; i--) {
for(int j = k; j < n; j++) {
if((a[j] >> i) & 1) {
std::swap(a[j], a[k]);
break;
}
}
if(((a[k] >> i) & 1) == 0) continue;
for(int j = 0; j < n; j++)
if(j != k && ((a[j] >> i) & 1))
a[j] ^= a[k];
++k; if(k == n) break;
}
}; Gauss(); i64 ans = 0ll;
for(int i = 0; i < k; i++) ans ^= a[i];
return ans;
}
struct LinearBasis {
static const int bit = 63;
i64 base[bit]; std::vector<i64> v;
int zero = 0, rank = 0;
LinearBasis() {memset(base, 0, sizeof(base)); v.clear();}
bool ask(i64 x) {
for(int i = bit - 1; i >= 0; i--)
if(x & (1ll << i)) x ^= base[i];
return x == 0;
}
void insert(i64 x) {
if(x == 0) {return zero = 1, void();}
for(int i = bit - 1; i >= 0; i--) {
if(!(x >> i & 1)) continue;
if(!base[i]) {
base[i] = x;
rank++;
return;
}
x ^= base[i];
}
if(x == 0) zero = 1;
}
void merge(LinearBasis &b) {
for(int i = bit - 1; i >= 0; i--)
if(b.base[i]) insert(b.base[i]);
}
i64 max_xor() {
i64 res = 0;
for(int i = bit - 1; i >= 0; i--)
if((res ^ base[i]) > res) res ^= base[i];
return res;
}
i64 min_xor() {
if(zero) return 0;
for(int i = 0; i < bit; i++)
if(base[i]) return base[i];
return 0;
}
void rebuild() {
i64 tmp[bit]; v.clear();
memcpy(tmp, base, sizeof(base));
for(int i = bit - 1; i >= 0; i--)
for(int j = i - 1; j >= 0; j--)
if(tmp[i] & (1ll << j)) tmp[i] ^= tmp[j];
for(int i = 0; i < bit; i++) if(tmp[i]) v.push_back(tmp[i]);
}
i64 kth_xor(i64 k) {
k -= zero; if(k == 0) return 0ll;
int r = v.size(); // rebuild first
i64 total = 1LL << r, res = 0ll;
if(k >= total) return -1;
for(int i = bit - 1; i >= 0; i--)
if(k & (1ll << i)) res ^= v[i];
return res;
}
};
}8.并查集
namespace DSU {
std::vector<int> fa, r;
void init(int x) {
fa.resize(x + 1);
r.resize(x + 1);
fill(r.begin(), r.end(), 1);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void unit(int x, int y) {
if(r[x] > r[y]) std::swap(x, y);
int a = find(x), b = find(y);
if(a == b) return;
r[b] += r[a];
fa[a] = b;
}
}9.tarjan缩点
int id = 0, top = 0, cnt = 0;
std::vector<int> low(n + 1), dfn(n + 1, 0), st(n + 1), siz(n + 1, 0);
std::vector<bool> vis(n + 1, 0);
std::vector<int> deg(n + 1, 0), f(n + 1, 1e9), p(n + 1);
auto tarjan = [&](auto self, int u)->void{
dfn[u] = low[u] = ++ id;
st[++top] = u;
vis[u] = true;
for(auto v : adj[u]) {
if(!dfn[v]) self(self, v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
++cnt;
while(st[top + 1] != u) {
int v = st[top--];
vis[v] = false;
p[v] = cnt; siz[cnt]++;
f[cnt] = min(f[cnt], a[v]);
}
}
};
for(int i = 1; i <= n; i++) if(!dfn[i] && a[i] <= 2e4) tarjan(tarjan, i);10.最大流
struct Network_Flow {
using ll = long long;
int cnt = 1, head[N], nxt[M << 1], to[M << 1], limit[M << 1];
void add(int u, int v, int w) {
nxt[++cnt] = head[u], head[u] = cnt, to[cnt] = v, limit[cnt] = w;
nxt[++cnt] = head[v], head[v] = cnt, to[cnt] = u, limit[cnt] = 0;
}
int T, dis[N], cur[N];
ll dfs(int u, ll res) {
if(u == T) return res;
ll flow = 0;
for(int i = cur[u]; i && res; i = nxt[i]) {
cur[u] = i;
int c = min(res, (ll)limit[i]), v = to[i];
if(dis[u] + 1 == dis[v] && c) {
int k = dfs(v, c);
flow += k, res -= k;
limit[i] -= k, limit[i ^ 1] += k;
}
}
if(!flow) dis[u] = -1;
return flow;
}
ll maxflow(int s, int t) {
T = t;
ll flow = 0;
while(1) {
std::queue<int> Q;
memcpy(cur, head, sizeof(head));
memset(dis, -1, sizeof(dis));
Q.push(s), dis[s] = 0;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
for(int i = head[u]; i; i = nxt[i]) {
int v = to[i];
if(dis[v] == -1 && limit[i])
dis[v] = dis[u] + 1, Q.push(v);
}
}
if(dis[t] == -1) return flow;
flow += dfs(s, 1e18);
}
}
} g;11.费用流(SPFA, 无优化)
struct Cost_Flow {
using PII = pair<int, int>;
int cnt = 1, head[N], nxt[M << 1], to[M << 1], flow[M << 1], dis[M << 1];
int incf[M << 1], pre[M << 1];
void add(int u, int v, int f, int d) {
nxt[++cnt] = head[u], to[cnt] = v, dis[cnt] = d, flow[cnt] = f, head[u] = cnt;
}// add two-way edge manually
int DIS[M << 1], vis[M << 1];
bool spfa(int s, int t) {
std::queue<int> Q;
memset(DIS, 0x3f, sizeof(DIS));
memset(vis, 0, sizeof(vis));
Q.push(s), DIS[s] = 0, vis[s] = 1;
incf[s] = 1 << 30;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
vis[u] = 0;
for(int i = head[u]; i; i = nxt[i]) {
if(!flow[i]) continue;
int v = to[i];
if(DIS[v] > DIS[u] + dis[i]) {
DIS[v] = DIS[u] + dis[i];
incf[v] = min(incf[u], flow[i]);
pre[v] = i;
if(!vis[v]) vis[v] = 1, Q.push(v);
}
}
}
return DIS[t] < 1061109567;
}
PII MCMF(int s, int t) {
int mincost = 0, maxflow = 0;
while(spfa(s, t)) {
int x = t;
maxflow += incf[t];
mincost += DIS[t] * incf[t];
int i;
while(x != s) {
i = pre[x];
flow[i] -= incf[t];
flow[i ^ 1] += incf[t];
x = to[i ^ 1];
}
}
return {maxflow, mincost};
}
} G; // Graph12.简单排序
namespace SORT {
using namespace std;
using i64 = long long;
void Sort(std::vector<int> &a, int l, int r) {
sort(a.begin() + l, a.begin() + 1 + r);
}
void quickSort(std::vector<int> &a, int l, int r) {
if(l >= r) return;
int i = l, j = r;
int pivot = a[l + (r - l) / 2];
while(i <= j) {
while(a[i] < pivot) i++;
while(a[j] > pivot) j--;
if(i <= j) {
swap(a[i], a[j]);
i++; j--;
}
}
if(l < j) quickSort(a, l, j);
if(i < r) quickSort(a, i, r);
}
i64 merge(std::vector<int> &a, int l, int mid, int r) {
std::vector<int> tmp(r - l + 1);
int i = l, j = mid + 1, k = 0;
i64 inv = 0;
while(i <= mid && j <= r) {
if(a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++], inv += (mid - i + 1);
}
while(i <= mid) tmp[k++] = a[i++];
while(j <= r) tmp[k++] = a[j++];
for(int t = 0; t < (int)tmp.size(); t++)
a[l + t] = tmp[t];
return inv;
}
i64 mergeSort(std::vector<int> &a, int l, int r) {
if(l >= r) return 0;
int mid = l + r >> 1;
i64 inv = 0;
inv += mergeSort(a, l, mid);
inv += mergeSort(a, mid + 1, r);
inv += merge(a, l, mid, r);
return inv;
}
}13.计算几何(二维)
namespace CG { // computational geometry
int sgn(double k) {
const double eps = 1e-6;
if(k > eps) return 1;
else if(k < -eps) return -1;
else return 0;
}
int cmp(double k1, double k2) {
return sgn(k1 - k2);
}
int inmid(double k1, double k2, double k3) {
return sgn(k1 - k3) * sgn(k2 - k3) <= 0;
}
struct point {
double x, y;
point operator + (const point &k1) const {return (point){k1.x + x, k1.y + y};}
point operator - (const point &k1) const {return (point){x - k1.x, y - k1.y};}
point operator * (double k1) const {return (point){x * k1, y * k1};}
point operator / (double k1) const {return (point){x / k1, y / k1};}
int operator == (const point &k1) const {return cmp(x, k1.x) == 0 && cmp(y, k1.y) == 0;}
point turn(double k1) {return (point){x * cos(k1) - y * sin(k1), x * sin(k1) + y * cos(k1)};}
point turn90() {return (point) {-y, x};}
bool operator < (const point k1) const {
int a = cmp(x, k1.x);
if(a == -1) return 1;
else if(a == 1) return 0;
else return cmp(y, k1.y) == -1;
}
double dis1() {return sqrt(x * x + y * y);}
double dis2() {return x * x + y * y;}
double dis(point k1) {return ((*this) - k1).dis1();}
point unit() {
int d = dis1();
if(d == 0) return (point){0, 0};
else return (point){x / d, y / d};
}
friend istream & operator >> (istream &input, point &p) {
input >> p.x >> p.y;
return input;
}
friend ostream & operator << (ostream &output, const point & p) {
output << fixed << setprecision(20) << p.x << " " << p.y;
return output;
}
double angle() {return atan2(y, x);}
point getdel() { // toHalf
if(sgn(x) == -1 || (sgn(x) == 0 && sgn(y) == -1))
return (*this) * (-1);
else return (*this);
}
bool getP() const {
return sgn(y) == 1 || (sgn(y) == 0 && sgn(x) == -1);
}
};
double cross(point k1, point k2) {
return k1.x * k2.y - k1.y * k2.x;
}
int inmid(point k1, point k2, point k3) {
return inmid(k1.x, k2.x, k3.x) && inmid(k1.y, k2.y, k3.y);
}
bool OnSegment(point k1, point k2, point q) {
return inmid(k1, k2, q) && sgn(cross(k1 - q, k2 - k1)) == 0;
// return sgn(cross(k2 - k1, q - k1)) == 0 && inmid(k1, k2, q);
}
point rotate(point a, double deg = 1.0, bool cw = false, point c = {0, 0}) {
double ang = deg / 180.0 * acos(-1);
if(cw == 1) ang = -ang; // clockwise
double COS = cos(ang), SIN = sin(ang);
double x = a.x - c.x;
double y = a.y - c.y;
double nx = x * COS - y * SIN;
double ny = x * SIN + y * COS;
return {nx + c.x, ny + c.y};// c = center
}
double dot(point k1, point k2) {
return k1.x * k2.x + k1.y * k2.y;
}
double rad(point k1, point k2) {
return atan2(cross(k1, k2), dot(k1, k2));
}
bool cmpAngle(point k1, point k2) {
return k1.getP() < k2.getP() || (k1.getP() == k2.getP() && sgn(cross(k1, k2)) > 0);
}
int side(point a, point b, point p) {
return sgn(cross(b - a, p - a));
}
point InterLine(point a1, point a2, point b1, point b2) {
double A1 = cross(b2 - b1, a1 - b1);
double A2 = cross(b2 - b1, a2 - b1);
return (a1 * A2 - a2 * A1) / (A2 - A1);
}
double peri(std::vector<point> poly) { // Polygon Perimeter
double res = 0;
int n = poly.size();
for(int i = 0; i < n; i++) {
res += poly[i].dis(poly[(i + 1) % n]);
}
return res;
}
double area(std::vector<point> poly) { // Polygon Area(with direction)
double res = 0;
int n = poly.size();
for(int i = 0; i < n; i++) {
res += cross(poly[i], poly[(i + 1) % n]);
}
return res / 2.0;
}
point projection(point k1, point k2, point q) {
point k = k2 - k1;
return k1 + k * (dot(q - k1, k) / k.dis2());
}
point reflect(point k1, point k2, point q) {
return projection(k1, k2, q) * 2.0 - q;
}
bool intersect(double l1, double r1, double l2, double r2) {
if(l1 > r1) swap(l1, r1);
if(l2 > r2) swap(l2, r2);
return cmp(r1, l2) != -1 && cmp(r2, l1) != -1;
}
bool InterSeg(point k1, point k2, point k3, point k4) {
return intersect(k1.x, k2.x, k3.x, k4.x) && intersect(k1.y, k2.y, k3.y, k4.y) &&
sgn(cross(k3 - k1, k4 - k1)) * sgn(cross(k3 - k2, k4 - k2)) <= 0 &&
sgn(cross(k1 - k3, k2 - k3)) * sgn(cross(k1 - k4, k2 - k4)) <= 0;
}
double disSP(point k1, point k2, point q) { // distance between segment and point
point k3 = projection(k1, k2, q);
if(inmid(k1, k2, k3)) return q.dis(k3);
else return min(q.dis(k1), q.dis(k2));
}
double disSS(point k1, point k2, point k3, point k4) { // distance between segments
if(InterSeg(k1, k2, k3, k4)) return 0;
else return min(min(disSP(k1, k2, k3), disSP(k1, k2, k4)),
min(disSP(k3, k4, k1), disSP(k3, k4, k2)));
}
struct circle {
point o;
double r;
friend istream & operator >> (istream &input, circle &p) {
return input >> p.o >> p.r;
}
int inside(point k) {
return cmp(r, o.dis(k));
}
};
struct line {
point p[2];
line(point k1, point k2) {
p[0] = k1, p[1] = k2;
}
point & operator [] (int k) {return p[k];}
int include(point k) {
return side(p[0], p[1], k) > 0;
}
point dir() { // direction
return p[1] - p[0];
}
line push(double eps = 1e-6) { // move outward eps(left side)
point delta = dir().turn90().unit() * eps;
return {p[0] - delta, p[1] - delta};
}
};
point InterLine(line k1, line k2) {
return InterLine(k1[0], k1[1], k2[0], k2[1]);
}
int parallel(line k1, line k2) {
return sgn(cross(k1.dir(), k2.dir())) == 0;
}
bool sameDir(line k1, line k2) {
return parallel(k1, k2) && sgn(dot(k1.dir(), k2.dir())) == 1;
}
bool operator < (line k1, line k2) {
if(sameDir(k1, k2)) return k2.include(k1[0]);
return cmpAngle(k1.dir(), k2.dir()); // Polar sorting
}
bool checkpos(line k1, line k2, line k3) { // about Half plane intersection
return k3.include(InterLine(k1, k2));
} // check ifor not the intersection of k1&k2 is on the left side of k3
std::vector<line> HalfPlane(std::vector<line> &L) {
//Find the intersection of half planes
//where the half plane is counterclockwise and the output is counterclockwise
std::sort(L.begin(), L.end());
std::deque<line> q;
int n = (int)L.size();
for(int i = 0; i < n; i++) {
if(i && sameDir(L[i], L[i - 1])) continue;
while(q.size() > 1 && !checkpos(q[q.size() - 2], q[q.size() - 1], L[i])) q.pop_back();
while(q.size() > 1 && !checkpos(q[1], q[0], L[i])) q.pop_front();
q.push_back(L[i]);
}
while(q.size() > 2 && !checkpos(q[q.size() - 2], q[q.size() - 1], q[0])) q.pop_back();
while(q.size() > 2 && !checkpos(q[1], q[0], q[q.size() - 1])) q.pop_front();
std::vector<line> ans;
for(int i = 0; i < q.size(); i++) ans.push_back(q[i]);
return ans;
}
double closepts(std::vector<point> &A, int l, int r) { // closest point-pair, return dis.
if(r - l <= 5) {
double ans = 1e18;
for(int i = l; i <= r; i++) for(int j = i + 1; j <= r; j++)
ans = min(ans, A[i].dis(A[j]));
return ans;
}
int mid = l + r >> 1;
double ans = min(closepts(A, l, mid), closepts(A, mid + 1, r));
std::vector<point> B;
for(int i = l; i <= r; i++) if(fabs(A[i].x - A[mid].x) <= ans) B.push_back(A[i]);
std::sort(B.begin(), B.end(), [](point k1, point k2) {return k1.y < k2.y;});
for(int i = 0; i < (int)B.size(); i++)
for(int j = i + 1; j < B.size() && B[j].y - B[i].y < ans; j++)
ans = min(ans, B[i].dis(B[j]));
return ans;
}
double cp(std::vector<point> &A) {
sort(A.begin(), A.end());
int n = A.size();
return closepts(A, 0, n - 1);
}
std::vector<point> getCL(circle k1, point k2, point k3) { // intersection of circle and line
point k = projection(k2, k3, k1.o);
double d = k1.r * k1.r - (k - k1.o).dis2();
if(sgn(d) == -1) return {};
point delta = (k3 - k2).unit() * sqrt(max((double)0.0, d));
return {k - delta, k + delta};
}
double area(circle k1, point k2, point k3) {
point k = k1.o;
k1.o = k1.o - k;
k2 = k2 - k;
k3 = k3 - k;
int pd1 = k1.inside(k2), pd2 = k1.inside(k3);
std::vector<point> A = getCL(k1, k2, k3);
if(pd1 >= 0) {
if(pd2 >= 0) return cross(k2, k3) / 2.0;
return k1.r * k1.r * rad(A[1], k3) / 2.0 + cross(k2, A[1]) / 2.0;
} else if(pd2 >= 0) {
return k1.r * k1.r * rad(k2, A[0]) / 2.0 + cross(A[0], k3) / 2.0;
} else {
int pd = cmp(k1.r, disSP(k2, k3, k1.o));
if(pd <= 0) return k1.r * k1.r * rad(k2, k3) / 2.0;
return cross(A[0], A[1]) / 2.0 + k1.r * k1.r * (rad(k2, A[0]) + rad(A[1], k3)) / 2.0;
}
}
circle getcircle(point k1, point k2, point k3) {
double a1 = k2.x - k1.x, b1 = k2.y - k1.y, c1 = (a1 * a1 + b1 * b1) / 2.0;
double a2 = k3.x - k1.x, b2 = k3.y - k1.y, c2 = (a2 * a2 + b2 * b2) / 2.0;
double d = a1 * b2 - a2 * b1;
point o = (point){k1.x + (c1 * b2 - c2 * b1) / d, k1.y + (a1 * c2 - a2 * c1) / d};
return (circle){o, k1.dis(o)};
}
circle getMCC(std::vector<point> A) { // Minimum circle coverage
std::random_device rd;
std::mt19937 rng(rd());
std::shuffle(A.begin(), A.end(), rng);
circle ans = (circle){A[0], 0};
for(int i = 1; i < (int)A.size(); i++) if(ans.inside(A[i]) == -1) {
ans = (circle){A[i], 0};
for(int j = 0; j < i; j++) if(ans.inside(A[j]) == -1) {
ans.o = (A[i] + A[j]) / 2;
ans.r = ans.o.dis(A[i]);
for(int k = 0; k < j; k++) if(ans.inside(A[k]) == -1)
ans = getcircle(A[i], A[j], A[k]);
}
}
return ans;
}
double getMDCC(std::vector<point> A) {
// Minimum Double Circle Coverage Problem
// Find two circles with the same radius that cover the given n points and have the smallest radius
// return that radius
int n = A.size();
double R = 1e18;
for(int i = 1; i <= 180; i++) {
for(int i = 0; i < n; i++) A[i] = rotate(A[i]);
std::sort(A.begin(), A.end(), [](point a, point b){return a.x < b.x;});
int l = 0, r = n - 1;
while(l <= r) {
int mid = l + r >> 1;
std::vector<point> r1, r2;
for(int i = 0; i <= mid; i++) r1.push_back(A[i]);
for(int i = mid + 1; i < n; i++) r2.push_back(A[i]);
double R1 = getMCC(r1).r;
double R2 = getMCC(r2).r;
if(min(R1, R2) > R) break;
if(R1 < R2) l = mid + 1;
else r = mid - 1;
R = min(R, max(R1, R2));
}
}
return R;
}
bool checkconvex(std::vector<point> A) {
int n = A.size();
A.push_back(A[0]);
A.push_back(A[1]);
for(int i = 0; i < n; i++)
if(sgn(cross(A[i + 1] - A[i], A[i + 2] - A[i])) == -1)
return 0;
return 1;
}
int contain(std::vector<point> A, point q) {
int pd = 0;
A.push_back(A[0]);
for(int i = 1; i < (int)A.size(); i++) {
point u = A[i - 1], v = A[i];
if(OnSegment(u, v, q)) return 1;
if(cmp(u.y, v.y) > 0) swap(u, v);
if(cmp(u.y, q.y) >= 0 || cmp(v.y, q.y) < 0) continue;
if(sgn(cross(u - v, q - v)) < 0) pd ^= 1;
}
return pd << 1;
}
std::vector<point> ConvexHull(std::vector<point> A, int flag = 1) { // flag=0 not-strict flag=1 strict
int n = A.size();
std::vector<point> ans(n * 2);
sort(A.begin(), A.end());
int now = -1;
for(int i = 0; i < A.size(); i++) {
while(now > 0 && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
ans[++now] = A[i];
}
int pre = now;
for(int i = n - 2; i >= 0; i--) {
while(now > pre && sgn(cross(ans[now] - ans[now - 1], A[i] - ans[now - 1])) < flag) now--;
ans[++now] = A[i];
}
ans.resize(now + 1);
return ans;
}
double convexDiameter(std::vector<point> A) { // Rotating Calipers
int now = 0, n = A.size();
double ans = 0;
for(int i = 0; i < A.size(); i++) {
now = max(now, i);
while(true) {
double k1 = A[i].dis(A[now % n]);
double k2 = A[i].dis(A[(now + 1) % n]);
ans = max(ans, max(k1, k2));
if(k2 > k1) now++;
else break;
}
}
return ans;
}
} using namespace CG;14.高精度
struct BigInteger {
static const int BASE = 1e8;
static const int WIDTH = 8;
vector<int> num;
bool sgn;
BigInteger(int x = 0) { *this = x; }
BigInteger(const string &s) { *this = s; }
BigInteger & operator = (int x) {
num.clear();
sgn = x >= 0;
if(!sgn) x = -x;
if(x == 0) num.push_back(0);
while(x > 0) {
num.push_back(x % BASE);
x /= BASE;
}
return *this;
}
BigInteger & operator = (const string &s) {
num.clear();
int len = s.size(), i = 0;
sgn = true;
if(s[0] == '-') sgn = false, i++;
for(int j = len - 1; j >= i; j -= WIDTH) {
int l = max(i, j - WIDTH + 1);
int x = 0;
for(int k = l; k <= j; k++)
x = x * 10 + (s[k] - '0');
num.push_back(x);
}
trim();
return *this;
}
void trim() {
while(num.size() > 1 && num.back() == 0) num.pop_back();
if(num.size() == 1 && num[0] == 0) sgn = true;
}
string toString() const {
stringstream ss;
if(!sgn) ss << '-';
ss << (num.empty() ? 0 : num.back());
for(int i = num.size() - 2; i >= 0; i--)
ss << setw(WIDTH) << setfill('0') << num[i];
return ss.str();
}
friend ostream &operator<<(ostream &out, const BigInteger &x) {
out << x.toString();
return out;
}
friend istream &operator>>(istream &in, BigInteger &x) {
string s;
in >> s;
x = s;
return in;
}
bool absLess(const BigInteger &rhs) const {
if(num.size() != rhs.num.size()) return num.size() < rhs.num.size();
for(int i = num.size() - 1; i >= 0; i--)
if(num[i] != rhs.num[i]) return num[i] < rhs.num[i];
return false;
}
bool operator<(const BigInteger &rhs) const {
if(sgn != rhs.sgn) return !sgn;
return sgn ? absLess(rhs) : rhs.absLess(*this);
}
bool operator > (const BigInteger &rhs) const { return rhs < *this; }
bool operator == (const BigInteger &rhs) const { return !(*this < rhs) && !(rhs < *this); }
bool operator != (const BigInteger &rhs) const { return !(*this == rhs); }
bool operator <= (const BigInteger &rhs) const { return !(*this > rhs); }
bool operator >= (const BigInteger &rhs) const { return !(*this < rhs); }
BigInteger operator - () const {
BigInteger res = *this;
if(!(num.size() == 1 && num[0] == 0)) res.sgn = !sgn;
return res;
}
BigInteger operator + (const BigInteger &rhs) const {
if(!sgn) return (-(*this) + rhs).operator-();
if(!rhs.sgn) return (*this - (-rhs));
BigInteger res;
res.sgn = true;
int carry = 0, n = max(num.size(), rhs.num.size());
res.num.resize(n);
for(int i = 0; i < n; i++) {
int a = i < (int)num.size() ? num[i] : 0;
int b = i < (int)rhs.num.size() ? rhs.num[i] : 0;
int sum = a + b + carry;
res.num[i] = sum % BASE;
carry = sum / BASE;
}
if(carry) res.num.push_back(carry);
return res;
}
BigInteger operator - (const BigInteger &rhs) const {
if(!rhs.sgn) return *this + (-rhs);
if(!sgn) return (-(*this) + rhs).operator-();
if(*this < rhs) return -(rhs - *this);
BigInteger res = *this;
int borrow = 0;
for(int i = 0; i < (int)rhs.num.size() || borrow; i++) {
res.num[i] -= (i < (int)rhs.num.size() ? rhs.num[i] : 0) + borrow;
if(res.num[i] < 0) res.num[i] += BASE, borrow = 1;
else borrow = 0;
}
res.trim();
return res;
}
BigInteger operator * (const BigInteger &rhs) const {
BigInteger res;
res.sgn = (sgn == rhs.sgn);
res.num.assign(num.size() + rhs.num.size(), 0);
for(size_t i = 0; i < num.size(); i++)
for(size_t j = 0; j < rhs.num.size(); j++)
res.num[i + j] += num[i] * rhs.num[j];
int carry = 0;
for(size_t i = 0; i < res.num.size(); i++) {
res.num[i] += carry;
carry = res.num[i] / BASE;
res.num[i] %= BASE;
}
res.trim();
return res;
}
BigInteger operator / (const BigInteger &rhs) const {
assert(rhs != 0);
BigInteger divident = *this, divisor = rhs;
divident.sgn = divisor.sgn = true;
BigInteger res, cur = 0;
res.num.resize(divident.num.size());
for(int i = divident.num.size() - 1; i >= 0; i--) {
cur.num.insert(cur.num.begin(), divident.num[i]);
cur.trim();
int l = 0, r = BASE - 1, ans = 0;
while(l <= r) {
int m = (l + r) / 2;
if(divisor * m <= cur) ans = m, l = m + 1;
else r = m - 1;
}
res.num[i] = ans;
cur = cur - divisor * ans;
}
res.sgn = (sgn == rhs.sgn);
res.trim();
return res;
}
BigInteger operator % (const BigInteger &rhs) const {
return *this - (*this / rhs) * rhs;
}
BigInteger operator + (const int &rhs) const {
return *this + BigInteger(rhs);
}
BigInteger operator - (const int &rhs) const {
return *this - BigInteger(rhs);
}
BigInteger operator * (const int &rhs) const {
BigInteger res;
res.sgn = (rhs >= 0 ? sgn : !sgn);
int mul = abs(rhs);
res.num.clear();
int carry = 0;
for(size_t i = 0; i < num.size(); i++) {
int cur = (int)num[i] * mul + carry;
res.num.push_back(cur % BigInteger::BASE);
carry = cur / BigInteger::BASE;
}
while(carry) {
res.num.push_back(carry % BigInteger::BASE);
carry /= BigInteger::BASE;
}
res.trim();
return res;
}
BigInteger operator/(const int &rhs) const {
assert(rhs != 0);
BigInteger res;
res.sgn = (rhs >= 0 ? sgn : !sgn);
int div = abs(rhs);
res.num.resize(num.size());
int rem = 0;
for(int i = num.size() - 1; i >= 0; i--) {
int cur = num[i] + rem * (int)BigInteger::BASE;
res.num[i] = cur / div;
rem = cur % div;
}
res.trim();
return res;
}
int operator % (const int &rhs) const {
assert(rhs != 0);
int rem = 0, div = abs((int)rhs);
for(int i = num.size() - 1; i >= 0; i--) {
rem = (rem * BigInteger::BASE + num[i]) % div;
}
if(!sgn) rem = -rem;
return (int)rem;
}
BigInteger qpow(BigInteger n, const BigInteger &mod) const {
BigInteger res = 1, base = *this;
while(n > 0) {
if(n.num[0] % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
n = n / 2;
}
return res;
}
};
using i256 = BigInteger;15.多项式
struct Poly {
std::vector<double> coef;
Poly(int n = 0) { coef.assign(n + 1, 0.0); }
Poly(const vector<double>& c) { coef = c; }
double operator()(double x) const {
double res = 0.0;
int n = coef.size() - 1;
for(int i = 0; i <= n; i++) res = res * x + coef[i];
return res;
}
double dvt(double x) const {
double res = 0.0;
int n = coef.size() - 1;
for(int i = 0; i < n; i++) res = res * x + (n - i) * coef[i];
return res;
}
friend istream& operator >> (istream& in, Poly& p) {
int n = p.coef.size() - 1;
for(int i = 0; i <= n; i++) in >> p.coef[i];
return in;
}
friend ostream& operator<<(ostream& out, const Poly& p) {
int n = p.coef.size() - 1;
int cnt = 0, pos = -1;
for(int i = 0; i <= n; i++) {
if(p.coef[i] == 0) cnt++;
if(p.coef[i] != 0 && pos == -1) pos = i;
}
if(cnt == n + 1) {
out << "0";
return out;
}
for(int i = 0; i < n - 1; i++) {
if(fabs(p.coef[i]) > 1 && p.coef[i] < 0)
out << p.coef[i] << "x^" << n - i;
if(fabs(p.coef[i]) > 1 && p.coef[i] > 0 && i > pos)
out << "+" << p.coef[i] << "x^" << n - i;
if(fabs(p.coef[i]) > 1 && p.coef[i] > 0 && i == pos)
out << p.coef[i] << "x^" << n - i;
if(fabs(p.coef[i]) == 1 && p.coef[i] < 0)
out << "-x^" << n - i;
if(fabs(p.coef[i]) == 1 && p.coef[i] > 0 && i > pos)
out << "+x^" << n - i;
if(fabs(p.coef[i]) == 1 && p.coef[i] > 0 && i == pos)
out << "x^" << n - i;
}
if(n >= 1) {
if(p.coef[n - 1] > 1) {
if(pos < n - 1) out << "+";
out << p.coef[n - 1] << "x";
} else if(p.coef[n - 1] < -1) {
out << p.coef[n - 1] << "x";
} else if(p.coef[n - 1] == 1) {
if(pos < n - 1) out << "+";
out << "x";
} else if(p.coef[n - 1] == -1) {
out << "-x";
}
}
if(fabs(p.coef[n]) < eps) return out;
if(p.coef[n] > 0 && pos < n) out << "+";
out << p.coef[n];
return out;
}
};16.扫描线(tmp)
#include<bits/stdc++.h>
#define lp p<<1
#define rp p<<1|1
using namespace std;
struct Event {
int x, type, yl, yr;
bool operator<(const Event& o) const {
if(x != o.x) return x < o.x;
return type > o.type;
}
};
struct SegTree {
int n;
std::vector<int> mx, tag; // maximum coverage times of the current interval; lazy tag
SegTree(int n = 0): n(n), mx(4*n+4, 0), tag(4*n+4, 0) {}
void push(int p) {
if(!tag[p]) return;
mx[lp] += tag[p], tag[lp] += tag[p];
mx[rp] += tag[p], tag[rp] += tag[p];
tag[p] = 0;
}
void update(int p,int l,int r,int ql,int qr,int v){
if(qr < l || r < ql) return;
if(ql <= l && r <= qr) {
mx[p] += v;
tag[p] += v;
return;
}
int m = l + r >> 1; push(p);
update(lp,l,m,ql,qr,v);
update(rp,m+1,r,ql,qr,v);
mx[p] = max(mx[lp], mx[rp]);
}
void update(int l,int r,int v){ if(l<=r) update(1,0,n-1,l,r,v); }
int query_max() const { return mx[1]; }
};
int solve(const std::vector<tuple<int,int,int>>& circles, int W, int H){
std::vector<pair<int,int>> ySegs;
std::vector<Event> ev;
ySegs.reserve(circles.size()*2);
ev.reserve(circles.size()*2);
for(auto &[x, y, r] : circles) {
if(W < 2*r || H < 2*r) continue;
int xL = x + r - W;
int xR = x - r;
int yL = y + r - H;
int yR = y - r;
if(xL >= xR|| yL >= yR) continue;
ySegs.emplace_back(yL, yR);
ySegs.emplace_back(yL, yR);
ev.push_back({xL, +1, -1, -1});
ev.push_back({xR, -1, -1, -1});
}
if(ev.empty()) return 0;
std::vector<int> ys;
// ys.reserve(ySegs.size()*2);
for(auto &p : ySegs) {
ys.push_back(p.first);
ys.push_back(p.second);
}
std::sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end(), [&](int a, int b){ return a == b; }), ys.end());
auto getid = [&](int v) {
int id = int(lower_bound(ys.begin(), ys.end(), v) - ys.begin());
if(id < 0) id = 0;
if(id >= (int)ys.size()) id = (int)ys.size()-1;
return id;
};
for(int i = 0; i < (int)ev.size(); ++i) {
int yL = ySegs[i].first, yR = ySegs[i].second;
int yl = getid(yL), yr = getid(yR);
if(yl > yr) swap(yl, yr);
ev[i].yl = yl, ev[i].yr = yr;
}
std::sort(ev.begin(), ev.end());
SegTree st((int)ys.size());
int ans = 0;
for(int i = 0; i < (int)ev.size();) {
int j = i, X = ev[i].x;
while(j < (int)ev.size() && ev[j].x == X && ev[j].type == 1)
st.update(ev[j].yl, ev[j].yr, +1), ++j;
ans = max(ans, st.query_max());
while(j < (int)ev.size() && ev[j].x == X && ev[j].type == -1)
st.update(ev[j].yl, ev[j].yr, -1), ++j;
i = j;
}
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; cin >> n;
int w, h;
cin >> w >> h;
std::vector<tuple<int,int,int>> circles(n);
for(int i = 0; i < n; ++i) {
int x,y,r;
cin >> x >> y >> r;
circles[i] = {x,y,r};
}
int ans1 = solve(circles, w, h);
int ans2 = solve(circles, h, w);
cout << max(ans1, ans2);
return 0;
}线段树求区间
struct SegmentTree {
int n;
std::vector<i64> tree;
SegmentTree(int n = 0) { init(n); }
void init(int n_) {
n = n_, tree.assign(8 * n + 4, 0);
}
void build(std::vector<i64> &a, int p, int l, int r) {
if(l == r) {
tree[p] = a[l];
return;
}
int mid = (l + r) >> 1;
build(a, lson, l, mid);
build(a, rson, mid + 1, r);
tree[p] = std::gcd(tree[lson], tree[rson]);
}
void build(vector<i64> &a) {
build(a, 1, 1, n);
}
void update(int p, int l, int r, int pos, i64 val) {
if(l == r) {
tree[p] = val;
return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(lson, l, mid, pos, val);
else update(rson, mid + 1, r, pos, val);
tree[p] = std::gcd(tree[lson], tree[rson]);
}
void update(int pos, i64 val) {
update(1, 1, n, pos, val);
}
i64 query(int p, int l, int r, int ql, int qr) {
if(ql <= l && r <= qr) return tree[p];
int mid = (l + r) >> 1;
i64 res = 0;
if(ql <= mid) res = std::gcd(res, query(lson, l, mid, ql, qr));
if(qr > mid) res = std::gcd(res, query(rson, mid + 1, r, ql, qr));
return res;
}
i64 query(int l, int r) {
return query(1, 1, n, l, r);
}
i64 query() {
return query(1, n);
}
};