在@acwing_gza的带歪领导之下,我也跟着一起秀了发了这个模板
共447行(虽然为了好看我多打了亿些换行)
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <functional>
namespace helper
{
typedef long long LL;
typedef unsigned long long ULL;
typedef std::pair<int, int> PII;
typedef std::pair<int, int> PDD;
typedef std::vector<int> VI;
typedef std::vector<LL> VLL;
typedef std::vector<ULL> VULL;
typedef std::vector<PII> VPII;
typedef std::vector<double> VD;
typedef std::vector<PDD> VPDD;
typedef std::vector<VI> VVI;
typedef std::vector<VD> VVD;
const int INF = 0x3f3f3f3f;
#define For(i, a, b, c) for (int i = (a); i < (b); i += (c))
#define R register
#define f first
#define s second
#define eb emplace_back
#define Max(a, b) a = max(a, (b));
#define Min(a, b) a = min(a, (b));
#define mcp(a, b) memcpy((a), (b), sizeof(a));
#define mcp2(a, b) memcpy((a), (b), sizeof(b));
#define fill(i, a, b, v) for (auto i = (a); i < (b); i ++ ) *i = (v)
#define f_inf(a) memset((a), 0x3f, sizeof(a));
#define f_h(a) memset((a), -1, sizeof(a));
#define lowbit(a) ((a) & -(a))
#define rt return 0
#define um unordered_map
#define us unordered_set
}
namespace IO
{
#define io ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
template<class Type>
inline void read(Type &x)
{
x = 0;
bool sign = 0;
char c = getchar();
if (c == '-') sign = 1, c = getchar();
while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
if (sign) x = -x;
}
template<class Type>
inline void write(Type x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template<class Type>
inline void write(Type *a, size_t n)
{
for (int i = 0; i < n; i ++ ) write(a[i]);
}
}
namespace math
{
unsigned qmi(unsigned a, unsigned b, unsigned p)
{
unsigned long long res = 1;
while (b)
{
if (b & 1) res = (unsigned long long)res * a % p;
a = (unsigned long long)a * a % p;
b >>= 1;
}
return res;
}
long long smul(long long a, long long b, long long p)
{
long long res = 0;
while (b)
{
if (b & 1) res = ((unsigned long long)res + a) % p;
a = ((unsigned long long)a << 1) % p;
b >>= 1;
}
return res;
}
std::vector<int> add(std::vector<int> &A, std::vector<int> &B)
{
if (A.size() < B.size()) return add(B, A);
std::vector<int> C;
int t = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.emplace_back(t % 10);
t /= 10;
}
if (t) C.emplace_back(t);
return C;
}
std::vector<int> sub(std::vector<int> &A, std::vector<int> &B)
{
std::vector<int> C;
for (int i = 0, t = 0; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.emplace_back((t + 10) % 10);
if (t < 0) t = 1;
else t = 0;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
std::vector<int> mul(std::vector<int> &A, int b)
{
std::vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.emplace_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
std::vector<int> div(std::vector<int> &A, int b, int &r)
{
std::vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.emplace_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return d;
}
}
namespace data_structure
{
template<class Type, const unsigned maxsize>
class stack
{
private:
Type s[maxsize];
unsigned len;
public:
void push(Type t)
{
if (len == maxsize) return;
s[len ++ ] = t;
}
Type top()
{
return s[len - 1];
}
void clear()
{
len = 0;
}
bool empty()
{
return !len;
}
void pop()
{
if (empty()) return;
len -- ;
}
unsigned size()
{
return len;
}
stack()
{
len = 0;
}
stack(Type *a, unsigned l)
{
len = l;
memcpy(s, a, l * sizeof(Type));
}
stack(std::vector<Type> a)
{
len = a.size();
for (unsigned i = 0; i < len; i ++ ) s[i] = a[i];
}
stack(std::vector<Type> a, unsigned l, unsigned r)
{
len = r - l;
for (unsigned i = 0; i < len; i ++ ) s[i] = a[i + l];
}
stack<Type, maxsize>(stack<Type, maxsize> &a)
{
memcpy(s, a.s, a.len * sizeof(Type));
len = a.len;
}
};
template<class Type, const unsigned maxsize, bool cmp(Type, Type) = std::greater<Type>()>
class heap
{
private:
Type h[maxsize];
unsigned len = 0;
public:
void push(Type t)
{
if (len == maxsize) return;
unsigned i;
h[i = len ++ ] = t;
while (i)
{
int f = i - 1 >> 1;
if (cmp(h[i], h[f])) break;
swap(h[i], h[f]);
i = f;
}
}
Type top()
{
return h[0];
}
unsigned size()
{
return len;
}
bool empty()
{
return !len;
}
void pop()
{
if (empty()) return;
Type t = h[0];
h[0] = h[ -- len];
unsigned i = 0;
while (i << 1 < len - 1)
{
if (i << 1 < len - 2 && h[(i << 1) + 1] < h[i + 1 << 1])
{
swap(h[i], h[i + 1 << 1]);
i = i + 1 << 1;
}
else
{
swap(h[i], h[(i << 1) + 1]);
i = (i << 1) + 1;
}
}
}
void clear()
{
len = 0;
}
heap()
{
}
heap(Type *a, int l)
{
for (unsigned i = 0; i < l; i ++ ) push(a[i]);
}
heap(std::vector<Type> a)
{
for (Type t : a) push(t);
}
heap(std::vector<Type> a, unsigned l, unsigned r)
{
for (unsigned i = l; i < r; i ++ ) push(a[i]);
}
heap<Type, maxsize, cmp>(heap<Type, maxsize, cmp> &a)
{
memcpy(h, a.h, maxsize, a.len * sizeof(Type));
len = a.len;
}
};
template<class Type, const unsigned maxsize, bool cmp(Type, Type) = std::less<Type>()>
class min_stack
{
private:
Type s[maxsize], m[maxsize];
unsigned len = 0;
public:
void push(Type t)
{
if (len == maxsize) return;
s[len] = t;
if (!len) m[len] = t;
else m[len] = (m[len - 1] ? cmp(m[len - 1], t) : t);
len ++ ;
}
Type top()
{
return s[len - 1];
}
unsigned size()
{
return len;
}
bool empty()
{
return !len;
}
void clear()
{
len = 0;
}
void pop()
{
if (!len) return;
len -- ;
}
Type min()
{
return m[len - 1];
}
min_stack()
{
}
min_stack(Type *a, unsigned l)
{
for (unsigned i = 0; i < l; i ++ ) push(a[i]);
}
min_stack(std::vector<Type> a)
{
for (Type t : a) push(t);
}
min_stack(std::vector<Type> a, unsigned l, unsigned r)
{
for (unsigned i = l; i < r; i ++ ) push(a[i]);
}
min_stack<Type, maxsize, cmp>(min_stack<Type, maxsize, cmp> &a)
{
memcpy(s, a.s, a.len * sizeof(Type));
memcpy(m, a.m, a.len * sizeof(Type));
len = a.len;
}
};
}
几行?去掉空行
bzd你自己去吧