Chonu

Posted on Edited on In , Valine:

A - Sakurako and Kosuke

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve(){
    int n;cin>>n;
    int m=1,cnt=0;
    for(int i=1;;i++){
        if(i&1){
            cnt-=(2*i-1);
        }else{
            cnt+=(2*i-1);
        }
        if(abs(cnt)<=n){
            continue;
        }else{
            m=i;
            break;
        }
    }            
    cout<<(m&1?"Kosuke":"Sakurako")<<"\n";
}

B - Sakurako and Water

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
    int n;cin>>n;
    vector<vector<int>>g(n+1,vector<int>(n+1));
    map<int,vector<int>>mp;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>g[i][j];
            if(g[i][j]<0){
                mp[i-j].push_back(abs(g[i][j]));
            }
        }
    }    
    int ans=0;
    for(auto &[x,y]:mp){
        sort(y.begin(),y.end(),greater<int>());
        ans+=y[0];
    }
    cout<<ans<<"\n";
}

C - Sakurako’s Field Trip

C这个题有一点说法，其实想明白什么时候换就可以

从左到n/2的位置每次考虑是否交换当前位置，当i这个位置与i-1的数相同的时候或者n-i+1与其下一个数（就是当前数与其遍历过的上一个数）相同的时候选择交换，可以证明这样操作对答案的增益一定是非负的

证明如下

  1. 如果a[i]==a[n-i+1]，操作无影响

  2. a[i]!=a[n-i+1]，

    设交换之前点i对答案的增益为 ans=(a[i]==a[i-1]+a[i]==a[i+1]+a[n-i+1]==a[n-i]+a[n-i+1]==a[n-i+2])

    交换之后点i对答案的增益为 ans1=(a[n-i+1]==a[i-1]+a[n-i+1]==a[i+1]+a[i]==a[n-i]+a[i]==a[n-i+2])

    最坏情况就是

    a[i]==a[i-1]&&a[i]!=a[i+1]&&a[n-i+1]!=a[n-i]&&a[n-i+1]!=a[n-i+2]

    a[n-i+1]==a[i+1]&&a[i]==a[n-i]&&a[i]==a[n-i+2]

    这样的话，交换之后答案多2，但是这种情况下在下一次交换过程中会被重新满足条件执行交换

综上，一直执行交换，最后求答案即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
    int n;cin>>n;
    vector<int>a(n+10,0),cnt(n+1,0);
    for(int i=1;i<=n;i++) cin>>a[i];
    int ans=0;
    for(int i=1;i<=(n+1)/2;i++){
        if(a[i]==a[i-1]||a[n-i+1]==a[n-i+2]){
            swap(a[i],a[n-i+1]);
        }
    }
    for(int i=1;i<=n-1;i++){
        if(a[i]==a[i+1]) ans++;
    }
    cout<<ans<<"\n";
}

D - Kousuke’s Assignment

没啥说的，遇到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
void solve(){
    int n;cin>>n;
    vector<int>a(n+1),pre(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pre[i]=pre[i-1]+a[i];
    }
    int ans=0,lst=0;
    map<int,int>mp;
    for(int i=1;i<=n;i++){
        if(a[i]==0){
            lst=i;ans++;
            continue;
        }
        int d=pre[i]-pre[lst];
        if(d==0){ 
            if(lst<i){
                ans++;
                lst=max(i,lst);
            }
        }else if(mp.count(d)){
            if(lst<mp[d]){
                 ans++;
                lst=max(i,lst);
            }
        }
        mp[d]=i;
    }
    cout<<ans<<'\n';
}

E - Sakurako, Kosuke, and the Permutation

每次交换完之后就保证当前位置不再交换,这样顺序从1到n就是最小交换次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
     int n;cin>>n;
     vector<int>a(n+1),pos(n+1);
     for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]]=i;
     }
     int ans=0;
     for(int i=1;i<=n;i++){
         if(a[i]==i) continue;
         if(pos[i]==a[i]&&a[a[i]]==i) continue;
         swap(a[pos[i]],a[a[i]]);
         swap(pos[a[pos[i]]],pos[a[a[i]]]);
         ans++;
     }
     cout<<ans<<"\n";
}

F - Kosuke’s Sloth

递推数列具有模周期性，找到第一个循环节中的下标再乘n即可

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
	int n,k;cin>>n>>k;
	f[1]=f[2]=1;
	int pos=0;
	for(int i=1;;i++){
		if(i>=3) f[i]=(f[i-1]+f[i-2])%k;
		if(f[i]%k==0){
			pos=i;
			break;
		}
	}
	cout<<(pos%mod)*(n%mod)%mod<<"\n";
}

Posted on In , Valine:

A - Profitable Interest Rate

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
    int a,b;cin>>a>>b;
    if(a>=b){
        cout<<a<<"\n";
    }else{
        int k=2*a-b;
        if(k>0){
            cout<<k<<"\n";
        }else{
            cout<<0<<"\n";
        }
    }            
}

B - Buying Lemonade

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(){
   int n,k;cin>>n>>k;
   vector<int>a(n);
   for(int i=0;i<n;i++) cin>>a[i];
   sort(a.begin(),a.end());
   int sum=0,ans=0,mn=0;
   for(int i=0;i<n;i++){
      a[i]-=mn;
      if(sum+a[i]*(n-i)<k){
         sum+=a[i]*(n-i);
         mn+=a[i];ans+=a[i]*(n-i);
      }else{
         ans+=k-sum;
         break;
      }  
      ans++; 
   }     
   cout<<ans<<"\n";       
}

C - Concatenation of Arrays

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void solve(){
    int n;cin>>n;
    vector<array<int,3>>a(n);
    for(int i=0;i<n;i++){
        cin>>a[i][0]>>a[i][1];
        a[i][2]=a[i][0]+a[i][1];
    }     
    sort(a.begin(),a.end(),[&](auto l,auto r){
        if(l[2]!=r[2])return l[2]<r[2]; 
        else return min(l[0],l[1])<min(r[0],r[1]);
    });
    for(int i=0;i<n;i++){
        cout<<a[i][0]<<" "<<a[i][1]<<" ";
    }
    cout<<"\n";
}

D - Skipping

只有答题才能得分，所以跳题相当于花费a[i]从位置i转移到b[i]

答题就是花费0从i转移到i-1

最终答案就是所有能遍历到的位置上的a[i]-cost[i]

b[i]小于等于i时选择跳过是不明智的，因为此时在到达b[i]的过程中通过答题到b[i]能获得的分数一定更大

i 到 j 有两种方法，第一种是 j=b[i]，直接从 i 跳到 j ；第二种是 i<j<b[i] ，从 i 跳到 b[i] 再向左答题到 j，两种方法的花费都是a[i]，

所以我们遍历所有位置，每次取能到当前位置且花费最小，转移到当前位置求每个能遍历到的位置的最小花费

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<pair<int,int>>a(n+1);
   for(int i=1;i<=n;i++) cin>>a[i].first;
   for(int i=1;i<=n;i++) cin>>a[i].second;
   priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
   pq.push({a[1].first,a[1].second});
   vector<int>dp(n+1,1e18);
   dp[1]=0;
   for(int i=2;i<=n;i++){
      while(pq.size()&&pq.top().second<i){
         pq.pop();
      }
      if(pq.empty()){
         break;
      }
      dp[i]=pq.top().first;   
      if(a[i].second>i){
         pq.push({dp[i]+a[i].first,a[i].second});
      }
   }  
   int sum=0,ans=0;          
   for(int i=1;i<=n;i++){
      sum+=a[i].first;
      ans=max(ans,sum-dp[i]);
   }
   cout<<ans<<"\n";
}

Posted on Edited on Valine:

数论

Tips

  1. 奇数的所有因子都是奇数

  2. 求大数$\frac{a}{b}$下取整取模=(a-a%b+mod)%mod*inv(b)%mod

    分子是多个数相乘也一样

    1
    2
    3
    4
    5
    6
    int b;cin>>b;//分母
        for(auto [u,v]:p){
            l=(l*power(u,v,mod))%mod;
            r=(r*power(u,v,b))%b;
        }
        cout<<(l-r+mod)%mod*power(b,mod-2,mod)%mod;

GCD&LCM

1
2
3
4
lcm(a,b)=a*b/gcd(a,b);//防止a*b过大，一般写为a/gcd(a,b)*b;
gcd(ka, kb) = k*gcd(a, b)
lcm(ka, kb) = k*lcm(a, b)
lcm(s/a,s/b)=s/gcd(a, b) (处理分数时，可以使用这个公式)

快速幂(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）

矩阵快速幂

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 Matrix {
    vector<vector<int>>x;
    int n;
    Matrix(int n) {
        this->n = n;
        x.resize(n + 1, vector<int>(n + 1, 0));
    }
    void init(int n){
        for(int i=1;i<=n;i++){
            x[i][i]=1;
        }
    }
    Matrix operator*(Matrix& b) {
        Matrix res(n);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n; k++) {
                    res.x[i][j] = (res.x[i][j] + x[i][k] * b.x[k][j]) % mod;
                }
            }
        }
        return res;
    }

    Matrix operator^(int k) {
        Matrix res(n);
        res.init(n);
        Matrix cnt = *this;
        while (k) {
            if (k & 1) res = res * cnt;
            cnt = cnt * cnt;
            k >>= 1;
        }
        return res;
    }
};

龟速乘

求(𝑎∗𝑏)𝑚𝑜𝑑𝑝的值，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;}

组合数

  1. $O(N^2)$

    $C_{a}^{b}=C_{a-1}^{b}+C_{a-1}^{b-1}$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    const int N = 2010, mod = 1e9 + 7;
    int c[N][N];
    void init(){
        for (int i = 0; i < N; i ++ ){
            for (int j = 0; j <= i; j ++ ){
                if (!j) c[i][j] = 1;
                else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
            }
        }
    }
    int C(int a,int b){
        return c[a][b];
    }

  2. $O(N)*log(mod)$

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    const int N = 100010, mod = 1e9 + 7;
    int fact[N], infact[N];
    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;
    }
    void init(){
        fact[0] = infact[0] = 1;
        for (int i = 1; i < N; i ++ ){
            fact[i] = fact[i - 1] * i % mod;
            infact[i] = infact[i - 1] * power(i, mod - 2, mod) % mod;
        }
    }
    int C(int a,int b){
        return fact[a] * infact[b] % mod * infact[a - b] % mod;
    }

  3. Lucas,$a,b<=10^{18},p<=10^{5}$,询问数极少

    image-20250403162122640

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    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;
    }
    int C(int a, int b, int p){
        if (b > a) return 0;
        int res = 1;
        for (int i = 1, j = a; i <= b; i ++, j -- ){
            res = res * j % p;
            res = res * power(i, p - 2, p) % p;
        }
        return res;
    }
    int lucas(int a, int b, int p){
        if (a < p && b < p) return C(a, b, p);
        return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
    }
    //询问C(a,b)%p时调用的是lucas(a,b,p)

  4. 不取模，高精度

    image-20250403162314021

    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
    const int N = 5010;
    int primes[N], cnt;
    int sum[N];
    bool st[N];
    void get_primes(int n){
        for (int i = 2; i <= n; i ++ ){
            if (!st[i]) primes[cnt ++ ] = i;
            for (int j = 0; primes[j] <= n / i; j ++ ){
                st[primes[j] * i] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }
    int get(int n, int p){
        int res = 0;
        while (n){
            res += n / p;
            n /= p;
        }
        return res;
    }
    vector<int> mul(vector<int> a, int b){
        vector<int> c;
        int t = 0;
        for (int i = 0; i < a.size(); i ++ ){
            t += a[i] * b;
            c.push_back(t % 10);
            t /= 10;
        }
        while (t){
            c.push_back(t % 10);
            t /= 10;
        }
        return c;
    }
    int main(){
        int a, b;
        cin >> a >> b;
        get_primes(a);
        for (int i = 0; i < cnt; i ++ ){
            int p = primes[i];
            sum[i] = get(a, p) - get(a - b, p) - get(b, p);
        }
        vector<int> res;
        res.push_back(1);
        for (int i = 0; i < cnt; i ++ )
            for (int j = 0; j < sum[i]; j ++ )
                res = mul(res, primes[i]);
        for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
        puts("");
        return 0;
    }

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// ax + b = 0 (mod m)
std::pair<i64, i64> sol(i64 a, i64 b, i64 m) {
    assert(m > 0);
    b *= -1;
    i64 x, y;
    i64 g = exgcd(a, m, x, y);
    if (g < 0) {
        g *= -1;
        x *= -1;
        y *= -1;
    }
    if (b % g != 0) {
        return {-1, -1};
    }
    x = x * (b / g) % (m / g);
    if (x < 0) {
        x += m / g;
    }
    return {x, m / g};
}
1
2
3
4
5
6
7
std::array<i64, 3> exgcd(i64 a, i64 b) {
    if (!b) {
        return {a, 1, 0};
    }
    auto [g, x, y] = exgcd(b, a % b);
    return {g, y, x - a / b * y};
}

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

模性质

  1. $当 n≥p时，很明显n!mod p＝0,n<p时,n!modp不为0$

结论

  1. $C_n^1+C_n^2+…+C_n^{n}==2^n-1$,$C_n^0+C_n^1+C_n^2+…+C_n^{n}==2^n$

Posted on Edited on 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**   高精度（BigInt）
 *    2023-09-11: https://qoj.ac/submission/176420
**/
constexpr int N = 1000;

struct BigInt {
    int a[N];
    BigInt(int x = 0) : a{} {
        for (int i = 0; x; i++) {
            a[i] = x % 10;
            x /= 10;
        }
    }
    BigInt &operator*=(int x) {
        for (int i = 0; i < N; i++) {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i++) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }
    BigInt &operator/=(int x) {
        for (int i = N - 1; i >= 0; i--) {
            if (i) {
                a[i - 1] += a[i] % x * 10;
            }
            a[i] /= x;
        }
        return *this;
    }
    BigInt &operator+=(const BigInt &x) {
        for (int i = 0; i < N; i++) {
            a[i] += x.a[i];
            if (a[i] >= 10) {
                a[i + 1] += 1;
                a[i] -= 10;
            }
        }
        return *this;
    }
};

std::ostream &operator<<(std::ostream &o, const BigInt &a) {
    int t = N - 1;
    while (a.a[t] == 0) {
        t--;
    }
    for (int i = t; i >= 0; i--) {
        o << a.a[i];
    }
    return o;
}

双哈希封装

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

SegmentTree单点修改

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
template<class Info>
struct SGT {
    int n;
    vector<Info> info;
    SGT() : n(0) {}
    SGT(int n1, Info v1 = Info()) {
        init(n1, v1);
    }
    template<class T>
    SGT(vector<T> I) {
        init(I);
    }
    void init(int n1, Info v1 = Info()) {
        init(vector(n1, v1));
    }
    template<class T>
    void init(vector<T> I) {
        n = I.size();
        info.assign(4 << __lg(n), Info());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = I[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};
 
constexpr int inf = 1E18;
struct Info {
    int len;
    int maxl;
    int maxr;
    int minl;
    int minr;
    int ans;
    Info() : len(0), maxl(-inf), maxr(-inf), minl(inf), minr(inf), ans(0) {}
    Info(int x, int i) : len(1), maxl(x + i), maxr(x - i), minl(x - i), minr(x + i), ans(0) {}
    //传参修改
};
 
Info operator+(const Info &a, const Info &b) {
    Info c;
    c.len = a.len + b.len;
    c.maxl = max(a.maxl, b.maxl);
    c.maxr = max(a.maxr, b.maxr);
    c.minl = min(a.minl, b.minl);
    c.minr = min(a.minr, b.minr);
    c.ans = max({a.ans, b.ans, a.maxl - b.minr, b.maxr - a.minl});
    return c;
}

调用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve(){
      int n,q;cin>>n>>q;
      SGT<Info>seg(n+1);
      for(int i=1;i<=n;i++){
        int x;cin>>x;
        seg.modify(i,Info{x,i});
        //传参赋值
      } 
      cout<<seg.query(1,n+1).ans<<"\n";      
      while(q--){
            int p,x;cin>>p>>x;
            seg.modify(p,Info{x,p});
            cout<<seg.query(1,n+1).ans<<"\n";            
      }
}

LazySegmentTree 基础区间修改

学习jiangly线段树的好题Problem - D - Codeforces

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

下标从1开始

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

左边第一个严格大于自身的下标

1
2
3
4
5
6
stack<int>stk;
    for(int i=1;i<=n;i++){
      while(!stk.empty()&&a[stk.top()]<=a[i]) stk.pop();
      c[i]=stk.size()?stk.top():0;
      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
7
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,c)代表给第pos个数加c，用于求前缀和
//tr.modify(pos,pos,c),这样代表差分修改的为pos位置赋值c，用于求第k个数

树状数组求逆序对

数值大的情况下要进行离散化,离散化下标从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
37
template<typename T>
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
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
/**   分数四则运算（Frac）
 *    2024-07-30: https://qoj.ac/submission/498911
**/
template<class T>
struct Frac {
    T num;
    T den;
    Frac(T num_, T den_) : num(num_), den(den_) {
        if (den < 0) {
            den = -den;
            num = -num;
        }
    }
    Frac() : Frac(0, 1) {}
    Frac(T num_) : Frac(num_, 1) {}
    explicit operator double() const {
        return 1. * num / den;
    }
    Frac &operator+=(const Frac &rhs) {
        num = num * rhs.den + rhs.num * den;
        den *= rhs.den;
        return *this;
    }
    Frac &operator-=(const Frac &rhs) {
        num = num * rhs.den - rhs.num * den;
        den *= rhs.den;
        return *this;
    }
    Frac &operator*=(const Frac &rhs) {
        num *= rhs.num;
        den *= rhs.den;
        return *this;
    }
    Frac &operator/=(const Frac &rhs) {
        num *= rhs.den;
        den *= rhs.num;
        if (den < 0) {
            num = -num;
            den = -den;
        }
        return *this;
    }
    friend Frac operator+(Frac lhs, const Frac &rhs) {
        return lhs += rhs;
    }
    friend Frac operator-(Frac lhs, const Frac &rhs) {
        return lhs -= rhs;
    }
    friend Frac operator*(Frac lhs, const Frac &rhs) {
        return lhs *= rhs;
    }
    friend Frac operator/(Frac lhs, const Frac &rhs) {
        return lhs /= rhs;
    }
    friend Frac operator-(const Frac &a) {
        return Frac(-a.num, a.den);
    }
    friend bool operator==(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den == rhs.num * lhs.den;
    }
    friend bool operator!=(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den != rhs.num * lhs.den;
    }
    friend bool operator<(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den < rhs.num * lhs.den;
    }
    friend bool operator>(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den > rhs.num * lhs.den;
    }
    friend bool operator<=(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den <= rhs.num * lhs.den;
    }
    friend bool operator>=(const Frac &lhs, const Frac &rhs) {
        return lhs.num * rhs.den >= rhs.num * lhs.den;
    }
    friend std::ostream &operator<<(std::ostream &os, Frac x) {
        T g = std::gcd(x.num, x.den);
        if (x.den == g) {
            return os << x.num / g;
        } else {
            return os << x.num / g << "/" << x.den / g;
        }
    }
};

莫队

基础莫队

属于离线算法，解决数据范围在[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';
    }
}

小波树

区间下标均为从0开始，区间询问均为左闭右开，第k小也是从0开始（所以第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
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
struct BitRank {
    // block 管理一行一行的bit
    std::vector<unsigned long long> block;
    std::vector<unsigned int> count;
    BitRank() {}
    // 位向量长度
    void resize(const unsigned int num) {
        block.resize(((num + 1) >> 6) + 1, 0);
        count.resize(block.size(), 0);
    }
    // 设置i位bit
    void set(const unsigned int i, const unsigned long long val) {
        block[i >> 6] |= (val << (i & 63));
    }
    void build() {
        for (unsigned int i = 1; i < block.size(); i++) {
            count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]);
        }
    }
    // [0, i) 1的个数
    unsigned int rank1(const unsigned int i) const {
        return count[i >> 6] +
            __builtin_popcountll(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
    }
    // [i, j) 1的个数
    unsigned int rank1(const unsigned int i, const unsigned int j) const {
        return rank1(j) - rank1(i);
    }
    // [0, i) 0的个数
    unsigned int rank0(const unsigned int i) const { return i - rank1(i); }
    // [i, j) 0的个数
    unsigned int rank0(const unsigned int i, const unsigned int j) const {
        return rank0(j) - rank0(i);
    }
};


class WaveletMatrix {
private:
    unsigned int height;
    std::vector<BitRank> B;
    std::vector<int> pos;

public:
    WaveletMatrix() {}
    WaveletMatrix(std::vector<int> vec)
        : WaveletMatrix(vec, *std::max_element(vec.begin(), vec.end()) + 1) {}
    // sigma: 字母表大小(字符串的话)，数字序列的话是数的种类
    WaveletMatrix(std::vector<int> vec, const unsigned int sigma) {
        init(vec, sigma);
    }
    void init(std::vector<int>& vec, const unsigned int sigma) {
        height = (sigma == 1) ? 1 : (64 - __builtin_clzll(sigma - 1));
        B.resize(height), pos.resize(height);
        for (unsigned int i = 0; i < height; ++i) {
            B[i].resize(vec.size());
            for (unsigned int j = 0; j < vec.size(); ++j) {
                B[i].set(j, get(vec[j], height - i - 1));
            }
            B[i].build();
            auto it = stable_partition(vec.begin(), vec.end(), [&](int c) {
                return !get(c, height - i - 1);
            });
            pos[i] = it - vec.begin();
        }
    }

    int get(const int val, const int i) { return val >> i & 1; }
    
    // [l, r) 中val出现的频率
    int rank(const int val, const int l, const int r) {
        return rank(val, r) - rank(val, l);
    } 
    // [0, i) 中val出现的频率
    int rank(int val, int i) {
        int p = 0;
        for (unsigned int j = 0; j < height; ++j) {
            if (get(val, height - j - 1)) {
                p = pos[j] + B[j].rank1(p);
                i = pos[j] + B[j].rank1(i);
            } else {
                p = B[j].rank0(p);
                i = B[j].rank0(i);
            }
        }
        return i - p;
    }
    // [l, r) 中k小
    int quantile(int k, int l, int r) {
        int res = 0;
        for (unsigned int i = 0; i < height; ++i) {
            const int j = B[i].rank0(l, r);
            if (j > k) {
                l = B[i].rank0(l);
                r = B[i].rank0(r);
            } else {
                l = pos[i] + B[i].rank1(l);
                r = pos[i] + B[i].rank1(r);
                k -= j;
                res |= (1 << (height - i - 1));
            }
        }
        return res;
    }
    int rangefreq(const int i, const int j, const int a, const int b, const int l,
                  const int r, const int x) {
        if (i == j || r <= a || b <= l) return 0;
        const int mid = (l + r) >> 1;
        if (a <= l && r <= b) {
            return j - i;
        } else {
            const int left =
                rangefreq(B[x].rank0(i), B[x].rank0(j), a, b, l, mid, x + 1);
            const int right = rangefreq(pos[x] + B[x].rank1(i),
                                        pos[x] + B[x].rank1(j), a, b, mid, r, x + 1);
            return left + right;
        }
    }
    // [l,r) 在[a, b) 值域的数字个数
    int rangefreq(const int l, const int r, const int a, const int b) {
        return rangefreq(l, r, a, b, 0, 1 << height, 0);
    }
    int rangemin(const int i, const int j, const int a, const int b, const int l,
                 const int r, const int x, const int val) {
        if (i == j || r <= a || b <= l) return -1;
        if (r - l == 1) return val;
        const int mid = (l + r) >> 1;
        const int res =
            rangemin(B[x].rank0(i), B[x].rank0(j), a, b, l, mid, x + 1, val);
        if (res < 0)
            return rangemin(pos[x] + B[x].rank1(i), pos[x] + B[x].rank1(j), a, b, mid,
                            r, x + 1, val + (1 << (height - x - 1)));
        else
            return res;
    }
    // [l,r) 在[a,b) 值域内存在的最小值是什么，不存在返回-1
    int rangemin(int l, int r, int a, int b) {
        return rangemin(l, r, a, b, 0, 1 << height, 0, 0);
    }
};

FHQ Treap

操作复杂度$log_2n$，

能够解决

  1. 插入一个数 x。
  2. 删除一个数 x（若有多个相同的数，应只删除一个）。
  3. 定义排名为比当前数小的数的个数 +1。查询 x的排名。
  4. 查询数据结构中排名为 x的数。
  5. 求 x 的前驱（前驱定义为小于 x，且最大的数）。
  6. 求 x 的后继（后继定义为大于 x，且最小的数）。

Posted on Edited on Valine:

XCPC 基础

对拍板子

介绍Windows环境下与Linux环境下的对拍

对拍去DEV

Windows环境

以DEV为例，首先建四个源代码到一个新建文件夹中，源代码分别命名为wa.cpp,data.cpp,violent.cpp,windows.cpp,除此之外什么也不需要添加

  1. 一份错误的/需要比对的代码，导入wa.cpp
  2. 一份暴力的/用来比对的代码，导入violent.cpp
  3. 一份用来造数据的代码
  4. 一份执行对拍程序的代码

wa.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main() {
	freopen("in.txt", "r", stdin); //读入数据生成器造出来的数据
	freopen("wa.txt", "w", stdout); //输出答案
	//下方注释为你的程序
    /*
	int a, b;
	cin >> a >> b;
	cout << a;
	*/
	return 0;
}

violent.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main() {
	freopen("in.txt", "r", stdin);      //读入数据生成器造出来的数据
	freopen("violent.txt", "w", stdout); //输出答案
	//下方程序为你已经导入的程序
    /*
	int a, b;
	cin >> a >> b;
	cout << a + b;
	*/
	return 0;
}

data.cpp

1
2
3
4
5
6
7
8
9
#include <bits/stdc++.h>
using namespace std;
int main() {
	struct _timeb T;
	_ftime(&T);
	srand(T.millitm); //获得毫秒，减小运行时间
	int a = rand(); //此时a是一个随机数字
	printf("%d\n", a);
}

windows.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;

int main() {
	while (1) { //一直循环，直到找到不一样的数据
		system("data.exe");
		system("violent.exe");
		system("wa.exe");
		if (system("fc wa.txt violent.txt")) //当 fc 返回 1 时，说明这时数据不一样
			break;                          //不一样就跳出循环
	}
	return 0;
}

注意，以上所有程序均需要编译并运行

前缀和(Prefix Sum)

通过构建前缀和数组，从而能做到O(1)时间复杂度的区间查询(rangeQuery)

一维前缀和

构建前缀和数组

1
2
vector<int>pre(n+1,0);
for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];

rangeQuery

1
pre[r]-pre[l-1]//求(l,r)区间和

二维前缀和

构建前缀和数组

1
2
3
4
5
6
7
vector<vector<int>>pre(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
        //pre[i][j]表示(1,1)为左上角,(i,j)为右下角的矩阵的和
    }
}

rangeQuery

1
2
pre[x2][y2]-pre[x2][y1-1]-pre[x1-1][y2]+pre[x1-1][y1-1];
//求左上角为(x1,y1)，右下角为(x2,y2)的矩阵和

差分(Difference)

通过构建差分数组，从而能做到O(1)时间复杂度的区间修改(rangeModify)

一维差分

  1. 单点修改，单点询问

构建差分数组

1
2
vector<int>dif(n+5);
for(int i=1;i<=n;i++) dif[i]=a[i]-a[i-1];

rangeModify

1
dif[l]+=k;dif[r+1]-=k;//(l,r)区间每个数都加k

Query

1
for(int i=1;i<=n;i++) b[i]+=b[i-1];//此时b[i]就是修改完后的第i个数的值

  1. 单点修改，区间询问

    具体就是构建两个差分数组，每次单点修改的左端加1，右端也加1，全部操作执行完求前缀和,区间询问[l,r]的时候相减即可

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    vector<int>L(n+10),R(n+10);
    for(int i=0;i<k;i++){
        int u,v;cin>>u>>v;
        L[u]++;R[v]++;
    }
    for(int i=1;i<=n;i++) {
        L[i]+=L[i-1];
        R[i]+=R[i-1];
    }
    for(int i=1;i<=k;i++){
        int l,r;cin>>l>>r;
        cout<<R[r]-L[l-1]<<"\n";
    }

二维差分

与一维差分不同的是，二维差分数组的构建与修改均可以通过差分函数来完成

1
2
3
4
5
6
7
vector<vector<int>>dif(n+5,vector<int>(m+5));
auto modify=[&](int x1,int y1,int x2,int y2,int x){
    dif[x1][y1]+=x;
    dif[x1][y2+1]-=x;
    dif[x2+1][y1]-=x;
    dif[x2+1][y2+1]+=x;
};

构建差分数组

1
2
3
4
5
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        modify(i,j,i,j,a[i][j]);
    }
}

rangeModify

1
modify(x1,y1,x2,y2,x);//对左上角为(x1,y1),右下角为(x2,y2)的矩阵每个数都加上x

Query

前缀和求

1
2
3
4
5
6
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        dif[i][j]+=dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1];
        //pre[i][j]表示(1,1)为左上角,(i,j)为右下角的矩阵的和
    }
}

间隔差分

[l,r]中间隔k个数字修改，其中r=l + k * n, 相当于[l,l+k,l+2 * k,… l + n * k]这么多数修改

构建差分数组

1
pre[l]++;pre[r]--;//注意此时一定是最右侧的点进行减，不是最右边减一

求和

1
2
3
4
5
for(int i=1;i<=sum;i++)//sum为整个数组大范围,写成这样，即使多次修改区间也能在一次遍历的时间里算完

for(int i=k;i<=sum;i++){
​	pre[i]+=pre[i-k];
}

双指针

以后固定一下双指针的书写方式

1
2
3
4
5
6
7
8
9
10
11
for(int i=0;i<n;){
       int j=i;
       while(j+1<n&&s[j]==s[j+1]){
           //&&后面是指针移动条件
           j+=1;
       }
       ans=max(ans,j-i+1);
       //更新答案
       //cout<<i<<" "<<j+1<<"+\n";
       i=j+1;
   }

jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
for (int i = 0, j = -1; i <= n; i++) {
    //j是左指针，i是右指针
            if (i == n || a[i] != -1) {
                if (j == -1) {
                    
                } else if (i == n) {
                    
                } else {
                    int l = j, r = i;
                    while (l + 1 != r) {
                        if (a[l] > a[r]) {
                            a[l + 1] = a[l] == 1 ? 2 : a[l] / 2;
                            l++;
                        } else {
                            a[r - 1] = a[r] == 1 ? 2 : a[r] / 2;
                            r--;
                        }
                    }
                 
                }
                j = i;
            }

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
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
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
 
using i128 = __int128;
using u128 = unsigned __int128;

template<class T>
constexpr T power(T a, u64 b, T res = 1) {
    for (; b != 0; b /= 2, a *= a) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}
 
template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return u64(a) * b % P;
}
 
template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}
 
constexpr i64 safeMod(i64 x, i64 m) {
    x %= m;
    if (x < 0) {
        x += m;
    }
    return x;
}
 
constexpr std::pair<i64, i64> invGcd(i64 a, i64 b) {
    a = safeMod(a, b);
    if (a == 0) {
        return {b, 0};
    }
    
    i64 s = b, t = a;
    i64 m0 = 0, m1 = 1;
 
    while (t) {
        i64 u = s / t;
        s -= t * u;
        m0 -= m1 * u;
        
        std::swap(s, t);
        std::swap(m0, m1);
    }
    
    if (m0 < 0) {
        m0 += b / s;
    }
    
    return {s, m0};
}
 
template<std::unsigned_integral U, U P>
struct ModIntBase {
public:
    constexpr ModIntBase() : x(0) {}
    template<std::unsigned_integral T>
    constexpr ModIntBase(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr ModIntBase(T x_) {
        using S = std::make_signed_t<U>;
        S v = x_ % S(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static U mod() {
        return P;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, mod() - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<mod()>(x, rhs.val());
        return *this;
    }
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, ModIntBase &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const ModIntBase &lhs, const ModIntBase &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    U x;
};
 
template<u32 P>
using ModInt = ModIntBase<u32, P>;
template<u64 P>
using ModInt64 = ModIntBase<u64, P>;
 
struct Barrett {
public:
    Barrett(u32 m_) : m(m_), im((u64)(-1) / m_ + 1) {}
 
    constexpr u32 mod() const {
        return m;
    }
 
    constexpr u32 mul(u32 a, u32 b) const {
        u64 z = a;
        z *= b;
        
        u64 x = u64((u128(z) * im) >> 64);
        
        u32 v = u32(z - x * m);
        if (m <= v) {
            v += m;
        }
        return v;
    }
 
private:
    u32 m;
    u64 im;
};
 
template<u32 Id>
struct DynModInt {
public:
    constexpr DynModInt() : x(0) {}
    template<std::unsigned_integral T>
    constexpr DynModInt(T x_) : x(x_ % mod()) {}
    template<std::signed_integral T>
    constexpr DynModInt(T x_) {
        int v = x_ % int(mod());
        if (v < 0) {
            v += mod();
        }
        x = v;
    }
    
    constexpr static void setMod(u32 m) {
        bt = m;
    }
    
    static u32 mod() {
        return bt.mod();
    }
    
    constexpr u32 val() const {
        return x;
    }
    
    constexpr DynModInt operator-() const {
        DynModInt res;
        res.x = (x == 0 ? 0 : mod() - x);
        return res;
    }
    
    constexpr DynModInt inv() const {
        auto v = invGcd(x, mod());
        assert(v.first == 1);
        return v.second;
    }
    
    constexpr DynModInt &operator*=(const DynModInt &rhs) & {
        x = bt.mul(x, rhs.val());
        return *this;
    }
    constexpr DynModInt &operator+=(const DynModInt &rhs) & {
        x += rhs.val();
        if (x >= mod()) {
            x -= mod();
        }
        return *this;
    }
    constexpr DynModInt &operator-=(const DynModInt &rhs) & {
        x -= rhs.val();
        if (x >= mod()) {
            x += mod();
        }
        return *this;
    }
    constexpr DynModInt &operator/=(const DynModInt &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr DynModInt operator*(DynModInt lhs, const DynModInt &rhs) {
        lhs *= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator+(DynModInt lhs, const DynModInt &rhs) {
        lhs += rhs;
        return lhs;
    }
    friend constexpr DynModInt operator-(DynModInt lhs, const DynModInt &rhs) {
        lhs -= rhs;
        return lhs;
    }
    friend constexpr DynModInt operator/(DynModInt lhs, const DynModInt &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::istream &operator>>(std::istream &is, DynModInt &a) {
        i64 i;
        is >> i;
        a = i;
        return is;
    }
    friend constexpr std::ostream &operator<<(std::ostream &os, const DynModInt &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() == rhs.val();
    }
    friend constexpr std::strong_ordering operator<=>(const DynModInt &lhs, const DynModInt &rhs) {
        return lhs.val() <=> rhs.val();
    }
    
private:
    u32 x;
    static Barrett bt;
};
 
template<u32 Id>
Barrett DynModInt<Id>::bt = 998244353;
 
using Z = ModInt<998244353>;

高精度

版本一 太全，不实用

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
const int MAXN = 5005;//位数
struct bign{
    int len, s[MAXN];
    bign (){  
    //初始化
        memset(s, 0, sizeof(s));
        len = 1;
    }
    bign (int num) { *this = num; }
    bign (const char *num) { *this = num; }  //让this指针指向当前字符串
    bign operator = (const int num){
        char s[MAXN];
        sprintf(s, "%d", num);  //sprintf函数将整型映到字符串中
        *this = s;
        return *this;  //再将字符串转到下面字符串转化的函数中
    }
    bign operator = (const char *num){
        for(int i = 0; num[i] == '0'; num++) ;  //去前导0
        len = strlen(num);
        for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; //反着存
        return *this;
    }
    bign operator + (const bign &b) const{ 
    //对应位相加，最为简单
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; g || i < max(len, b.len); i++){
            int x = g;
            if(i < len) x += s[i];
            if(i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;  //关于加法进位
            g = x / 10;
        }
        return c;
    }
    bign operator += (const bign &b){
        //如上文所说，此类运算符皆如此重载
        *this = *this + b;
        return *this;
    }
    void clean(){  
    //由于接下来的运算不能确定结果的长度，先大而估之然后再查
        while(len > 1 && !s[len-1]) len--;  //首位部分‘0’故删除该部分长度
    }
    bign operator * (const bign &b){ 
    //乘法重载在于列竖式，再将竖式中的数转为抽象，即可看出运算法则。
        bign c;
        c.len = len + b.len;
        for(int i = 0; i < len; i++){
            for(int j = 0; j < b.len; j++){
                c.s[i+j] += s[i] * b.s[j];//不妨列个竖式看一看
            }
        }
        for(int i = 0; i < c.len; i++){ 
            //关于进位，与加法意同
            c.s[i+1] += c.s[i]/10;
            c.s[i] %= 10;
        }
        c.clean();  //我们估的位数是a+b的长度和，但可能比它小（1*1 = 1）
        return c;
    }
    bign operator *= (const bign &b){
        *this = *this * b;
        return *this;
    }
    bign operator - (const bign &b){  
    //对应位相减，加法的进位改为借1
        //不考虑负数
        bign c;
        c.len = 0;
        for(int i = 0, g = 0; i < len; i++){
            int x = s[i] - g;
            if(i < b.len) x -= b.s[i];  //可能长度不等
            if(x >= 0) g = 0;  //是否向上移位借1
            else{
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }
    bign operator -= (const bign &b){
        *this = *this - b;
        return *this;
    }
    bign operator / (const bign &b) {
    //运用除是减的本质，不停地减，直到小于被减数
        bign c, f = 0; //可能会在使用减法时出现高精度运算
        for(int i = len-1; i >= 0; i--){  
            //正常顺序，从最高位开始
            f = f*10;  //上面位的剩余到下一位*10
            f.s[0] = s[i];  //加上当前位
            while(f >= b){
                f -= b;
                c.s[i]++;
            }
        }
        c.len = len;  //估最长位
        c.clean();
        return c;
    }
    bign operator /= (const bign &b){
        *this  = *this / b;
        return *this;
    }
    bign operator % (const bign &b){  
    //取模就是除完剩下的
        bign r = *this / b;
        r = *this - r*b;
        r.clean();
        return r;
    }
    bign operator %= (const bign &b){
        *this = *this % b;
        return *this;
    }
    bool operator < (const bign &b){ 
    //字符串比较原理
        if(len != b.len) return len < b.len;
        for(int i = len-1; i != -1; i--){
            if(s[i] != b.s[i]) return s[i] < b.s[i];
        }
        return false;
    }
    bool operator > (const bign &b){  
    //同理
        if(len != b.len) return len > b.len;
        for(int i = len-1; i != -1; i--){
            if(s[i] != b.s[i]) return s[i] > b.s[i];
        }
        return false;
    }
    bool operator == (const bign &b){
        return !(*this > b) && !(*this < b);
    }
    bool operator != (const bign &b){
        return !(*this == b);
    }
    bool operator <= (const bign &b){
        return *this < b || *this == b;
    }
    bool operator >= (const bign &b){
        return *this > b || *this == b;
    }
    string str() const{  
    //将结果转化为字符串（用于输出）
        string res = "";
        for(int i = 0; i < len; i++) res = char(s[i]+'0')+res;
        return res;
    }
};
istream& operator >> (istream &in, bign &x){
//重载输入流
    string s;
    in >> s;
    x = s.c_str();  //string转化为char[]
    return in;
}
ostream& operator << (ostream &out, const bign &x){  
//重载输出流
    out << x.str();
    return out;
}

声明方式

1
2
3
bign a;//除了声明外其他如整型般使用
    a="333333333333333333333333333";
    cout<<a*a<<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
37
38
39
40
41
42
43
44
45
46
47
48
49
constexpr int N = 1000;
struct BigInt {
    int a[N];
    BigInt(int x = 0) : a{} {
        for (int i = 0; x; i++) {
            a[i] = x % 10;
            x /= 10;
        }
    }
    BigInt &operator*=(int x) {
        for (int i = 0; i < N; i++) {
            a[i] *= x;
        }
        for (int i = 0; i < N - 1; i++) {
            a[i + 1] += a[i] / 10;
            a[i] %= 10;
        }
        return *this;
    }
    BigInt &operator/=(int x) {
        for (int i = N - 1; i >= 0; i--) {
            if (i) {
                a[i - 1] += a[i] % x * 10;
            }
            a[i] /= x;
        }
        return *this;
    }
    BigInt &operator+=(const BigInt &x) {
        for (int i = 0; i < N; i++) {
            a[i] += x.a[i];
            if (a[i] >= 10) {
                a[i + 1] += 1;
                a[i] -= 10;
            }
        }
        return *this;
    }
};
std::ostream &operator<<(std::ostream &o, const BigInt &a) {
    int t = N - 1;
    while (a.a[t] == 0) {
        t--;
    }
    for (int i = t; i >= 0; i--) {
        o << a.a[i];
    }
    return o;
}

STL

int128库函数自定义

int128范围是$-2^{127}-2^{127-1}$

unsigned int128范围是$0-2^{128}$,约39位数

给int128 赋初值不能直接用一个很大的数字,比如1E100，这样赋出来是LONG_LONG_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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using i128 = __int128;
 
ostream &operator<<(ostream &os, i128 n) {
    if (n == 0) {
        return os << 0;
    }
    string s;
    while (n > 0) {
        s += char('0' + n % 10);
        n /= 10;
    }
    reverse(s.begin(), s.end());
    return os << s;
}
 
i128 toi128(const string &s) {
    i128 n = 0;
    for (auto c : s) {
        n = n * 10 + (c - '0');
    }
    return n;
}
 
i128 sqrti128(i128 n) {
    i128 lo = 0, hi = 1E16;
    while (lo < hi) {
        i128 x = (lo + hi + 1) / 2;
        if (x * x <= n) {
            lo = x;
        } else {
            hi = x - 1;
        }
    }
    return lo;
}

i128 gcd(i128 a, i128 b) {
    while (b) {
        a %= b;
        std::swap(a, b);
    }
    return 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
using i64 = long long;
using i128 = __int128;

/**   
	上取整下取整
**/
i64 ceilDiv(i64 n, i64 m) {
    if (n >= 0) {
        return (n + m - 1) / m;
    } else {
        return n / m;
    }
}
 
i64 floorDiv(i64 n, i64 m) {
    if (n >= 0) {
        return n / m;
    } else {
        return (n - m + 1) / m;
    }
}

/**   
	最大值赋值
**/
template<class T>
void chmax(T &a, T b) {
    if (a < b) {
        a = b;
    }
}

/**   
	最大公约数
**/
i128 gcd(i128 a, i128 b) {
    return b ? gcd(b, a % b) : a;
}

/**   
	精确开平方
**/
i64 sqrt(i64 n) {
    i64 s = std::sqrt(n);
    while (s * s > n) {
        s--;
    }
    while ((s + 1) * (s + 1) <= n) {
        s++;
    }
    return s;
}

/**   
	精确开平方
**/
i64 get(i64 n) {
    i64 u = std::sqrt(2.0L * n);
    while (u * (u + 1) / 2 < n) {
        u++;
    }
    while (u * (u - 1) / 2 + 1 > n) {
        u--;
    }
    return u;
}

/**   
	求 Log
**/
int logi(int a, int b) {
    int t = 0;
    i64 v = 1;
    while (v < b) {
        v *= a;
        t++;
    }
    return t;
}
 
int llog(int a, int b) {
    if (a <= b) {
        int l = logi(a, b);
        return (l == 0 ? 0 : std::__lg(2 * l - 1));
    }
    int l = logi(b, a + 1) - 1;
    assert(l > 0);
    return -std::__lg(l);
}

FloorSqrt(下取整开方)

常用于推出来的平方式子

例如image-20250313201111951

1
2
3
4
5
6
7
auto floorSqrt=[&](int n){
        int x = sqrt(n);
        if (1LL * x * x > n) {
            x--;
        }
        return x;
    };

bitset

位运算复杂度$O(\frac{n}{w})$,int定义时w=32

1
2
3
4
5
6
bitset<1000>bs //构造函数
bitset<1000>bs(val)//val>=0,构造出它的二进制形式
count() //返回bitset中值为1的位的数量
test(pos)// 返回 std::bitset 中位于 pos 位置的值
set(pos) //将 std::bitset 中位于 pos 位置的值设为 1
flip(pos)// 将 std::bitset 中位于 pos 位置的值取反

sqrt

对long long使用sqrt，类型转换为long double

1
x=(long double)sqrt(x);//x为long long类型

pdbs

头文件及命名空间，注意编译器开g++

1
2
3
#include <bits/extc++.h> //类似万能头，包含大多扩展库
using namespace __gnu_cxx;
using namespace __gnu_pbds;

平衡二叉树常见成员函数

1
2
3
4
5
6
7
8
empty() / size()
insert(x) // 插入元素x
erase(x) // 删除元素/迭代器x
order_of_key(x) // 返回元素x的排名
find_by_order(x) // 返回排名为x的元素迭代器
lower_bound(x) / upper_bound(x) // 返回迭代器
join(Tree) // 将Tree树的全部元素并入当前的树
split(x, Tree) // 将大于x的元素放入Tree树

代码

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
#include <bits/extc++.h>
using namespace __gnu_pbds;
bool Solve() {
    using PII = pair<int, int>;
    tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> ver;
    map<int, int> dic;
    int n; cin >> n;
    while (n--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) { // 插入一个元素x，允许重复
            ver.insert({x, ++dic[x]});
        } else if (op == 2) { // 删除元素x，若有重复，则任意删除一个
            ver.erase({x, dic[x]--});
        } else if (op == 3) { // 查询元素x的排名（排名定义为比当前数小的数的个数+1）
            cout << ver.order_of_key({x, 1}) + 1 << endl;
        } else if (op == 4) { // 查询排名为x的元素
            x--;
            cout << ver.find_by_order(x)->first << endl;
        } else if (op == 5) { // 查询元素x的前驱
            int idx = ver.order_of_key({x, 1}) - 1; // 无论x存不存在，idx都代表x的位置，需要-1
            cout << ver.find_by_order(idx)->first << endl;
        } else if (op == 6) { // 查询元素x的后继
            int idx = ver.order_of_key( {x, dic[x]}); // 如果x不存在，那么idx就是x的后继
            if (ver.find({x, 1}) != ver.end()) idx++; // 如果x存在，那么idx是x的位置，需要+1
            cout << ver.find_by_order(idx)->first << endl;
        }
    }
    return 0;
}

防卡unordered_map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

unordered_map<int, int, custom_hash> mp;

卡时

1
2
3
4
5
auto start=clock();//程序开头
auto time=clock();//中断点
clock在windows环境下单位为毫秒(*1000得秒)
在Linux环境下为微秒(*1000000得秒)
if(time-start>=900) break;//程序已经执行0.9s，中断退出

multiset/multimap删除

st.erase(x);//若是值，则会删除所有值为x的数

但是删st.erase(st.find(x));//只会删除一个

set遍历时不能执行删除操作，会RE

vector遍历过程中可以执行删除操作

string(size,char)赋值

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
40
41
42
1.find（str，pos）//找到的返回下标，找不到返回string：：npos
2.count//（起始位，终止位，目标物）
3.getline(cin,s)//整行读入，并将结果存储在字符串s里面
4.s.erase(pos,n)//把字符串s从pos开始的n个字符删除
5.mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//以实时时间作为种子产生一个64位数的随机数，调用的时候写rng(),可能为正也可能为负
6.__builtin_popcount( )//返回括号内数字二进制表达中1的个数
7.//二维map（以int为例）
map<int,map<int,int>>mp;
8.for (auto t : {"DFS", "dfs"}//t[0]有两个，是D和d。都等效为t[0]
9.substr(起始位置，长度)//用来截取string类型的字符串 
10 s.replace(p0,n0,n,ch)//删除p0开始的n0个字符，然后在p0处插入n个字符ch
11.//在平面内，从(0,0)到点(x,y)的路径数f[x][y]=f[x-1][y]+f[x][y-1]
12.//ceil函数向上取整（对浮点）
13.// 0x7fffffff表示int类型的最大值(7个f)
14.//在数字前面补零 printf(“%050d”,n)-----格式化输出50位的n，不够的在前面补零。
15.//double型不能用位运算
16.// 用cout输出的时候Setprecision(p)表示保留有效数字p位
//再加fixed前面修饰可以改为保留小数点后p位
17.//setw用来设置字段宽度
18.//加0边ascll，减0变int，减‘a’求第几个位置，%26防止爆位
19.//类似对1e9+7取模要从一开始计算的时候就取，不能只对答案取模
20.//gcd(a,b)和lcm(a,b)在a,b最小的情况下就是a=gcd（a,b）与b=lcm（a,b）;
21.//用k加 （1e9+7）再模1e9+7防止因k小于0造成的错误
22.//异或实际上就是二进制的不进位加法，异或同一个数两次相当于没有异或这个数
23.//iota配合sort实现单数组的多数组对应下标绑定排序
24..iota（起始位，末位，初始值）//用来批量递增赋值数组，增量为1 
25.//用STL包括位运算可能爆int的时候记得写成0LL,1LL
26.//二分查找.lower_bound和upper找不到会返回数组最后一个元素下标+1       
27.//清空标记形不要用vector,用C-array老实的memset
28.//iota配合sort执行结构化排序 举例
//iota(p.begin(),p.end(),0);
//sort(p.begin(),p.end(),[&](int i,int j){
//  return a[i]<a[j];
//});
//该代码执行后是p中元素按照a的元素大小进行排序,a[p[0]]就是a中第0小的元素值
//p[0]就是这个第一小的元素在原数组中的坐标
29 //转移的时候,记得初始化所有的最左端点的前一个数(-1/0)
//所有的右端点初始化为右端点的后一个数(n/n+1)
30 //vector二分插入，保证数组有序
//a.insert(upper_bound(a.begin(),a.end(),x),x);
//insert是在迭代器前一个位置插入元素

进制转换

10进制转其他进制（n是数字，k是进制）

大于10的数字用字符表示

1
2
3
4
5
6
7
8
9
10
11
void solve(){
     int n;cin>>n;
     int k;cin>>k;
     string ans;
     while(n){
        ans.push_back(n%k<10 ? n%k+'0' : n%k-10+'A');
        n/=k;
     }        
     reverse(ans.begin(),ans.end());
     cout<<ans<<'\n';
}

其他进制转十进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unordered_map<char,int>it;
int r,ans;
void init(){
    int s=10;
    for (char i='A';i<='Z';i++) {
        it[i]=s++;
    }
}
int main(){
    string n;cin>>r>>n;
    init();
    for(int i=0;i<n.size();i++){
        ans*=r;
        if(isalpha(n[i])) ans+=it[n[i]];
        else ans+=n[i]-'0';
    }
    cout<<ans<<endl;

字符串进制转化

1
2
stoi(s) //s需要是字符串，只能将string类型字符串转化为10进制，且不超过int范围
auto s=to_string(x)//将x转化为字符串形式

二分

左端点减1，右端点加1

实数域二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto check = [&](double t) {
    // write
};
double lo = 0;
double hi = 1E12;
while (hi - lo > max(1.0, lo) * eps) {
    double x = (lo + hi) / 2;
    if (check(x)) {
        hi = x;
    } else {
        lo = x;
    }
}
cout << lo << "\n";

基姆拉尔森计算公式

计算自1970年的某年某月某日是星期几

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int d[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeap(int y) {
    return y % 400 == 0 || (y % 4 == 0 && y % 100 != 0);
}

int daysInMonth(int y, int m) {
    return d[m - 1] + (isLeap(y) && m == 2);
}

int getDay(int y, int m, int d) {
    int ans = 0;
    for (int i = 1970; i < y; i++) {
        ans += 365 + isLeap(i);
    }
    for (int i = 1; i < m; i++) {
        ans += daysInMonth(y, i);
    }
    ans += d;
    return (ans + 2) % 7 + 1;
}

三分模板

整数三分

每次都将区间变为[l,mid1],(mid1,mid2],(mid2,r]三个区间
根据条件判断将l,r指针移动至哪个区间，复杂度为log以3为底(区间大小)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void solve(){
    int l=2,r=999;
    while (l<r){
        int mid1 = l + (r - l) / 3;
        int mid2 = r - (r - l) / 3;
        int s=query(mid1,mid2);
        if (s == mid1 * mid2){
            l = mid2 + 1;
        }else if (s == mid1 * mid2 + mid1){
            l = mid1 + 1;
            r = mid2;
        }else{
            r = mid1;
        }
    }
    cout << "! " << l << endl;
}

实数三分

1
2
3
4
5
6
7
8
9
10
11
12
13
const double eps = 1e-9;//根据条件判断
while(r - l < eps) {
    double lmid = l + (r - l) / 3;
    double rmid = r - (r - l) / 3;
    lans = cal(lmid),rans = cal(rmid);
    // 求凹函数的极小值
    if(lans <= rans) r = rmid;
    else l = lmid;
    // 求凸函数的极大值
    if(lans >= rans) l = lmid;
    else r = rmid;
}
cout << l << endl;

Trick

比赛相关

  1. 认真读题至少2遍，必要时和队友确认题意
  2. 想思路前务必带入样例验证思路，否则请重复步骤1
  3. 初始化不要多次声明vector(特别是二分这种多次用到初始化的)，用遍历的方式去赋初始值
  4. 遇到m*(n+1)/2，不要先定义k=(n+1)/2,m可能是偶数
  5. 取模相关，建议所有都取模，最后(答案+mod)%mod
  6. 二分左端点开到0,右端点是最大答案可能数+1
  7. 注意数据随机生成的字样

切入点/典中典

  1. 子序列选择问题，暴力做法是枚举所有可能的子序列，当然这一定做不到，复杂度是$2^n$级别的

​ sol1 一般这类问题都可以通过dp解决，找到能够”拼接”起来的转移方程

​ sol2 通过组合数解决，注意应该直接计算保留的子序列方案数 not 删除的种类数

  1. q个询问此类问题一般都是复杂度O(1)[提前预处理]，O(logn)[预处理后在线询问]，有位运算的可以通过最高位的限制控制在位数之内

  2. 区间[l,r]询问,转换成前缀和处理,即pre[r]-pre[l-1]

  3. red求能组成多少个不同的red，只需要求每个’e’前面多少个r和后面多少个d，两者相乘即可

  4. 将问题抽象成数学问题

  5. 01串常见做法是将0->-1，这样能迅速求出区间和

  6. 思考想hint，正难则反

  7. 每个位置可以选0/1，dp

  8. 中位数想-1+1前缀和,转化为01串

  9. 长度为n的区间子数组{连续}一共n*(n+1)/2个{长度为1的n个，为2的n-1个…}

  10. image-20250131130929293

  11. 有这么一个事实，素数是密集的，说人话就是素数两两之间挨的非常近， ≤n 的素数两两距离大约是 log(n),所以可以

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for (i64 d = r - l; d >= 0; d--) {//枚举距离
            for (i64 a = l; a + d <= r; a++) {//左端点
                i64 b = a + d;
                if (std::gcd(a, b) == 1) {
                    std::cout << a * g << " " << b * g << "\n";
                    return;
                }
            }
        }

  12. 如果可以，先确定做法的复杂度，再去想切入点和怎么做

  13. 构造题可以先考虑几个极端情况，再试着拼接这些极端情况从而锁定构造方式和规律

  14. 构造非质数的数，常用trick是构造成非2的偶数（两数同奇偶，差值abs为偶数），也常构造为1

  15. 试试暴力

  16. 有次数限制的可以开while循环限制次数打暴力

  17. 二维n×m矩阵映射到一维，(x,y)->(x*m+y)×一个数

  18. 对于长度为 n 的01字符串 s，发现当 s1 与 sn 相等时 “01” 与 “10” 子串（必须连续）数量相等，无论中间填的什么

  19. 按位XOR/OR/AND操作考虑每位的贡献

  20. 最大化两两配对四种非法位，自身不能和自身配对

    配对过程就是很典的思路：当最大值大于剩下的所有数，非配对数为最大值-其他所有数之和；否则非配对数为所有数字之和为偶数?0:1

  21. 构造方法：增量构造

  22. 选[l,r]区间可以转化成某个前缀+后缀，二分

  23. 条件合并区间用栈

  24. 构造题大多都很贪心，都能构造出来

  25. 给定数很大就想二进制

  26. 从后向前推，很chang

  27. 大模拟就用STL

  28. 对一个数执行+a,+b,-a,-b操作，等价于执行+-gcd(a,b)

  29. 每次删去一个最大/最小值，等价于每次将答案锁定在dp[l,r]中间，可以O(n^2)解决，更新方式为dp[l,r]=dp[l-1,r],dp[l,r+1]…

  30. dp转移写+1，而不是-1

数论

  1. 将数x分开，每块最多t，分开的操作为拆成两个和为x的正整数，求次数
1
ans += (a[i] - 1) / t;
  1. 中位数就想二分
  2. 二进制乘以2，相当于整个数左移一位，末位补0，乘$2^{k}$就是左移k位
  3. 6x+8y+10z,取数不限可以遍历>=6的所有偶数
  4. 对于一个数组中的gcd，从左到右gcd如果递减，每次起码缩小一半(原因就是gcd一旦变化，一定会变成原有gcd的因数)，所以gcd的变化是log级别的
  5. 递推数列具有模周期性，对于斐波那契数列，这个周期不会超过 60× 模数。
  6. 皮亚诺定理:模数为k的循环节长度不会超过6k
  7. 当题面给定数字范围可能超过long long的时候，首先应该想到按位贪心等算法，而不是高精度或i128
  8. $\sum_{i=1}^{t}i*()$类似的式子很常见的做法是指标变换，例如 $\sum_{i=1}^{t}(i-1)*s_{i}=\sum_{i=2}^{t}\sum_{j=2}^{i}s_i=\sum_{j=2}^{t}\sum_{i=j}^{t}s_i=\sum_{j=2}^{t}suf_j$，这样就变成后缀和问题（Problem - C - Codeforces，2023山东CCPC F题）
  9. 将数列分为若干组（k组），组与组连续。$\sum_{i=1}^{k}i*s_i==\sum_{i=1}^{k}suf_i$,如果是自己定在哪里切割数列，就直接选取不同位置加其后缀和（如果是i-x则需要先空出x个数，这样才能保证值为正）
  10. 取模状态下的除法要变成乘以它的乘法逆元
  11. 稍微基础一点的,[0,n-1]的数组中位数是a[n/2],[]
  12. 找gcd(x,y)==g,实际等效于$x==a1g$&&$y==b1g$&&gcd(a1,b1)==1(a1,b1互质)

操作问题

  1. 数组中异或最终变成某个确定数的问题，可以使用前/后缀异或和的方法dp转移

  2. 循环移位 - 加长数组至2倍,然后直接找循环节出现的起始和结束位置

  3. $操作a_{i}-=1;a_{i+1}+=1$，无操作限制求极差，将使得序列变成不递减序列，二分求极大极小做差

  4. 操作$a_i+=x$,次数不限，最终要求到某个数/求mex…,可以用dp,dp[a[i]+x]+=(dp[$a[i]$]-1)，或者对x取模,用map存储,

  5. 数组递增1的维护，二分查找最后一个数即可

    1
    我们发现：每次只会将有序数组中的某个值的数+ 1 ,而在一个有序数组中，将某个值的数+1其实并不会改变整个序列的有序性，例如[1,1,2,2,3,3]我们需要将一个值为2的数+1,修改后会变为[1,1,2,3(2+1),3,3]，我们只需要将最后的那个2 进行+1操作即可（二分查找）。

    1. 每次将[1,n]的线段切分为两段，左右mid之和是n+1

    2. 只有两行的东西，遍历到第i列就代表之前的都操作完了

    3. 多次分组问题，调和级数

      1
      2
      3
      4
      5
      6
      7
      for (int k = 1; k <= m; k++) {//所有组数
              i64 ans = 0;
              for (int i = k - 1; i < m; i += k) {//遍历每组所需要的值
                  ans += b[i] + 1;
              }
              std::cout << ans << " \n"[k == m];
          }

    4. 给定大小关系给排序：可以直接用比较器

      1
      2
      3
      4
      5
      6
      7
      8
      vector<int> p(n);
          iota(p.begin(), p.end(), 0);
          sort(p.begin(), p.end(),
          [&](int x, int y) {
              if(g[x][y] == '1') return x < y;
              else return x > y;
          });
          for(auto i : p) cout << i + 1 << " "; cout << '\n';

  6. 任意次数+1，-1使得数组变为一个数，操作次数最小，找中位数(排序后的mid/mid+1/mid-1)

  7. map<int,int> sl;//差分求区间最大值，或者说单点最大值
    for (int i = 0; i < n ; i ++){
        int l,r;
        cin >> l >> r;
        a[i] = {l,r};
        sl[l] ++, sl[r + 1] --;
    }
    int ans= 0,res = 0;
    for (auto [u,v] : sl){
        res += v;
        ans = max(ans, res);
    }

图论

  1. 有其他增项的最短路
  2. 有无某种特性可以点数*2为无，点数 *2+1为有
  3. 联通性/图论的题经常会枚举边

交互题

  1. 从特殊点切入，找其他点和特殊点的关系，再从特殊点向外推

DP

  1. 着重注意dp的状态之间的影响关系！

Hint

  1. 两图n<=1000，可以双图BFS

DEBUG

  1. 当程序连输入的数据都输出不来，就是程序中某段卡死了

好题

[1600思维]Ordered Permutations

构造

  1. 二进制构造(题目限制构造长度/与二进制有关/给定数很大时)

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)时，后手无论选择什么我们都和其选择一样即可获胜，因为二进制下需要偶数次选择偶数才能将这个数归零