Chonu

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

版本二

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

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
unordered_map<int,int>mp;
mp.reserve(1024);
mp.max_load_factor(0.25);

卡时

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

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

基姆拉尔森计算公式

计算自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可能是偶数

切入点/典中典

  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，两者相乘即可

数论

  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

操作问题

  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存储,

图论

  1. 有其他增项的最短路
  2. 有无某种特性可以点数*2为无，点数 *2+1为有

DEBUG

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

Posted on In , Valine:

G Shift and Reverse

Topic

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

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

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

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

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

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

Analyse

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

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

Posted on Edited on In , , Valine:

Manacher

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> manacher(string s) {
    string t = "#";
    for (auto c : s) {
        t += c;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n);
    for (int i = 0, j = 0; i < n; i++) {
        if (2 * j - i >= 0 && j + r[j] > i) {
            r[i] = min(r[2 * j - i], j + r[j] - i);
        }
        while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {
            r[i] += 1;
        }
        if (i + r[i] > j + r[j]) {
            j = i;
        }
    }
    return r;
}

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

KMP

Z函数(扩展kmp/exkmp)

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

Posted on Edited on In , , Valine:

数论

快速幂(Power)

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

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

快速幂求质数的乘法逆元

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

龟速乘

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

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

exgcd

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

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

Pollard-Rho & Miller Rabin

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
namespace factor {
    using f64 = long double;
    ll p;
    f64 invp;
    void setmod(ll x) {
        p = x, invp = (f64) 1 / x;
    }
    ll mul(ll a, ll b) {
        ll z = a * invp * b + 0.5;
        ll res = a * b - z * p;
        return res + (res >> 63 & p);
    }
    ll pow(ll a, ll x, ll res = 1) {
        for(;x;x >>= 1, a = mul(a, a))
            if(x & 1) res = mul(res, a);
        return res;
    }
    inline ll rho(ll n) {
        if(!(n & 1)) return 2;
        static std::mt19937_64 gen((size_t)"hehezhou");
        ll x = 0, y = 0, prod = 1;
        auto f = [&](ll o) { return mul(o, o) + 1; };
        setmod(n);
        for(int t = 30, z = 0;t % 64 || std::gcd(prod, n) == 1;++t) {
            if (x == y) x = ++ z, y = f(x);
            if(ll q = mul(prod, x + n - y)) prod = q;
            x = f(x), y = f(f(y));
        }
        return std::gcd(prod, n);
    }
    bool checkprime(ll p) {
        if(p == 1) return 0;
        setmod(p);
        ll d = __builtin_ctzll(p - 1), s = (p - 1) >> d;
        for(ll a : {2, 3, 5, 7, 11, 13, 82, 373}) {
            if(a % p == 0)
                continue;
            ll x = pow(a, s), y;
            for(int i = 0;i < d;++i, x = y) {
                y = mul(x, x);
                if(y == 1 && x != 1 && x != p - 1)
                    return 0;
            }
            if(x != 1) return 0;
        }
        return 1;
    }
    std::vector<ll> factor(ll x) {
        std::queue<ll> q; q.push(x);
        std::vector<ll> res;
        for(;q.size();) {
            ll x = q.front(); q.pop();
            if(x == 1) continue;
            if(checkprime(x)) {
                res.push_back(x);
                continue;
            }
            ll y = rho(x);
            q.push(y), q.push(x / y);
        }
        sort(res.begin(), res.end());
        return res;
    }
}
void solve(){
    ll n; cin >> n;
    if(factor::checkprime(n)) {
        cout << "Prime" << '\n';
        return;
    }else {
        auto res = factor::factor(n);
        //返回n的质因子，有重复，即res中元素乘积就是n
        cout << res.back() << '\n';
    }   
}

线性筛/欧拉筛(Sieve)

时间复杂度O(n)

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

期望

期望的线性性质：

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

举例：

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

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

线性基(Basis)

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

Posted on Edited on In , , Valine:

XCPC 数据结构

双哈希封装

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
struct Shash{  
    const ll base[2]={29,31};
    //base存储基数
    const ll hashmod[2]={(ll)1e9+9,998244353};
    //hashmod存储模数
    array<vector<ll>,2>hsh;
    array<vector<ll>,2>pwMod;
    //hsh[2] 和 pwMod[2]：这两个二维 vector 分别用于存储哈希值和幂模值。
    //其中，hsh[i][j] 表示字符串前 j 个字符在基数 base[i] 和模数 hashmod[i] 下的哈希值；
    //pwMod[i][j] 表示基数 base[i] 的 j 次幂对 hashmod[i] 取模的结果。
    void init(string S){
        int n=S.size();S=' '+S;
        hsh[0].resize(n+1),hsh[1].resize(n+1);
        pwMod[0].resize(n+1),pwMod[1].resize(n+1);
        for(int i=0;i<2;++i){
            pwMod[i][0]=1;
            for (int j=1;j<=n;++j){
                pwMod[i][j]=pwMod[i][j-1]*base[i]%hashmod[i];
                hsh[i][j]=(hsh[i][j-1]*base[i]+S[j])%hashmod[i];
            }
        }
    }
    //get函数输出[l,r]这段字符的哈希值,first是第一个模数下哈希值,second是第二个
    pair<ll,ll>get(int l,int r){
        pair<ll,ll> ans;
        ans.first=(hsh[0][r]-hsh[0][l-1]*pwMod[0][r-l+1])%hashmod[0];
        ans.second=(hsh[1][r]-hsh[1][l-1]*pwMod[1][r-l+1])%hashmod[1];
        ans.first=(ans.first+hashmod[0])%hashmod[0];
        ans.second=(ans.second+hashmod[1])%hashmod[1];
        return ans;
    }
};
bool same(Shash &a,int la,int ra,Shash &b,int lb,int rb){
    return a.get(la,ra)==b.get(lb,rb);
}

声明方式

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

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

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

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
struct DSU {
    vector<int> f,siz;
    DSU() {}
    DSU(int n) {
        init(n);
    }
    void init(int n) {
        f.resize(n);
        iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) {
        return siz[find(x)];
    }
};

声明方式

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

可撤销并查集(DSU With Rollback)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**   
	可撤销并查集（DSU With Rollback）
**/
struct DSU {
    std::vector<int> siz;
    std::vector<int> f;
    std::vector<std::array<int, 2>> his;
    
    DSU(int n) : siz(n + 1, 1), f(n + 1) {
        std::iota(f.begin(), f.end(), 0);
    }
    
    int find(int x) {
        while (f[x] != x) {
            x = f[x];
        }
        return x;
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) {
            std::swap(x, y);
        }
        his.push_back({x, y});
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int time() {
        return his.size();
    }
    
    void revert(int tm) {
        while (his.size() > tm) {
            auto [x, y] = his.back();
            his.pop_back();
            f[y] = y;
            siz[x] -= siz[y];
        }
    }
};

线段树

通用版

区间开方(板子: HDU 4027)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
template <class T> 
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)    
    struct node {
        int l, r;
        T sum; // 注意初始赋值
        T mx=0;
    };
    vector<T> w;
    vector<node> t;
    LSGT(int n) {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }
    LSGT(vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void pushdown(node &p) { // 在此更新下递函数
        return;
    }
    void pushup(node &p, node &l, node &r) { // 在此更新上传函数
        p.sum = l.sum + r.sum;
        p.mx=max(l.mx,r.mx);
    }
    void pushdown(int p) { // 不需要动
        pushdown(t[l(p)]);
        pushdown(t[r(p)]);
    }
    void pushup(int p) { // 不需要动
        pushup(t[p], t[l(p)], t[r(p)]);
    }
    void build(int l, int r, int p = 1) {
        if (l == r) {
            t[p] = {l, r, w[l],w[l]};
            return;
        }
        t[p] = {l, r};
        int mid = (l + r) >> 1;
        build(l, mid,l(p));
        build(mid + 1, r, r(p));
        pushup(p);
    }
    void modify(int l, int r, int p = 1) { // 区间修改
        if(t[p].mx<=1) return;
        if(t[p].l==t[p].r){
            t[p].sum=(int)sqrt(t[p].sum);
            t[p].mx=t[p].sum;
            return;
        }else{
            int mid = (t[p].l + t[p].r) >>1 ;
            if (l <= mid) modify(l, r,l(p));
            if (mid < r) modify(l, r, r(p));
        }
        pushup(p);
    }
    T asp(int l, int r, int p = 1) { // 区间询问，不合并
        if (l <= t[p].l && t[p].r <= r) {
            return t[p].sum;
        }
        //pushdown(p);
        int mid = (t[p].l + t[p].r) / 2;
        T ans = 0;
        if (l <= mid) ans += asp(l, r,l(p));
        if (mid < r) ans += asp(l, r, r(p));
        return ans;
    }
    void debug(int p = 1) {
        cout << "[" << t[ p].l << ", " << t[p].r << "]: ";
        cout << "sum = " << t[p].sum << ", ";
        cout << endl;
        if (t[p].l == t[p].r) return;
        debug(l(p)), debug(r(p));
    }
#undef l(p)
#undef r(p)
};

线段树 ( SegmentTree+Info )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
struct Info{
    int lc, rc, ls, rs, len, ans;
};
Info operator+(Info a, Info b) {
    Info c = {0, 0, 0, 0, 0};
    c.ans = max(a.ans, b.ans);
    if (a.rc == 0 && b.lc == 0) c.ans = max(c.ans, a.rs + b.ls);
    c.lc = a.lc, c.rc = b.rc;
    c.ls = a.ls;
    if (a.ls == a.len && a.rc == b.lc) c.ls += b.ls;
    c.rs = b.rs;
    if (b.rs == b.len && a.rc == b.lc) c.rs += a.rs;
    c.len = a.len + b.len;
    return c;
}
struct segtree{
    struct Node {
        int l, r;
        Info info;
    } tr[N << 2];
 
    void pull(int u) {
        tr[u].info = tr[u << 1].info + tr[u << 1 | 1].info;
    }
 
    void build(int u, int l, int r) {
        tr[u] = {l, r};
        if (l == r) {
            tr[u].info = {0, 0, 1, 1, 1, 1};
            return;
        }
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pull(u);
    }
 
    void modify(int u, int x) {
        if (tr[u].l == tr[u].r) {
            tr[u].info.lc ^= 1;
            tr[u].info.rc ^= 1;
            tr[u].info.ans ^= 1;
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x);
        if (x > mid) modify(u << 1 | 1, x);
        pull(u);
    }
 
    Info query(int u, int l, int r) {
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].info;
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        if (l > mid) return query(u << 1 | 1, l, r);
        return query(u << 1, l, r) + query(u << 1 | 1, l, r);
    }
}t;
void solve() {
    int n,m;cin>>n>>m;
    t.build(1,1,n);
    while(m--){
        int op;cin>>op;
        if(op==1){
            int x;cin>>x;
            t.modify(1,x);
        }else{
            int l,r;cin>>l>>r;
            cout<<t.query(1,l,r).ans<<endl;
        }
    }
}

LazySegmentTree 基础区间修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
template<class Info, class Tag>
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LSGT() {}
    LSGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LSGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
#undef l(p)
#undef r(p)
};

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

单调栈解决NGE问题

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

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

单调队列(滑动窗口)

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

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

Trie树

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

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

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

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

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
template<typename T>
struct Fenwick{
    int n;
    vector<T> tr;
    Fenwick(int n) : n(n), tr(n + 1, 0){}
    int lowbit(int x){
        return x & -x;
    }
    void modify(int x, T c){
        for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
    }
    void modify(int l, int r, T c){
        modify(l, c);
        if (r + 1 <= n) modify(r + 1, -c);
    }
    T query(int x){
        T res = T();
        for(int i = x; i; i -= lowbit(i)) res += tr[i];
        return res;
    }
    T query(int l, int r){
        return query(r) - query(l - 1);
    }
    int find_first(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] < sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans + 1;
    }
    int find_last(T sum){
        int ans = 0; T val = 0;
        for(int i = __lg(n); i >= 0; i--){
            if ((ans | (1 << i)) <= n && val + tr[ans | (1 << i)] <= sum){
                ans |= 1 << i;
                val += tr[ans];
            }
        }
        return ans;
    }
};
using BIT = Fenwick<int>;

声明方式

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

树状数组求逆序对

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

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

树状数组jiangly

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct Fenwick {
    int n; vector<T>a;
    Fenwick(int n_ = 0) {
        init(n_);
    }
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

ST表

解决RMQ问题，预处理复杂度为O(nlogn),O(1)查询,常数比线段树小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct ST {
    int n;
    vector<int>lg;
    vector<vector<int>> mx, mn;
    ST(vector<int>init){
        n=init.size()-1;
        lg.resize(n);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        mx.resize(n + 1, vector<int>(lg[n] + 1));
        mn.resize(n + 1, vector<int>(lg[n] + 1));
        for (int i = 1; i <= n; i++) {
            mx[i][0] = init[i];
            mn[i][0] = init[i];
        }
        int k = lg[n];
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
                mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int getmax(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = lg[r - l + 1];
        return max(mx[l][k], mx[r - (1 << k) + 1][k]);
    }
    int getmin(int l, int r) {
        if (l > r) {
            swap(l, r);
        }
        int k = lg[r - l + 1];
        return min(mn[l][k], mn[r - (1 << k) + 1][k]);
    }
};

解决区间gcd问题

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct ST {
    int n;
    vector<int>lg;
    vector<vector<int>> g;
    ST(vector<int>init){
        n=init.size()-1;
        lg.resize(n);
        for (int i = 2; i <= n; i++) {
            lg[i] = lg[i / 2] + 1;
        }
        g.resize(n + 1, vector<int>(lg[n] + 1));
        for (int i = 1; i <= n; i++) {
            g[i][0] = init[i];
        }
        int k = lg[n];
        for (int j = 1; j <= k; j++) {
            for (int i = 1; i + (1 << j) - 1 <= n; i++) {
                g[i][j] = gcd(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int query(int l, int r) {
        int k=lg[r - l + 1];
        return gcd(g[l][k], g[r - (1 << k) + 1][k]);
    }
};

自动取模与排列组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
const int maxn = 3e5 + 5, mod = 1e9 + 7;
template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}

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

mint fact[maxn], invfact[maxn];

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

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

莫队

基础莫队

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
vector<array<int,3>>query(q+1);
    int siz=(int)(ceil(pow(n,0.5)));
    vector<int>k(n+1);
    for(int i=1;i<=n;i++){
        k[i]=(i-1)/siz+1;
    }
    for(int i=1;i<=q;i++){
        int l,r;cin>>l>>r;
        query[i]={l,r,i};
    }
    sort(query.begin()+1,query.end(),[&](auto x,auto y){
        if(k[x[0]]!=k[y[0]]) return k[x[0]]<k[y[0]];
        if(k[x[0]]&1) return x[1]<y[1];
        return x[1]>y[1];
    });
    int l=1,r=0,val=0;
	vector<int>ans(q+1);
    auto add=[&](int x){
    };
    auto del=[&](int x){
    };
    for(int i=1;i<=q;i++){
        auto [ql,qr,id]:query[i];
        while(l>ql) add(a[--l]);
        while(r<qr) add(a[++r]);
        while(l<ql) del(a[l++]);
        while(r>qr) del(a[r--]);
        ans[id]=val;
    }

树链剖分

HLD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
struct HLD {
    int n;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    int cur;
    HLD() {}
    HLD(int n) {
        init(n);
    }
    void init(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 0;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root ) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        /*
           标记每个点的深度dep[]
           标记每个点的父亲parent[]
           标记每个非叶子节点的子树大小(含它自己)
        */
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) {
                u = parent[top[u]];
            } else {
                v = parent[top[v]];
            }
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) {
        //返回两点的距离
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int jump(int u, int k) {
        //向上跳k步，返回跳跃后的节点
        if (dep[u] < k) {
            return -1;
        }
        int d = dep[u] - k;
        while (dep[top[u]] > d) {
            u = parent[top[u]];
        }
        return seq[in[u] - dep[u] + d];
    }
    bool isAncester(int u, int v) {
        //判断u是否是v的祖先
        return in[u] <= in[v] && in[v] < out[u];
    }
    int rootedParent(int u, int v) {
        /*
            在以u为根的子树中，找到v的直接父节点
         */
        swap(u, v);
        if (u == v) {
            return u;
        }
        if (!isAncester(u, v)) {
            return parent[u];
        }
        auto it = upper_bound(adj[u].begin(), adj[u].end(), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    int rootedSize(int u, int v) {
        /*
         * 在以u为根的子树中，计算以v为根的子树的大小
         */
        if (u == v) {
            return n;
        }
        if (!isAncester(v, u)) {
            return siz[v];
        }
        return n - siz[rootedParent(u, v)];
    }
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

点权与线段树操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
struct HLD {
    int n,cur;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    HLD(int n) {
        this->n = n;
        siz.resize(n);
        top.resize(n);
        dep.resize(n);
        parent.resize(n);
        in.resize(n);
        out.resize(n);
        seq.resize(n);
        cur = 1;
        adj.assign(n, {});
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void work(int root ) {
        top[root] = root;
        dep[root] = 0;
        parent[root] = -1;
        dfs1(root);
        dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1) {
            adj[u].erase(find(adj[u].begin(), adj[u].end(), parent[u]));
        }
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) {
                swap(v, adj[u][0]);
            }
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur;
    }
};
template<class Info, class Tag>
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
    int n;
    vector<Info> info;
    vector<Tag> tag;
    template<class T>
    LSGT(vector<T> init1) {
        init(init1);
    }
    template<class T>
    void init(vector<T> init1) {
        n = init1.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init1[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag& v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
#undef l(p)
#undef r(p)
};
struct Tag {
    int add;
    Tag(int add1=0):add(add1){}
    void apply(Tag t) {
        add+=(t.add);
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        sum += 1LL * t.add * len;
    }
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = (a.sum + b.sum);
    return c;
}
void solve() {
    int n,m,r,p;cin>>n>>m>>r>>p;
    //r为根,p为取模数
    vector<int>a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<vector<int>>g(n+1);
    HLD t(n+1);
    for(int i=0;i<n-1;i++){
        int x,y;cin>>x>>y;
        t.addEdge(x,y);
    }
    t.work(r);
    vector<Info>k(n+1);
    for(int i=1;i<=n;i++){
        k[t.in[i]].sum=a[i];
    }
    LSGT<Info,Tag>sgt(k);
    auto range=[&](int x,int y,int z){
        while(t.top[x]!=t.top[y]){
            if(t.dep[t.top[x]]<t.dep[t.top[y]]) swap(x,y);
            sgt.Apply(t.in[t.top[x]],t.in[x]+1,z);
            x=t.parent[t.top[x]];
        }
        if(t.dep[x]>t.dep[y]) swap(x,y);
        sgt.Apply(t.in[x],t.in[y]+1,z);
    };
    auto query=[&](int x,int y){
        int ans=0;
        while(t.top[x]!=t.top[y]){
            if(t.dep[t.top[x]]<t.dep[t.top[y]]) swap(x,y);
            ans=(ans+sgt.query(t.in[t.top[x]],t.in[x]+1).sum)%p;
            x=t.parent[t.top[x]];
        }
        if(t.dep[x]>t.dep[y]) swap(x,y);
        ans=(ans+sgt.query(t.in[x],t.in[y]+1).sum)%p;
        return ans;
    };
    while(m--){
        int op;cin>>op;
        if(op==1){
            int x,y,z;cin>>x>>y>>z;
            range(x,y,z);//区间加
        }else if(op==2){
            int x,y;cin>>x>>y;
            cout<<query(x,y)<<"\n";//区间和
        }else if(op==3){
            int x,z;cin>>x>>z;
            sgt.Apply(t.in[x],t.in[x]+t.siz[x],z);//子树加
        }else{
            int x;cin>>x;
            cout<<(sgt.query(t.in[x],t.in[x]+t.siz[x]).sum)%p<<"\n";//子树和
        }
    }
}

再版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
template <class T> 
struct LSGT {
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)    
    struct node {
        int l, r;
        T sum; // 注意初始赋值
        T add=0;
    };
    vector<T> w;
    vector<node> t;
    LSGT(){};
    LSGT(int n) {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }
    LSGT(vector<int> in) {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void init(vector<int> in){
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            w[i] = in[i];
        }
        t.resize((n << 2) + 1);
        build(1, n);
    }
    void pushdown(node &p,T add) { // 在此更新下递函数
        p.sum=(p.sum+(p.r-p.l+1)*add)%mod;
        p.add=(p.add+add)%mod;
        return;
    }
    void pushup(node &p, node &l, node &r) { // 在此更新上传函数
        p.sum = (l.sum + r.sum)%mod;
    }
    void pushdown(int p) { // 不需要动
        pushdown(t[l(p)],t[p].add); 
        pushdown(t[r(p)],t[p].add);
        t[p].add=0;
    }
    void pushup(int p) { // 不需要动
        pushup(t[p], t[l(p)], t[r(p)]);
    }
    void build(int l, int r, int p = 1) {
        if (l == r) {
            t[p] = {l, r, w[l]};
            return;
        }
        t[p] = {l, r};
        int mid = (l + r) >> 1;
        build(l, mid,l(p));
        build(mid + 1, r, r(p));
        pushup(p);
    }
    void modify(int l, int r, T val,int p = 1) { // 区间修改
        if(l<=t[p].l&&t[p].r<=r){
            t[p].sum=(t[p].sum+(t[p].r-t[p].l+1)*val)%mod;
            t[p].add=(t[p].add+val)%mod;
            return;
        }
        pushdown(p);
        int mid=(t[p].l+t[p].r)>>1;
        if(l<=mid) modify(l,r,val,l(p));
        if(mid<r) modify(l,r,val,r(p));
        pushup(p);
    }
    T ask(int l, int r, int p = 1) { // 区间询问，不合并
        if (l <= t[p].l && t[p].r <= r) {
            return t[p].sum;
        }
        pushdown(p);
        int mid = (t[p].l + t[p].r) / 2;
        T ans = 0;
        if (l <= mid) ans = (ans+ ask(l, r,l(p)))%mod;
        if (mid < r) ans = (ans+ask(l, r, r(p)))%mod;
        return ans;
    }
    void debug(int p = 1) {
        cout << "[" << t[ p].l << ", " << t[p].r << "]: ";
        cout << "sum = " << t[p].sum << ", ";
        cout << endl;
        if (t[p].l == t[p].r) return;
        debug(l(p)), debug(r(p));
    }
#undef l(p)
#undef r(p)
};

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

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

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

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

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

主席树

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

区间静态第k小

包括离散化,pos-1是因为b数组下标从0开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
int cnt=0;
struct Node{
    int l,r,rt,sum;
};
vector<Node>tr(N<<5);

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

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

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

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

FHQ Treap

操作复杂度$log_2n$，

能够解决

  1. 插入一个数 x。

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

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

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

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

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

Posted on Edited on In , Valine:

A Intelligent Warehouse

Topic

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

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

Analyse

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

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

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

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

B Intelligent Robot

C Smart Browser

Topic

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

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

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

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

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

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

Analyse

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

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