跳转至

板子

回滚并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct Roll_DSU{
    struct Data {
        int son, fa, sizson, sizfa, fson;
        LL sum;
    } st[maxn];
    int top;
    // 撤销栈

    int fa[maxn],siz[maxn];
    LL sum;
    void clear(){
        // iota 递增赋值
        std::iota(fa+1,fa+1+n,1),std::fill(siz+1,siz+1+n,1);
        sum=0;
    }
    int find(int x){
        return x == fa[x] ? x : find(fa[x]);
    }
    void merge(int x, int y) {
        x=find(x), y=find(y);
        if (x == y) return;
        LL lst = sum;
        sum += 1ll * siz[x] * siz[y]; // 答案--连通的点对数量 （按需修改）
        if (siz[x] < siz[y])
            st[++top] = { x, y, siz[x], siz[y], fa[x], lst }, fa[x] = y, siz[y] += siz[x];
        else
            st[++top] = { y, x, siz[y], siz[x], fa[y], lst }, fa[y] = x, siz[x] += siz[y];
    }
    void rollback(){
        Data &t = st[top];
        fa[t.son]=t.fson, siz[t.son]=t.sizson, siz[t.fa]=t.sizfa, sum=t.sum;
        top--;
    }
}dsu;

线性基

堪比高斯消元的动态线性基，from Menci。性质同高斯消元。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
LL num[70];
void insert(LL x) {
    for(int i=63;i>=0;i--){
        if(!((x>>i)&1)) continue;
        if(num[i]) x^=num[i];
        else{
            // 在该位插入 并消元 能达到和高斯消元一样的效果
            // 用 a[0...i - 1] 消去 x 的第 [0, i - 1] 位上的 1
            for(int j=0;j<i;j++) if((x>>j)&1) x^=num[j];

            // 用 x 消去 a[i + 1, 60] 的第 i 位上的 1
            for(int j=i+1;j<=63;j++) if((num[j]>>i)&1) num[j]^=x;
            num[i]=x;
            return ;
        }
    }
}

从中选任意多个数与某个数的异或最大值：

1
2
3
4
5
6
7
LL qry(LL x) {
    LL res=x;
    for (int i=63;i>=0;i--)
        if ((res^num[i])>res)
            res^=num[i];
    return res;
}

01-trie

大端序：高位向低位建，用于算选一个数与某个数取 xor-max：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 0-1 trie
// 高位向低位建 高位向低位贪心
struct Trie01{
    int ch[maxn*63][2],cnt=1;

    void ins(LL x){
        int now=1;
        for(int i=63;i>=0;i--){
            int c=(x>>i)&1;
            if(!ch[now][c]) ch[now][c]=++cnt;
            now = ch[now][c];
        }
    }

    LL getmax(LL x){ // x能异或出的最大值
        LL res=0;
        int now=1;
        for(int i=63;i>=0;i--){
            int c=(x>>i)&1;
            if(ch[now][c^1]) now=ch[now][c^1], res|=(1ll<<i);
            else now=ch[now][c];
        }
        return res;
    }
}t;

哈希表

请注意 0xfffff 是要严格比 maxn 小的二进制全1的数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct MyHash {
    int operator()(ull key) {
        return (key % maxn + maxn) % maxn;
    }
    int operator()(int key) {
        return (key ^ key << 2 ^ key >> 3) & 0xfffff;
    }
    int operator()(const std::string& key) {
        return key.length();
    }
    // ...
};

template<typename _k, typename _v, typename _hash = MyHash>
struct hash_map {
    struct Data {
        _k key;
        _v val;
        int pre; // 链式前向星
    } e[maxn];
    int tot, head[maxn];

    void clear() {
        while (tot) head[_hash()(e[tot].key)] = 0, tot--;
    }

    _v& operator[](_k key) {
        int now = _hash()(key);
        for (int p = head[now]; p; p = e[p].pre) if (e[p].key == key) return e[p].val;
        // 否则新建
        e[++tot] = {key, _v(), head[now]}, head[now] = tot;
        return e[tot].val;
    }
};

一般的 ull -> int 哈希表：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn = 1e5+10;

struct hash_map{
    struct Data{
        ull key;
        int val,pre;
    }e[maxn];
    int head[maxn], tot;
    int hash(ull key){
        return (key ^ key<<2 ^ key>>3) & 0xfffff;
    }
    void clear(){
        while(tot) head[hash(e[tot].key)]=0, tot--;
    }
    int& operator[](ull key){
        int now=hash(key);
        for(int p=head[now];p;p=e[p].pre) if(e[p].key == key) return e[p].val;
        e[++tot]={key,0,head[now]}, head[now]=tot;
        return e[tot].val;
    }
};

其实就是链式前向星。。。

点分树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using LL = long long;
using std::cin;
using std::cout;

const int maxn = 1e5+10;

struct Edge{
    int v,pre;
}e[maxn*2];
int head[maxn],tot;
void add(int u,int v){
    e[++tot]={v,head[u]},head[u]=tot;
}

// find weight
// mxsiz::最大子树大小 mxsiz最小的点是重心 别忘了0初始化
// sumsiz::当前的分治子树大小
int siz[maxn],mxsiz[maxn],cen,sumsiz;
bool vis[maxn];
void getcen(int now,int fa) {
    siz[now]=1;
    mxsiz[now]=0;
    for(int p=head[now]; p; p=e[p].pre) {
        int v=e[p].v;
        if(v==fa || vis[v]) continue;
        getcen(v,now);
        siz[now]+=siz[v];
        mxsiz[now]=std::max(mxsiz[now],siz[v]);
    }
    mxsiz[now] = std::max(mxsiz[now],sumsiz-siz[now]); // 向上的树大小
    if(mxsiz[now] <= mxsiz[cen]) cen=now; // 如果揉到一起写，必须小于等于
}

// 点分树上父亲
int _f[maxn];
void build(int now){
    vis[now]=1;
    // dfs to calc here
    for(int p=head[now];p;p=e[p].pre){
        int v=e[p].v;
        if(v==_f[now] || vis[v]) continue;
        sumsiz=siz[v], cen=0;
        getcen(v,now),getcen(cen,0);
        _f[cen]=now, build(cen);
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<n;i++) {
        int u,v;
        cin >> u >> v;
        add(u,v),add(v,u);
    }
    sumsiz=n,mxsiz[cen=0]=INT_MAX;
    getcen(1,0),getcen(cen,0);
    build(cen);
    return 0;
}

李超线段树

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
#include <bits/stdc++.h>

using std::cin;
using std::cout;
using LL = long long;
using ull = unsigned long long;
using ld = long double;

const int maxn = 4e5+10;   // 总线段
const int maxm=39990;      // 值域
const ld eps = 1e-7;
int n;
bool eq(ld x,ld y) {
    return fabsl(x-y)<eps;
}

struct Seg {
    ld k,b;
    int l,r;
    int id;
    ld operator()(int x) const {
        if(l<=x && x<=r) return k*x+b;
        else return -INFINITY;
        // if max, it's -INF; or, it's INF.
        // make sure you won't choose illegal segs
    }
} t[maxm<<2];
**define**{: #define .hash} lid id<<1
**define**{: #define .hash} rid id<<1|1

// 向下标记
//void upd(int id,int l,int r,Seg f) {
//  Seg &now = t[id];
//  int mid=l+r>>1;
//  // 根据mid上的取值进行分讨，tag存mid上最优的线段
//  if(f(mid) > now(mid)) {
//      // 先看自己更不更新
//      if(now(l) > f(l)) upd(lid,l,mid,now);
//      if(now(r) > f(r)) upd(rid,mid+1,r,now);
//      // 说明原来存的线段还有利用价值（now在交点以外的部分仍然更优）
//      // 接着向下改
//      now = f;
//  } else {
//      if(f(l) > now(l)) upd(lid,l,mid,f);
//      if(f(r) > now(r)) upd(rid,mid+1,r,f);
//  }
//}
void upd(int id,int l,int r,Seg f) {
    Seg &now = t[id];
    int mid=l+r>>1;
    if(f(mid) > now(mid)) std::swap(now,f); // 动态开点这么写就寄了，只能swap线段的k和b（要保证f的ls/rs=0）
    if(f(l) > now(l)) upd(lid,l,mid,f);
    if(f(r) > now(r)) upd(rid,mid+1,r,f);
}

// 返回线段（如有需要可以在Seg里打上id）
// 注意是标记永久化，每一层都要和自己t[id]取个max/min
Seg smax(const Seg& a,const Seg& b,int x) {
    if(a(x) > b(x)) return a;
    else return b;
}
Seg qry(int id,int l,int r,int pos) {
    if(l==r) return t[id];
    int mid=l+r>>1;
    if(pos<=mid) return smax(t[id],qry(lid,l,mid,pos),pos);
    else return smax(t[id],qry(rid,mid+1,r,pos),pos);
}
void join(int id,int l,int r,int ll,int rr,Seg i) {
    if(l==ll && r==rr) {
        upd(id,l,r,i);
        return ;
    }
    int mid=l+r>>1;
    if(rr<=mid) join(lid,l,mid,ll,rr,i);
    else if(ll>mid) join(rid,mid+1,r,ll,rr,i);
    else join(lid,l,mid,ll,mid,i),join(rid,mid+1,r,mid+1,rr,i);
}

// 李超树合并优化dp
// 动态开点！
**define**{: #define .hash} lid t[id].ls
**define**{: #define .hash} rid t[id].rs
int merge(int id, int y, int l, int r) {
    if (!id || !y) return id + y;
    upd(id, l, r, t[y]);
    int mid = l+r>>1;
    lid = merge(lid, t[y].ls, l, mid);
    rid = merge(rid, t[y].rs, mid + 1, r);
    return id;
}

/*
if(x0==x1) {
    k = {0,std::max(y0,y1),x0,x0,tot};
} else {
    k.k=1.0L*(y1-y0)/(x1-x0);
    k.b=1.0L*y1-k.k*x1;
    k.l= std::min(x0,x1);
    k.r= std::max(x0,x1);
    k.id=tot;
}
*/

分解质因数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using LL = long long;
using ull = unsigned long long;
using ld = long double;

const int maxn = 1e7+10;
std::bitset<maxn> np;
int prime[maxn],cnt;
int x;
int main() {
    np[1]=1;
    for(int i=2; i<maxn; i++) {
        if(!np[i]){
            prime[++cnt]=i;
            for(int j=i+i; j<maxn; j+=i) np[j]=1;
        }
    }
    cin >> x;
    int i=1;
    while(i<=cnt && x!=1){
        while(x%prime[i]) i++;
        cout << prime[i] << '*';
        x/=prime[i];
    }
    return 0;
}