Chonu

Posted on In , Valine:

D. Transitivity

Given a simple undirected graph with $n$ vertices and $m$ edges, and it’s guaranteed that

We define an undirected graph to be transitive if and only if for any two different vertices $u, v$ :

If there exists a path starting from $u$ and ending at $v$ in the graph, then there should exists an edge connected $u$ and $v$ in the graph.

Now you should add some undirected edges to the graph (add at least one edge). You need to ensure that after adding edges, the graph is still a simple undirected graph and is transitive.

The question is, how many edges need to be added at least?

Recall that a simple undirected graph is an undirected graph that does not have more than one edge between any two vertices and no edge starts and ends at the same vertex.

$n_{k}^9$

Posted on Edited on In , Valine:

B 军训 II

对于这类问题一个很经典的思路就是求每个位置的贡献

首先能感性的判断出来从小到大/从大到小排不整齐度是最小的(因为最大/最小值都是依次递增的)

然后可以理性的证明一下：

对于已经排好序的数组a 有a1<=a2<=a3<=…<=an,此时交换a2,ak(假设a2<ak);

交换完的结果就是l在[1,k-1],r在[l,k-1]的区间内最大值变大，最小值不变,l在[k,n]，r在[l,n]的区间内最大值不变，最小值变小

身高相同的人可以交换位置,$A_{k}^k$,表示k个身高相同的人的排列方案,

注意特判全相等序列(从小到大和从大到小排列一样)

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
void solve(){
    int n;cin>>n;
    vector<int>a(n);
    map<int,int>mp;
    for(int i=0;i<n;i++){
        cin>>a[i];mp[a[i]]++;
    }
    sort(a.begin(),a.end());
    int ans1=0,ans2=1;
    for(int i=0;i<n;i++){
        for(int j=i;j<n;j++){
            ans1+=a[j]-a[i];
        }
    }
    auto A=[&](int x){
        int tem=1;
        for(int i=1;i<=x;i++){
            tem=(tem*i)%mod;
        }
        return tem;
    };
    a.erase(unique(a.begin(),a.end()),a.end());
    for(auto i:a){
        ans2=(ans2*A(mp[i]))%mod;
    }
    if(a.size()!=1) ans2=(ans2*2)%mod;
    cout<<ans1<<' '<<ans2<<endl;
}

K 取沙子游戏

考虑n的奇偶性

当n为奇数时，第一手取1必然获胜

当n为偶数时，考虑变成必胜态，即将n减去某两个数得到奇数，可知这两个数必然为一奇一偶，且先手必选偶数，当先手选择奇数后，后手必胜。

由于选择的是偶数，初步猜想寄了，因为后手必然不会选择奇数，所以后手选择偶数阻止先手到达必胜态，此时第二轮到达先手手上的数还是偶数，这样归纳一下可以发现当n为偶数的时候，先后手都只会选择偶数

考虑二进制，当先手第一次选择lowbit(n)时，后手无论选择什么我们都和其选择一样即可获胜，因为二进制下需要偶数次选择偶数才能将这个数归零

Posted on In , Valine:

G Shift and Reverse

Topic

Bobo has a sequence $a_1,a_2,\dots,a_n$. He can rearrange the sequence using the following operation any number of times:

+ Select an integer i ($1 \le i \le n$) and change the sequence to $a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$.

Bobo would like to know the number of different sequences can be obtained modulo $(10^9+7)$.

波波有一个序列$a_1,a_2,\dots,a_n$。他可以使用以下操作任意次数重新排列序列:

选择整数i($1 \le i \le n$)并将序列更改为$a_i, a_{i-1}, \dots, a_1, a_n, a_{n-1}, \dots, a_{i+1}$。

Bobo想知道有多少个不同的序列对$(10^9+7)$取模。

Analyse

遇到题目没思路就先模拟一下

一个新的数组a,标号从a1-an,假定选择k进行反转操作，执行操作后的序列为$a_{k},a_{k-1}…a_{k+2},a_{k+1},$

Posted on Edited on In , , Valine:

Manacher

能在O(N)的时间内求出以每个位置为回文中心的回文半径

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
vector<int> manacher(string s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

void solve(){
    string s;cin>>s;
    auto r=manacher(s);
    int ans=0;
    for (int i = 1; i < 2 * s.size(); i++) {
        ans = max(ans, r[i] - 1);
    }
    cout<<ans<<"\n";
}

KMP

Z函数(扩展kmp/exkmp)

能在O(n)的时间范围里找到给定字符串s，对于每个位置i，s整个字符串和$(s[i]-s[n-1])(等价于s.substr(i))$的LCP(最长公共前缀)

Posted on Edited on In , , Valine:

数论

快速幂(Power)

快速幂求$a^b$ % p，其中a,b,p均∈[1,1e9],时间复杂度为$O(logb)$

1
2
3
4
5
6
7
8
9
int power(int a, int b, int p) {
    int res = 1;
    for (; b; b /= 2, a = a * a % p) {
        if (b % 2) {
            res = 1LL * res * a % p;
        }
    }
    return res;
}

快速幂求质数的乘法逆元

1
2
//快速幂求x mod p的乘法逆元：适用于p为质数
power（x,p-2,p）

龟速乘

求(𝑎∗𝑏)𝑚𝑜𝑑𝑝的值，a，b，p范围均[1,1e18]。

1
2
3
4
5
6
7
8
LL qadd(LL a, LL b, LL p){
    LL res = 0;
    while (b){
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
return res;}

exgcd

x,y为可行解，g为a，b的gcd

1
2
3
4
5
6
7
8
9
int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

Pollard-Rho & Miller Rabin

期望复杂度O($n^{1/4}$)

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
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
namespace factor {
    using f64 = long double;
    ll p;
    f64 invp;
    void setmod(ll x) {
        p = x, invp = (f64) 1 / x;
    }
    ll mul(ll a, ll b) {
        ll z = a * invp * b + 0.5;
        ll res = a * b - z * p;
        return res + (res >> 63 & p);
    }
    ll pow(ll a, ll x, ll res = 1) {
        for(;x;x >>= 1, a = mul(a, a))
            if(x & 1) res = mul(res, a);
        return res;
    }
    inline ll rho(ll n) {
        if(!(n & 1)) return 2;
        static std::mt19937_64 gen((size_t)"hehezhou");
        ll x = 0, y = 0, prod = 1;
        auto f = [&](ll o) { return mul(o, o) + 1; };
        setmod(n);
        for(int t = 30, z = 0;t % 64 || std::gcd(prod, n) == 1;++t) {
            if (x == y) x = ++ z, y = f(x);
            if(ll q = mul(prod, x + n - y)) prod = q;
            x = f(x), y = f(f(y));
        }
        return std::gcd(prod, n);
    }
    bool checkprime(ll p) {
        if(p == 1) return 0;
        setmod(p);
        ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
        for(ll a : {2, 3, 5, 7, 11, 13, 82, 373}) {
            if(a % p == 0)
                continue;
            ll x = pow(a, s), y;
            for(int i = 0;i < d;++i, x = y) {
                y = mul(x, x);
                if(y == 1 && x != 1 && x != p - 1)
                    return 0;
            }
            if(x != 1) return 0;
        }
        return 1;
    }
    std::vector<ll> factor(ll x) {
        std::queue<ll> q; q.push(x);
        std::vector<ll> res;
        for(;q.size();) {
            ll x = q.front(); q.pop();
            if(x == 1) continue;
            if(checkprime(x)) {
                res.push_back(x);
                continue;
            }
            ll y = rho(x);
            q.push(y), q.push(x / y);
        }
        sort(res.begin(), res.end());
        return res;
    }
}
void solve(){
    ll n; cin >> n;
    if(factor::checkprime(n)) {
        cout << "Prime" << '\n';
        return;
    }else {
        auto res = factor::factor(n);
        //返回n的质因子，有重复，即res中元素乘积就是n
        cout << res.back() << '\n';
    }   
}

线性筛/欧拉筛(Sieve)

时间复杂度O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> minp, primes;
void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (i * p > n) {
                break;
            }
            minp[i * p] = p;
            if (p == minp[i]) {
                break;
            }
        }
    }
}
//primes数组存储所有的质数，minp[i]表示i的最小质因子

期望

期望的线性性质：

$E[f(s)^{2}]=\sum _{x=start}^{end}x^{2}*P(x) $

举例：

$E[f(s)^{2}]$ 表示集合s中所有数的按位异或，其中s中的数表示为x，范围为[0,1024] 就可以展开为$\sum _{x=0}^{1024}x^{2}*P(x)$

其中P(x)可以累乘，最终乘取模数的逆元求出答案

线性基(Basis)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Basis {
    vector<int>p;
    Basis() {
        p.assign(64,0);
    }
    void add(int x) {//插入一个数x
        for(int i=63;i>=0;i--){
            if(!(x>>i)){
                continue;
            }
            if(!p[i]){
                p[i]=x;break;
            }
            x^=p[i];
        }
    }
    int mx(){ //找最大值
        int ans=0;
        for(int i=63;i>=0;i--){
            ans=max(ans,ans^p[i]);
        }
        return ans;
    }
};

Posted on Edited on In , , Valine:

XCPC 数据结构

双哈希封装

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
struct Shash{  
    const ll base[2]={29,31};
    //base存储基数
    const ll hashmod[2]={(ll)1e9+9,998244353};
    //hashmod存储模数
    array<vector<ll>,2>hsh;
    array<vector<ll>,2>pwMod;
    //hsh[2] 和 pwMod[2]：这两个二维 vector 分别用于存储哈希值和幂模值。
    //其中，hsh[i][j] 表示字符串前 j 个字符在基数 base[i] 和模数 hashmod[i] 下的哈希值；
    //pwMod[i][j] 表示基数 base[i] 的 j 次幂对 hashmod[i] 取模的结果。
    void init(string S){
        int n=S.size();S=' '+S;
        hsh[0].resize(n+1),hsh[1].resize(n+1);
        pwMod[0].resize(n+1),pwMod[1].resize(n+1);
        for(int i=0;i<2;++i){
            pwMod[i][0]=1;
            for (int j=1;j<=n;++j){
                pwMod[i][j]=pwMod[i][j-1]*base[i]%hashmod[i];
                hsh[i][j]=(hsh[i][j-1]*base[i]+S[j])%hashmod[i];
            }
        }
    }
    //get函数输出[l,r]这段字符的哈希值,first是第一个模数下哈希值,second是第二个
    pair<ll,ll>get(int l,int r){
        pair<ll,ll> ans;
        ans.first=(hsh[0][r]-hsh[0][l-1]*pwMod[0][r-l+1])%hashmod[0];
        ans.second=(hsh[1][r]-hsh[1][l-1]*pwMod[1][r-l+1])%hashmod[1];
        ans.first=(ans.first+hashmod[0])%hashmod[0];
        ans.second=(ans.second+hashmod[1])%hashmod[1];
        return ans;
    }
};
bool same(Shash &a,int la,int ra,Shash &b,int lb,int rb){
    return a.get(la,ra)==b.get(lb,rb);
}

声明方式

1
2
3
Shash a;
a.init(s)//s是待处理字符串
if(same(a,l,r,b,l,r))//判断字符串a,b在l,r区间内是否相等

删除某几个字符串得到新的哈希值

1
2
//假设删除s[i],s[i+1]两个字符，得到新的字符串的哈希值就是hsh[i-1][0]*pmMod[n-(i+1)][0]+get(i+2,n).first
//(以上为在第一个模底下的新的字符串哈希值)

并查集

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 DSU {
    vector<int> f,siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[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;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
};

声明方式

1
2
3
4
DSU dsu(N)//声明一个大小为N，名称为dsu的并查集
dsu.merge(a,b)//合并a,b
dsu.find(x)//找到x的祖宗节点
dsu.size(x)//以x为祖宗节点的个数

可撤销并查集(DSU With Rollback)

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
/**   
	可撤销并查集（DSU With Rollback）
**/
struct DSU {
    std::vector<int> siz;
    std::vector<int> f;
    std::vector<std::array<int, 2>> his;
    
    DSU(int n) : siz(n + 1, 1), f(n + 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    
    int find(int x) {
        while (f[x] != x) {
            x = f[x];
        }
        return x;
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        his.push_back({x, y});
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int time() {
        return his.size();
    }
    
    void revert(int tm) {
        while (his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }
};

线段树

通用版

区间开方(板子: HDU 4027)

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
template <class T> 
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)    
    struct node {
        int l, r;
        T sum; // 注意初始赋值
        T mx=0;
    };
    vector<T> w;
    vector<node> t;
    LSGT(int n) {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }
    LSGT(vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void pushdown(node &p) { // 在此更新下递函数
        return;
    }
    void pushup(node &p, node &l, node &r) { // 在此更新上传函数
        p.sum = l.sum + r.sum;
        p.mx=max(l.mx,r.mx);
    }
    void pushdown(int p) { // 不需要动
        pushdown(t[l(p)]);
        pushdown(t[r(p)]);
    }
    void pushup(int p) { // 不需要动
        pushup(t[p], t[l(p)], t[r(p)]);
    }
    void build(int l, int r, int p = 1) {
        if (l == r) {
            t[p] = {l, r, w[l],w[l]};
            return;
        }
        t[p] = {l, r};
        int mid = (l + r) >> 1;
        build(l, mid,l(p));
        build(mid + 1, r, r(p));
        pushup(p);
    }
    void modify(int l, int r, int p = 1) { // 区间修改
        if(t[p].mx<=1) return;
        if(t[p].l==t[p].r){
            t[p].sum=(int)sqrt(t[p].sum);
            t[p].mx=t[p].sum;
            return;
        }else{
            int mid = (t[p].l + t[p].r) >>1 ;
            if (l <= mid) modify(l, r,l(p));
            if (mid < r) modify(l, r, r(p));
        }
        pushup(p);
    }
    T asp(int l, int r, int p = 1) { // 区间询问，不合并
        if (l <= t[p].l && t[p].r <= r) {
            return t[p].sum;
        }
        //pushdown(p);
        int mid = (t[p].l + t[p].r) / 2;
        T ans = 0;
        if (l <= mid) ans += asp(l, r,l(p));
        if (mid < r) ans += asp(l, r, r(p));
        return ans;
    }
    void debug(int p = 1) {
        cout << "[" << t[ p].l << ", " << t[p].r << "]: ";
        cout << "sum = " << t[p].sum << ", ";
        cout << endl;
        if (t[p].l == t[p].r) return;
        debug(l(p)), debug(r(p));
    }
#undef l(p)
#undef r(p)
};

线段树 ( SegmentTree+Info )

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
struct Info{
    int lc, rc, ls, rs, len, ans;
};
Info operator+(Info a, Info b) {
    Info c = {0, 0, 0, 0, 0};
    c.ans = max(a.ans, b.ans);
    if (a.rc == 0 && b.lc == 0) c.ans = max(c.ans, a.rs + b.ls);
    c.lc = a.lc, c.rc = b.rc;
    c.ls = a.ls;
    if (a.ls == a.len && a.rc == b.lc) c.ls += b.ls;
    c.rs = b.rs;
    if (b.rs == b.len && a.rc == b.lc) c.rs += a.rs;
    c.len = a.len + b.len;
    return c;
}
struct segtree{
    struct Node {
        int l, r;
        Info info;
    } tr[N << 2];
 
    void pull(int u) {
        tr[u].info = tr[u << 1].info + tr[u << 1 | 1].info;
    }
 
    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) {
            tr[u].info = {0, 0, 1, 1, 1, 1};
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pull(u);
    }
 
    void modify(int u, int x) {
        if (tr[u].l == tr[u].r) {
            tr[u].info.lc ^= 1;
            tr[u].info.rc ^= 1;
            tr[u].info.ans ^= 1;
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x);
        if (x > mid) modify(u << 1 | 1, x);
        pull(u);
    }
 
    Info query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].info;
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        if (l > mid) return query(u << 1 | 1, l, r);
        return query(u << 1, l, r) + query(u << 1 | 1, l, r);
    }
}t;
void solve() {
    int n,m;cin>>n>>m;
    t.build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int x;cin>>x;
            t.modify(1,x);
        }else{
            int l,r;cin>>l>>r;
            cout<<t.query(1,l,r).ans<<endl;
        }
    }
}

LazySegmentTree 基础区间修改

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
template<class Info, class Tag>
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LSGT() {}
    LSGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LSGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        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 >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
#undef l(p)
#undef r(p)
};

struct Tag {
    // 定义要下放什么标记
    int mul,add;
    //Tag(...): ... {} // 初始化
    Tag(int _mul=1,int _add=0):mul(_mul),add(_add){}
    void apply(Tag t) {
        // 怎么用父结点的标记更新儿子的标记
        mul=mul*t.mul;
        add=(add*t.mul+t.add);
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        //如果是只有add标记,注意sum=sum+t.add;
        // 怎么用父结点的标记更新儿子存储的信息
        // 这里 jls 原本没有区间长度 len 这个形参，但我觉得可能常用就自己加上了
        sum = (sum * t.mul + 1LL * t.add * len);
    }
};
Info operator+(Info a, Info b) {
    Info c;
    // a 和 b 一通操作弄出 c
    c.sum = (a.sum + b.sum);
    return c;
}
void solve(){
    int n;cin>>n;
    vector<Info>a(n+1);
    for(int i=1;i<=n;i++){
        int x;cin>>a[i].sum;
    }
    LSGT<Info,Tag>sgt(a);
    int m;cin>>m;
    while(m--){
        int t,l,r;cin>>t>>l>>r;
        r+=1;
        if(t==1){
            int c;cin>>c;
            sgt.Apply(l,r,Tag(c,0));
        }else if(t==2){
            int c;cin>>c;
            sgt.Apply(l, r, Tag(1, c));
        }else{
            cout<<sgt.query(l,r).sum<<endl;
        }
    }
}
signed main(){
    IOS;
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

单调栈解决NGE问题

右边第一个严格大于当前元素的数的下标

1
2
3
4
5
6
stack<int>stk;
for(int i=n-1;i>=0;i--){
    while(!stk.empty()&&a[stk.top()]<=a[i]) stk.pop();
    b[i]=stk.size()?stk.top():-1;
    stk.push(i);
}

单调队列(滑动窗口)

以最小值为例，最大值的区别就是第一行while pop时的条件的区别

1
2
3
4
5
6
7
8
9
10
11
12
deque<int>q;
    //单调队列求最小值
    for(int i=0;i<n;i++){
        while(q.size()&&a[q.back()]>=a[i]) q.pop_back();
        //将队尾所有大于等于遍历到当前元素的数pop出去
        q.push_back(i);
        //新元素入队
        while(q.size()&&i-k>=q.front()) q.pop_front();
        //将已经划出去的队头pop出去
        if(i>=k-1) cout<<a[q.front()]<<" ";
        //当前元素就是窗口值k之内最小的元素
    }

Trie树

快速查询多个字符串中的前缀和，时间复杂度为O(m),其中m是待查询/插入的字符串长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(string x){
    int p=0;
    for(int i=0;i<x.length();i++){
        int u=x[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
        cnt[p]+=1;
    }
}
int query(string x){
    int p=0,op=0;
    for(int i=0;i<x.length();i++){
        int u=x[i]-'a';
        if(!son[p][u]) return op;
        p=son[p][u];
        op+=(cnt[p]);
    }
    return op;
}

字典树也可以快速查询某个字符串有没有出现过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void insert(string x){
    int p=0;
    for(int i=0;i<x.length();i++){
        int u=x[i]-'a';
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
    cnt[p]+=1;
}
int query(string x){
    int p=0,op=0;
    for(int i=0;i<x.length();i++){
        int u=x[i]-'a';
        if(!son[p][u]) return 0;
        p=son[p][u];
    }
    op+=cnt[p];
    return op;
}

树状数组

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
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
    Fenwick(int n) : n(n), tr(n + 1, 0){}
    int lowbit(int x){
        return x & -x;
    }
    void modify(int x, T c){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
    void modify(int l, int r, T c){
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    T query(int l, int r){
        return query(r) - query(l - 1);
    }
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
};
using BIT = Fenwick<int>;

声明方式

1
2
3
4
5
6
BIT tr(n);//n是大小
//注意输入的时候要从1-n输入,vactor开n+1;
tr.modify(n,k)//第n个数加上k
tr.modify(1,n,k)//从1到n每个数加k
tr.query(x)//查询第x个数    
//三星提醒：初始化的时候是tr.modify(pos,pos,c),这样才代表只给pos位置赋值c

树状数组求逆序对

数值大的情况下要进行离散化,离散化下标从1开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int n;cin>>n;
    vector<int>a(n);
    BIT tr(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        tr.modify(a[i],1);
        ans+=(i-tr.query(a[i]));
    }
    cout<<ans<<endl;
}

树状数组jiangly

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
struct Fenwick {
    int n; vector<T>a;
    Fenwick(int n_ = 0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

ST表

解决RMQ问题，预处理复杂度为O(nlogn),O(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
35
36
37
38
39
struct ST {
    int n;
    vector<int>lg;
    vector<vector<int>> mx, mn;
    ST(vector<int>init){
        n=init.size()-1;
        lg.resize(n);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        mx.resize(n + 1, vector<int>(lg[n] + 1));
        mn.resize(n + 1, vector<int>(lg[n] + 1));
        for (int i = 1; i <= n; i++) {
            mx[i][0] = init[i];
            mn[i][0] = init[i];
        }
        int k = lg[n];
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
                mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int getmax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = lg[r - l + 1];
        return max(mx[l][k], mx[r - (1 << k) + 1][k]);
    }
    int getmin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = lg[r - l + 1];
        return min(mn[l][k], mn[r - (1 << k) + 1][k]);
    }
};

解决区间gcd问题

预处理复杂度为$O(n(logn+logv))$,查询复杂度$O(logv)$,其中v为值域

该问题”区间gcd”中，线段树查询的复杂度为$O(logn+logv)$

ST表可以用来解决可重复贡献问题，例如「区间按位与」、「区间按位或」、「区间 GCD」，ST 表都能高效地解决。

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
struct ST {
    int n;
    vector<int>lg;
    vector<vector<int>> g;
    ST(vector<int>init){
        n=init.size()-1;
        lg.resize(n);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        g.resize(n + 1, vector<int>(lg[n] + 1));
        for (int i = 1; i <= n; i++) {
            g[i][0] = init[i];
        }
        int k = lg[n];
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                g[i][j] = gcd(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int query(int l, int r) {
        int k=lg[r - l + 1];
        return gcd(g[l][k], g[r - (1 << k) + 1][k]);
    }
};

自动取模与排列组合

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
const int maxn = 3e5 + 5, mod = 1e9 + 7;
template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}

    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
using mint = ModInt<mod>;

mint fact[maxn], invfact[maxn];

void init(){
    fact[0] = invfact[0] = 1;
    for(int i = 1; i < maxn; i++) fact[i] = fact[i - 1] * i;
    invfact[maxn - 1] = fact[maxn - 1].inv();
    for(int i = maxn - 2; i; i--)
        invfact[i] = invfact[i + 1] * (i + 1);  
}

inline mint C(int a, int b){
    if (a < 0 || b < 0 || a < b) return 0;
    return fact[a] * invfact[b] * invfact[a - b];
}

莫队

基础莫队

属于离线算法，解决数据范围在[1,1e5]范围内的题;

如果n，m同阶(n==m),时间复杂度为$n\sqrt{n}$,排序按照左端点块顺序与右端点来排序

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
vector<array<int,3>>query(q+1);
    int siz=(int)(ceil(pow(n,0.5)));
    vector<int>k(n+1);
    for(int i=1;i<=n;i++){
        k[i]=(i-1)/siz+1;
    }
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        query[i]={l,r,i};
    }
    sort(query.begin()+1,query.end(),[&](auto x,auto y){
        if(k[x[0]]!=k[y[0]]) return k[x[0]]<k[y[0]];
        if(k[x[0]]&1) return x[1]<y[1];
        return x[1]>y[1];
    });
    int l=1,r=0,val=0;
	vector<int>ans(q+1);
    auto add=[&](int x){
    };
    auto del=[&](int x){
    };
    for(int i=1;i<=q;i++){
        auto [ql,qr,id]:query[i];
        while(l>ql) add(a[--l]);
        while(r<qr) add(a[++r]);
        while(l<ql) del(a[l++]);
        while(r>qr) del(a[r--]);
        ans[id]=val;
    }

树链剖分

HLD

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
struct HLD {
    int n;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    int cur;
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root ) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        /*
           标记每个点的深度dep[]
           标记每个点的父亲parent[]
           标记每个非叶子节点的子树大小(含它自己)
        */
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) {
        //返回两点的距离
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int jump(int u, int k) {
        //向上跳k步，返回跳跃后的节点
        if (dep[u] < k) {
            return -1;
        }
        int d = dep[u] - k;
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        return seq[in[u] - dep[u] + d];
    }
    bool isAncester(int u, int v) {
        //判断u是否是v的祖先
        return in[u] <= in[v] && in[v] < out[u];
    }
    int rootedParent(int u, int v) {
        /*
            在以u为根的子树中，找到v的直接父节点
         */
        swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    int rootedSize(int u, int v) {
        /*
         * 在以u为根的子树中，计算以v为根的子树的大小
         */
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

点权与线段树操作

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
struct HLD {
    int n,cur;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    HLD(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 1;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root ) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
};
template<class Info, class Tag>
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
    int n;
    vector<Info> info;
    vector<Tag> tag;
    template<class T>
    LSGT(vector<T> init1) {
        init(init1);
    }
    template<class T>
    void init(vector<T> init1) {
        n = init1.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init1[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag& v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
#undef l(p)
#undef r(p)
};
struct Tag {
    int add;
    Tag(int add1=0):add(add1){}
    void apply(Tag t) {
        add+=(t.add);
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        sum += 1LL * t.add * len;
    }
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = (a.sum + b.sum);
    return c;
}
void solve() {
    int n,m,r,p;cin>>n>>m>>r>>p;
    //r为根,p为取模数
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<vector<int>>g(n+1);
    HLD t(n+1);
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        t.addEdge(x,y);
    }
    t.work(r);
    vector<Info>k(n+1);
    for(int i=1;i<=n;i++){
        k[t.in[i]].sum=a[i];
    }
    LSGT<Info,Tag>sgt(k);
    auto range=[&](int x,int y,int z){
        while(t.top[x]!=t.top[y]){
            if(t.dep[t.top[x]]<t.dep[t.top[y]]) swap(x,y);
            sgt.Apply(t.in[t.top[x]],t.in[x]+1,z);
            x=t.parent[t.top[x]];
        }
        if(t.dep[x]>t.dep[y]) swap(x,y);
        sgt.Apply(t.in[x],t.in[y]+1,z);
    };
    auto query=[&](int x,int y){
        int ans=0;
        while(t.top[x]!=t.top[y]){
            if(t.dep[t.top[x]]<t.dep[t.top[y]]) swap(x,y);
            ans=(ans+sgt.query(t.in[t.top[x]],t.in[x]+1).sum)%p;
            x=t.parent[t.top[x]];
        }
        if(t.dep[x]>t.dep[y]) swap(x,y);
        ans=(ans+sgt.query(t.in[x],t.in[y]+1).sum)%p;
        return ans;
    };
    while(m--){
        int op;cin>>op;
        if(op==1){
            int x,y,z;cin>>x>>y>>z;
            range(x,y,z);//区间加
        }else if(op==2){
            int x,y;cin>>x>>y;
            cout<<query(x,y)<<"\n";//区间和
        }else if(op==3){
            int x,z;cin>>x>>z;
            sgt.Apply(t.in[x],t.in[x]+t.siz[x],z);//子树加
        }else{
            int x;cin>>x;
            cout<<(sgt.query(t.in[x],t.in[x]+t.siz[x]).sum)%p<<"\n";//子树和
        }
    }
}

再版

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
template <class T> 
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)    
    struct node {
        int l, r;
        T sum; // 注意初始赋值
        T add=0;
    };
    vector<T> w;
    vector<node> t;
    LSGT(){};
    LSGT(int n) {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }
    LSGT(vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void init(vector<int> in){
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void pushdown(node &p,T add) { // 在此更新下递函数
        p.sum=(p.sum+(p.r-p.l+1)*add)%mod;
        p.add=(p.add+add)%mod;
        return;
    }
    void pushup(node &p, node &l, node &r) { // 在此更新上传函数
        p.sum = (l.sum + r.sum)%mod;
    }
    void pushdown(int p) { // 不需要动
        pushdown(t[l(p)],t[p].add); 
        pushdown(t[r(p)],t[p].add);
        t[p].add=0;
    }
    void pushup(int p) { // 不需要动
        pushup(t[p], t[l(p)], t[r(p)]);
    }
    void build(int l, int r, int p = 1) {
        if (l == r) {
            t[p] = {l, r, w[l]};
            return;
        }
        t[p] = {l, r};
        int mid = (l + r) >> 1;
        build(l, mid,l(p));
        build(mid + 1, r, r(p));
        pushup(p);
    }
    void modify(int l, int r, T val,int p = 1) { // 区间修改
        if(l<=t[p].l&&t[p].r<=r){
            t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*val)%mod;
            t[p].add=(t[p].add+val)%mod;
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) modify(l,r,val,l(p));
        if(mid<r) modify(l,r,val,r(p));
        pushup(p);
    }
    T ask(int l, int r, int p = 1) { // 区间询问，不合并
        if (l <= t[p].l && t[p].r <= r) {
            return t[p].sum;
        }
        pushdown(p);
        int mid = (t[p].l + t[p].r) / 2;
        T ans = 0;
        if (l <= mid) ans = (ans+ ask(l, r,l(p)))%mod;
        if (mid < r) ans = (ans+ask(l, r, r(p)))%mod;
        return ans;
    }
    void debug(int p = 1) {
        cout << "[" << t[ p].l << ", " << t[p].r << "]: ";
        cout << "sum = " << t[p].sum << ", ";
        cout << endl;
        if (t[p].l == t[p].r) return;
        debug(l(p)), debug(r(p));
    }
#undef l(p)
#undef r(p)
};

struct HLD {
    int n, idx;
    vector<vector<int>> ver;
    vector<int> siz, dep;
    vector<int> top, son, parent;
    vector<int> in, id, val;
    LSGT<int>seg;

    HLD(int n) {
        this->n = n;
        ver.resize(n + 1);
        siz.resize(n + 1);
        dep.resize(n + 1);

        top.resize(n + 1);
        son.resize(n + 1);
        parent.resize(n + 1);

        idx = 0;
        id.resize(n + 1);
        val.resize(n + 1);
    }
    void add(int x, int y) { // 建立双向边
        ver[x].push_back(y);
        ver[y].push_back(x);
    }
    void dfs1(int x) {
        siz[x] = 1;
        dep[x] = dep[parent[x]] + 1;
        for (auto y : ver[x]) {
            if (y == parent[x]) continue;
            parent[y] = x;
            dfs1(y);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    }
    void dfs2(int x, int up) {
        id[x] = ++idx;
        val[idx] = in[x]; // 建立编号
        top[x] = up;
        if (son[x]) dfs2(son[x], up);
        for (auto y : ver[x]) {
            if (y == parent[x] || y == son[x]) continue;
            dfs2(y, y);
        }
    }
    void work(int root, auto in) { // 在此初始化
        this->in = in;
        dfs1(root);
        dfs2(root, root);
        seg.init(val); // 建立线段树
    }

    void modify(int l, int r, int val) { // 链上修改
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]]) {
                swap(l, r);
            }
            seg.modify(id[top[l]], id[l], val);
            l = parent[top[l]];
        }
        if (dep[l] > dep[r]) {
            swap(l, r);
        }
        seg.modify(id[l], id[r], val);
    }
    void modify(int root, int val) { // 子树修改
        seg.modify(id[root], id[root] + siz[root] - 1, val);
    }
    int ask(int l, int r) { // 链上查询
        int ans = 0;
        while (top[l] != top[r]) {
            if (dep[top[l]] < dep[top[r]]) {
                swap(l, r);
            }
            ans = (ans+seg.ask(id[top[l]], id[l]))%mod;
            l = parent[top[l]];
        }
        if (dep[l] > dep[r]) {
            swap(l, r);
        }
        return (ans + seg.ask(id[l], id[r]))%mod;
    }
    int ask(int root) { // 子树查询
        return (seg.ask(id[root], id[root] + siz[root] - 1))%mod;
    }
};

主席树

Persistent Segment Tree（可持久化权值线段树）

区间静态第k小

包括离散化,pos-1是因为b数组下标从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
int cnt=0;
struct Node{
    int l,r,rt,sum;
};
vector<Node>tr(N<<5);

int build(int l,int r){
    int p=++cnt;
    tr[p].sum=0;
    int mid=l+r>>1;
    if(l<r){
        tr[p].l=build(l,mid);
        tr[p].r=build(mid+1,r);
    }
    return p;
}

int update(int pre,int l,int r,int x){
    int p=++cnt;
    tr[p]=tr[pre];tr[p].sum++;
    int mid=l+r>>1;
    if(l<r){
        if(x<=mid)tr[p].l=update(tr[pre].l,l,mid,x);
        else tr[p].r=update(tr[pre].r,mid+1,r,x);
    }
    return p;
}

int query(int u,int v,int l,int r,int k){
    if(l>=r) return l;
    int x=tr[tr[v].l].sum-tr[tr[u].l].sum;
    int mid=l+r>>1;
    if(x>=k) return query(tr[u].l,tr[v].l,l,mid,k);
    else return query(tr[u].r,tr[v].r,mid+1,r,k-x);
}

void solve(){
    int n,m;cin>>n>>m;
    vector<int>a(n),b(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    int len=b.size();
    tr[0].rt=build(1,len);
    for(int i=0;i<n;i++){
        int x=lower_bound(b.begin(),b.end(),a[i])-b.begin()+1;
        tr[i+1].rt=update(tr[i].rt,1,len,x);
    }
    while(m--){
        int l,r,k;cin>>l>>r>>k;//求区间[l,r]内的第k小
        int pos=query(tr[l-1].rt,tr[r].rt,1,len,k);
        cout<<b[pos-1]<<'\n';
    }
}

FHQ Treap

操作复杂度$log_2n$，

能够解决

  1. 插入一个数 x。

  2. 删除一个数 x（若有多个相同的数，应只删除一个）。

  3. 定义排名为比当前数小的数的个数 +1。查询 x的排名。

  4. 查询数据结构中排名为 x的数。

  5. 求 x 的前驱（前驱定义为小于 x，且最大的数）。

  6. 求 x 的后继（后继定义为大于 x，且最小的数）。

Posted on Edited on In , Valine:

A Intelligent Warehouse

Topic

In MI Intelligent Warehouse, there are $n_{}$ products, where the $i_{}$-th product is of size $a_i$. We always need to box producsts into all kinds of containers, and it will be safer and more cost efficient(效率高的) if for any two sizes of products, one is the other’s multiple, since(因为) there won’t be any residual(残余的) room in one container. So for each boxing we need to choose some products that for any two chosen products, either $a_i$ is multiple of $a_j$ or $a_j$ is multiple of $a_i$. Print the maximum number of products that can be chosen in one boxing.

在mi智能仓库中，有$n_{}$个产品，其中$i_{}$个产品的尺寸为$a_i$。我们总是需要把产品装进各种各样的容器中，如果任意两个尺寸的产品，一个是另一个的倍数，这样会更安全且成本效益更高，因为一个容器里不会有剩余的空间。因此，对于每次装箱，我们需要选择一些产品，对于任意两个选择的产品，要么是$a_i$是$a_j$的倍数，要么是$a_j$是$a_i$的倍数。打印出在一次装箱中选择的产品的最大数量。

Analyse

目的是选择若干个数字，其中任意两个数均成倍数关系

考虑最终选定的序列，将其排序后，每个数都必然是最大数的约数，所以其实存在一种递推关系，当$ai$是某个数列的最大数时，将$ai$的倍数加进来，整个数列必然也满足条件

考虑dp，dp[i]表示以i结尾的最长序列，dp关系式也如上文所说

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
constexpr int N=1e7;
int dp[N+10],mp[N+10];
void solve() {
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int x;cin>>x;
        mp[x]++;
    }
    int ans=0;
    for(int i=1;i<=N;i++){
        if(mp[i]){
            dp[i]+=mp[i];
            for(int j=i*2;j<=N;j+=i){
                dp[j]=max(dp[i],dp[j]);
            }
            ans=max(ans,dp[i]);
        }
    }
    cout<<ans;
}

B Intelligent Robot

C Smart Browser

Topic

In some social platforms(社交平台), there are some netizen(平台) who like to post “www“. Since the string is like the grass(草), which contains plenty of “/\“ shapes, so there are also some netizen who post “grass“.

As a fast, smart, and convenient browser, MI Browser can recognize this kind of text and show some special effects. Specifically(具体来说), given a string, MI Browser will determine(确定) the number of “/\“ shapes made by character “w“, where “w“ itself and the gap(间隙) between two adjacent(相邻的) “w“s both give one `/\` shape. If still not clear, please turn to sample input/output for more details.

As a MI fan, you want to detect(探究) the relationship between the special effects and the number of “/\“ shapes, so the thing you should do first is to determine the number of “/\“ shapes by yourself.

在一些社交平台上，有些网民喜欢发布“www”。由于这个字符串看起来很像草，其中包含了许多“/\”的形状，因此也有一些网民发布“grass”。

作为一款快速、智能且便捷的浏览器，MI浏览器能够识别这种文本并展示一些特殊效果。具体来说，给定一个字符串，MI浏览器会确定由字符“w”构成的“/\”形状的数量，其中“w”本身以及两个相邻“w”之间的间隙都构成一个“/\”形状。如果仍然不清楚，请参考示例输入输出以获取更多详情。

作为MI浏览器的粉丝，你想要探究这些特殊效果与“/\”形状数量之间的关系，因此你首先要做的就是自己确定“/\”形状的数量。

Analyse

双指针判断以v分隔开的w的字符数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    string s;cin>>s;
    int ans=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='w'){
            int cnt=1;
            while(s[i+1]=='w'&&i+1<s.length()){
                i++;cnt++;
            }
            ans+=2*cnt-1;
        }
    }
    cout<<ans<<endl;
}