\[\texttt{Tips for C++ Programming} \]
0.快读快输
inline char gc() { static char buf[1000000], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++; }
inline int read() { char c = gc(); int res = 0, f = 1; for (; c < '0' || c > '9'; c = gc()) if (c == '-') f = -1; for (; c >= '0' && c <= '9'; c = gc()) res = res * 10 + c - '0'; return res * f; }
inline void write(int x) { static int sta[50], top = 0; if (x < 0) putchar('-'), x = -x; do { sta[ top++ ] = x % 10; x /= 10; } while (x); while (top) putchar(sta[ --top ] + 48); }
inline void writesp(int x) { write(x); putchar(' '); }
inline void writeln(int x) { write(x); putchar('\n'); }
1.for 循环宏定义
#define UP(l, i, a, b) for (l i = (l)(a); i <= (l)(b); ++i)
#define DOWN(l, i, a, b) for (l i = (l)(a); i >= (l)(b); --i)
2.快读快输（听说 \(n \geq 5\times 10^8\) 时更快？）
#include <cstdio>
#include <sys/mman.h>
#include <sys/stat.h>
char *p;
inline int read() {
int x = 0, r = 1;
while (*p < 48) {if (*p == '-') r = -r; p++;}
while (*p >= 48) x = (x << 3) + (x << 1) + *p - 48, p++;
return x * r;
}
inline void write(int x) {
char s[20]; int c = 0;
do {s[ c++ ] = x % 10; x /= 10;} while(x);
for (int i = c - 1; i >= 0; --i) putchar_unlocked(s[i] + 48);
putchar('\n');
}
inline void init() {
struct stat in;
fstat(0, &in);
p = (char*)mmap(0, in.st_size, 1, 2, 0, 0);
}
3.高精度模板
class BigInteger {
private:
std :: vector <int> vec;
public:
BigInteger() {
vec.clear();
}
BigInteger* operator = (int n) {
vec.clear();
while (n) {
vec.emplace_back(n % 10);
n /= 10;
}
return this;
}
BigInteger* operator = (std :: string s) {
int len = s.length();
reverse(s.begin(), s.begin() + len);
vec.clear();
for (int i = 0; i < len; i++) vec.emplace_back(s[i] - '0');
return this;
}
BigInteger operator + (const BigInteger A) {
BigInteger C;
C.vec.emplace_back(0);
for (int i = 0; i < vec.size() || i < A.vec.size(); i++) {
int a = (i < vec.size() ? vec[i] : 0);
int b = (i < A.vec.size() ? A.vec[i] : 0);
C.vec[i] += a + b;
C.vec.emplace_back(C.vec[i] / 10);
C.vec[i] %= 10;
}
while (C.vec.back() == 0) {
C.vec.pop_back();
if (C.vec.empty()) break;
}
return C;
}
BigInteger operator - (const BigInteger A) {
std :: vector <int> temp;
for (int i = 0; i < vec.size(); i++) temp.emplace_back(vec[i]);
BigInteger C;
for (int i = 0; i < vec.size() || i < A.vec.size(); i++) {
int a = (i < vec.size() ? vec[i] : 0);
int b = (i < A.vec.size() ? A.vec[i] : 0);
if (a >= b) C.vec.emplace_back(a - b);
else {
while (a < b) {
a += 10; vec[ i + 1 ]--;
}
C.vec.emplace_back(a - b);
}
}
vec.swap(temp);
while (C.vec.back() == 0) {
C.vec.pop_back();
if (C.vec.empty()) break;
}
return C;
}
struct complex {
double real, imaginary;
complex() = default;
complex(const double Re = 0.0, const double Im = 0.0) : real(Re), imaginary(Im) {}
complex operator + (const complex &A) {
return complex(real + A.real, imaginary + A.imaginary);
}
complex operator - (const complex &A) {
return complex(real - A.real, imaginary - A.imaginary);
}
complex operator * (const complex &A) {
return complex(real * A.real - imaginary * A.imaginary, imaginary * A.real + real * A.imaginary);
}
};
void fft(std :: vector <complex> &a, int inv, std :: vector <int> rev, int limit) {
const double pi = acos(-1.0);
for (int i = 0; i < limit; i++)
if (i < rev[i]) std :: swap(a[i], a[ rev[i] ]);
for (int mid = 1; mid < limit; mid <<= 1) {
complex Wn = complex(cos(pi / mid), inv * sin(pi / mid));
for (int L = 0; L < limit; L += (mid << 1)) {
complex w = complex(1, 0);
for (int j = 0; j < mid; j++, w = w * Wn) {
complex w1 = a[ L + j ], w2 = a[ L + j + mid ];
a[ L + j ] = w1 + w2 * w;
a[ L + j + mid ] = w1 - w2 * w;
}
}
}
}
BigInteger operator * (const BigInteger A) {
int limit = 1, l = 0;
std :: vector <int> rev;
std :: vector <complex> a, b;
rev.clear(); rev.emplace_back(0);
int len = vec.size() + A.vec.size() + 1;
for (; limit <= len; limit <<= 1, l++);
for (int i = 1; i < limit; i++)
rev.emplace_back((rev[ i >> 1 ] >> 1) | ((i & 1) << (l - 1)));
for (int i = 0; i < limit; i++) {
if (i < vec.size()) a.emplace_back(complex(vec[i], 0)); else a.emplace_back(complex(0, 0));
if (i < A.vec.size()) b.emplace_back(complex(A.vec[i], 0)); else b.emplace_back(complex(0, 0));
}
fft(a, 1, rev, limit); fft(b, 1, rev, limit);
for (int i = 0; i < limit; i++) a[i] = a[i] * b[i];
fft(a, -1, rev, limit);
BigInteger C;
for (int i = 0; i <= vec.size() + A.vec.size(); i++) {
C.vec.emplace_back(std :: round(a[i].real / limit));
}
for (int i = 0; i < C.vec.size(); i++) {
if (i == C.vec.size() - 1) {
C.vec.emplace_back(C.vec[i] / 10);
C.vec[i] %= 10;
break;
}
else {
C.vec[ i + 1 ] += C.vec[i] / 10;
C.vec[i] %= 10;
}
}
while (C.vec.back() == 0) {
C.vec.pop_back();
if (C.vec.empty()) break;
}
return C;
}
BigInteger operator / (const int p) {
BigInteger C;
std :: reverse(vec.begin(), vec.end());
long long x = 0;
for (int i = 0; i < vec.size(); i++) {
x = x * 10 + vec[i];
C.vec.emplace_back(x / p);
x %= p;
}
std :: reverse(vec.begin(), vec.end());
std :: reverse(C.vec.begin(), C.vec.end());
while (C.vec.back() == 0) C.vec.pop_back();
return C;
}
int operator % (const int p) {
BigInteger C;
std :: reverse(vec.begin(), vec.end());
int x = 0;
for (int i = 0; i < vec.size(); i++) {
x = (1ll * x * 10 + vec[i]) % p;
}
std :: reverse(vec.begin(), vec.end());
return x;
}
bool operator < (const BigInteger A) {
if (vec.size() < A.vec.size()) return true;
else if (vec.size() > A.vec.size()) return false;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] < A.vec[i]) return true;
else if (vec[i] > A.vec[i]) return false;
}
return false;
}
bool operator == (const BigInteger A) {
if (vec.size() != A.vec.size()) return false;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] != A.vec[i]) return false;
}
return true;
}
bool operator > (const BigInteger A) {
if (vec.size() > A.vec.size()) return true;
else if (vec.size() < A.vec.size()) return false;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] > A.vec[i]) return true;
else if (vec[i] < A.vec[i]) return false;
}
return false;
}
bool operator <= (const BigInteger A) {
return (*this) < A || (*this) == A;
}
bool operator >= (const BigInteger A) {
return (*this) > A || (*this) == A;
}
void write() {
if (vec.empty()) std :: cout << 0;
for (int i = vec.size() - 1; ~i; i--) std :: cout << vec[i];
}
void writeln() {
write(); std :: cout << '\n';
}
void writesp() {
write(); std :: cout << ' ';
}
};
4.Splay 模板
struct Splay {
struct Node {
int val, cnt, siz;
Node *fa, *ch[2];
Node() {
val = cnt = siz = 0;
fa = ch[0] = ch[1] = NULL;
}
};
Node *root = NULL;
inline Node *newnode() {
return new Node;
}
inline void Clear(Node *x) {
x -> val = x -> cnt = x -> siz = 0;
x -> fa = x -> ch[0] = x -> ch[1] = NULL;
}
inline void update(Node *x) {
if (x -> ch[0] == NULL && x -> ch[1] == NULL) x -> siz = x -> cnt;
else if (x -> ch[0] == NULL) x -> siz = x -> ch[1] -> siz + x -> cnt;
else if (x -> ch[1] == NULL) x -> siz = x -> ch[0] -> siz + x -> cnt;
else x -> siz = x -> ch[0] -> siz + x -> ch[1] -> siz + x -> cnt;
}
inline int id(Node *x) {
if (x -> fa != NULL) return x -> fa -> ch[1] == x;
else return -1;
}
inline void rotate(Node *x) {
Node *father = x -> fa, *grandfather = father -> fa;
int it = id(x), it2 = id(father);
father -> ch[it] = x -> ch[ it ^ 1 ];
if (x -> ch[ it ^ 1 ] != NULL) x -> ch[ it ^ 1 ] -> fa = father;
father -> fa = x;
x -> ch[ it ^ 1 ] = father;
if (grandfather != NULL) grandfather -> ch[it2] = x;
x -> fa = grandfather;
update(father);
update(x);
}
inline void splay(Node *x) {
while (x -> fa != NULL) {
if (x -> fa == root) {
rotate(x);
}
else if (id(x) == id(x -> fa)) {
rotate(x -> fa);
rotate(x);
}
else {
rotate(x);
rotate(x);
}
}
root = x;
}
inline void insert(int val) {
if (root == NULL) {
root = newnode();
root -> val = val;
root -> cnt = 1;
update(root);
}
else {
Node *now = root, *father = now -> fa;
while (true) {
if (now -> val == val) {
now -> cnt++;
update(now);
break;
}
else if (val < now -> val) {
father = now;
now = now -> ch[0];
}
else {
father = now;
now = now -> ch[1];
}
if (now == NULL) {
now = newnode();
father -> ch[ val > father -> val ] = now;
now -> fa = father;
now -> val = val;
now -> cnt = 1;
update(now);
update(father);
break;
}
}
splay(now);
}
}
inline void del(int val) {
if (root -> ch[0] == NULL && root -> ch[1] == NULL && root -> cnt == 1) {
Clear(root);
root = NULL;
return ;
}
Node *now = root;
while (true) {
if (val < now -> val) {
now = now -> ch[0];
}
else if (val > now -> val) {
now = now -> ch[1];
}
else break;
}
splay(now);
if (root -> cnt > 1) {
root -> cnt--;
update(root);
}
else {
Node *left = root -> ch[0], *right = root -> ch[1];
Clear(root);
if (left == NULL) root = right, root -> fa = NULL;
else if (right == NULL) root = left, root -> fa = NULL;
else {
right -> fa = NULL;
root = left;
root -> fa = NULL;
Node *now = root;
while (now -> ch[1] != NULL) now = now -> ch[1];
splay(now);
root -> ch[1] = right;
right -> fa = root;
update(root);
}
}
}
inline int Rank(int val) {
Node *now = root;
while (true) {
if (val < now -> val) now = now -> ch[0];
else if (val > now -> val) now = now -> ch[1];
else break;
}
splay(now);
return (now -> ch[0] != NULL ? now -> ch[0] -> siz : 0) + 1;
}
inline int kth(int k) {
int ans = 0;
Node *now = root;
while (true) {
int left = 0;
if (now -> ch[0] != NULL) left = now -> ch[0] -> siz;
if (k <= left) {
now = now -> ch[0];
}
else if (k <= left + now -> cnt) {
ans = now -> val;
break;
}
else {
k -= left + now -> cnt;
now = now -> ch[1];
}
}
splay(now);
return ans;
}
inline int prec() {
Node *now = root -> ch[0];
if (now == NULL) return -inf;
while (now -> ch[1] != NULL) now = now -> ch[1];
return now -> val;
}
inline int succ() {
Node *now = root -> ch[1];
if (now == NULL) return inf;
while (now -> ch[0] != NULL) now = now -> ch[0];
return now -> val;
}
};