mint

constexpr int P = 1000000007;
// assume -P <= x < 2P
int norm(int x) 
{
  if (x < 0) x += P;
  if (x >= P) x -= P;
  return x;
}
template<class T>
T qpow(T a, int b) 
{
  T res = 1;
  for (; b; b /= 2, a *= a) 
  {
    if (b % 2) res *= a;
  }
  return res;
}
struct Z
{
  int x;
  Z(int x = 0) : x(norm(x)){}
  int val()const{return x;}
  Z operator - ()const{return Z(norm(P - x));}
  Z inv()const {assert(x != 0); return qpow(*this, P - 2);}
  Z &operator *= (const Z &rhs){x = x * rhs.x % P; return *this;}
  Z &operator += (const Z &rhs){x = norm(x + rhs.x); return *this;}
  Z &operator -= (const Z &rhs){x = norm(x - rhs.x); return *this;}
  Z &operator /= (const Z &rhs){return *this *= rhs.inv();}
  friend Z operator * (const Z &lhs, const Z &rhs){Z ret = lhs; ret *= rhs; return ret;}
  friend Z operator + (const Z &lhs, const Z &rhs){Z ret = lhs; ret += rhs; return ret;}
  friend Z operator - (const Z &lhs, const Z &rhs){Z ret = lhs; ret -= rhs; return ret;}
  friend Z operator / (const Z &lhs, const Z &rhs){Z ret = lhs; ret /= rhs; return ret;}
};

树状数组

template <typename T>
struct fenwick
{
  const int n;
  vector<T> a;
  fenwick(int n) : n(n), a(n) {}
  void add(int x, T v)
  {
    for (int i = x + 1; i <= n; i += i & -i)
    {
      a[i - 1] += v;
    }
  }
  void build(vector<int> b)
  {
    for (int i = 0; i < n; i++)
      add(i, b[i]);
  }
  T sum(int x)
  {
    T res = 0;
    for (int i = x; i > 0; i -= i & -i)
    {
      res += a[i - 1];
    }
    return res;
  }
  T sum(int l, int r)
  {
    return sum(r) - sum(l);
  }
};

小素数判定

inline bool isprime(int x)
{
  if (x < 2) return false;
  for (int i = 2; i <= x / i; i ++) if (x % i == 0) return false;
  return true;
}

vector<int> pri;
vector<int> notpri(maxn);
for (int i = 2; i < maxn; i ++)
{
  if (notpri[i] == 0) pri.push_back(i);
  for (int j = 0; pri[j] * i < maxn; j ++)
  {
    notpri[i * pri[j]] = 1;
    if (i % pri[j] == 0) break;
  }
}

线段树

template <class Info,
          class Merge = plus<Info>>
struct SegmentTree
{
  const int n;
  const Merge merge;
  vector<Info> info;
  SegmentTree(int n) : n(n), merge(Merge()), info(4 << __lg(n)) {}
  SegmentTree(vector<Info> init) : SegmentTree(init.size())
  {
    function<void(int, int, int)> build = [&](int x, int l, int r)
    {
      if (r - l == 1)
      {
        info[x] = init[l];
        return;
      }
      int m = (l + r) / 2;
      build(x * 2, l, m);
      build(x * 2 + 1, m, r);
      pull(x);
    };
    build(1, 0, n);
  }
  void pull(int x)
  {
    info[x] = merge(info[x * 2], info[x * 2 + 1]);
  }
  void change(int x, int l, int r, int v, const Info &in)
  {
    if (r - l == 1)
    {
      info[x] = in;
      return;
    }
    int m = (l + r) / 2;
    if (v < m)
      change(x * 2, l, m, v, in);
    else
      change(x * 2 + 1, m, r, v, in);
    pull(x);
  }
  void change(int x, const Info &in)
  {
    change(1, 0, n, x, in);
  }
  void Init(vector<int> ve)
  {
    for (int i = 0; i < n; i++)
      change(i, ve[i]);
  }
  Info RangeQuery(int x, int l, int r, int ql, int qr)
  {
    if (l >= qr || r <= ql)
      return Info();
    if (l >= ql && r <= qr)
      return info[x];
    int m = (l + r) / 2;
    return merge(RangeQuery(x * 2, l, m, ql, qr), RangeQuery(x * 2 + 1, m, r, ql, qr));
  }
  Info RangeQuery(int l, int r)
  {
    return RangeQuery(1, 0, n, l, r);
  }
};

struct Data
{
  int x;
  Data(int v = 0) : x(v){};
};

Data operator+(const Data &lhs, const Data &rhs)
{
  return lhs.x + rhs.x;
}

主席树

struct Info
{
  int c[2];
  i64 s[2];
  Info() : c{}, s{} {}
  Info(int x, int v) : Info()
  {
    c[x] = 1;
    s[x] = v;
  }
};

Info operator+(const Info &a, const Info &b)
{
  Info c;
  c.c[0] = a.c[0] + b.c[0];
  c.c[1] = a.c[1] + b.c[1];
  c.s[0] = a.s[0] + b.s[0];
  c.s[1] = a.s[1] + b.s[1];
  return c;
}

void apply(Info &a, int b)
{
  if (b)
  {
    swap(a.c[0], a.c[1]);
    swap(a.s[0], a.s[1]);
  }
}

void apply(int &a, int b)
{
  a ^= b;
}

template <class Info, class Tag,
          class Merge = plus<Info>>
struct LazySegmentTree
{
  const int n;
  const Merge merge;
  vector<Info> info;
  vector<Tag> tag;
  LazySegmentTree(int n) : n(n), merge(Merge()), info(4 << __lg(n)), tag(4 << __lg(n)) {}
  LazySegmentTree(vector<Info> init) : LazySegmentTree(init.size())
  {
    function<void(int, int, int)> build = [&](int p, int l, int r)
    {
      if (r - l == 1)
      {
        info[p] = init[l];
        return;
      }
      int m = (l + r) / 2;
      build(2 * p, l, m);
      build(2 * p + 1, m, r);
      pull(p);
    };
    build(1, 0, n);
  }
  void pull(int p)
  {
    info[p] = merge(info[2 * p], info[2 * p + 1]);
  }
  void apply(int p, const Tag &v)
  {
    ::apply(info[p], v);
    ::apply(tag[p], v);
  }
  void push(int p)
  {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = Tag();
  }
  void modify(int p, int l, int r, int x, const Info &v)
  {
    if (r - l == 1)
    {
      info[p] = v;
      return;
    }
    int m = (l + r) / 2;
    push(p);
    if (x < m)
    {
      modify(2 * p, l, m, x, v);
    }
    else
    {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int p, const Info &v)
  {
    modify(1, 0, n, p, v);
  }
  Info rangeQuery(int p, int l, int r, int x, int y)
  {
    if (l >= y || r <= x)
    {
      return Info();
    }
    if (l >= x && r <= y)
    {
      return info[p];
    }
    int m = (l + r) / 2;
    push(p);
    return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y));
  }
  Info rangeQuery(int l, int r)
  {
    return rangeQuery(1, 0, n, l, r);
  }
  bool rangeApply(int p, int l, int r, int x, int y, const Tag &v)
  {
    if (l >= y || r <= x)
    {
      return true;
    }
    if (l >= x && r <= y && info[p].c[0] + info[p].c[1] == r - l)
    {
      apply(p, v);
      return true;
    }
    if (l >= x && r <= y && info[p].c[0] + info[p].c[1] == 0)
    {
      return false;
    }
    int m = (l + r) / 2;
    push(p);
    bool res;
    if (rangeApply(2 * p + 1, m, r, x, y, v))
    {
      res = rangeApply(2 * p, l, m, x, y, v);
    }
    else
    {
      res = false;
    }
    pull(p);
    return res;
  }
  bool rangeApply(int l, int r, const Tag &v)
  {
    return rangeApply(1, 0, n, l, r, v);
  }
};

莫队

inline void solve()
{
  int n, q; cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x, x --;
  cin >> q;
  vector<int> l(q), r(q);
  for (int i = 0; i < q; i ++)
  {
    cin >> l[i] >> r[i];
    l[i] --;
  }
  vector<int> fa(q);
  iota(fa.begin(), fa.end(), 0);
  const int B = max(1.0, n / sqrt(q));
  sort(fa.begin(), fa.end(), [&](int x, int y)
  {
    if (l[x] / B == l[y] / B) return r[x] < r[y];
    return l[x] < l[y];
  });
  vector<int> cnt(n);
  int L = 0, R = 0, res = 0;
  auto add = [&](int x, int c)
  {
    res -= cnt[x] / 2;
    cnt[x] += c;
    res += cnt[x] / 2;
  };
  vector<int> ans(q);
  for (int x : fa)
  {
    while (L > l[x]) add(a[-- L], 1);
    while (R < r[x]) add(a[R ++], 1);
    while (L < l[x]) add(a[L ++], -1);
    while (R > r[x]) add(a[-- R], -1);
    ans[x] = res;
  }
  for (int x : ans) cout << x << "\n";
}

组合数

vector<Z> fac(n + 1), invfac(n + 1);
fac[0] = 1;
for (int i = 1; i <= n; i ++) fac[i] = fac[i - 1] * i;
invfac[n] = fac[n].inv();
for (int i = n; i; i --) invfac[i - 1] = invfac[i] * i;

计算几何

const int maxn = 1005;
const double eps = 1e-5;

inline int sgn(double x){return fabs(x) < eps ? 0 : (x < 0 ? -1 : 1);}
inline int cmp(double x, double y){return sgn(x - y);}

struct Point
{
  double x;
  double y;
};
typedef Point Vector;
Vector operator + (Vector a, Vector b){return (Vector){a.x + b.x, a.y + b.y};} //点的四则运算
Vector operator - (Vector a, Vector b){return (Vector){a.x - b.x, a.y - b.y};}
Vector operator * (Vector a, double b){return (Vector){a.x * b, a.y * b};}
Vector operator / (Vector a, double b){return (Vector){a.x / b, a.y / b};}
double operator & (Vector a, Vector b){return a.x * b.x + a.y * b.y;} // 点积
double operator ^ (Vector a, Vector b){return a.x * b.y - a.y * b.x;} // 叉积
double PointDistance(Point a, Point b){return sqrt((b - a) & (b - a));} // 点距

struct Line // 直线
{
  Point Pa;
  Point Pb;
};
typedef Line Segment; // 线段 
double LineDistance(Line a, Segment b){return ((b.Pa - a.Pa) ^ (b.Pb - a.Pa)) / ((b.Pb - b.Pa) ^ (a.Pb - a.Pa)) * PointDistance(a.Pa, a.Pb);}
// 平行线距
struct Status
{
  double Length;
  int Flag;
};
inline bool operator < (Status a, Status b){return sgn(b.Length - a.Length) > 0;}

inline bool InLine(double x, double y, double z){return sgn(x - z) * sgn(y - z) <= 0;}
inline bool InLine(Point P1, Point P2, Point P3){return InLine(P1.x, P2.x, P3.x) && InLine(P1.y, P2.y, P3.y);} // 共线

inline double Cross(Point P1, Point P2, Point P3)
{
  return (P1.x - P3.x) * (P2.y - P3.y) - (P1.y - P3.y) * (P2.x - P3.x);
}

inline Point GetCrossPoint(Point P1, Point P2, Point P3, Point P4) // 求交点
{
  double W1 = (P1 - P3) ^ (P4 - P3), W2 = (P4 - P3) ^ (P2 - P3);
  return (Point)((P1 * W2 + P2 * W1) / (W1 + W2));
}

区间调度

int N = read(), D = read();
vector<PII> A(N);
For(i,0,N-1)
{
  A[i].fir = read();
  A[i].sec = read();
}
sort(A.begin(), A.end(), [&](const PII &a, const PII &b){return a.sec < b.sec;});
int x = LLONG_MIN, ans = 0;
for (auto [l, r] : A)
{
  if (x + D - 1 < l) ans ++, x = r;
}

数论分块

for (int l = 1, r; l <= min(N, K); l = r + 1)
{
  r = min(N, K / (K / l));
  ans -= (r - l + 1) * (K / l) * (l + r) / 2;
}

稀疏表

struct DualSpareTable
{
  int n, Log;
  vector<vector<int>> ST;
  DualSpareTable(int n) : n(n)
  {
    Log = 32 - __builtin_clz(n);
    ST = vector<vector<int>> (Log, vector<int>(n, INF));
  }
  void RangeChmin(int l, int r, int x)
  {
    int d = 31 - __builtin_clz(r - l);
    ST[d][l] = min(ST[d][l], x);
    ST[d][r - (1 << d)] = min(ST[d][r - (1 << d)], x);
  }
  vector<int> Get()
  {
    for (int i = Log - 2; i >= 0; -- i)
    {
      for (int j = 0; j < n - (1 << i); j ++)
      {
        ST[i][j] = min(ST[i][j], ST[i + 1][j]);
        ST[i][j + (1 << i)] = min(ST[i][j + (1 << i)], ST[i + 1][j]);
      }
    }
    return ST[0];
  }
};

并查集

struct dsu
{
  vector<int> fa, sz;

  dsu(int n) : fa(n), sz(n, 1){iota(fa.begin(), fa.end(), 0);}
  int find(int x){while (x != fa[x]) x = fa[x] = fa[fa[x]]; return x;}
  bool same(int x, int y){return find(x) == find(y);}
  bool merge(int x, int y)
  {
    x = find(x); y = find(y);
    if (x == y) return false;
    sz[x] += sz[y];
    fa[y] = x;
    return true;
  }
  int size(int x){return sz[find(x)];}
};

平衡树

struct Trie
{
  vector<int> l, r, c;
  Trie() : l(1, -1), r(1, -1), c(1, 0) {}
  int newNode()
  {
    int i = l.size();
    l.push_back(-1);
    r.push_back(-1);
    c.push_back(0);
    return i;
  }
  int getNext(int i, int a, bool read = true)
  {
    if (a == 0)
    {
      if (l[i] == -1 and !read)
      {
        int ni = newNode();
        l[i] = ni;
      }
      return l[i];
    }
    else
    {
      if (r[i] == -1 and !read)
      {
        int ni = newNode();
        r[i] = ni;
      }
      return r[i];
    }
  }
  void add(ll x)
  {
    int i = 0;
    c[0]++;
    for (ll b = 1ll << K; b; b >>= 1)
    {
      int a = (x & b) ? 1 : 0;
      i = getNext(i, a, false);
      c[i]++;
    }
  }
  void del(ll x)
  {
    int i = 0;
    c[0]--;
    for (ll b = 1ll << K; b; b >>= 1)
    {
      int a = (x & b) ? 1 : 0;
      i = getNext(i, a, false);
      c[i]--;
    }
  }
  int count(ll x)
  { // count <= x
    int i = 0, res = 0;
    for (ll b = 1ll << K; b; b >>= 1)
    {
      int a = (x & b) ? 1 : 0;
      if (a == 1)
      {
        if (l[i] != -1)
          res += c[l[i]];
      }
      i = getNext(i, a);
      if (i == -1)
        return res;
    }
    res += c[i];
    return res;
  }
  ll getKth(int k)
  {
    if (k <= 0 or c[0] < k)
      return -1;
    int i = 0;
    ll res = 0;
    for (ll b = 1ll << K; b; b >>= 1)
    {
      if (l[i] != -1 and c[l[i]] >= k)
      {
        i = l[i];
      }
      else
      {
        k -= c[l[i]];
        i = r[i];
        res |= b;
      }
    }
    return res;
  }
};

去重、离散化

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int inf = 1e18;
constexpr int maxn = 2e5 + 5;
constexpr int mod = 998244353;
inline void solve()
{
  int n; cin >> n;
  vector<int> a(n);
  for (int &x : a) cin >> x;
  vector<int> b(a);
  sort(a.begin(), a.end());
  a.erase(unique(a.begin(), a.end()), a.end());
  for (int x : a) cout << x << " ";
  cout << "\n";
  vector<int> id(n);
  for (int i = 0; i < n; i ++)
  {
    id[i] = distance(a.begin(), lower_bound(a.begin(), a.end(), b[i]));
  }
  for (int x : id) cout << x << " ";
  cout << "\n";
}


signed main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
/*
The details you should care:

*/

struct Map
{
  typedef int T;
  vector<T> d;
  void add(T x)
  {
    d.push_back(x);
  }
  void init()
  {
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
  }
  inline int size(){return (int)d.size();}
  inline T operator[](T x){return distance(a.begin(), lower_bound(a.begin(), a.end(), b[i]));}
};