Hello World

基础算法

STL容器

C++标准模板库 Standard Template Library，简称STL。STL库：STL容器和STL算法。

底层实现方式：

queue：队列是先进先出的，和排队类似。队头的访问和删除操作只能在队头进行，添加操作只能在队尾进行。不能访问队列中间的元素。

priority_queue（大根堆）：完全二叉树，它和普通队列的区别在于，优先队列的队头元素总是最大的——即执行 pop 操作时，删除的总是最大的元素；执行 top 操作时，返回的是最大元素的引用。priority_queue 默认的元素比较器是 less 。对于队头的元素 x 和任意非队头的元素 y，表达式“x<y”必为 false。priority_queue 的第三个类型参数可以用来指定排序规则。priority_queue 队头的元素只能被查看或者修改，不能被删除。

set：红黑树

unordered_set：哈希表（取决于哈希函数，通常比set快）

map：红黑树

unordered_set：哈希表（取决于哈希函数）

重载小于号

struct edge
{
    int u, v, w;
    bool operator<(const edge &t) const
    {
        return w < t.w;
    }
};

快读

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int128

void scan(__int128 &x) { //输入
	x = 0;
	int f = 1;
	char ch;
	if((ch = getchar()) == '-') f = -f;
	else x = x*10 + ch-'0';
	while((ch = getchar()) >= '0' && ch <= '9')
		x = x*10 + ch-'0';
	x *= f;
}

void _print(__int128 x) {
	if(x > 9) _print(x/10);
	putchar(x%10 + '0');
}
void print(__int128 x) { //输出
	if(x < 0) {
		x = -x;
		putchar('-');
	}
	_print(x);
}

高精度

命名空间

typedef long long ll;
typedef long double ld;
typedef complex<ld> pt;
const int MOD = 1e9 + 7;
const ld PI = acos(-1.L);
 
template<class T> struct cplx {
  T x, y;
  cplx() {
    x = 0.0;
    y = 0.0;
  }
  cplx(T nx, T ny = 0) {
    x = nx;
    y = ny;
  }
  cplx operator+(const cplx &c) const {
    return {x + c.x, y + c.y};
  }
  cplx operator-(const cplx &c) const {
    return {x - c.x, y - c.y};
  }
  cplx operator*(const cplx &c) const {
    return {x*c.x - y * c.y, x*c.y + y * c.x};
  }
  cplx& operator*=(const cplx &c) {
    return *this = {x*c.x - y * c.y, x*c.y + y * c.x};
  }
  inline T real() const {
    return x;
  }
  inline T imag() const {
    return y;
  }
  // Only supports right scalar multiplication like p*c
  template<class U> cplx operator*(const U &c) const {
    return {x * c, y * c};
  }
  template<class U> cplx operator/(const U &c) const {
    return {x / c, y / c};
  }
  template<class U> void operator/=(const U &c) {
    x /= c;
    y /= c;
  }
};
#define polar(r,a)  (cplx<ld>){r*cos(a),r*sin(a)}
 
const int DIG = 9, FDIG = 4;
const int BASE = 1e9, FBASE = 1e4;
typedef cplx<ld> Cplx;
 
 
// use mulmod when taking mod by int v and v>2e9
// you can use mod by bigint in that case too
struct BigInt {
  int sgn;
  vector<int> a;
  BigInt() : sgn(1) {}
  BigInt(ll v) {
    *this = v;
  }
  BigInt& operator = (ll v) {
    sgn = 1;
    if (v < 0) sgn = -1, v = -v;
    a.clear();
    for (; v > 0; v /= BASE) a.push_back(v % BASE);
    return *this;
  }
  BigInt(const BigInt& other) {
    sgn = other.sgn;
    a = other.a;
  }
  friend void swap(BigInt& a, BigInt& b) {
    swap(a.sgn, b.sgn);
    swap(a.a, b.a);
  }
  BigInt& operator = (BigInt other) {
    swap(*this, other);
    return *this;
  }
  BigInt(BigInt&& other) : BigInt() {
    swap(*this, other);
  }
  BigInt(const string& s) {
    read(s);
  }
  void read(const string& s) {
    sgn = 1;
    a.clear();
    int k = 0;
    for (; k < s.size() && (s[k] == '-' || s[k] == '+'); k++)
      if (s[k] == '-') sgn = -sgn;
    for (int i = s.size() - 1; i >= k; i -= DIG) {
      int x = 0;
      for (int j = max(k, i - DIG + 1); j <= i; j++) x = x * 10 + s[j] - '0';
      a.push_back(x);
    }
    trim();
  }
  friend istream& operator>>(istream &in, BigInt &v) {
    string s;
    in >> s;
    v.read(s);
    return in;
  }
  friend ostream& operator<<(ostream &out, const BigInt &v) {
    if (v.sgn == -1 && !v.zero()) out << '-';
    out << (v.a.empty() ? 0 : v.a.back());
    for (int i = (int) v.a.size() - 2; i >= 0; --i)
      out << setw(DIG) << setfill('0') << v.a[i];
    return out;
  }
  bool operator<(const BigInt &v) const {
    if (sgn != v.sgn) return sgn < v.sgn;
    if (a.size() != v.a.size()) return a.size() * sgn < v.a.size() * v.sgn;
    for (int i = (int)a.size() - 1; i >= 0; i--)
      if (a[i] != v.a[i]) return a[i] * sgn < v.a[i] * sgn;
    return 0;
  }
  bool operator>(const BigInt &v) const {
    return v < *this;
  }
  bool operator<=(const BigInt &v) const {
    return !(v < *this);
  }
  bool operator>=(const BigInt &v) const {
    return !(*this < v);
  }
  bool operator==(const BigInt &v) const {
    return !(*this < v) && !(v < *this);
  }
  bool operator!=(const BigInt &v) const {
    return *this < v || v < *this;
  }
  friend int __cmp(const BigInt& x, const BigInt& y) {
    if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
    for (int i = (int) x.a.size() - 1; i >= 0; --i) if (x.a[i] != y.a[i])
        return x.a[i] < y.a[i] ? -1 : 1;
    return 0;
  }
 
  BigInt operator-() const {
    BigInt res = *this;
    if (zero()) return res;
    res.sgn = -sgn;
    return res;
  }
 
  void __add(const BigInt& v) {
    if (a.size() < v.a.size()) a.resize(v.a.size(), 0);
    for (int i = 0, carry = 0; i < max(a.size(), v.a.size()) || carry; ++i) {
      if (i == a.size()) a.push_back(0);
      a[i] += carry + (i < (int) v.a.size() ? v.a[i] : 0);
      carry = a[i] >= BASE;
      if (carry) a[i] -= BASE;
    }
  }
 
  void __sub(const BigInt& v) {
    for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) {
      a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0);
      carry = a[i] < 0;
      if (carry) a[i] += BASE;
    }
    this->trim();
  }
 
  BigInt operator+=(const BigInt& v) {
    if (sgn == v.sgn) __add(v);
    else if (__cmp(*this, v) >= 0) __sub(v);
    else {
      BigInt vv = v;
      swap(*this, vv);
      __sub(vv);
    }
    return *this;
  }
 
  BigInt operator-=(const BigInt& v) {
    if (sgn == v.sgn) {
      if (__cmp(*this, v) >= 0) __sub(v);
      else {
        BigInt vv = v;
        swap(*this, vv);
        __sub(vv);
        sgn = -sgn;
      }
    } else __add(v);
    return *this;
  }
 
  template< typename L, typename R >
  typename enable_if <
  is_convertible<L, BigInt>::value &&
  is_convertible<R, BigInt>::value &&
  is_lvalue_reference < R&& >::value,
  BigInt >::type friend operator + (L&& l, R&& r) {
    BigInt result(forward<L>(l));
    result += r;
    return result;
  }
  template< typename L, typename R >
  typename enable_if <
  is_convertible<L, BigInt>::value &&
  is_convertible<R, BigInt>::value &&
  is_rvalue_reference < R&& >::value,
  BigInt >::type friend operator + (L&& l, R&& r) {
    BigInt result(move(r));
    result += l;
    return result;
  }
  template< typename L, typename R >
  typename enable_if <
  is_convertible<L, BigInt>::value &&
  is_convertible<R, BigInt>::value,
  BigInt >::type friend operator - (L&& l, R&& r) {
    BigInt result(forward<L>(l));
    result -= r;
    return result;
  }
 
  friend pair<BigInt, BigInt> divmod(const BigInt& a1, const BigInt& b1) {
    ll norm = BASE / (b1.a.back() + 1);
    BigInt a = a1.abs() * norm, b = b1.abs() * norm, q = 0, r = 0;
    q.a.resize(a.a.size());
    for (int i = a.a.size() - 1; i >= 0; i--) {
      r *= BASE;
      r += a.a[i];
      ll s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()];
      ll s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1];
      ll d = ((ll) BASE * s1 + s2) / b.a.back();
      r -= b * d;
      while (r < 0) r += b, --d;
      q.a[i] = d;
    }
    q.sgn = a1.sgn * b1.sgn;
    r.sgn = a1.sgn;
    q.trim();
    r.trim();
    auto res = make_pair(q, r / norm);
    if (res.second < 0) res.second += b1;
    return res;
  }
  BigInt operator/(const BigInt &v) const {
    return divmod(*this, v).first;
  }
  BigInt operator%(const BigInt &v) const {
    return divmod(*this, v).second;
  }
  void operator/=(int v) {
    if (llabs(v) >= BASE) {
      *this /= BigInt(v);
      return;
    }
    if (v < 0) sgn = -sgn, v = -v;
    for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) {
      ll cur = a[i] + rem * (ll)BASE;
      a[i] = (int) (cur / v);
      rem = (int) (cur % v);
    }
    trim();
  }
  BigInt operator/(int v) const {
    if (llabs(v) >= BASE) return *this / BigInt(v);
    BigInt res = *this;
    res /= v;
    return res;
  }
  void operator/=(const BigInt &v) {
    *this = *this / v;
  }
  ll operator%(ll v) const {
    int m = 0;
    for (int i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (ll) BASE) % v;
    return m * sgn;
  }
  void operator*=(int v) {
    if (llabs(v) >= BASE) {
      *this *= BigInt(v);
      return;
    }
    if (v < 0) sgn = -sgn, v = -v;
    for (int i = 0, carry = 0; i < a.size() || carry; ++i) {
      if (i == a.size()) a.push_back(0);
      ll cur = a[i] * (ll) v + carry;
      carry = (int) (cur / BASE);
      a[i] = (int) (cur % BASE);
    }
    trim();
  }
  BigInt operator*(int v) const {
    if (llabs(v) >= BASE) return *this * BigInt(v);
    BigInt res = *this;
    res *= v;
    return res;
  }
 
  static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) {
    vector<ll> p(max(old_digits, new_digits) + 1);
    p[0] = 1;
    for (int i = 1; i < (int) p.size(); i++)
      p[i] = p[i - 1] * 10;
    vector<int> res;
    ll cur = 0;
    int cur_digits = 0;
    for (int i = 0; i < (int) a.size(); i++) {
      cur += a[i] * p[cur_digits];
      cur_digits += old_digits;
      while (cur_digits >= new_digits) {
        res.push_back((ll)(cur % p[new_digits]));
        cur /= p[new_digits];
        cur_digits -= new_digits;
      }
    }
    res.push_back((int) cur);
    while (!res.empty() && !res.back())
      res.pop_back();
    return res;
  }
 
  void fft(vector<Cplx>& a, bool invert) const {
    int n = a.size();
    for (int i = 1, j = 0; i < n; ++i) {
      int bit = n / 2;
      for (; j >= bit; bit /= 2) j -= bit;
      j += bit;
      if (i < j) swap(a[i], a[j]);
    }
    for (int len = 2; len <= n; len *= 2) {
      ld ang = 2 * PI / len * (invert ? -1 : 1);
      Cplx wlen = polar(1, ang);
      for (int i = 0; i < n; i += len) {
        Cplx w(1);
        for (int j = 0; j < len / 2; ++j) {
          Cplx u = a[i + j], v = a[i + j + len / 2] * w;
          a[i + j] = u + v;
          a[i + j + len / 2] = u - v;
          w *= wlen;
        }
      }
    }
    if (invert) for (int i = 0; i < n; ++i) a[i] /= n;
  }
  void multiply_fft(const vector<int> &a, const vector<int> &b, vector<int> &res) const {
    vector<Cplx> fa(a.begin(), a.end()), fb(b.begin(), b.end());
    int n = 1;
    while (n < max(a.size(), b.size())) n *= 2;
    n *= 2;
    fa.resize(n);
    fb.resize(n);
    fft(fa, 0);
    fft(fb, 0);
    for (int i = 0; i < n; ++i) fa[i] *= fb[i];
    fft(fa, 1);
    res.resize(n);
    ll carry = 0;
    for (int i = 0; i < n; i++) {
      ll t = (ll)(fa[i].real() + 0.5) + carry;
      carry = t / FBASE;
      res[i] = t % FBASE;
    }
  }
  static inline int rev_incr(int a, int n) {
    int msk = n / 2, cnt = 0;
    while ( a & msk ) {
      cnt++;
      a <<= 1;
    }
    a &= msk - 1;
    a |= msk;
    while ( cnt-- ) a >>= 1;
    return a;
  }
  static vector<Cplx> FFT(vector<Cplx> v, int dir = 1) {
    Cplx wm, w, u, t;
    int n = v.size();
    vector<Cplx> V(n);
    for (int k = 0, a = 0; k < n; ++k, a = rev_incr(a, n))
      V[a] = v[k] / ld(dir > 0 ? 1 : n);
    for (int m = 2; m <= n; m <<= 1) {
      wm = polar( (ld)1, dir * 2 * PI / m );
      for (int k = 0; k < n; k += m) {
        w = 1;
        for (int j = 0; j < m / 2; ++j, w *= wm) {
          u = V[k + j];
          t = w * V[k + j + m / 2];
          V[k + j] = u + t;
          V[k + j + m / 2] = u - t;
        }
      }
    }
    return V;
  }
  static void convolution(const vector<int>& a, const vector<int>& b, vector<int>& c) {
    int sz = a.size() + b.size() - 1;
    int n  = 1 << int(ceil(log2(sz)));
    vector<Cplx> av(n, 0), bv(n, 0), cv;
    for (int i = 0; i < a.size(); i++) av[i] = a[i];
    for (int i = 0; i < b.size(); i++) bv[i] = b[i];
    cv = FFT(bv);
    bv = FFT(av);
    for (int i = 0; i < n; i++) av[i] = bv[i] * cv[i];
    cv = FFT(av, -1);
    c.resize(n);
    ll carry = 0;
    for (int i = 0; i < n; i++) {
      ll t = ll(cv[i].real() + 0.5) + carry;
      carry = t / FBASE;
      c[i] = t % FBASE;
    }
  }
  BigInt mul_simple(const BigInt &v) const {
    BigInt res;
    res.sgn = sgn * v.sgn;
    res.a.resize(a.size() + v.a.size());
    for (int i = 0; i < a.size(); i++) if (a[i])
        for (int j = 0, carry = 0; j < v.a.size() || carry; j++) {
          ll cur = res.a[i + j] + (ll) a[i] * (j < v.a.size() ? v.a[j] : 0) + carry;
          carry = (int) (cur / BASE);
          res.a[i + j] = (int) (cur % BASE);
        }
    res.trim();
    return res;
  }
  BigInt mul_fft(const BigInt& v) const {
    BigInt res;
    convolution(convert_base(a, DIG, FDIG), convert_base(v.a, DIG, FDIG), res.a);
    res.a = convert_base(res.a, FDIG, DIG);
    res.trim();
    return res;
  }
  void operator*=(const BigInt &v) {
    *this = *this * v;
  }
  BigInt operator*(const BigInt &v) const {
    if (1LL * a.size() * v.a.size() <= 1000111) return mul_simple(v);
    return mul_fft(v);
  }
 
  BigInt abs() const {
    BigInt res = *this;
    res.sgn *= res.sgn;
    return res;
  }
  void trim() {
    while (!a.empty() && !a.back()) a.pop_back();
  }
  bool zero() const {
    return a.empty() || (a.size() == 1 && !a[0]);
  }
  friend BigInt gcd(const BigInt &a, const BigInt &b) {
    return b.zero() ? a : gcd(b, a % b);
  }
};
BigInt power(BigInt a, ll k) {
  BigInt ans = 1;
  while (k > 0) {
    if (k & 1) ans *= a;
    a *= a;
    k >>= 1;
  }
  return ans;
}

命名空间2

struct bigNum{
  int A[1001];//高精度加法实质上是对数组操作，所以结构体需要一个数组成员
  int Len;//在计算中需要用到数组的长度，所以将它作为成员列出
  void input(){
        string s;
        cin>>s;//输入字符串 
        memset(A,0,sizeof(A));//将数组A中的所有元素初始化为0 
        Len=s.length();//数组长度即为字符串的长度 
        for(int i=0;i<Len;i++){
        A[i]=s[i]-'0';
        }//将字符串转换成对应的数字 
        reverse(A,A+Len);//将数组A反转（逆序），方便后面计算 
           
    }  //输入函数：将输入的字符串转化为数组并将数组逆序 
    void output(){
      for(int i=0;i<Len;i++){
        cout<<A[i];
    }
  }//输出函数 
  bigNum operator + (const bigNum x) const{
     bigNum tmp;
     tmp.Len=max(Len,x.Len);
     int C[tmp.Len];
     memset(C,0,sizeof(C));
     for(int i=0;i<=tmp.Len;i++){
    //注意由于涉及到进位，和的位数可能会比加数多一位，所以这里要计算到tmp.Len,而不是tmp.Len-1 
         tmp.A[i]=A[i]+x.A[]+C[i];
         if(tmp.A[i]>=10) {
             C[i+1]=(tmp.A[i])/10;
             tmp.A[i]%=10;
       }
     }
     if (tmp.A[tmp.Len]>0) tmp.Len++;
     reverse(tmp.A,tmp.A+tmp.Len); //将求和后的数组反转，便于之后输出
     memset(C,0,sizeof(C));//将数组C初始化，所有元素值为0，以备下次计算时使用。
     return tmp;
     
  }//重载运算符 +  高精度加法（将输入的两个含有数字的字符串相加，求和） 
};
//结构体bigNum 中有变量 A[i]、Len；函数input output 和重载的运算+

双指针（尺取法）

双指针（又称尺取法）是一个常用的优化技巧，用来解决序列的区间问题。

两个指针 $i,j$ ，有两种扫描方向：

1. 反向扫描： $i,j$ 方向相反， $i$ 从头到尾， $j$ 从尾到头，在中间相会。
2. 同向扫描： $i,j$ 方向相同，都从头到尾，可以让 $j$ 跑在 $i$ 前面。
   • 同向扫描的两个指针称为“快慢指针”，快慢指针在序列上产生一个大小可变的“滑动窗口”，有灵活的应用。

洛谷 P1147 连续自然数和

归并排序

主要利用分治思想，时间复杂度 $O(n\log n)$

1. 对数列不断等长拆分，直到一个数的长度。
2. 回溯时，按升序合并左右两段。
3. 重复以上两个过程,直到递归结束。

合并

1. $i,j$ 分别指向 $a$ 的左右段起点， $k$ 指向 $b$ 的起点。
2. 枚举 $a$ 数组，如果左数≤右数，把左数放入 $b$ 数组，否则，把右数放入 $b$ 数组。（这里的等于保证了排序的稳定）
3. 把左段或右段剩余的数放入 $b$ 数组。
4. 把 $b$ 数组的当前段复制回 $a$ 数组。

ST表（Sparse Table，稀疏表）

洛谷 P1440 求m区间内的最小值

Q：给定一个长度为 $N$ 的数列，和 $M$ 次询问，求出每一次询问的区间内数字的最大值。

ST表主要用来解决RMQ(区间最大/最小值查询)问题。主要应用倍增思想，可以实现 $O(n\log n)$ 预处理、 $O(1)$ 查询。

1.预处理ST表

倍增法递推：用两个等长小区间拼凑一个大区间

$f[i][j] $ 以第 $i $ 个数为起点，长度为 $2^j$ )的区间中的最大值。

$f [ i ] [ j ] = m a x ( f [ i ] [ j - 1 ] , f [ i + 2 ^ { j - 1 } ] [ j - 1 ] )$

区间终点： $i + 2^j - 1 \leq n$

const int N = 500005;
int f[N][32] = {0};
// 区间长度为2^0=1的时，只有本身元素，所以直接输入
for (int i = 1; i <= n; i++)
    cin >> f[i][0];
// 最大长度需要小于2^20
for (int j = 1; j <= 20; j++)
{
    // 枚举起点,i+2^j-1大于n，代表以及超出范围里
    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]);
    }
}

2.处理询问

对查询区间 $[l,r]$ 做分割、拼凑，区间长度的指数 $k=\log_2(r-l+1)$

$\begin{align}&k=0:{1}\&k=1:{2,3}\&k=2:{4,5,6,7}\&k=3:{8,9,10,\cdots,15}\end{align}$

观察发现： $2 ^ { k } \leq r - l + 1 \lt 2 \cdot 2 ^ { k }$

即区间 $[l,r]$ 必可以用两个长度为 $2^k$ 的区间重叠拼凑。

凡是符合结合律且可重复贡献的信息查询都可以使用ST表，显然最大值、最小值、最大公因数、最小公倍数、按位或、
按位与都符合这个条件。

如果涉及区间修改操作，就要使用线段树啦。

即 $\max(f[l][k],f[r-2^k+1][k])$

// q次查询
for (int i = 1, l, r; i <= q; i++)
{
    // 区间起点l和重点r
    cin >> l >> r;
    // 区间长度的指数
    int k = log2(r - l + 1);
    // 前取2^k,后取2^k
    cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;
}

完整代码

const int N = 500005;
int f[N][32] = {0};

int n, q;
cin >> n >> q;

// 区间长度为2^0=1的时，只有本身元素，所以直接输入
for (int i = 1; i <= n; i++)
    cin >> f[i][0];
// 最大长度需要小于2^30
for (int j = 1; j <= 20; j++)
{
    // 枚举起点,i+2^j-1大于n，代表以及超出范围里
    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]);
    }
}

// q次查询
for (int i = 1, l, r; i <= q; i++)
{
    // 区间起点l和重点r
    cin >> l >> r;
    // 区间长度的指数
    int k = log2(r - l + 1);
    // 前取2^k,后取2^k
    cout << max(f[l][k], f[r - (1 << k) + 1][k]) << endl;
}