ACM

[TOC]

定义

开头

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const double Pi = acos(-1.0);
const double eps = 1e-8;
const int maxn = 1e7 + 10;

快读

正常快读

inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}

读入挂

inline char nc() {
    static char buf[100000], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int rd(){
  int x = 0; char ch = nc();
  while (ch < '0' || ch>'9') {ch = nc(); }
  while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = nc(); }
  return x;
}

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);
}

优化

/* 开启优化的情况下未赋初始值的变量可能赋随机值 */
// O2优化
#pragma GCC optimize(2)
// O3优化
#pragma GCC optimize(3)

STL 黑科技

可持久化平衡树

#include <ext/rope>
using namespace __gnu_cxx;

rope<int> a;
rope<char> a;
a.push_back(x)	// 在末尾插入
a.pop_back(x)	// 删除最后一个元素
a.size()	// 返回长度
a.insert(int pos, x)	// 在pos插入x
a.erase(int pos, int sum)	// 在pos删除sum个元素
a.replace(int pos, x)	// 将pos替换为x
a.substr(int pos, int sum)	// 在pos处截取sum个元素
a.at(x) a[x] 	//访问第x个元素

字符串

字符串哈希+二分最长公共前缀

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 1e5 + 10;
const int N = 1e5 + 10;
const int P = 131;
ULL h[N], h2[N], p[N];
char s[maxn], s2[maxn];
int n;
void init()
{

    n = strlen(s + 1);
    for (int i = n; i >= 1; i--)
        s2[n - i + 1] = s[i];
    s2[n + 1] = '\0';
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        h[i] = h[i - 1] * P + s[i];
        h2[i] = h2[i - 1] * P + s2[i];
        p[i] = p[i - 1] * P;
    }
}
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
ULL get_re(int l, int r)
{
    swap(l, r);
    l = n - l + 1;
    r = n - r + 1;
    return h2[r] - h2[l - 1] * p[r - l + 1];
}
signed main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s + 1);
        init();
        int a[30] = {0};
        for (int i = 1; i <= n; i++)
            a[s[i] - 'a' + 1]++;
        for (int i = 1; i <= 26; i++)
            a[i] += a[i - 1];
        int l = -1;
        for (int i = 1; i <= n; i++)
        {
            if (a[s[i] - 'a'] > i - 1)
            {
                l = i;
                break;
            }
        }
        // cout << get(1, 3) << " " << get_re(5, 7) << endl;
        // cout << l << endl;
        if (l == -1)
        {
            printf("%s\n", s + 1);
            continue;
        }
        int min_posr = n;
        for (int i = n - 1; i > l; i--)
        {
            int len = i - l + 1;
            int ll = 0, rr = len;
            while (ll < rr)
            {
                int mid = ll + rr + 1 >> 1;
                ULL hhash1 = get_re(min_posr - mid + 1, min_posr);
                ULL hhash2 = get_re(i - mid + 1, i);
                if (hhash1 == hhash2)
                    ll = mid;
                else
                    rr = mid - 1;
            }
            if (ll != len)
            {
                if (s[min_posr - rr] > s[i - rr])
                {
                    min_posr = i;
                    // cout << min_posr << "\n";
                }
            }
            else
            {
                int len2 = min_posr - l - ll + 1;
                int lll = 0, rrr = len2;
                while (lll < rrr)
                {
                    int mid = lll + rrr + 1 >> 1;
                    ULL hhash1 = get(l + ll, l + ll + mid - 1);
                    ULL hhash2 = get_re(min_posr - ll - mid + 1, min_posr - ll);
                    if (hhash1 == hhash2)
                        lll = mid;
                    else
                        rrr = mid - 1;
                }
                // cout << l << " " << ll << " " << min_posr << " " << lll << "\n";
                // cout << l + ll + lll << " " << min_posr - ll - lll << "\n";
                // cout << i << "\n";
                if (s[l + ll - 1 + lll + 1] < s[min_posr - ll + 1 - lll - 1])
                    min_posr = i;
                // cout << 1 << " \n";
            }
        }
        for (int i = 1; i < l; i++)
            printf("%c", s[i]);
        for (int i = min_posr; i >= l; i--)
            printf("%c", s[i]);
        for (int i = min_posr + 1; i <= n; i++)
            printf("%c", s[i]);
        puts("");
    }
}

后缀数组

const int maxn = 2e5 + 10;
// n：串长。
// m：字符集大小。
// s[0..n − 1] ：字符串。
// sa[1..n] ：字典序第 i 小的是哪个后缀。
// rank[0..n − 1] ：后缀 i 的排名。
// height[i] ：lcp(sa[i], sa[i − 1])，最长公共前缀。
int rk[maxn], sa[maxn], height[maxn], tmp[maxn], cnt[maxn];
char s[maxn];
void suffixarray(int &n, int m)
{
    int i, j, k;
    n++;
    for (i = 0; i < n * 2 + 5; i++)
        rk[i] = sa[i] = height[i] = tmp[i] = 0;
    for (i = 0; i < m; i++)
        cnt[i] = 0;
    for (i = 0; i < n; i++)
        cnt[rk[i] = s[i]]++;
    for (i = 1; i < m; i++)
        cnt[i] += cnt[i - 1];
    for (i = 0; i < n; i++)
        sa[--cnt[rk[i]]] = i;
    for (k = 1; k <= n; k <<= 1)
    {
        for (i = 0; i < n; i++)
        {
            j = sa[i] - k;
            if (j < 0)
                j += n;
            tmp[cnt[rk[j]]++] = j;
        }
        sa[tmp[cnt[0] = 0]] = j = 0;
        for (i = 1; i < n; i++)
        {
            if (rk[tmp[i]] != rk[tmp[i - 1]] || rk[tmp[i] + k] != rk[tmp[i - 1] + k])
                cnt[++j] = i;
            sa[tmp[i]] = j;
        }
        memcpy(rk, sa, n * sizeof(int));
        memcpy(sa, tmp, n * sizeof(int));
        if (j >= n - 1)
            break;
    }
    for (j = rk[height[i = k = 0] = 0]; i < n - 1; i++, k++)
        while (~k && s[i] != s[sa[j - 1] + k])
            height[j] = k--, j = rk[sa[j] + 1];
}

字典树

struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }
  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};

AC自动机

#include <bits/stdc++.h>
using namespace std;
const int N = 156, L = 1e6 + 6;
namespace AC
{
    const int SZ = N * 80;
    int tot, tr[SZ][26];
    int fail[SZ], idx[SZ], val[SZ];
    int cnt[N]; // 记录第 i 个字符串的出现次数
    void init()
    {
        memset(fail, 0, sizeof(fail));
        memset(tr, 0, sizeof(tr));
        memset(val, 0, sizeof(val));
        memset(cnt, 0, sizeof(cnt));
        memset(idx, 0, sizeof(idx));
        tot = 0;
    }
    void insert(char *s, int id)
    { // id 表示原始字符串的编号
        int u = 0;
        for (int i = 1; s[i]; i++)
        {
            if (!tr[u][s[i] - 'a'])
                tr[u][s[i] - 'a'] = ++tot;
            u = tr[u][s[i] - 'a']; // 转移
        }
        idx[u] = id; // 以 u 为结尾的字符串编号为 idx[u]
    }
    queue<int> q;
    void build()
    {
        for (int i = 0; i < 26; i++)
            if (tr[0][i])
                q.push(tr[0][i]);
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < 26; i++)
            {
                if (tr[u][i])
                {
                    fail[tr[u][i]] =
                        tr[fail[u]][i]; // fail数组：同一字符可以匹配的其他位置
                    q.push(tr[u][i]);
                }
                else
                    tr[u][i] = tr[fail[u]][i];
            }
        }
    }
    int query(char *t)
    { // 返回最大的出现次数
        int u = 0, res = 0;
        for (int i = 1; t[i]; i++)
        {
            u = tr[u][t[i] - 'a'];
            for (int j = u; j; j = fail[j])
                val[j]++;
        }
        for (int i = 0; i <= tot; i++)
            if (idx[i])
                res = max(res, val[i]), cnt[idx[i]] = val[i];
        return res;
    }
} // namespace AC
int n;
char s[N][100], t[L];
int main()
{
    while (~scanf("%d", &n))
    {
        if (n == 0)
            break;
        AC::init(); // 数组清零
        for (int i = 1; i <= n; i++)
            scanf("%s", s[i] + 1), AC::insert(s[i], i); // 需要记录该字符串的序号
        AC::build();
        scanf("%s", t + 1);
        int x = AC::query(t);
        printf("%d\n", x);
        for (int i = 1; i <= n; i++)
            if (AC::cnt[i] == x)
                printf("%s\n", s[i] + 1);
    }
    return 0;
}

数据结构

线段树

struct Seg {
    int t[maxn << 2], tag[maxn << 2];
    void up(int id) {
        t[id] = t[id << 1]+t[id << 1 | 1];
    }
    void build(int id, int l, int r) {
        t[id] = 0;
        tag[id] = 0;
        if (l == r) return;
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
    void down(int id) {
        if (!tag[id]) return;
        tag[id << 1 | 1] += tag[id];
        tag[id << 1] += tag[id];
        t[id << 1] += tag[id];
        t[id << 1 | 1] += tag[id];
        tag[id] = 0;
    }
    void modify(int id, int l, int r, int ql, int qr, int v) {
        if (l >= ql && r <= qr) {
            tag[id] += v;
            t[id] += v;
            return;
        }
        down(id);
        int mid = l + r >> 1;
        if (ql <= mid) modify(id << 1, l, mid, ql, qr, v);
        if (qr > mid) modify(id << 1 | 1, mid + 1, r, ql, qr, v);
        up(id);
    }
    int query(int id, int l, int r) {
        if (t[id]) return -1;
        if (l == r) return l;
        down(id);
        int mid = l + r >> 1;
        if (!t[id << 1]) return query(id << 1, l, mid);
        else return query(id << 1 | 1, mid + 1, r);
    }
//  int find(int id, int l, int r, int p) {
//     
//  }
}seg;

typedef long long ll;
const int maxn = 3e5 + 10;
int a[maxn];
struct Tree
{
    int l, r;
    ll sum;
};
struct Seg
{
    Tree t[maxn << 2];
    inline void up(int id) { t[id].sum = t[id << 1].sum + t[id << 1 | 1].sum; }
    void build(int id, int l, int r)
    {
        t[id].l = l;
        t[id].r = r;
        if (l == r)
        {
            t[id].sum = a[l];
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        up(id);
    }
    void update(int id, int ql, int qr, int v)
    {
        if (t[id].l == t[id].r)
        {
            t[id].sum += v;
            return;
        }
        int mid = t[id].l + t[id].r >> 1;
        if (ql <= mid)
            update(id << 1, ql, qr, v);
        if (qr > mid)
            update(id << 1 | 1, ql, qr, v);
        up(id);
    }
    ll query(int id, int l, int r)
    {
        if (l <= t[id].l && t[id].r <= r)
            return t[id].sum;
        int mid = (t[id].l + t[id].r) >> 1;
        if (l > mid)
            return query(id << 1 | 1, l, r);
        else if (r <= mid)
            return query(id << 1, l, r);
        else
            return query(id << 1, l, r) + query(id << 1 | 1, l, r);
    }
} seg;

区间合并

typedef long long ll;
const int maxn = 2e5 + 10;
int a[maxn];
struct Tree
{
    int l, r;
    int lenl, lenr;
    ll sum;
    int sz;
};
struct Seg
{
    Tree t[maxn << 2];
    void up(int id)
    {
        t[id] = merge(t[id << 1], t[id << 1 | 1]);
    }
    Tree merge(Tree x, Tree y)
    {
        Tree tmp;
        tmp.sz = x.sz + y.sz;
        tmp.l = x.l;
        tmp.r = y.r;
        tmp.sum = x.sum + y.sum + (a[x.r] <= a[y.l] ? (ll)x.lenr * y.lenl : 0);
        tmp.lenl = x.lenl + (x.lenl == x.sz && a[x.r] <= a[y.l] ? y.lenl : 0);
        tmp.lenr = y.lenr + (y.lenr == y.sz && a[x.r] <= a[y.l] ? x.lenr : 0);
        return tmp;
    }
    void build(int id, int l, int r)
    {
        t[id].l = l;
        t[id].r = r;
        if (l == r)
        {
            t[id].lenl = t[id].lenr = 1;
            t[id].sum = 1;
            t[id].sz = 1;
            return;
        }
        int mid = l + r >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
        up(id);
    }
    void update(int id, int l, int r)
    {
        if (t[id].l == t[id].r)
            return;
        int mid = (t[id].l + t[id].r) >> 1;
        if (l <= mid)
            update(id << 1, l, r);
        else
            update(id << 1 | 1, l, r);
        up(id);
    }
    Tree query(int id, int l, int r)
    {
        if (l <= t[id].l && t[id].r <= r)
            return t[id];
        int mid = (t[id].l + t[id].r) >> 1;
        if (l > mid)
            return query(id << 1 | 1, l, r);
        else if (r <= mid)
            return query(id << 1, l, r);
        else
            return merge(query(id << 1, l, r), query(id << 1 | 1, l, r));
    }
} seg;

珂朵莉树

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using ll = long long;
#define all(x) std::begin(x), std::end(x)
inline ll mul(ll a, ll b, ll p)
{
    return static_cast<__int128_t>(a) * b % p;
}
inline ll power(ll a, ll i, ll p)
{
    ll res = 1;
    while (i)
    {
        if (i & 1)
            res = mul(res, a, p);
        a = mul(a, a, p);
        i >>= 1;
    }
    return res;
}
class ODT
{
private:
    struct Node
    {
        int l, r;
        mutable ll val;
        Node(int l = 0, int r = 0, ll val = 0) : l(l), r(r), val(val) {}
        bool operator<(const Node &a) const
        {
            return l < a.l;
        }
    };
    set<Node> odt;

public:
    void insert(int l, int r, ll val)
    {
        odt.insert(Node(l, r, val));
    }
    auto split(int pos)
    {
        auto it = odt.lower_bound(Node(pos));
        if (it != odt.end() && it->l == pos)
            return it;
        --it;
        int l = it->l, r = it->r;
        ll val = it->val;
        odt.erase(it);
        odt.insert(Node(l, pos - 1, val));
        return odt.insert(Node(pos, r, val)).first;
    }
    void assign(int l, int r, ll val)
    {
        auto end = split(r + 1), begin = split(l);
        odt.erase(begin, end);
        odt.insert(Node(l, r, val));
    }
    void work(int l, int r, ...)
    {
        auto itr = split(r + 1), itl = split(l);
        for (; itl != itr; ++itl)
        {
            // work
        }
    }
    void add(int l, int r, ll k)
    { // 暴力拿出区间求和
        auto itr = split(r + 1), itl = split(l);
        for (; itl != itr; ++itl)
        {
            itl->val += k;
        }
    }
    ll rank(int l, int r, int kth)
    { // 暴力排序，一个一个数
        vector<pair<ll, int>> v;
        auto itr = split(r + 1), itl = split(l);
        for (; itl != itr; ++itl)
        {
            v.push_back({itl->val, itl->r - itl->l + 1});
        }
        sort(all(v), [](const pair<ll, int> &a, const pair<ll, int> &b)
             { return a.first != b.first ? a.first < b.first : a.second < b.second; });
        for (const auto &[val, cnt] : v)
        {
            kth -= cnt;
            if (kth <= 0)
            {
                return val;
            }
        }
        return -1;
    }

    ll sum(int l, int r, ll k, ll p)
    { // 暴力拿出区间，一个一个计算
        ll res = 0;
        auto itr = split(r + 1), itl = split(l);
        for (; itl != itr; ++itl)
        {
            res = (res + mul(power(itl->val, k, p), itl->r - itl->l + 1, p)) % p;
        }
        return res;
    }
};
ODT odt;

主席树

// 洛谷P3834
#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int maxn = 2e5 + 10;
int rt[maxn], tot = 0;
int a[maxn], b[maxn];
unordered_map<int, int> mp;
struct Tree
{
    int lson, rson;
    int sum;
};
struct Seg
{
    Tree t[maxn * 40];
    void up(int id)
    {
        t[id].sum = t[t[id].lson].sum + t[t[id].rson].sum;
    }
    void build(int &id, int l, int r)
    {
        if (!id)
            id = ++tot;
        if (l == r)
            return;
        int mid = l + r >> 1;
        build(t[id].lson, l, mid);
        build(t[id].rson, mid + 1, r);
    }
    void update(int pre, int &id, int pos, int l, int r)
    {
        if (!id)
            id = ++tot;
        if (l == r)
        {
            t[id].sum = t[pre].sum + 1;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
        {
            t[id].rson = t[pre].rson;
            update(t[pre].lson, t[id].lson, pos, l, mid);
        }
        else
        {
            t[id].lson = t[pre].lson;
            update(t[pre].rson, t[id].rson, pos, mid + 1, r);
        }
        up(id);
    }
    int query(int pre, int id, int k, int l, int r)
    {
        if (l == r)
            return l;
        int tmp_sum = t[t[id].lson].sum - t[t[pre].lson].sum;
        int mid = l + r >> 1;
        if (k <= tmp_sum)
            return query(t[pre].lson, t[id].lson, k, l, mid);
        else
            return query(t[pre].rson, t[id].rson, k - tmp_sum, mid + 1, r);
    }
} seg;
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int num = unique(b + 1, b + 1 + n) - (b + 1);
    seg.build(rt[0], 1, num);
    for (int i = 1; i <= num; i++)
        mp[b[i]] = i;
    for (int i = 1; i <= n; i++)
        seg.update(rt[i - 1], rt[i], mp[a[i]], 1, num);
    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        cout << b[seg.query(rt[l - 1], rt[r], k, 1, num)] << "\n";
    }
}
signed main()
{
    FAST;
    int t = 1;
    while (t--)
        solve();
}

// codeforces 961E
#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define int long long
const int maxn = 2e5 + 10;
int a[maxn], b[maxn];
unordered_map<int, int> mp;
int rt[maxn], tot = 0;
struct Tree
{
    int lson, rson;
    int sum;
};
struct Seg
{
    Tree t[maxn << 5];
    void up(int id)
    {
        t[id].sum = t[t[id].lson].sum + t[t[id].rson].sum;
    }
    void build(int &id, int l, int r)
    {
        if (!id)
            id = ++tot;
        if (l == r)
        {
            t[id].sum = 0;
            return;
        }
        int mid = l + r >> 1;
        build(t[id].lson, l, mid);
        build(t[id].rson, mid + 1, r);
    }
    void update(int pre, int &id, int pos, int l, int r)
    {
        if (!id)
            id = ++tot;
        if (l == r)
        {
            t[id].sum = t[pre].sum + 1;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
        {
            t[id].rson = t[pre].rson;
            update(t[pre].lson, t[id].lson, pos, l, mid);
        }
        else
        {
            t[id].lson = t[pre].lson;
            update(t[pre].rson, t[id].rson, pos, mid + 1, r);
        }
        up(id);
    }
    int query(int pre, int id, int l, int r, int L, int R)
    {
        if (L <= l && r <= R)
            return t[id].sum - t[pre].sum;
        int mid = l + r >> 1;
        if (R <= mid)
            return query(t[pre].lson, t[id].lson, l, mid, L, R);
        else if (L > mid)
            return query(t[pre].rson, t[id].rson, mid + 1, r, L, R);
        else
            return query(t[pre].lson, t[id].lson, l, mid, L, R) + query(t[pre].rson, t[id].rson, mid + 1, r, L, R);
    }
} seg;
void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], b[i] = a[i];
    sort(b + 1, b + 1 + n);
    int num = unique(b + 1, b + 1 + n) - (b + 1);
    seg.build(rt[n + 1], 1, num);
    for (int i = 1; i <= num; i++)
        mp[b[i]] = i;
    for (int i = n; i >= 1; i--)
        seg.update(rt[i + 1], rt[i], mp[a[i]], 1, num);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] > i)
        {
            int l = lower_bound(b + 1, b + 1 + num, i) - b;
            ans += seg.query(rt[min(n + 1, a[i] + 1)], rt[i + 1], 1, num, l, num);
        }
    }
    cout << ans << "\n";
}
signed main()
{
    FAST;
    int t = 1;
    while (t--)
        solve();
}

可持久化并查集

// 洛谷P3402
#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int maxn = 2e5 + 10;
int tot, rt[maxn * 40];
int n;
struct TreeNode
{
    int fa, dep;
    int lson, rson;
};
struct Seg
{
    TreeNode t[maxn * 40];
    void build(int &id, int l, int r)
    {
        if (!id)
            id = ++tot;
        if (l == r)
        {
            t[id].fa = l;
            return;
        }
        int mid = l + r >> 1;
        build(t[id].lson, l, mid);
        build(t[id].rson, mid + 1, r);
    }
    void change(int pre, int &id, int l, int r, int pos, int v)
    {
        id = ++tot;
        if (l == r)
        {
            t[id].fa = v, t[id].dep = t[pre].dep;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
        {
            t[id].rson = t[pre].rson;
            change(t[pre].lson, t[id].lson, l, mid, pos, v);
        }
        else
        {
            t[id].lson = t[pre].lson;
            change(t[pre].rson, t[id].rson, mid + 1, r, pos, v);
        }
    }
    void update(int id, int l, int r, int pos)
    {
        if (l == r)
        {
            t[id].dep++;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid)
            update(t[id].lson, l, mid, pos);
        else
            update(t[id].rson, mid + 1, r, pos);
    }
    int query(int id, int l, int r, int pos)
    {
        if (l == r)
            return id;
        int mid = l + r >> 1;
        if (pos <= mid)
            return query(t[id].lson, l, mid, pos);
        else
            return query(t[id].rson, mid + 1, r, pos);
    }
    int find(int now, int x)
    {
        int node = query(rt[now], 1, n, x);
        return t[node].fa == x ? node : find(now, t[node].fa);
    }
    void merge(int now, int x, int y)
    {
        int nodex = find(now, x), nodey = find(now, y);
        if (t[nodex].fa == t[nodey].fa)
            return;
        if (t[nodex].dep > t[nodey].dep)
            swap(nodex, nodey);
        change(rt[now - 1], rt[now], 1, n, t[nodex].fa, t[nodey].fa);
        if (t[nodex].dep == t[nodey].dep)
            update(rt[now], 1, n, t[nodey].fa);
    }
} seg;

void solve()
{
    int m;
    cin >> n >> m;
    seg.build(rt[0], 1, n);
    for (int i = 1; i <= m; i++)
    {
        int op, x, y;
        cin >> op;
        rt[i] = rt[i - 1];
        if (op == 1)
        {
            cin >> x >> y;
            seg.merge(i, x, y);
        }
        else if (op == 2)
        {
            cin >> x;
            rt[i] = rt[x];
        }
        else
        {
            cin >> x >> y;
            cout << (seg.find(i, x) == seg.find(i, y) ? 1 : 0) << "\n";
        }
    }
}
signed main()
{
    FAST;
    int t = 1;
    while (t--)
        solve();
}

LCA

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int n, m, s;
struct lca
{
    int cnt, head[maxn];
    struct edge
    {
        int to, next;
    } e[maxn << 1];
    void add(int u, int v)
    {
        e[++cnt] = {v, head[u]};
        head[u] = cnt;
        e[++cnt] = {u, head[v]};
        head[v] = cnt;
    }

    int dep[maxn];
    int lg[maxn];
    int fa[maxn][22];

    void init()
    {
        for (int i = 1; i <= maxn; ++i)
        {
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
            //		cout << i << " -> " << lg[i] << endl;
        }
    }

    void dfs(int now, int pre)
    {
        fa[now][0] = pre;
        dep[now] = dep[pre] + 1;
        for (int i = 1; i <= lg[dep[now]]; ++i)
            fa[now][i] = fa[fa[now][i - 1]][i - 1];
        for (int i = head[now]; i; i = e[i].next)
            if (e[i].to != pre)
                dfs(e[i].to, now);
    }

    int LCA(int x, int y)
    {
        if (dep[x] < dep[y])
            swap(x, y);
        while (dep[x] > dep[y])
            x = fa[x][lg[dep[x] - dep[y]] - 1];
        if (x == y)
            return x;
        for (int k = lg[dep[x]] - 1; k >= 0; --k)
            if (fa[x][k] != fa[y][k])
                x = fa[x][k], y = fa[y][k];
        return fa[x][0];
    }

} lca;
int main () {
	scanf("%d%d%d", &n, &m, &s);
	for (int i = 1; i < n; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		lca.add(x, y);
	}
	lca.init();
	lca.dfs(s, 0);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", lca.LCA(x, y));
	}
	return 0;
}

扫描线

#include <algorithm>
#include <cstdio>
#include <cstring>
#define maxn 300
using namespace std;

int lazy[maxn << 3];  // 标记了这条线段出现的次数
double s[maxn << 3];

struct node1 {
  double l, r;
  double sum;
} cl[maxn << 3];  // 线段树

struct node2 {
  double x, y1, y2;
  int flag;
} p[maxn << 3];  // 坐标

// 定义sort比较
bool cmp(node2 a, node2 b) { return a.x < b.x; }

// 上传
void pushup(int rt) {
  if (lazy[rt] > 0)
    cl[rt].sum = cl[rt].r - cl[rt].l;
  else
    cl[rt].sum = cl[rt * 2].sum + cl[rt * 2 + 1].sum;
}

// 建树
void build(int rt, int l, int r) {
  if (r - l > 1) {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    build(rt * 2, l, (l + r) / 2);
    build(rt * 2 + 1, (l + r) / 2, r);
    pushup(rt);
  } else {
    cl[rt].l = s[l];
    cl[rt].r = s[r];
    cl[rt].sum = 0;
  }
  return;
}

// 更新
void update(int rt, double y1, double y2, int flag) {
  if (cl[rt].l == y1 && cl[rt].r == y2) {
    lazy[rt] += flag;
    pushup(rt);
    return;
  } else {
    if (cl[rt * 2].r > y1) update(rt * 2, y1, min(cl[rt * 2].r, y2), flag);
    if (cl[rt * 2 + 1].l < y2)
      update(rt * 2 + 1, max(cl[rt * 2 + 1].l, y1), y2, flag);
    pushup(rt);
  }
}

int main() {
  int temp = 1, n;
  double x1, y1, x2, y2, ans;
  while (scanf("%d", &n) && n) {
    ans = 0;
    for (int i = 0; i < n; i++) {
      scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
      p[i].x = x1;
      p[i].y1 = y1;
      p[i].y2 = y2;
      p[i].flag = 1;
      p[i + n].x = x2;
      p[i + n].y1 = y1;
      p[i + n].y2 = y2;
      p[i + n].flag = -1;
      s[i + 1] = y1;
      s[i + n + 1] = y2;
    }
    sort(s + 1, s + (2 * n + 1));  // 离散化
    sort(p, p + 2 * n, cmp);  // 把矩形的边的横坐标从小到大排序
    build(1, 1, 2 * n);       // 建树
    memset(lazy, 0, sizeof(lazy));
    update(1, p[0].y1, p[0].y2, p[0].flag);
    for (int i = 1; i < 2 * n; i++) {
      ans += (p[i].x - p[i - 1].x) * cl[1].sum;
      update(1, p[i].y1, p[i].y2, p[i].flag);
    }
    printf("Test case #%d\nTotal explored area: %.2lf\n\n", temp++, ans);
  }
  return 0;
}

莫队

基础莫队

题意是寻找0~i，j~n中不同的数有多少个。
创建一个a[i]=a[i+n];的数组
理解为j~i+n中查询
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m,x,y,block;
int a[N*2],cnt[N*2],ans[N*2];
struct node{
    int i;
    int l;
    int r;
} q[N*2];

void add(int x,int &res){
    if(cnt[x]==0)
        res++;
    cnt[x]++;
}

void del(int x,int &res){
    cnt[x]--;
    if(cnt[x]==0)
        res--;
}

bool cmp(node l,node r){
    return l.l/block == r.l/block ? l.r < r.r : l.l/block < r.l/block;
}

int main(){
    while(~scanf("%d %d",&n,&m)){
        memset(cnt, 0, sizeof cnt);
        for (int i = 1; i <= n;i++){
            scanf("%d", &a[i]);
            a[i + n] = a[i];
        }
        for (int i = 1; i <= m;i++){
            scanf("%d %d", &x, &y);
            q[i] = {i,y,x+n};
        }
        block = sqrt((double)n * n / m);
        sort(q + 1, q + 1 + m, cmp);
        for (int k = 1, i = 0, j = 0, res = 0; k <= m;k++){
            int id = q[k].i;
            int l = q[k].l;
            int r = q[k].r;
            while(i<r)
                add(a[++i], res);
            while(i>r)
                del(a[i--], res);
            while(j<l)
                del(a[j++], res);
            while(j>l)
                add(a[--j], res);
            ans[id] = res;
        }
        for (int i = 1; i <= m;i++){
            printf("%d\n", ans[i]);
        }
    }
}

带修莫队

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int M = 1e6 + 10;

int n, m, block, csum = 0, tsum = 0;//csum表示查询次数，tsum表示有几个时间点
struct change
{
    int x, old, now;
} chan[N];
struct node
{
    int l;
    int r;
    int tim;
    int id;
} q[N];
int a[N], qk[N], cnt[M], ans[N];

bool cmp(node x, node y)
{
    return qk[x.l] == qk[y.l] ? (qk[x.r] == qk[y.r] ? x.tim < y.tim : x.r < y.r) : x.l < y.l;//先比较左区间，再比较右区间，再比较时间;
}

void add(int x, int &res)
{
    if (cnt[x] == 0)
        res++;
    cnt[x]++;
}

void del(int x, int &res)
{
    cnt[x]--;
    if (cnt[x] == 0)
        res--;
}

signed main()
{
    scanf("%d %d", &n, &m);
    block = pow(n, 2.0 / 3); //分块
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        qk[i] = (i - 1) / block + 1; //初始化分块区间，快速求得每个点属于哪块
    }
    for (int i = 1; i <= m; i++)
    {
        char s;
        int x, y;
        getchar();
        scanf("%c", &s);
        scanf("%d %d", &x, &y);
        if (s == 'R')
        {                       //修改操作
            chan[++tsum].x = x; //tsum记录第几次修改，x记录哪个点被修改，old记录原来颜色，now记录新颜色
            chan[tsum].old = a[x];
            chan[tsum].now = y;
            a[x] = y; //修改颜色
        }
        else
        {
            q[++csum].l = x;    //l记录区间左值
            q[csum].r = y;      //r记录区间右值
            q[csum].tim = tsum; //tim记录时间戳
            q[csum].id = csum;  //ID记录第几次询问
        }
    }
    sort(q + 1, q + 1 + csum, cmp);
    int r = 0, l = 1, tim = tsum;
    int res = 0;
    for (int i = 1; i <= csum; i++)
    {
        //处理时间轴
        while (q[i].tim > tim)
        {
            tim++;
            int x = chan[tim].x;
            if (l <= x && x <= r)
            {
                del(a[x], res);
                add(chan[tim].now, res);
            }
            a[x] = chan[tim].now;
        }
        while (q[i].tim < tim)
        {
            int x = chan[tim].x;
            if (l <= x && x <= r)
            {
                del(a[x], res);
                add(chan[tim].old, res);
            }
            a[x] = chan[tim].old;
            tim--;
        }
        //先处理x轴
        while (r < q[i].r)
            add(a[++r], res);
        while (r > q[i].r)
            del(a[r--], res);
        while (l < q[i].l)
            del(a[l++], res);
        while (l > q[i].l)
            add(a[--l], res);
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= csum; i++)
    {
        printf("%d\n", ans[i]);
    }
}

二分图染色板子

#pragma   warning(disable:4996)
#include  <bits/stdc++.h>
//#define   int long long
#define   fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
typedef	long long ll;
using namespace std;
const double PI = acos(-1);
const int N = 1e5 + 10;
const int mod =1e9+7;
int t;
int col[N];
int fa[N];
vector<int>ve[N];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool bit(int s) {
    for (int i = 0; i <ve[s].size(); i++) {
        int y = ve[s][i];
        if (col[s] == col[y]) {
            return false;
        }
        if (!col[y]) {
            col[y] = 3 - col[s];
            if (!bit(y)) {
                return false;
            }
        }
    }
    return true;
}
signed main() {
    fast;
    cin >> t;
    int ca = 1;
    while (t--) {
        int n, m, s;
        cin >> n >> m >> s;
        for (int i = 0; i < n; i++) {
            ve[i].clear();
            fa[i] = i;
            col[i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            ve[x].push_back(y);
            ve[y].push_back(x);
            int X = find(x);
            int Y = find(y);
            if (X != Y) {
                fa[X] = Y;
            }
        }
        int judge =find(0);
        bool flag = true;
        for (int i = 0; i < n; i++) {
            if (find(i) != judge) {
                flag = false;
            }
        }
        if (!flag) {
            printf("Case %d: NO\n", ca++);
            continue;
        }
        col[s] = 1;
        if(bit(s))
            printf("Case %d: NO\n", ca++);
        else {
            printf("Case %d: YES\n", ca++);
        }
    }
}

#pragma   warning(disable:4996)
#include  <bits/stdc++.h>
//#define   int long long
#define   fast ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
typedef	long long ll;
using namespace std;
const double PI = acos(-1);
const int N = 5e5 + 10;
const int mod = 1e9 + 7;
int t;
int col[N];
int fa[N];
struct node{
    int to;
    int next;
}e[N];
int tot;
int head[N];
void add(int u, int v) {
    e[tot].to = v;
    e[tot].next = head[u];
    head[u] = tot++;
    e[tot].to = u;
    e[tot].next = head[v];
    head[v] = tot++;
}
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
bool bit(int u) {
    for (int i = head[u]; i; i=e[i].next) {
        int v = e[i].to;
        if (col[u] == col[v]) {
            return false;
        }
        if (!col[v]) {
            col[v] = 3 - col[u];
            if (!bit(v)) {
                return false;
            }
        }
    }
    return true;
}
signed main() {
    fast;
    cin >> t;
    int ca = 1;
    while (t--) {
        int n, m, s;
        tot = 1;
        cin >> n >> m >> s;
        memset(e, 0, sizeof e);
        memset(head, 0, sizeof head);
        for (int i = 0; i < n; i++) {
            fa[i] = i;
            col[i] = 0;
        }
        for (int i = 1; i <= m; i++) {
            int x, y;
            cin >> x >> y;
            add(x, y);
            int X = find(x);
            int Y = find(y);
            if (X != Y) {
                fa[X] = Y;
            }
        }
        int judge = find(0);
        bool flag = true;
        for (int i = 0; i < n; i++) {
            if (find(i) != judge) {
                flag = false;
            }
        }
        if (!flag) {
            printf("Case %d: NO\n", ca++);
            continue;
        }
        col[s] = 1;
        if (bit(s))
            printf("Case %d: NO\n", ca++);
        else {
            printf("Case %d: YES\n", ca++);
        }
    }
}

匈牙利算法板子

#pragma warning(disable:4996)
//#include <bits/stdc++.h>
#include<queue>
#include<map>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
//#define int long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
const int inf = 0x3f3f3f;
const int N = 5e4 + 100;
const double eps = 1e-8;
const double pi = acos(-1.0);
typedef long long ll;
using namespace std;
int t;
struct node {
	int to;
	int next;
}e[N];
int head[305], tot, mat[305], n, m, p, k, v;
bool vis[305];
void add(int u, int v) {
	e[tot].to = v;
	e[tot].next = head[u];
	head[u] = tot++;
}
bool find(int u) {
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (!vis[v]) {
			vis[v] = 1;
			if (!mat[v] || find(mat[v])) {
				mat[v] = u;
				return true;
			}
		}
	}
	return false;
}
signed main() {
	scanf("%d",&t);
	while (t--) {
		tot = 1;
		bool flag = true;
		memset(head, 0, sizeof head);
		memset(mat, 0, sizeof mat);
		scanf("%d %d", &p, &n);
		for (int u = 1; u <= p; u++) {
			scanf("%d",&k);
			if (k == 0) {
				flag = false;
			}
			for (int i = 1; i <= k; i++) {
				scanf("%d",&v);
				add(u, v);
			}
		}
		int ans = 0;
		if (!flag) {
			printf("NO\n");
			continue;
		}
		for (int i = 1; i <= p; i++) {
			memset(vis, 0, sizeof vis);
			if (find(i))ans++;
		}
		if (ans == p)printf("YES\n");
		else printf("NO\n");
	}
}

km算法n^3

int nx, ny;//两边的点数
ll g[N][N];//二分图描述
ll linker[N], lx[N], ly[N];//y 中各点匹配状态，x,y 中的点标号
ll slack[N];
bool visx[N], visy[N];
int pre[N];
void bfs(int k) {
    int x, y = 0, yy = 0;
    ll delta;
    memset(pre, 0, sizeof pre);
    for (int i = 1;i <= ny;i++)slack[i] = 1e13;
    linker[y] = (ll)k;
    while (1) {
        x = linker[y];delta = 1e13;visy[y] = true;
        for (int i = 1;i <= ny;i++) {
            if (!visy[i]) {
                if (slack[i] > lx[x] + ly[i] - g[x][i]) {
                    slack[i] = lx[x] + ly[i] - g[x][i];
                    pre[i] = y;
                }
                if (slack[i] < delta)delta = slack[i], yy = i;
            }
        }
        for (int i = 0;i <= ny;i++) {
            if (visy[i]) {
                lx[linker[i]] -= delta;
                ly[i] += delta;
            }
            else slack[i] -= delta;
        }
        y = yy;
        if (linker[y] == -1)break;
    }
    while (y) {
        linker[y] = linker[pre[y]];
        y = pre[y];
    }
}
ll KM() {
    memset(linker, -1, sizeof linker);
    memset(lx, 0, sizeof lx);
    memset(ly, 0, sizeof ly);
    for (int i = 1;i <= ny;i++) {
        memset(visy, false, sizeof visy);
        bfs(i);
    }
    ll res = 0;
    for (int i = 1;i <= ny;i++)
        if (linker[i] != -1)
            res += g[linker[i]][i];
    return res;
 
}

网络流

最小费用最大流

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
//算最大费用权值改为负即可
struct Dinic
{
    struct Edge
    {
        int v, rev, cap, cos;
    };
    vector<Edge> G[maxn];
    int dis[maxn], cur[maxn], vis[maxn], n, sp, tp;
    // nn为总点数
    void init(int nn)
    {
        n = nn;
        for (int i = 0; i <= n; ++i)
            G[i].clear();
    }
    void addedge(int u, int v, int cap, int cos)
    {

        G[u].push_back(Edge{v, (int)G[v].size(), cap, cos});
        G[v].push_back(Edge{u, (int)G[u].size() - 1, 0, -cos});
    }
    int bfs()
    {
        queue<int> q;
        for (int i = 0; i <= n; ++i)
            dis[i] = inf, vis[i] = 0;
        dis[sp] = 0, q.push(sp), vis[sp] = 1;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            vis[u] = 0;
            for (auto &e : G[u])
            {
                if (e.cap && dis[e.v] > dis[u] + e.cos)
                {

                    dis[e.v] = dis[u] + e.cos;
                    if (!vis[e.v])
                        q.push(e.v), vis[e.v] = 1;
                }
            }
        }
        return dis[tp] != inf;
    }
    int dfs(int u, int flow)
    {
        if (u == tp || !flow)
            return flow;
        int ret = 0, tmp;
        vis[u] = 1;
        for (int &i = cur[u]; i < G[u].size(); ++i)
        {
            auto &e = G[u][i];
            if (!vis[e.v] && dis[e.v] == dis[u] + e.cos && (tmp = dfs(e.v, min(e.cap, flow - ret))))
            {

                ret += tmp, e.cap -= tmp, G[e.v][e.rev].cap += tmp;
                if (ret == flow)
                {
                    vis[u] = 0;
                    return ret;
                }
            }
        }
        if (!ret)
            vis[u] = 1;
        return ret;
    }
    /*
     * 直接调用获取最小费用和最大流
     * 输入: s-源点，t-汇点
     * 返回值: pair<int,int> 第一个是最小费用，第二个是最大流
     */
    pair<int, int> mincostmaxflow(int s, int t)
    {
        sp = s, tp = t;
        int mincost = 0, maxflow = 0;
        while (bfs())
        {

            for (int i = 0; i <= n; ++i)
                cur[i] = 0;
            int f = dfs(sp, inf);
            mincost += f * dis[tp];
            maxflow += f;
        }
        return make_pair(mincost, maxflow);
    }
} mcmf;
int a[maxn], b[maxn];
void solve()
{
    int n, m;
    scanf("%d%d", &n, &m);
    mcmf.init(n + m + 5);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    int s = 0, t = n + m + 1;
    for (int i = 1, u; i <= m; i++)
    {
        scanf("%d%d", &u, &b[i]);
        mcmf.addedge(s, i, 1, 0);
        mcmf.addedge(i, m + u, 1, 0);
        mcmf.addedge(i, m + b[i], 1, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        mcmf.addedge(m + i, t, a[i], 0);
        mcmf.addedge(m + i, t, inf, 1);
    }
    auto ans = mcmf.mincostmaxflow(s, t);
    printf("%d\n", ans.first);
    for (int i = 1; i <= m; i++)
    {
        for (auto it : mcmf.G[i])
        {
            int v = it.v;
            if (v > m + n)
                continue;
            if (v == m + b[i])
            {
                printf(it.cap ? "1" : "0");
                break;
            }
        }
    }
    printf("\n");
}
int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
        solve();
}

最大流

#include <algorithm>
#include <iostream>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
#define maxn 450
#define INF 0x3f3f3f3f
struct Edge
{
    int from, to, cap, flow;
    Edge(int u, int v, int c, int f) : from(u), to(v), cap(c), flow(f) {}
};
struct Dinic
{
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    int d[maxn], cur[maxn];
    bool vis[maxn];
    void init(int n)
    {
        for (int i = 0; i < n; i++)
            G[i].clear();
        edges.clear();
    }
    void AddEdge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool BFS()
    {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while (!Q.empty())
        {
            int x = Q.front();
            Q.pop();
            for (int i = 0; i < G[x].size(); i++)
            {
                Edge &e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow)
                {
                    vis[e.to] = 1;
                    d[e.to] = d[x] + 1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    int DFS(int x, int a)
    {
        if (x == t || a == 0)
            return a;
        int flow = 0, f;
        for (int &i = cur[x]; i < G[x].size(); i++)
        {
            Edge &e = edges[G[x][i]];
            if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0)
            {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0)
                    break;
            }
        }
        return flow;
    }
    int Maxflow(int s, int t)
    {
        this->s = s;
        this->t = t;
        int flow = 0;
        while (BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s, INF);
        }
        return flow;
    }
} a;

#include<algorithm>
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=505;      //最大结点总个数
const int maxm=1000005;      //最大边的总条数：注意要包括反向边个数，即总条数=正向边总条数*2
int s;               //源点
int t;               //汇点
int head[maxn];      //点u邻接表的第一条边
int cnt;             //边的数量，从0开始编号
struct edge
{
    int w;           //边的流量（残量）
    int to;          //该边通向的结点v
    int next;        //点u邻接表的下一条边
}e[maxm];
void addedge(int u,int v,int w)   //添加一条u->v，最大容量为w的边
{
    //建立正向边
    e[cnt].w=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
    //建立反向边
    e[cnt].w=0;        //有些图是需要建立双向边(例如求最小割时），则反向边的初始残量不为0
    e[cnt].to=u;
    e[cnt].next=head[v];
    head[v]=cnt;
    cnt++;
}
int dis[maxn];     //dis数组记录层次
bool bfs()         //利用BFS建立分成图，从而可以多次DFS增广
{
    memset(dis,-1,sizeof(dis));     //初始化dis数组
    queue<int> q;
    q.push(s);
    dis[s]=0;      //源点层次为0
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].w>0&&dis[v]==-1)     //可达&&未分层
            {
                dis[v]=dis[u]+1;         //分层
                if(v==t)                 //若到达汇点，则分层结束，返回true
                    return true;
                q.push(v);
            }
        }
    }
    return false;  //运行到此处，说明汇点已不可达，返回false
}
int cur[maxn];     //弧优化：cur数组用于记录上一次DFS增广时u已经增广到第几条边，从而优化时间
int dfs(int u,int flow)       //flow代表流入u点的最大流量
{
    if(u==t)
        return flow;          //到达汇点，直接返回flow
    for(int &i=cur[u];i!=-1;i=e[i].next)
    {                         //注意i前面用&引用，这样就可以直接改变cur[u]
        int v=e[i].to;
        if(dis[v]==dis[u]+1&&e[i].w>0)   //v为u的下一层&&可达
        {
            int k=dfs(v,min(flow,e[i].w));
            if(k>0)
            {
                e[i].w-=k;         //正向边-=k
                e[i^1].w+=k;       //反向边+=k
                return k;
            }
        }
    }
    return 0;       //无法继续增广，返回0
}
int dinic()
{
    int ans=0;      //记录总流量
    while(bfs())    //分层
    {
        for(int i=0;i<maxn;i++)    //初始化cur数组，即将head数组赋给cur数组
             cur[i]=head[i];
        while(int k=dfs(s,INF))    //增广
            ans+=k;
    }
    return ans;
}
void init()
{
   memset(head,-1,sizeof(head));
   cnt=0;
}

inline void addl(int u,int v,int w)
{
    edge[cnt].e=v;
    edge[cnt].v=w;
    edge[cnt].nxt=head[u];
    head[u]=cnt++;
}
void datasetting()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();x=read();
    int a,b,c;
    for(int i=0;i<m;i++)
    {
        a=read();b=read();c=read();
        addl(a,b,c);addl(b,a,0);
    }
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        int r=q.front();q.pop();
        for(int i=head[r];i!=-1;i=edge[i].nxt)
        {
            int j=edge[i].e;
            if(dis[j]==-1&&edge[i].v)
            {
                dis[j]=dis[r]+1;
                q.push(j);
            }
        }
    }
    return dis[n]!=-1;//若不可以到终点（起点）就返回false 
}
int dfs(int u,int flo)//dfs就是求节点u在残量为flo时的最大增量 
{
    if(u==n)return flo;
    int detla=flo;
    for(int i=cur[u];i!=-1;i=edge[i].nxt)
    {
        cur[u]=edge[i].nxt;
        int v=edge[i].e;
        if(dis[v]==(dis[u]+1)&&(edge[i].v)>0)
        {
            int d=dfs(v,min(detla,edge[i].v));
            edge[i].v-=d;edge[i ^ 1].v+=d;
            detla-=d;
            if(detla==0)break;
        }
    }
    return flo-detla;//返回这个点已经被允许流过的流量
}
int dini()
{
    int ans=0;
    while(bfs())
    {
        for(int i=1;i<=n;i++)cur[i]=head[i];
        ans+=dfs(1,INF);
    }
    return ans;
}

数学

数论分块

快速计算形如\sum_{1=1}^nf(i)g(\left\lfloor\dfrac ni\right\rfloor)的和式

for (int l = 1, r = 0; l <= n; l = r + 1)
{
    r = n / (n / l);
    ans += (r - (l - 1)) * (n / l);
}

欧拉函数

线性筛（同时得到欧拉函数和素数表）

const int MAXN = 10000000;
bool check[MAXN + 10];
int phi[MAXN + 10];
int prime[MAXN + 10];
int tot; //素数的个数
void phi_and_prime_table(int N)
{
    memset(check, false, sizeof(check));
    phi[1] = 1;
    tot = 0;
    for (int i = 2; i <= N; i++)
    {
        if (!check[i])
        {
            prime[tot++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < tot; j++)
        {
            if (i * prime[j] > N)
                break;
            check[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] * (prime[j] - 1);
            }
        }
    }
}

求单个数的欧拉函数

long long eular(long long n)
{
    long long ans = n;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            ans -= ans / i;
            while (n % i == 0)
                n /= i;
        }
    }
    if (n > 1)
        ans -= ans / n;
    return ans;
}

模拟退火

void solve()
{
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //高质量随机
    double T = 100, delta = 0.98;
    double x = 50;
    double ans = f(x);
    while (T > eps)
    {
        double a = rng() % 2;
        if (a == 0)
            a = -1;
        double nx = x + a * T;
        if (nx >= 0 && nx <= 100 && f(nx) < ans)
        {
            ans = f(nx);
            x = nx;
        }
        T *= delta;
    }
    printf("%.4f\n", ans);
}

Lucas

int f[N];
int mod = 1e9 + 7;
// int mul(int a, int b, int p)
// {
//     int ans = 0;
//     for (; b; b >>= 1, a = (a + a) % p)
//         if (b & 1)
//             ans = (ans + a) % p;
//     return ans;
// }
int qpow(int a, int b, int mod)
{
    int ans = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)
            ans = ans * a % mod;
    return ans;
}
void init()
{
    for (int i = 1; i <= 1e6 + 10; i++)
    {
        f[i] = qpow(i, mod - 2, mod);
    }
}
int c(int n, int m)
{
    if (n < m)
        return 0;
    int ans = 1;
    for (int i = 1; i <= m; i++)
    {
        ans = ans * (((n - m + i) % mod) * f[i] % mod) % mod;
    }
    return ans;
}
int lucas(int m, int n)
{
    if (m == 0)
        return 1;
    return (lucas(n / mod, m / mod) * c(n % mod, m % mod)) % mod;
}

FFT和NTT

const long double PI = acos(-1.0);
const int MOD = (int)1e9 + 7;
inline int mul(int a,int b){
    int res = (ll)a * b % MOD;
    if(res < 0) res += MOD;
    return res;
}
inline void add(int &a,int b){
    a += b;
    if(a >= MOD) a -= MOD;
}
inline void sub(int &a,int b){
    a -= b;
    if(a < 0) a += MOD;
}
const int Maxn = 5e5 + 5;
const double Pi=acos(-1);
struct CP
{
  CP (double xx=0,double yy=0){x=xx,y=yy;}
  double x,y;
  CP operator + (CP const &B) const
  {return CP(x+B.x,y+B.y);}
  CP operator - (CP const &B) const
  {return CP(x-B.x,y-B.y);}
  CP operator * (CP const &B) const
  {return CP(x*B.x-y*B.y,x*B.y+y*B.x);}
}f[Maxn * 3],p[Maxn * 3];
int tr[Maxn * 3];
int n,m;
void fft(CP *f,bool flag)
{
  for (int i=0;i<n;i++)
    if (i<tr[i])swap(f[i],f[tr[i]]);
  //枚举区间长度
  for(int p=2;p<=n;p<<=1){
    int len=p>>1;//待合并的长度
    CP tG(cos(2*Pi/p),sin(2*Pi/p));
    if(!flag)tG.y*=-1;//p次单位根
    for(int k=0;k<n;k+=p){//枚举起始点
      CP buf(1,0);//遍历一个子问题并合并
      for(int l=k;l<k+len;l++){
        CP tt=buf*f[len+l];
        f[len+l]=f[l]-tt;
        f[l]=f[l]+tt;
        buf=buf*tG;
      }
    }
  }
}

class NTTClass{
public:
    static const int MAXL=22;
    static const int MAXN=1<<MAXL;
    static const int root=3;
    static const int MOD=998244353;
    int rev[MAXN];
    int fast_pow(int a,int b){
        int ans=1;
        while(b){
            if(b&1)ans=1ll*ans*a%MOD;
            a=1ll*a*a%MOD;
            b>>=1;
        }
        return ans;
    }
    void transform(int n,int *t,int typ){
        for(int i=0;i<n;i++)
            if(i<rev[i])swap(t[i],t[rev[i]]);
        for(int step=1;step<n;step<<=1){
            int gn=fast_pow(root,(MOD-1)/(step<<1));
            for(int i=0;i<n;i+=(step<<1)){
                int g=1;
                for(int j=0;j<step;j++,g=1ll*g*gn%MOD){
                    int x=t[i+j],y=1ll*g*t[i+j+step]%MOD;
                    t[i+j]=(x+y)%MOD;
                    t[i+j+step]=(x-y+MOD)%MOD;
                }
            }
        }
        if(typ==1)return;
        for(int i=1;i<n/2;i++)swap(t[i],t[n-i]);
        int inv=fast_pow(n,MOD-2);
        for(int i=0;i<n;i++)t[i]=1ll*t[i]*inv%MOD;
    }
    void ntt(int p,int *A,int *B,int *C){
        transform(p,A,1);
        transform(p,B,1);
        for(int i=0;i<p;i++)C[i]=1ll*A[i]*B[i]%MOD;
        transform(p,C,-1);
    }
    void mul(int *A,int *B,int *C,int n,int m) {
        int p=1,l=0;
        while(p<=n+m)p<<=1,l++;
        //printf("n = %d, m = %d\n",n,m);
        for (int i=n+1;i<p;i++) A[i] = 0;
        for (int i=m+1;i<p;i++) B[i] = 0;
        //for (int i=0;i<p;i++) printf("%d ",A[i]);puts("");
        //for (int i=0;i<p;i++) printf("%d ",B[i]);puts("");
        for(int i=0;i<p;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
        ntt(p,A,B,C);
        //puts("C:");for (int i=0;i<p;i++) printf("%d ",C[i]);puts("");
    }
}NTT;

判断两球相交部分体积

typedef struct point {
    double x, y, z;
    point() {}
    point(double a, double b, double c) {
        x = a;
        y = b;
        z = c;
    }
    point operator -(const point& b)const {    
        return point(x - b.x, y - b.y, z - b.z);
    }
    point operator +(const point& b)const {     
        return point(x + b.x, y + b.y, z + b.z);
    }
    point operator *(const double& k)const {    
        return point(x * k, y * k, z * k);
    }
    point operator /(const double& k)const {    
        return point(x / k, y / k, z / k);
    }
    double operator *(const point& b)const {   
        return x * b.x + y * b.y + z * b.z;
    }
}point;
double dist(point p1, point p2) {       
    return sqrt((p1 - p2) * (p1 - p2));
}
typedef struct sphere {
    double r;
    point centre;
}sphere;
double SphereInterVS(sphere a, sphere b) {
    double d = dist(a.centre, b.centre);
    if (d + a.r <= b.r) {
        return (4.0 / 3.0) * PI * a.r * a.r * a.r;
    }
    if (d + b.r <= a.r) {
        return (4.0 / 3.0) * PI * b.r * b.r * b.r;
    }
    double t = (d * d + a.r * a.r - b.r * b.r) / (2.0 * d);//
    double h = sqrt((a.r * a.r) - (t * t)) * 2;
    double angle_a = 2 * acos((a.r * a.r + d * d - b.r * b.r) / (2.0 * a.r * d)); 
    double angle_b = 2 * acos((b.r * b.r + d * d - a.r * a.r) / (2.0 * b.r * d)); 
    double l1 = ((a.r * a.r - b.r * b.r) / d + d) / 2;
    double l2 = d - l1;
    double x1 = a.r - l1, x2 = b.r - l2;
    double v1 = PI * x1 * x1 * (a.r - x1 / 3);
    double v2 = PI * x2 * x2 * (b.r - x2 / 3);
    double v = v1 + v2;
    return v;
}

求数组中子数组起码k个最大平均值

double find(double p[], int k,int n) {
	double l = 600000;
	double r = 0;
	for (int i = 1; i <= n; i++) {
		l = min(l, p[i]);
		r = max(r, p[i]);
	}
	while (r - l > 1e-7) {
		double mid = (r + l) / 2;
		double suma[N] = {0};
		for (int i = 1; i <= n; i++) {
			suma[i] = suma[i-1] + p[i] - mid;
		}
		double premin = 0;
		double summax = 0;
		for (int i = k; i <= n; i++) {
			summax = max(summax, suma[i] - premin);
			premin = min(premin, suma[i - k + 1]);
		}
		if (summax > 0)
			l = mid;
		else r = mid;
	}
	return l;
}

求逆序对数

归并排序求逆序对数

int merge_count(int a[], int left, int mid, int right)
{
    int *b = new int[right - left + 1];
    int P1 = left;
    int P2 = mid + 1;
    int i = 0;
    int S3 = 0;
    while (P1 <= mid && P2 <= right)
    {
        if (a[P1] <= a[P2]){
            b[i++] = a[P1++];
        }
        else{
            b[i++] = a[P2++];
            S3 += (mid - P1) + 1;
        }
    }
    while (P1 <= mid){
        b[i++] = a[P1++];
    }
    while (P2 <= right){
        b[i++] = a[P2++];
    }
    for (int i = 0; i < right - left + 1; ++i){
        a[i + left] = b[i];
    }
    delete[] b;
    return S3;
}
 
int count_inver(int a[], int left, int right)
{
    if (left >= right)
        return 0;
    int mid = (left + right) / 2;
    int S1 = count_inver(a, left, mid);
    int S2 = count_inver(a, mid + 1, right);
    int S3 = merge_count(a, left, mid, right);
    return (S1 + S2 + S3);
}

计算几何

struct Point
{
    double x, y;
    Point() {}
    Point(double x, double y) : x(x), y(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 p) { return Vector(a.x * p, a.y * p); }
Vector operator/(Vector a, double p) { return Vector(a.x / p, a.y / p); }
int dcmp(double x)
{
    if (fabs(x) <= eps)
        return 0;
    else if (x > 0)
        return 1;
    return -1;
}
bool operator==(const Point &a, const Point &b) { return dcmp(a.x - b.x) == 0 && dcmp(a.y - b.y) == 0; }
double Dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double Length(Vector a) { return sqrt(Dot(a, a)); }
double Angle(Vector a, Vector b) { return acos(Dot(a, b) / Length(a) / Length(b)); }
double Cross(Vector a, Vector b)
{
    return a.x * b.y - a.y * b.x;
}
Vector Rotate(Vector a, double rad) { return Vector(a.x * cos(rad) - a.y * sin(rad), a.x * sin(rad) + a.y * cos(rad)); }
double Distance(Point a, Point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
double Area(Point a, Point b, Point c) { return fabs(Cross(b - a, c - a) / 2); }

bool Intersect(Point A, Point B, Point C, Point D)
{
    double t1 = Cross(C - A, D - A) * Cross(C - B, D - B);
    double t2 = Cross(A - C, B - C) * Cross(A - D, B - D);
    return dcmp(t1) < 0 && dcmp(t2) < 0;
}
bool StrictIntersect(Point A, Point B, Point C, Point D)
{
    return dcmp(max(A.x, B.x) - min(C.x, D.x)) >= 0 && dcmp(max(C.x, D.x) - min(A.x, B.x)) >= 0 && dcmp(max(A.y, B.y) - min(C.y, D.y)) >= 0 && dcmp(max(C.y, D.y) - min(A.y, B.y)) >= 0 && dcmp(Cross(C - A, D - A) * Cross(C - B, D - B)) <= 0 && dcmp(Cross(A - C, B - C) * Cross(A - D, B - D)) <= 0;
}
Point GetLineIntersection(Point P, Vector v, Point Q, Vector w)
{
    Vector u = P - Q;
    double t = Cross(w, u) / Cross(v, w);
    return P + v * t;
}

凸包

#include <bits/stdc++.h>
using namespace std;
#define FAST ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
typedef long long ll;
const int maxn = 2e5 + 50;
struct point
{
    double x, y;
} p[maxn];
inline point del(point a, point b) { return (point){(b.x - a.x), (b.y - a.y)}; }
inline double dis(point a, point b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); }
inline double Xmul(point a, point b) { return a.x * b.y - b.x * a.y; }
inline bool operator<(const point &a, const point &b)
{
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}
int n, s[maxn];
void run()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i].x >> p[i].y;
    sort(p + 1, p + 1 + n);
    double ans = 0;
    int cnt = 0;
    s[++cnt] = 1, s[++cnt] = 2;
    for (int i = 3; i <= n; ++i)
    {
        point u = del(p[s[cnt - 1]], p[s[cnt]]);
        point v = del(p[s[cnt]], p[i]);
        while (Xmul(u, v) < 0.0)
        {
            if (cnt == 1)
                break;
            cnt--;
            u = del(p[s[cnt - 1]], p[s[cnt]]), v = del(p[s[cnt]], p[i]);
        }
        s[++cnt] = i;
    }
    int tmp = cnt;
    s[++cnt] = n, s[++cnt] = n - 1;
    for (int i = n - 2; i >= 1; --i)
    {
        point u = del(p[s[cnt - 1]], p[s[cnt]]);
        point v = del(p[s[cnt]], p[i]);
        while (Xmul(u, v) < 0.0)
        {
            if (cnt == 1)
                break;
            cnt--;
            u = del(p[s[cnt - 1]], p[s[cnt]]), v = del(p[s[cnt]], p[i]);
        }
        s[++cnt] = i;
    }
    for (int i = 1; i <= cnt; ++i)
        cout << p[s[i]].x << ' ' << p[s[i]].y << "\n";
    for (int i = 1; i <= cnt - 1; ++i)
        ans += dis(p[s[i]], p[s[i + 1]]);
}
signed main()
{
    FAST;
    run();
    return 0;
}

矩阵乘

struct Matrix
{
    int mat[2][2];
    int x, y;
    Matrix(int a = 2, int b = 2)
    {
        x = a, y = b;
        memset(mat, 0, sizeof(mat));
    }
    Matrix operator*(Matrix a)
    {
        Matrix res(x, a.y);
        for (int i = 0; i < x; i++)
        {
            for (int j = 0; j < y; j++)
                for (int k = 0; k < y; k++)
                    res.mat[i][j] = (res.mat[i][j] + mat[i][k] * a.mat[k][j]);
        }
        return res;
    }
};

高斯消元

const int maxn = 1e3 + 10;
double mat[maxn][maxn];
double ans[maxn];
int n;
// false代表无解,true代表有解,解在ans[1]...ans[n]中
bool gauss()
{
    for (int i = 1; i <= n; i++)
    {
        int maxrow = i;
        for (int row = i + 1; row <= n; row++)
        {
            if (abs(mat[row][i]) > abs(mat[maxrow][i]))
                maxrow = row;
        }
        if (maxrow != i)
            swap(mat[i], mat[maxrow]);
        if (mat[i][i] == 0)
            return false;
        for (int row = i + 1; row <= n; row++)
        {
            double k = mat[row][i] / mat[i][i];
            for (int j = i; j <= n + 1; j++)
                mat[row][j] -= k * mat[i][j];
        }
    }
    for (int i = n; i >= 1; i--)
    {
        ans[i] = mat[i][n + 1] / mat[i][i];
        for (int row = n - 1; row >= 1; row--)
            mat[row][n + 1] -= mat[row][i] * ans[i], mat[row][i] = 0;
    }
    return true;
}