发表于

鉴于省选第一轮已经滚粗了。。
我把我犯过的错误及对应的题目记下来，以警示自己。

！！：不容易在调试时发现
考试前一定要保持清醒&充足睡眠
平时训练一定要保证清醒&充足睡眠

三明治等含有鸡蛋或火腿的食物不要吃！（沙门氏菌）

学会静态+人眼（用脑子）查错！！
明明没有改它，为什么它变了？？！！越界了！！检查循环变量！！

对拍要试试极限数据看看是否超时

交上去一个优秀的暴力（最优化剪枝

浮躁，是人生中最大的错误。

再看漫画或者打游戏就要变小狗了ww
隔膜打的多，题目全tm看错！

不能急，冲动的时候什么都做不了。去洗把脸吧！

1) 多测没有清空应当清空的数组或变量（包括某些输入的数组）！！

  • luogu4382 劈配
  • luogu2055 [ZJOI2009]假期的宿舍
  • poj3691 DNA repair
  • UVA10652 Board Wrapping
  • hdu6328（调了两天，zyb都没有看出的错误：多测时，n不同，线段树的形态也不同。要注意赋初值和清空时的区别（指分治每层的清空）。and 多测对拍n一直取相同值也是不好的。。）
  • hdu5396（线段树的build要注意对非叶子节点的初始化）

2) 没有去掉调试时的输出（请用cerr!）

  • luogu4365 秘密袭击

3) 邻接表的nume出错（异或时没有成对出现或者第一个nume为0，请int nume=1;)

  • luogu2765 魔术球问题
  • zkw费用流

4) 变量名/数组名打错(i/j/x,n/m,x/y)(搞错对象)！！

  • luogu2763 试题库问题
  • uva1515 pool construction
  • poj2947 Widget Factory
  • luogu2051 [AHOI2009]中国象棋
  • hdu3414 Tour Route
  • luogu1903 [国家集训队]数颜色
  • poj2985The k-th Largest Group
  • luogu3502 [POI2010]Hamsters
  • hiho1419 后缀数组四·重复旋律4
  • UVA11796 Dog Distance
  • luogu3157 [CQOI2011]动态逆序对
  • luogu3377 【模板】左偏树（可并堆）
  • zroi#363. 陈太阳与乐谱 *2！！
  • #444. 彩虹糖
  • ch5103 传纸条（被wyy批判教育了一番）

5) 边界出错(n/n+1）！！

  • luogu2447 [SDOI2010]外星千足虫

6) 答案忘记更新或者在某处少更新！！修改操作少修改某些值！！

  • luogu2447 [SDOI2010]外星千足虫
  • bzoj1453: [Wc]Dface双面棋盘

7) 输出与题意不符（少复制了什么）！！

  • poj2947 Widget Factory（少输出’.’）
  • bzoj1027 [JSOI2007]合金 （1输成-1）

8) 没有初始化或初始化出错！！(dp等)

  • luogu1070 道路游戏
  • luogu3502 [POI2010]Hamsters

9) 多测没有把数据读完就输出

  • hdu3414 Tour Route

10) 做完一个就要break（循环忘记退出）！！

  • hdu3414 Tour Route

11) (空间）数组开小了（点数算少了/边数算少了）！！

  • luogu1341 无序字母对
  • luogu2055 [ZJOI2009]假期的宿舍
  • luogu1345 [USACO5.4]奶牛的电信Telecowmunication
  • luogu3502 [POI2010]Hamsters
  • luogu2463 [SDOI2008]Sandy的卡片
  • luogu2657 [SCOI2009]windy数
  • 正睿2018暑期集训AB班刷题营Day2 B. 配对
  • #378. 【2018普转提day19专题】打架
  • ch5102 Mobile Service
  • hdu5634 Rikka with Phi（zyb的教导：因为数组越界后会发生什么谁也不知道啊。。wa,tle,red都有可能。。zyf也因为数组开小t了。。）
  • bzoj3123（主席树启发式合并，双log啊，启发式合并空间都要多一个log，因为不能回收利用）
  • csa online xormax trie合并（动态开点至少要2logn，能开3logn更好;zyb:造极限数据输出tot）
  • poj3171（线段树对应的范围要看好了）

12) 输入时出错（出现0之类的，读错，多度，少读）！！

  • luogu1346 电车

13) 爆int爆int爆int,类型出错，忘记强制类型转换,LL写成int（int×int爆int）！！

  • luogu1265 公路修建
  • bzoj4765 普通计算姬
  • UVA10368 Euclid’s Game（没有数据范围。）
  • 正睿2018暑期集训AB班刷题营Day5 A. 友谊巨轮
  • bzoj2115 [Wc2011] Xor
  • luogu3066 [Usaco2012 Dec]Running Away From the Barn
  • 南外校内18-10-16 a
  • 南外校内18-10-23 c（前面改过的LL后面相应的没改）
  • bzoj2124: 等差子序列（所有和hash相关的量都要用ll！！）
  • hdu4348 to the moon（要LL！）
  • bzoj4310
  • hdu5306
  • bzoj4355
  • poj1180

14) 程序的顺序出错（逻辑顺序）或者逻辑错误（经常性的错误，不过没有记录，大概是认为和题目有关，实际上是思维严谨性的问题，感性理解之后要严谨的证明）

  • luogu1484 种树
  • #109. 【17 提高 7】当那一天来临
  • bzoj2124: 等差子序列（变量名打反）
  • bzoj4892 dna
  • Gym 101194F
  • bzoj3277（长代码就容易出现逻辑错误，请静下心来肉眼查错。错误会比较多，在对拍前先查明显的错误，如k<<=1写成++k..）
  • gym101955B
  • bzoj4310

15) 下标出现负数/下标越界

  • bzoj4765 普通计算姬
  • bzoj2124: 等差子序列

16) 题目分析有误

  • luogu2022 有趣的数

17) max/min设置的有误

  • luogu3369 【模板】普通平衡树

18) eps设置太小会t

19) (apio2018)使用set查找时尽量不要用pair，对双关键字排序要注意

20) 数组下标打反

  • bzoj1027 [JSOI2007]合金

21) 程序改一半忘了

  • bzoj1027 [JSOI2007]合金

22) 对拍忘记srand

  • hiho1419 后缀数组四·重复旋律4

23) 未定义行为

  • UVA1342 That Nice Euler Circuit（a[i]=point(read(),read())其中读入的顺序可能会反过来）

24) 四舍五入得到-0，正确的姿势是int(x+0.5)。保留1位小数则是printf(“%.1f”,int(a10+0.5)1.0/10);

25) 没有取模！！

  • 正睿2018暑期集训AB班刷题营Day2 B. 配对
  • #108. 【17 提高 7】强军战歌

26) (a+=b)%=c 而不是 (a+=b)%c;

  • 27) long long用%d输出

  • zroi #261. 萌新拆塔（cjq也是！233）

28) 模拟赛中犯的错

  • 没有把所有复制的地方都改正。
  • 用错了变量
  • dijk没改成小根堆！！好几次了啊！

29) double写成int

  • luogu4525 【模板】自适应辛普森法1

30) 求割边用fa

  • #359. 【2018普转提day18专题】嘤嘤

31) 1到n的最短路上的边用ds[x]+e[i].f+dt[y]==ds[n]判断，从s或t向外延伸都是错的

  • #359. 【2018普转提day18专题】嘤嘤

32) memset(a,0x3f,sizeof(a))如果a是指针，sizeof(a)只有8个字节

  • #359. 【2018普转提day18专题】嘤嘤

33) 数组只开大1而越界了。。

34) 树上dp时sz没有和背包大小取min

  • 南外校内18-10-16 a

35) 以为没爆int实际爆了，三个int相加爆了，以为类型转换了实际没有转。。

  • 南外校内18-10-16 a

36) 递归变量和全局变量重复

  • #423. 锅锅

37) 使用stl容器前没有判是否为空（如set）

  • #467. 数的距离

38) 涉及图的题目，要注意重边和自环！！

  • luoguP1850 换教室

39) 注意运输符的结合律，连等的时候要注意变量的改变！

  • #322. 【Jiangsu Training Contest 5】Graph

40) 输入scanf(“%d”,a+i)写成scanf(“%d”,a+1)

  • bzoj3585╱luogu4137 mex

41) add_ans和ass_ans搞混

  • csa Min Max Sum

42) bzoj3123专属错误：T是数据类型不是数据组数！！

43) 题意理解错误/题目读错

  • bzoj3277（本质相同的子串算多次！！）
  • usaco2018-12ptA rounded down to the nearest integer（向下取整，不是round）

44) 预处理使用n，但n还没有读入（应该用N）

  • gym101955B

45) 动态数据结构在多测时尽量不要用memset，容易mle（好像不用的空间就不算）

  • hdu4348 to the moon

46) 死于未定义行为（而且很难调）（调用顺序，有符号溢出在玄学的优化下gg）

  • gym102028 H

47) priority_queue没有改成小根堆

  • dijk
  • 19-1-1 B

48) 滚动数组每层要清空！！（或者确保每个值都被重新赋值了）

  • poj2411

发表于

1.块状数组/块状链表
2.上下界网络流
3.fft/ntt
4.dp斜率优化/四边形不等式/决策单调性
5.数论（反演/筛，置换）
6.图论（tarjan，仙人掌（圆方树））
7.数据结构（线段树合并和分裂，主席树，点分治，平衡树，二叉堆，cdq分治，整体二分，lct，k-d tree）
8.容斥
9.高精度除法

发表于

内啡肽：冷静作用
促进内啡肽分泌的方式：运动，冥想，深呼吸，笑

多巴胺：预期奖励
短期大量释放多巴胺，让我们更追求短期快感，更没耐心。
更多的多巴胺或提高阈值，导致更难获得快乐。
保持平常心，减少情绪波动，降低多巴胺分泌。

差不多退役了
算法竞赛教会我什么呢
多年之后还能影响到我的估计只有思维上多出的一丝敏捷（这都没有就啥都没有了
吉老师线段树什么的怎么可能记得呢（亏我熬夜到一点去调代码，结果是思维方式有问题
（把tag放在一起考虑，，合并起来也方便

要是有机会去wc的话，接下来一段时间的目标是数学和dp
有机会了（这是你颓废那么多天的结果吗。。

阅读全文 »

发表于

分块&莫队

分块：

如果我们把每m个元素分为一块，共有n/m块，每次区间加的操作会涉及O(n/m)个整块，以及区间两侧两个不完整的块中至多2m个元素。每次操作的复杂度是O(n/m)+O(m)，根据均值不等式，当m取√n时总复杂度最低。(hzwer)

分块：

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;++i){
	bl[i]=(i-1)/blk+1;
}
nb=bl[n];
for(int i=1;i<=nb;++i){
	lblk[i]=(i-1)*blk+1;
	rblk[i]=i*blk;
}
rblk[nb]=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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=1000+8;
int n,b;
int x,y;
int nume,head[N];
struct edge{
	int to,nxt;
}e[N<<1];
IL void add_edge(int x,int y)
{
	e[++nume]=(edge){y,head[x]};head[x]=nume;
}
int k,bl[N],ct[N];
//vector<int> s[N];
int num,st[N];
IL void dfs(int x,int fa)
{
	int tmp=num;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to!=fa){
			dfs(to,x);
			if(num-tmp>=b){
				++k;
				ct[k]=x;
				while(num>tmp){
					//s[k].pb(st[num]);
					bl[st[num]]=k;
					--num;
				}
			}
		}
	}
	st[++num]=x;
}
int main()
{
	n=io;b=io;
	for(int i=1;i<n;++i){
		x=io;y=io;
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs(1,0);
	//if(!num)	ct[++num]=1; 
	while(num>0){
		//s[k].pb(st[num]);
		bl[st[num]]=k;
		--num;
	}
	printf("%d\n",k);
	for(int i=1;i<=n;++i){
		printf("%d ",bl[i]);
	}
	printf("\n");
	for(int i=1;i<=k;++i){
		printf("%d ",ct[i]);
	}
	return 0;
}

莫队：

普通莫队、带修改莫队、树上莫队、回滚莫队（见全网最详细、最深的四类莫队算法讲解）
普通莫队：
先按左指针所在块升序，同一块按右指针升序。
复杂度：设块长m，共n/m块，左指针移动q·m次，右指针移动n·n/m次，m取n/sqrt(q)时，为n·sqrt(q)

莫队：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int curl=1,curr=0; 
for(int i=1;i<=qn;++i){
	while(curl<b[i].l){
		remove(curl);++curl;
	}
	while(curl>b[i].l){
		--curl;add(curl);
	}
	while(curr<b[i].r){
		++curr;add(curr);
	}
	while(curr>b[i].r){
		remove(curr);--curr;
	}
	solve(i);
}

把块大小blk设成定值不易出错，方便调块大小卡常。

luogu4396 [AHOI2013]作业
莫队+分块：在区间上莫队，在值域上分块。莫队的转移是O(1)。每个询问求答案是用分块，复杂度根号，查询的总复杂度为q根号n。总复杂度是O(n·sqrt(q)+q·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
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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,QN=1000000+8,NB=350;
const int blk=300;
int n,qn;
int a[N];
struct ques{
	int l,r,a,b,id;
}b[QN];
int bl[N],nb,lblk[NB],rblk[NB];//值域也是1到n，共用一个bl 
IL bool cmp(const ques &a,const ques &b)
{
	if(bl[a.l]!=bl[b.l])	return bl[a.l]<bl[b.l];
	return a.r<b.r;
}	
int cnt[N],num1[NB],num2[NB];
IL void add(int x)
{
	++cnt[a[x]];
	++num1[bl[a[x]]];
	if(cnt[a[x]]==1)	++num2[bl[a[x]]];
}
IL void remove(int x)
{
	--cnt[a[x]];
	--num1[bl[a[x]]];
	if(cnt[a[x]]==0)	--num2[bl[a[x]]];
}
int ans1[QN],ans2[QN];
IL void solve(int x)
{
	int ans1=0,ans2=0;
	int l=b[x].a,r=b[x].b;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
	}
	else{
		for(int i=bl[l]+1;i<=bl[r]-1;++i){
			ans1+=num1[i];ans2+=num2[i];
		}
		for(int i=l;i<=rblk[bl[l]];++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
		for(int i=lblk[bl[r]];i<=r;++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
	}
	::ans1[b[x].id]=ans1;
	::ans2[b[x].id]=ans2;
}
IL void MAIN()
{
	int curl=1,curr=0; 
	for(int i=1;i<=qn;++i){
		while(curl<b[i].l){
			remove(curl);++curl;
		}
		while(curl>b[i].l){
			--curl;add(curl);
		}
		while(curr<b[i].r){
			++curr;add(curr);
		}
		while(curr>b[i].r){
			remove(curr);--curr;
		}
		solve(i);
	}
	for(int i=1;i<=qn;++i){
		printf("%d %d\n",ans1[i],ans2[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=io;
	}
	for(int i=1;i<=qn;++i){
		b[i].l=io;b[i].r=io;b[i].a=io;b[i].b=io;
		b[i].id=i;
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=(i-1)*blk+1;
		rblk[i]=i*blk;
	}
	rblk[nb]=n;
	
	sort(b+1,b+qn+1,cmp);
	MAIN();
	return 0;
}

luogu1903 [国家集训队]数颜色/维护队列
带修改莫队：多了一个时间轴。排序第一关键字是左端点所在块编号，第二关键字是右端点所在块编号，第三关键字是时间。左指针移动的复杂度为q·n，右指针的复杂度为n/m·n，时间轴的指针的复杂度为n/m·n/m·q，n和q同阶的时候，m取n^(2/3)时最优。比较需要调块大小。

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=133333+8,QN=133333+8,VAL=1000000+8;
const int blk=6000;
int n,qn,qn1,qn2;
int a[N],c[N];
int bl[N];
struct ques1{
	int l,r,id,cur;
}b1[QN];
struct ques2{
	int pos,a,b;
}b2[QN];
IL bool cmp(const ques1 &a,const ques1 &b)
{
	if(bl[a.l]!=bl[b.l])	return a.l<b.l;
	if(bl[a.r]!=bl[b.r])	return a.r<b.r;
	return a.cur<b.cur;
}
int curl=1,curr=0,cur=0;
int tot=0,cnt[VAL];
IL void add(int x)
{
	++cnt[x];
	if(cnt[x]==1)	++tot;
}
IL void remove(int x)
{
	--cnt[x];
	if(cnt[x]==0)	--tot;
} 
IL void change(int pos,int x)
{
	if(curl<=pos&&pos<=curr){
		remove(a[pos]);
		add(x);
	}
	a[pos]=x;
}
int ans[QN];
IL void MAIN()
{
	for(int i=1;i<=qn1;++i){
		while(cur<b1[i].cur){
			++cur;
			change(b2[cur].pos,b2[cur].b);
		}
		while(cur>b1[i].cur){
			change(b2[cur].pos,b2[cur].a);
			--cur;
		}
		while(curl<b1[i].l){
			remove(a[curl]);++curl;
		}
		while(curl>b1[i].l){
			--curl;add(a[curl]);
		}
		while(curr<b1[i].r){
			++curr;add(a[curr]);
		}	
		while(curr>b1[i].r){
			remove(a[curr]);--curr;
		}
		ans[b1[i].id]=tot;
	}
	for(int i=1;i<=qn1;++i){
		printf("%d\n",ans[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=c[i]=io;
		bl[i]=(i-1)/blk+1;
	}
	for(int i=1;i<=qn;++i){
		char ch;
		scanf("%c",&ch);
		if(ch=='Q'){
			++qn1;
			b1[qn1].l=io;b1[qn1].r=io;
			b1[qn1].id=qn1;b1[qn1].cur=qn2;
		}
		else{
			++qn2;
			b2[qn2].pos=io;
			b2[qn2].a=c[b2[qn2].pos];
			c[b2[qn2].pos]=b2[qn2].b=io;
		}
	}
	sort(b1+1,b1+qn1+1,cmp);
	MAIN();
	return 0;
}

atcoder1219 歴史の研究
回滚莫队：用来处理不适合添加或者删除的情况。对于处于同一块的左指针，每次移动之前将左指针放在下一个块的第一个位置，移动之后再把左指针放到下一个块的第一个位置。这样可以使得问题只有添加没有删除（或者删除变的可以处理）。复杂度同普通莫队。

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,QN=100000+8,NB=350;
const int blk=300;
int n,qn;
int tot,ori[N],a[N];
struct ques{
	int l,r,id;
}b[QN];
int nb,bl[N],lblk[NB],rblk[NB];
IL bool cmp(const ques &a,const ques &b)
{
	if(bl[a.l]!=bl[b.l])	return bl[a.l]<bl[b.l];
	return a.r<b.r;	
}
int cnt[N];
LL ans[QN];
IL void MAIN()
{
	int curl=0,curr=0;
	LL ans=0,tmp=0;
	for(int i=1;i<=qn;++i){
		int l=b[i].l,r=b[i].r;
		if(bl[l]!=bl[b[i-1].l]){
			curl=rblk[bl[l]]+1;
			curr=rblk[bl[l]];
			tmp=0;
			memset(cnt,0,sizeof(cnt));
		}
		if(bl[l]==bl[r]){
			ans=0;
			for(int i=l;i<=r;++i){
				++cnt[a[i]];
				ans=max(ans,1ll*cnt[a[i]]*ori[a[i]]);
			}
			for(int i=l;i<=r;++i){
				--cnt[a[i]];
			}
			::ans[b[i].id]=ans;
			continue;
		}
		while(curr<r){
			++curr;++cnt[a[curr]];
			tmp=max(tmp,1ll*cnt[a[curr]]*ori[a[curr]]);
		}
		ans=tmp;
		while(curl>l){
			--curl;++cnt[a[curl]];
			ans=max(ans,1ll*cnt[a[curl]]*ori[a[curl]]);
		}
		while(curl<rblk[bl[l]]+1){
			--cnt[a[curl]];++curl;
		}
		::ans[b[i].id]=ans;
	}
	for(int i=1;i<=qn;++i){
		printf("%lld\n",::ans[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		ori[i]=a[i]=io;
	}
	sort(ori+1,ori+n+1);
	tot=unique(ori+1,ori+n+1)-ori-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
	}
	
	for(int i=1;i<=qn;++i){
		b[i].l=io;b[i].r=io;
		b[i].id=i;
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;	
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=(i-1)*blk+1;
		rblk[i]=i*blk;
	}
	rblk[nb]=n;
	
	sort(b+1,b+qn+1,cmp);
	MAIN();
	return 0;
}

区间众数
离线：回滚莫队 时间n·sqrt(q) 空间n
在线：分块 时间n·sqrt(q) 空间n

luogu5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III
区间众数 众数的次数 在线
先离散化数据，将每个数据都放到对应的桶里(vector)，并记下排名。
再预处理一个f[i][j]表示第i个块到第j个块中的众数是多少，同时也可以记下众数是什么。
对于每一个[l,r]，ans开始是f[bl[l]+1][bl[r]-1]为中间块的众数。
对于左边的数字，在其对应的vector中找从他开始往后ans个数的位置是否<=r(首先要保证有后ans个数)，如果有则++ans
对于右边的数字，在其对应的vector中找从他开始往前ans个数的位置是否>=l(首先要保证有前ans个数)，如果有则++ans
复杂度：ans自增最多blk次，因为每次更新的数的位置要跨越[bl[l]+1][bl[r]-1]，这样就是两边区间的数的个数。预处理复杂度为n·n/m，每次查询复杂度为m，总复杂度n·n/m+q·m

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=500000+8,NB=750;
const int blk=700;
int n,qn,nb;
int ori[N],tot,a[N];
int bl[N],lblk[N],rblk[N];
int f[NB][NB];
int pos[N];
vector<int> set_pos[N];
int cnt[N];
int l,r,lstans;
IL void MAIN()
{
	int ans=0;
	while(qn--){
		l=io^lstans;r=io^lstans;
		if(bl[l]+1<=bl[r]-1)	ans=f[bl[l]+1][bl[r]-1];
		else	ans=0;
		if(bl[l]==bl[r]){
			for(int i=l;i<=r;++i){
				while(pos[i]+ans<set_pos[a[i]].size()&&set_pos[a[i]][pos[i]+ans]<=r){
					++ans;
				}
			}
		} 
		else{
			for(int i=l;i<=rblk[bl[l]];++i){
				while(pos[i]+ans<set_pos[a[i]].size()&&set_pos[a[i]][pos[i]+ans]<=r){
					++ans;
				}
			}
			for(int i=lblk[bl[r]];i<=r;++i){
				while(pos[i]-ans>=0&&set_pos[a[i]][pos[i]-ans]>=l){
					++ans;
				}
			}
		}
		printf("%d\n",ans);
		lstans=ans; 
	}	
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=ori[i]=io;
	}
	sort(ori+1,ori+n+1);
	tot=unique(ori+1,ori+n+1)-ori-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
		pos[i]=set_pos[a[i]].size();
		set_pos[a[i]].pb(i);
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=blk*(i-1)+1;
		rblk[i]=blk*i;
	}
	rblk[nb]=n;
	
	for(int i=1;i<=n;i+=blk){
		memset(cnt,0,sizeof(cnt));
		int t=0;
		for(int j=i;j<=n;++j){
			++cnt[a[j]];
			if(cnt[a[j]]>t)	t=cnt[a[j]];
			if(rblk[bl[j]]==j){
				f[bl[i]][bl[j]]=t;
			}
		}
	}
	
	MAIN();
	return 0;
}

发表于

基础

把编辑器/编译器调到舒服的状态（见考试安排）
学会用批处理和写对拍（见批处理）
学会随机化生成（见随机化）
学会离散化（这种最方便）

1
2
3
4
5
6
7
8
for(int i=1;i<=n;++i){
	a[i]=ori[i]=io;
}
sort(ori+1,ori+n+1);
tot=unique(ori+1,ori+n+1)-ori-1;
for(int i=1;i<=n;++i){
	a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
}

掌握c风格输入输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
scanf：
int -> %d
long long -> %lld
unsigned int -> %u
unsigned long long -> %llu
float -> %f
double -> %lf
long double -> %Lf
char -> %c
char a[] -> %s
printf：
int -> %d
long long -> %lld
unsigned int -> %u
unsigned long long -> %llu
float -> %f
double -> %f （和scanf不一样！）
long double -> %Lf
char -> %c
char a[] -> %s

稳固代码风格：

1
2
3
4
5
6
7
8
9
++i
只有函数的大括号换行，其他不换行
用c风格输入输出
无论什么系统，使用快读
尽量用局部变量
规定范围的常量用对应变量的大写命名
主体在MAIN()中处理，在main()中做预处理，较长的函数要分段
部分分写在namespace里
所有函数加IL(inline)

附个模板：

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
int main()
{
	return 0;
}

分块&莫队

分块、莫队：暴力的加强版，思维难度小，代码量小，复杂度未必最优。（适合康复第一阶段训练）
（具体题目&代码见【学习笔记】分块&莫队）

图论

存图方式：
1、邻接矩阵
2、邻接表
nume=1为了方便找反向边，=-1则head要设为-1（小于0即可）

1
2
3
4
5
6
7
8
9
10
11
12
13
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
for(int i=head[x];i;i=e[i].nxt){
	int to=e[i].to;
	...
}

单元最短路径

（spfa它死了）
dijkstra：要求边权都是非负数
1、稠密图（m和n^2同级别），复杂度n^2
2、稀疏图，堆优化，复杂度(m+n)logm（注意到logm和logn同级别）
3、边权较小，桶优化，时间复杂度(m+n·最大边权），空间复杂度（n·最大边权+m）
对于不同的条件，使用不同的方法找最小边权。

dijk基于贪心，只要一个点被选中标记之后，任何其他路径不会使它更优即可使用。
spfa则是使图中的每条边都满足三角形不等式（不满足则存在不合题意的环），即对于边(x,y,z)，cal(dp[x],z)>dp[y]，其中cal代表某种运算。

堆优化dijk

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,M=200000+8;
int n,m,s;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
int dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII> >pq;
IL void dijk()
{	
	memset(dis,0x3f,sizeof(dis));
	//memset(vis,0,sizeof(vis));
	dis[s]=0;
	pq.push(mp(0,s));
	while(!pq.empty()){
		int x=pq.top().se;
		pq.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				pq.push(mp(dis[to],to)); 
			}
		}
	}
	for(int i=1;i<=n;++i){
		printf("%d ",dis[i]);
	}
}
int main()
{
	n=io;m=io;s=io;
	for(int i=1;i<=m;++i){
		x=io;y=io;z=io;
		add_edge(x,y,z);
		//add_edge(y,x,z);
	}
	dijk();
	return 0;
}

01bfs：边权为0或1的图求单源最短路
通过双端队列bfs，边权为0则从队头入队，边权为1从队尾入队。任意时刻保持队列的“两段性”和“单调性”
一个点最多入队两次，可以用vis判断（不用也是正确的）。复杂度n+m

luogu1948 [USACO08JAN]电话线Telephone Lines
二分答案后转化成01bfs

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<deque>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=1000+8,P=10000+8;
int n,p,k;
int ori[P],tot;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[P<<1];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
deque<int> q;
int dis[N];
//bool vis[N];
IL bool ok(int mid)
{
	q.clear();
	memset(dis,0x3f,sizeof(dis));
	//memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.pb(1);
	while(!q.empty()){//每个值最多入队两次，+1和+0各入队一次 
		int x=q.front();
		q.pop_front();
		//if(vis[x])	continue;
		//vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+(e[i].f>mid)){
				dis[to]=dis[x]+(e[i].f>mid);
				if(e[i].f<=mid){
					q.push_front(to);
				}
				else{
					q.pb(to);
				}
			} 
		}
	}
	return dis[n]<=k;
}
IL void MAIN()
{
	int l=0,r=tot,mid=0,ans=tot+1;
	while(l<=r){
		mid=(l+r)>>1;
		if(ok(mid)){
			ans=mid;
			r=mid-1; 
		}
		else{
			l=mid+1;
		}
	}
	if(ans<=tot)	printf("%d",ori[ans]);
	else	printf("-1");
}
int main()
{
	n=io;p=io;k=io;
	for(int i=1;i<=p;++i){
		x=io;y=io;z=io;
		ori[i]=z;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	sort(ori+1,ori+p+1);
	tot=unique(ori+1,ori+p+1)-ori-1;
	for(int i=2;i<=nume;++i){
		e[i].f=lower_bound(ori+1,ori+tot+1,e[i].f)-ori;
	}
	MAIN();
	return 0;
}

bzoj3073. [Pa2011]Journeys
线段树建图后转化成01bfs

线段树建图的步骤：（from lvzelong2014）
1、A树每个节点向父亲连边，B树每个节点向儿子连边。边权为零。
2、每个B树的叶子节点向对应的A树的叶子节点连边。
3、对于a~b连向c~d，在A树上找到a~b对应的区间u1,u2……un，将其连向虚拟节点p1，边权为0
4、虚拟节点p1到虚拟节点p2连上边权为1的边
5、在B树上找到c~d对应的区间v1,v2……vn从p2连到这些区间，边权为0

3-5的连边为(a,b)->(c,d)，(c,d)->(a,b)要再连一次。
也可以将p1,p2合并成一个点，然后将3或者5中边权改为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
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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=500000+8,M=100000+8;
int n,m,p;
int a,b,c,d;
int numn;
int nume,head[N*8+M*2];
struct edge{
	int to,nxt,f;
}e[N*9+M*4*25];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
#define ls (t<<1)
#define rs (t<<1|1)
int tr1[N*4],tr2[N*4];
IL void add1(int t,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr){
		add_edge(tr1[t],numn,1);
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)	add1(ls,l,mid,ll,rr);
	if(mid<rr)	add1(rs,mid+1,r,ll,rr);
}	
IL void add2(int t,int l,int r,int ll,int rr)
{
	if(ll<=l&&r<=rr){
		add_edge(numn,tr2[t],0);
		return;
	}
	int mid=(l+r)>>1;
	if(ll<=mid)	add2(ls,l,mid,ll,rr);
	if(mid<rr)	add2(rs,mid+1,r,ll,rr);
}
IL void add()
{
	++numn;
	add1(1,1,n,a,b);
	add2(1,1,n,c,d);
	++numn;
	add1(1,1,n,c,d);
	add2(1,1,n,a,b);
}
int be[N],en[N];
IL void build1(int t,int l,int r)
{
	tr1[t]=++numn;
	if(l==r){
		be[l]=numn;
		return;
	}
	int mid=(l+r)>>1;
	build1(ls,l,mid);
	build1(rs,mid+1,r);
	add_edge(tr1[ls],tr1[t],0);
	add_edge(tr1[rs],tr1[t],0);
}
IL void build2(int t,int l,int r)
{
	tr2[t]=++numn;
	if(l==r){
		en[l]=numn;
		return;
	}
	int mid=(l+r)>>1;
	build2(ls,l,mid);
	build2(rs,mid+1,r);
	add_edge(tr2[t],tr2[ls],0);
	add_edge(tr2[t],tr2[rs],0);
}
IL void init()
{
	build1(1,1,n);
	build2(1,1,n);
	for(int i=1;i<=n;++i){
		add_edge(en[i],be[i],0);//
	}
}
int dis[N*8+M*2];
deque<int> q;
IL void bfs01()
{
	memset(dis,0x3f,sizeof(dis));
	dis[be[p]]=0;
	q.pb(be[p]);
	while(!q.empty()){
		int x=q.front();
		q.pop_front();
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				if(e[i].f)	q.pb(to);
				else	q.push_front(to);
			}		
		}
	}
	for(int i=1;i<=n;++i){
		//if(i!=p)	printf("%d\n",dis[en[i]]);
		//else	printf("0\n");
		printf("%d\n",dis[be[i]]);
	}
}
int main()
{
	n=io;m=io;p=io;
	init();
	for(int i=1;i<=m;++i){
		a=io;b=io;c=io;d=io;
		add();
	}
	bfs01();
	return 0;
}

手写队列：
1、普通队列 he=1,ta=0;q[++ta]=x;while(he<=ta){…}
2、循环队列 he=1,ta=1;q[ta++]=x;while(he!=ta){…}

luogu3008 [USACO11JAN]道路和飞机Roads and Planes
缩点+拓扑+dijk

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=25000+8,M=50000+8;
int n,r,p,s;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M*3];
IL void add_edge(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
}
int num,bl[N];
vector<int> v[N];
IL void dfs(int x)
{
	bl[x]=num;
	v[num].pb(x);
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(!bl[to]){
			dfs(to);
		}
	}
}
int ind[N];
int q[N],he,ta;
int dis[N];
bool vis[N];
priority_queue<PII,vector<PII>,greater<PII> > pq; 
IL void solve(int t)
{
	while(!pq.empty())	pq.pop();
	for(int i=0;i<v[t].size();++i){
		pq.push(mp(dis[v[t][i]],v[t][i])); 
	}
	while(!pq.empty()){
		int x=pq.top().second;
		pq.pop();
		if(vis[x])	continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(dis[to]>dis[x]+e[i].f){
				dis[to]=dis[x]+e[i].f;
				if(bl[to]==bl[x]){
					pq.push(mp(dis[to],to));
				}
			}
			if(bl[to]!=bl[x]){
				--ind[bl[to]];
				if(!ind[bl[to]])	q[++ta]=bl[to];
			}	
		}
	}
}
IL void MAIN()
{
	he=1;ta=0;
	if(ind[bl[s]])	q[++ta]=bl[s];
	for(int i=1;i<=num;++i){
		if(!ind[i])	q[++ta]=i;
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	while(he<=ta){
		int x=q[he];
		++he;
		solve(x);
	}
	for(int i=1;i<=n;++i){
		if(dis[i]>5e8)	printf("NO PATH\n");//不能用if(dis[i]==0x3f3f3f3f)，因为存在负边权 
		else	printf("%d\n",dis[i]);
	}
}
int main()
{
	n=io;r=io;p=io;s=io;
	for(int i=1;i<=r;++i){
		x=io;y=io;z=io;
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	for(int i=1;i<=n;++i){
		if(!bl[i]){
			++num;
			dfs(i);
		}
	}	
	for(int i=1;i<=p;++i){
		x=io;y=io;z=io;
		++ind[bl[y]];
		add_edge(x,y,z);
	}
	MAIN();
	return 0;
}

任意两点间最短路

dijk n^3或nmlogm
floyd n^3（还可以用于解决传递闭包）

最大流

dinic

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000+8,M=100000+8;
int n,m,s,t;
int x,y,z;
int nume=1,head[N];
struct edge{
	int to,nxt,f;
}e[M*2];
IL void add_edge_2(int x,int y,int z)
{
	e[++nume]=(edge){y,head[x],z};head[x]=nume;
	e[++nume]=(edge){x,head[y],0};head[y]=nume;
}
int cur[N];
int dis[N];
int q[N],he,ta;
IL int dfs(int x,int low)
{
	if(x==t||!low)	return low;
	int flow=0,tmp=0;
	for(int &i=cur[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(dis[to]==dis[x]+1&&(tmp=dfs(to,min(low,e[i].f)))){
			flow+=tmp;
			low-=tmp;
			e[i].f-=tmp;
			e[i^1].f+=tmp;
			if(!low)	return flow;
		}
	}
	if(low)	dis[x]=0;
	return flow;
}
IL bool bfs()
{
	memset(dis,0,sizeof(dis));
	he=1;ta=0;
	q[++ta]=s;
	dis[s]=1;
	while(he<=ta){
		int x=q[he];
		++he;
		for(int i=head[x];i;i=e[i].nxt){
			int to=e[i].to;
			if(!dis[to]&&e[i].f){
				dis[to]=dis[x]+1;
				q[++ta]=to;
				if(to==t)	return 1;
			}
		}
	}
	return 0;
}
IL void dinic()
{
	int maxflow=0;
	while(bfs()){
		for(int i=1;i<=n;++i)	cur[i]=head[i];
		maxflow+=dfs(s,INT_MAX);
	}
	printf("%d",maxflow);
}
int main()
{
	n=io;m=io;s=io;t=io;
	for(int i=1;i<=m;++i){
		x=io;y=io;z=io;
		add_edge_2(x,y,z);
	}
	dinic();
	return 0;
}

数论

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000000+8;
int n,qn;
int min_p[N],pri[N],num;
int main()
{
	n=io;qn=io;
	for(int i=2;i<=n;++i){
		if(!min_p[i]){
			min_p[i]=i;
			pri[++num]=i;
		}
		for(int j=1;j<=num&&pri[j]<=min_p[i]&&pri[j]<=n/i;++j){
			min_p[pri[j]*i]=pri[j];
		}
	}
	while(qn--){
		int x=io;
		printf(min_p[x]==x?"Yes\n":"No\n");
	}
	return 0;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
LL a,b,mod;
IL LL ksm(LL a,LL b)
{
	LL tmp=1%mod;
	while(b){
		if(b&1)	tmp=tmp*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return tmp;
}
int main()
{
	a=io;b=io;mod=io;
	printf("%lld^%lld mod %lld=%lld",a,b,mod,ksm(a,b));
	return 0;
}

luogu2568 GCD
所求为sum{prime}sum(2*sum(phi[i])(i=1 to n/prime)-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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=10000000+8;
int n;
int phi[N],min_p[N],pri[N],num;
LL sum[N],ans;
int main()
{
	n=io;
	phi[1]=1;
	sum[1]=1;
	for(int i=2;i<=n;++i){
		if(!min_p[i]){
			min_p[i]=i;
			pri[++num]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=num&&pri[j]<=min_p[i]&&pri[j]<=n/i;++j){
			min_p[i*pri[j]]=pri[j];
			phi[i*pri[j]]=phi[i]*(i%pri[j]?pri[j]-1:pri[j]);
		}
		sum[i]=sum[i-1]+phi[i];
	}
	for(int i=1;i<=num;++i){
		ans+=sum[n/pri[i]]*2-1;
	}
	printf("%lld",ans);
	return 0;
}

发表于

from 23forever

数据结构

并查集:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Ufs {
  int n, fa[MAXN + 5], rk[MAXN + 5];
  void operator() (const int _n) {
    n = _n;
    for (int i = 1; i <= n; ++i) {
      fa[i] = i;
      rk[i] = 1;
    }
  }
  int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
  }
  void unionSet(int x, int y) {
    int p = find(x), q = find(y);
    if (p == q) return;
    if (rk[p] < rk[q]) {
      fa[p] = q;
    } else {
      if (rk[p] == rk[q]) ++rk[q];
      fa[q] = p;
    }
  }
}DSU;

字符串hash:

1
2
3
4
5
6
ULL getHsh(char *s) {
  int len = strlen(s);
  ULL ret = 0;
  for (int i = 0; i < len; ++i) ret = ret * P + s[i];
  return ret;
}

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct BinaryIndexTree {
  int n, c[MAXN + 5];
  void operator() (int _n) {
    n = _n;
    memset(c, 0, sizeof(c));
  }
  int lowbit(int x) {
    return x & (-x);
  }
  void modify(int x, int v) {
    for (; x <= n; x += lowbit(x)) c[x] += v;
  }
  int getSum(int x) {
    int ret = 0;
    for (; x; x -= lowbit(x)) ret += c[x];
    return ret;
  }
} Bit;

ST表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void init() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) a[i] = read();
  for (int i = 1; i <= n; ++i) st[i][0] = a[i];
  for (int j = 1; (1 << j) <= n; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
      st[i][j] = max(a, b);
    }
  }
}
inline int query(int x, int y) {
  int k = log2(y - x + 1);
  int a = st[x][k], b = st[y - (1 << k) + 1][k];
  return max(a, b);
}

KMP：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void getFail() {
  fail[0] = 0;
  fail[1] = 0;
  for (int i = 1; i <= m; ++i) {
    int j = fail[i];
    while (j && p[i] != p[j]) j = fail[j];
    fail[i + 1] = p[i] == p[j] ? j + 1 : 0;
  }
}
void calc() {
  int j = 0;
  for (int i = 0; i <= n; ++i) {
    while (j && t[i] != p[j]) j = fail[j];
    if (t[i] == p[j]) ++j;
    if (j == m) printf("%d\n", i - m + 2);
  }
}

manacher：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int manacher() {
  int ret = 0;
  s[n++] = '$';
  s[n++] = '#';
  for (int i = 0; i < len; ++i) {
    s[n++] = a[i];
    s[n++] = '#';
  }
  for (int i = 0; i < n; ++i) {
    f[i] = i < mx ? min(f[2 * id - i], mx - i) : 1;
    while (s[i + f[i]] == s[i - f[i]]) ++f[i];
    if (f[i] + i > mx) {
      mx = f[i] + i;
      id = i;
    }
    ret = max(ret, f[i]);
  }
  return --ret;
}

线段树：

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
struct SegmentTree {
  struct Node {
    LL delta, mul, sum;
  }s[MAXN * 4 + 5];
  SegmentTree() {}
  #define lson p << 1
  #define rson p << 1 | 1
  void add(int p, int len, LL v) {
    s[p].delta = (s[p].delta + v) % mod;
    s[p].sum = (s[p].sum + v * len) % mod;
  }
  void mul(int p, LL v) {
    s[p].mul = s[p].mul * v % mod;
    s[p].delta = s[p].delta * v % mod;
    s[p].sum = s[p].sum * v % mod;
  }
  void pd(int p, int len) {
    if (s[p].mul != 1) {
      mul(lson, s[p].mul);
      mul(rson, s[p].mul);
      s[p].mul = 1;
    }
    if (s[p].delta) {
      add(lson, len - len / 2, s[p].delta);
      add(rson, len / 2, s[p].delta);
      s[p].delta = 0;
    } 
  }
  void upd(int p) {
    s[p].sum = (s[lson].sum + s[rson].sum) % mod;
  }
  void build(int p, int l, int r) {
    s[p].mul = 1;
    if (l == r) {
      s[p].sum = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    upd(p);
  }
  void modify(int p, int l, int r, int x, int y, LL v) {
    if (x <= l && y >= r) {
      add(p, r - l + 1, v);
      return;
    }
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y, v);
    if (y > mid) modify(rson, mid + 1, r, x, y, v);
    upd(p);
  }
  void update(int p, int l, int r, int x, int y, LL v) {
    if (x <= l && y >= r) {
      mul(p, v);
      return;
    }
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    if (x <= mid) update(lson, l, mid, x, y, v);
    if (y > mid) update(rson, mid + 1, r, x, y, v);
    upd(p);
  }
  LL query(int p, int l, int r, int x, int y) {
    if (x <= l && y >= r) return s[p].sum % mod;
    pd(p, r - l + 1);
    int mid = (l + r) >> 1;
    LL ret = 0;
    if (x <= mid) ret = query(lson, l, mid, x, y);
    if (y > mid) ret = (ret + query(rson, mid + 1, r, x, y)) % mod;
    return ret;
  }
}Sgt;

AC自动机：

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
struct ACAutomaton {
  int tot, trie[MAXN + 5][CS], cnt[MAXN + 5];
  int fail[MAXN + 5], val[MAXN + 5];
  queue<int> que;
  ACAutomaton() {}
  void init() {
    tot = 0;
    memset(fail, 0, sizeof(fail));
    memset(cnt, 0, sizeof(cnt));
    memset(val, 0, sizeof(val));
    memset(trie, 0, sizeof(trie));
  }
  void insert(char *p, int id) {
    int m = strlen(p), now = 0;
    for (int i = 0; i < m; ++i) {
      int c = p[i] - 'a';
      if (!trie[now][c]) trie[now][c] = ++tot;
      now = trie[now][c];
    }
    val[now] = id;
  }
  void getFail() {
    for (int i = 0; i < CS; ++i) {
      int u = trie[0][i];
      if (u) {
        fail[u] = 0;
        que.push(u);
      }
    }
    while (!que.empty()) {
      int cur = que.front();
      que.pop();
      for (int i = 0; i < CS; ++i) {
        int u = trie[cur][i];
        if (u) {
          fail[u] = trie[fail[cur]][i];
          que.push(u);
        } else {
          trie[cur][i] = trie[fail[cur]][i];
        }
      }
    }
  }
  void query(char *t) {
    int n = strlen(t), now = 0;
    for (int i = 0; i < n; ++i) {
      now = trie[now][t[i] - 'a'];
      int j = now;
      while (j) {
        if (val[j]) ++cnt[val[j]];
        j = fail[j];
      }
    } 
    int mx = 0;
    for (int i = 1; i <= n; ++i) mx = max(mx, cnt[i]);
    printf("%d\n", mx);
    for (int i = 1; i <= n; ++i) {
      if (cnt[i] == mx) puts(p[i]);
    }
  }
}AC;

线性基：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct LinearBasis {
  LL b[MAXL + 5];
  void insert(LL x) {
    for (int i = MAXL; ~i; --i) {
      if (x & (1LL << i)) {
        if (!b[i]) {
          b[i] = x;
          return;
        } else {
          x ^= b[i];
        }
      }
    }
  }
  LL query() {
    LL ret = 0;
    for (int i = MAXL; ~i; --i) ret = max(ret, (b[i] ^ ret));
    return ret;
  }
}LB;

左偏树：

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 Heap {
  int ls, rs, val, fa, dis;
}h[MAXN + 5];
struct LeftistHeap {
  #define u h[x]
  #define uls h[u.ls]
  #define urs h[u.rs]
  #define o h[y]
  LeftistHeap() {
    h[0].val = -1;
  }
  int find(int x) {
    return u.fa ? find(u.fa) : x;
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (u.val > o.val || (u.val == o.val && x > y)) swap(x, y);
    u.rs = merge(u.rs, y);
    urs.fa = x;
    if (uls.dis < urs.dis) swap(u.ls, u.rs);
    u.dis = urs.dis + 1;
    return x;
  }
  void delNode(int x) {
    u.val = -1;
    uls.fa = 0;
    urs.fa = 0;
  }
  int top(int x) {
    return u.val;
  }
  void del(int x) {
    delNode(x);
    merge(u.ls, u.rs);  
  }
  void build(int x, int v) {
    u.val = v;
  }
}SH;

非旋treap

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
struct Treap {
  int ls, rs, sz, key, val;
  bool rev;
  Treap() {}
}t[MAXN + 5];
struct FhqTreap {
  int tot;
  #define u t[x]
  #define uls t[u.ls]
  #define urs t[u.rs]
  #define o t[y]
  #define ols t[o.ls]
  #define ors t[o.rs]
  FhqTreap() {}
  void createNode(int x) {
    t[++tot].val = x;
    t[tot].sz = 1;
    t[tot].key = rand();
  }
  void upd(int x) {
    u.sz = uls.sz + urs.sz + 1;
  }
  void rev(int x) {
    u.rev ^= 1;
  }
  void pd(int x) {
    if (u.rev) {
      if (u.ls) rev(u.ls);
      if (u.rs) rev(u.rs);
      swap(u.ls, u.rs);
      u.rev ^= 1;
    }
  }
  pii split(int x, int n) {
    if (!n) return mp(0, x);
    pd(x);
    int m = uls.sz;
    if (n == m) {
      int tmp = u.ls;
      u.ls = 0;
      upd(x);
      return mp(tmp, x);
    } else if (n == m + 1) {
      int tmp = u.rs;
      u.rs = 0;
      upd(x);
      return mp(x, tmp);
    } else if (n < m) {
      pii tmp = split(u.ls, n);
      u.ls = tmp.se;
      upd(x);
      return mp(tmp.fi, x);
    }
    pii tmp = split(u.rs, n - m - 1);
    u.rs = tmp.fi;
    upd(x);
    return mp(x, tmp.se);
  }
  int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (u.key < o.key) {
      pd(x);
      u.rs = merge(u.rs, y);
      upd(x);
      return x;
    } else {
      pd(y);
      o.ls = merge(x, o.ls);
      upd(y);
      return y;
    }
  }
  void insert(int k, int x) {
    pii tmp = split(rt, k - 1);
    createNode(x);
    rt = merge(tmp.fi, merge(tot, tmp.se));
  }
  void rever(int x, int y) {
    pii tmp1 = split(rt, x - 1), tmp2 = split(tmp1.se, y - x + 1);
    t[tmp2.fi].rev ^= 1;
    rt = merge(merge(tmp1.fi, tmp2.fi), tmp2.se);
  }
  void print(int x) {
    if (!x) return;
    pd(x);
    print(u.ls);
    printf("%d ", u.val);
    print(u.rs);
  }
}T;

主席树：

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
struct ChairTree {
  struct Node {
    int ls, rs, sz;
  }s[MAXN * 60 + 5];
  int tot;
  #define lson s[p].ls
  #define rson s[p].rs
  ChairTree() {} 
  void insert(int &p, int l, int r, int x) {
    s[++tot] = s[p];
    p = tot;
    ++s[p].sz;
    if (l == r) return; 
    int mid = (l + r) >> 1;
    if (x <= mid) {
      insert(lson, l, mid, x);
    } else {
      insert(rson, mid + 1, r, x);
    }
  }
  int query(int rtl, int rtr, int l, int r, int k) {
    if (l == r) return l;
    int sz = s[s[rtr].ls].sz - s[s[rtl].ls].sz;
    int mid = (l + r) >> 1;
    if (k <= sz) {
      return query(s[rtl].ls, s[rtr].ls, l, mid, k);
    } else {
      return query(s[rtl].rs, s[rtr].rs, mid + 1, r, k - sz);
    }
  }
}CT;

LCT：

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
struct LinkCutTree {
  struct Node {
    int ch[2], fa;
    bool rev;
  }s[MAXN + 5];
  #define ls ch[0]
  #define rs ch[1]
  #define u s[x]
  #define uls s[u.ls]
  #define urs s[u.rs]
  #define ufa s[u.fa]
  #define o s[y]
  #define ols s[s[y].ls]
  #define ors s[s[y].rs]
  #define ofa s[s[z].fa]
  #define v s[z]
  #define vls s[s[z].ls]
  #define vrs s[s[z].rs]
  int top, st[MAXN + 5];
  void pd(int x) {
    if (u.rev) {
      u.rev ^= 1;
      uls.rev ^= 1;
      urs.rev ^= 1;
      swap(u.ls, u.rs);
    }
  }
  bool isRoot(int x) {
    return ufa.ls != x && ufa.rs != x;
  } 
  void rotate(int x) {
    int y = u.fa, z = o.fa, l, r;
    if (o.ls == x) {
      l = 0;
    } else {
      l = 1;
    }
    r = l ^ 1;
    if (!isRoot(y)) {
      if (v.ls == y) {
        v.ls = x;
      } else {
        v.rs = x;
      }
    }
    u.fa = z;
    o.fa = x;
    s[u.ch[r]].fa = y;
    o.ch[l] = u.ch[r];
    u.ch[r] = y;
  }
  void splay(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isRoot(i); i = s[i].fa) {
      st[++top] = s[i].fa;
    }
    for (int i = top; i; --i) pd(st[i]);
    while (!isRoot(x)) {
      int y = u.fa, z = o.fa;
      if (!isRoot(y)) {
        if (v.ls == y ^ o.ls == x) {
          rotate(x);
        } else {
          rotate(y);
        }
      }
      rotate(x);
    }
  }
  void access(int x) {
    for (int last = 0; x; last = x, x = u.fa) {
      splay(x);
      u.rs = last;
    }
  }
  void makeRoot(int x) {
    access(x);
    splay(x);
    u.rev ^= 1;
  }
  void link(int x, int y) {
    makeRoot(x); 
    u.fa = y;
  }
}LCT;

后缀数组：

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
bool cmp(int i, int j, int k) {
  return y[i] == y[j] && y[i + k] == y[j + k];
}
void getSA(int m) {
  for (int i = 1; i <= m; ++i) b[i] = 0;
  for (int i = 1; i <= n; ++i) ++b[x[i] = r[i]];
  for (int i = 1; i <= m; ++i) b[i] += b[i - 1];
  for (int i = n; i; --i) sa[b[x[i]]--] = i;
  for (int k = 1; k <= n; k <<= 1) {
    int p = 0;
    for (int i = n - k + 1; i <= n; ++i) y[++p] = i;
    for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++p] = sa[i] - k;
    for (int i = 1; i <= m; ++i) b[i] = 0;
    for (int i = 1; i <= n; ++i) ++b[x[y[i]]];
    for (int i = 1; i <= m; ++i) b[i] += b[i - 1];
    for (int i = n; i; --i) sa[b[x[y[i]]]--] = y[i];
    swap(x, y);
    p = 1, x[sa[1]] = 1;
    for (int i = 2; i <= n; ++i) x[sa[i]] = cmp(sa[i], sa[i - 1], k) ? p : ++p;
    m = p;
    if (m == n) break;
  }
}
void getHeight() {
  int k = 0;
  for (int i = 1; i <= n; ++i) rk[sa[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (k) --k;
    int j = sa[rk[i] - 1];
    while (r[i + k] == r[j + k]) ++k;
    height[rk[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
struct SuffixAutomaton {
  int last, tot;
  int trans[MAXN + 5][CS], link[MAXN + 5], len[MAXN + 5], sz[MAXN + 5];
  int id[MAXN + 5], pre[MAXN + 5];
  SuffixAutomaton() : last(1), tot(1) {}
  void extend(int x) {
    int c = x - 'a', cur = ++tot, p = last;
    len[cur] = len[last] + 1;
    while (p && !trans[p][c]) {
      trans[p][c] = cur;
      p = link[p];
    }
    if (!p) {
      link[cur] = 1;
    } else {
      int q = trans[p][c];
      if (len[p] + 1 == len[q]) {
        link[cur] = q;
      } else {
        int nq = ++tot;
        len[nq] = len[p] + 1;
        memcpy(trans[nq], trans[q], sizeof(trans[q]));
        while (p && trans[p][c] == q) {
          trans[p][c] = nq;
          p = link[p];
        }
        link[nq] = link[q];
        link[q] = nq;
        link[cur] = nq;
      }
    }
    sz[cur] = 1;
    last = cur;
  }
}SAM;

树链剖分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void buildTree(int u) {
  depth[u] = depth[fa[u]] + 1;
  sz[u] = 1;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v != fa[u]) {
      fa[v] = u;
      buildTree(v);
      sz[u] += sz[v];
      if (sz[son[u]] < sz[v]) son[u] = v;
    }
  }
}
void buildChain(int u, int topf) {
  top[u] = topf;
  id[u] = ++cnt;
  mp[id[u]] = u;
  if (!son[u]) return;
  buildChain(son[u], topf);
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v != fa[u] && v != son[u]) buildChain(v, v);
  }
}

图论

spfa：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void spfa(const int s) {
  memset(d, 0x3f, sizeof(d));
  que.push(s);
  d[s] = 0;
  in_que[s] = true;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    in_que[u] = false;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        if (!in_que[v]) {
          in_que[v] = true;
          que.push(v);
        }
      }
    }
  }
}

dijkstra：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dijkstra(const int s) {
  memset(d, 0x3f, sizeof(d));
  Q.push(Node(s, 0));
  d[s] = 0;
  while (!Q.empty()) {
    int u = Q.top().u;
    Q.pop();
    if (vis[u]) continue;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        if (!vis[v]) Q.push(Node(v, d[v]));
      }
    }
    vis[u] = true;
  }
}

prim：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int prim(const int s) {
  memset(d, 0x3f, sizeof(d));
  Q.push(HeapNode(s, 0));
  d[s] = 0;
  int cnt = 0, ret = 0;
  while (!Q.empty()) {
    int u = Q.top().u;
    Q.pop();
    if (vis[u]) continue;
    ++cnt;
    ret += d[u];
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[v] > w) {
        d[v] = w;
        if (!vis[v]) Q.push(HeapNode(v, w));
      }
    }
    vis[u] = true;
  }
  return cnt < n ? -1 : ret;
}

kruskal：

1
2
3
4
5
6
7
8
9
10
11
12
13
int kruskal() {
  sort(e + 1, e + 1 + m);
  int ret = 0, cnt = n;
  for (int i = 1; i <= m; ++i) {
    int u = e[i].u, v = e[i].v, w = e[i].w;
    if (DSU.find(u) != DSU.find(v)) {
      DSU.unionSet(u, v);
      ret += w;
      --cnt;
    }
  }
  return cnt == 1 ? ret : -1;
}

倍增求LCA：

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
void buildTree(int u, int fa) {
  an[u][0] = fa;
  depth[u] = depth[fa] + 1;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (v == fa) continue;
    buildTree(v, u);
  }
}
int LCA(int u, int v) {
  if (depth[u] < depth[v]) swap(u, v);
  int k = depth[u] - depth[v];
  for (int i = 0; (1 << i) <= k; ++i) {
    if (k & (1 << i)) u = an[u][i];
  }
  if (u == v) return u;
  for (int i = MAXL - 1; ~i; --i) {
    if (an[u][i] != an[v][i]) {
      u = an[u][i];
      v = an[v][i];
    }
  }
  return an[u][0];
}
void init() {
  //enableFileIO();
  tot = 0;
  memset(head, -1, sizeof(head));
  n = read();
  m = read();
  rt = read();
  for (int i = 1; i < n; ++i) {
    int u = read(), v = read();
    add(u, v);
  }
  buildTree(rt, 0);
  for (int i = 1; i < MAXL; ++i) {
    for (int u = 1; u <= n; ++u) {
      an[u][i] = an[an[u][i - 1]][i - 1];
    }
  }
}

二分图匹配:

1
2
3
4
5
6
7
8
9
10
11
12
13
bool hungary(int u) {
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!vis[v]) {
      vis[v] = true;
      if (!res[v] || hungary(res[v])) {
        res[v] = u;
        return true;
      }
    }
  }
  return false;
}

求无向图割点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void tarjan(int u) {
  dfn[u] = low[u] = ++ind;
  int sum = 0;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (dfn[u] <= low[v]) {
        ++sum;
        if (u != rt || sum > 1) is_cut[u] = true;
      }
    } else {
      low[u] = min(low[u], dfn[v]);
    }
  }
}

spfa判负环：

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
bool spfa(const int s) {
  memset(d, 0x3f, sizeof(d));
  memset(in_que, false, sizeof(in_que));
  memset(cnt, 0, sizeof(cnt));
  que.push(s);
  in_que[s] = true;
  d[s] = 0;
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    in_que[u] = false;
    for (int i = head[u]; ~i; i = edge[i].nxt) {
      int v = edge[i].to, w = edge[i].w;
      if (d[u] + w < d[v]) {
        d[v] = d[u] + w;
        cnt[v] = cnt[u] + 1;
        if (cnt[v] >= n) return false;
        if (!in_que[v]) {
          que.push(v);
          in_que[v] = true;
        }
      }
    }
  }
  return true;
}

tarjan缩点：

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
void tarjan(int u) {
  dfn[u] = low[u] = ++ind;
  sta.push(u);
  in_sta[u] = true;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_sta[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (low[u] == dfn[u]) {
    int k;
    sum[++scc_num] = 0;
    do {
      k = sta.top();
      belong[k] = scc_num;
      sum[scc_num] += val[k];
      in_sta[k] = false;
      sta.pop();
    } while (k != u);
  }
}

拓扑排序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void topsort() {
  for (int i = 1; i <= scc_num; ++i) { 
    if (!in[i]) {
      d[i] = sum[i];
      que.push(i);
    }
  }
  while (!que.empty()) {
    int u = que.front();
    que.pop();
    for (int i = h[u]; ~i; i = e[i].nxt) {
      int v = e[i].to;
      d[v] = max(d[v], d[u] + sum[v]);
      if (!--in[v]) que.push(v);
    }
  }
}

dinic求最大流：

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
struct Dinic {
  int level[MAXN + 5], cur[MAXN + 5];
  queue<int> que;
  bool makeLevelGraph(const int s, const int t) {
    memset(level, 0, sizeof(level));
    while (!que.empty()) que.pop();
    que.push(s);
    level[s] = 1;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to, cap = edge[i].cap;
        if (cap && !level[v]) {
          level[v] = level[u] + 1;
          que.push(v);
        }
      }
      if (level[t]) return true;
    }
    return false;
  }
  int findAugPath(int u, int t, int flow) {
    if (u == t || !flow) return flow;
    int used = 0;
    for (int &i = cur[u]; ~i && used < flow; i = edge[i].nxt) {
      int v = edge[i].to, &cap = edge[i].cap, &rcap = edge[i ^ 1].cap;
      if (cap && level[v] == level[u] + 1) {
        int d = findAugPath(v, t, min(flow - used, cap));
        if (d) {
          used += d;
          rcap += d;
          cap -= d;
          return d;
        } else {
          level[v] = -INF;
        }
      }
    }
    return 0;
  }
  int operator()(const int s, const int t) {
    int ret = 0, f;
    while (makeLevelGraph(s, t)) {
      memcpy(cur, head, sizeof(head));
      while (f = findAugPath(s, t, INF)) ret += f;
    }
    return ret;
  }
}dinic;

最小费用最大流：

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
struct Mfmc {
  int d[MAXN + 5], pre[MAXN + 5], id[MAXN + 5];
  queue<int> que;
  bool in_que[MAXN + 5];
  bool spfa(const int s, const int t) {
    memset(d, 0x3f, sizeof(d));
    memset(pre, -1, sizeof(pre));
    que.push(s);
    d[s] = 0;
    pre[s] = 0;
    in_que[s] = true;
    while (!que.empty()) {
      int u = que.front();
      que.pop();
      in_que[u] = false;
      for (int i = head[u]; ~i; i = edge[i].nxt) {
        int v = edge[i].to, cap = edge[i].cap, cost = edge[i].cost;
        if (cap && d[u] + cost < d[v]) {
          d[v] = d[u] + cost;
          pre[v] = u;
          id[v] = i;
          if (!in_que[v]) {
            in_que[v] = true;
            que.push(v);
          }
        }
      }
    }
    return ~pre[t];
  }
  pii operator()(const int s, const int t) {
    int min_cost = 0, max_flow = 0;
    while (spfa(s, t)) {
      int f = INF;
      for (int u = t; u != s; u = pre[u]) f = min(f, edge[id[u]].cap);
      for (int u = t; u != s; u = pre[u]) {
        edge[id[u]].cap -= f;
        edge[id[u] ^ 1].cap += f;
      }
      max_flow += f;
      min_cost += f * d[t];
    }
    return mp(max_flow, min_cost);
  }
}mfmc;

2-sat：

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
stack<int> sta;
bool in_sta[MAXN + 5];
int dfn[MAXN + 5], low[MAXN + 5], idx, scc_num, belong[MAXN + 5];
void tarjan(int u) {
  dfn[u] = low[u] = ++idx;
  sta.push(u);
  in_sta[u] = true;
  for (int i = head[u]; ~i; i = edge[i].nxt) {
    int v = edge[i].to;
    if (!dfn[v]) {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    } else if (in_sta[v]) {
      low[u] = min(low[u], dfn[v]);
    }
  }
  if (dfn[u] == low[u]) {
    int k;
    ++scc_num;
    do {
      k = sta.top();
      belong[k] = scc_num;
      in_sta[k] = false;
      sta.pop();
    } while (k != u);
  }
}
int n, m;
void init() {
  //enableFileIO();
  tot = 0;
  memset(head, -1, sizeof(head));
  n = read();
  m = read();
  for (int i = 1; i <= m; ++i) {
    int u = read(), a = read(), v = read(), b = read();
    if (a && b) {
      add(u + n, v);
      add(v + n, u);
    } else if (!a && b) {
      add(v + n, u + n);
      add(u, v);
    } else if (a && !b) {
      add(u + n, v + n);
      add(v, u);
    } else {
      add(u, v + n);
      add(v, u + n);
    }
  }
}
int main() {
  init();
  for (int i = 1; i <= 2 * n; ++i) {
    if (!dfn[i]) tarjan(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (belong[i] == belong[i + n]) {
      puts("IMPOSSIBLE");
      return 0;
    }
  }
  puts("POSSIBLE");
  for (int i = 1; i <= n; ++i) {
    printf("%d ", belong[i] < belong[i + n]);
  }
  printf("\n");
  return 0;
}

数论

快速幂：

1
2
3
4
5
6
7
8
9
10
LL fastPow(LL b, LL p, LL m) {
  LL ret = 1;
  b %= m;
  while (p) {
    if (p & 1) ret = ret % m * b % m;
    b = b % m * b % m;
    p >>= 1;
  }
  return ret % m;
}

埃氏筛：

1
2
3
4
5
6
for (int i = 2; i <= n; ++i) {
    if (c[i]) continue;
    for (int j = i; j <= n / i; ++j) {
      c[i * j] = true;
    }
  }

求1-n的phi值

1
2
3
4
5
6
7
8
for (int i = 2; i <= n; ++i) phi[i] = i;
for (int i = 2; i <= n; ++i) {
  if (phi[i] == i) {
    for (int j = i; j <= n; j += i) {
      phi[j] = phi[j] / i * (i - 1);
    }
  }
}

求1-n的所有约数

1
2
3
4
5
for (int i = 1; i <= n; ++i) {
  for (int j = 1; j <= n / i; ++j) {
    fac[i * j].push_back(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
29
30
31
32
33
34
35
36
37
38
struct Matrix {
  LL a[MAXN + 5][MAXN + 5];
  int n, m;
  Matrix() {}
  Matrix(int _n, int _m) : n(_n), m(_m) {
    memset(a, 0, sizeof(a));
  }
  void operator() (int _n, int _m) {
    n = _n;
    m = _m;
    memset(a, 0, sizeof(a));
  }
  void init() {
    memset(a, 0, sizeof(a));
    for (int i = 1; i <= n; ++i) a[i][i] = 1;
  }
  Matrix operator * (const Matrix &mat) {
    Matrix ret(n, m);
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        for (int k = 1; k <= mat.n; ++k) {
          ret.a[i][j] = (ret.a[i][j] + a[i][k] * mat.a[k][j]) % MOD;
        }
      }
    }
    return ret;
  }
}a;
Matrix fastPow(Matrix mat, LL k) {
  Matrix ret(mat.n, mat.m);
  ret.init();
  while (k) {
    if (k & 1) ret = ret * mat;
    mat = mat * mat;
    k >>= 1;
  }
  return ret;
}

线性求逆元：

1
2
3
4
5
6
7
int main() {
  init();
  ans[1] = 1;
  for (int i = 2; i <= n; ++i) ans[i] = 1LL * (p - p / i) * ans[p % i] % p;
  for (int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
  return 0;
}

快速乘：

1
2
3
4
5
6
7
8
9
LL fastMul(LL b, LL p, LL m) {
  LL ret = 0;
  while (p) {
    if (p & 1) ret = (ret + b) % m;
    b = (b + b) % m;
    p >>= 1;
  }
  return ret;
}

拓展欧几里得：

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

拓展中国剩余定理：

1
2
3
4
5
6
7
8
9
10
11
12
13
LL excrt(LL *a, LL *m) {
  LL ret = m[1], lcm = a[1], x, y;
  for (int i = 2; i <= n; ++i) {
    m[i] = (m[i] - ret % a[i] + a[i]) % a[i];
    LL g = exgcd(lcm, a[i], x, y);
    if (m[i] % g) return -1;
    LL k = fastMul(x, m[i] / g, a[i]); //x * m[i] / g % a[i];
    ret += k * lcm;
    lcm = lcm / g * a[i];
    ret = (ret % lcm + lcm) % lcm;
  }
  return ret;
}

发表于

算任意四点的贡献
① 如果这四个点构成的是凹四边形：
四种圆中除了在圆上的三点之外，只有一种圆会包含剩余一个点，所以一个凹四边形对答案贡献为1。
② 构成的是凸多边形：
四种圆中有两种圆会包含剩余的一个点（被包含的点分别是对角和大于180°的两个点），因此一个凸四边形对答案的贡献为2。
s=凹四边形个数+2*凸四边形个数，答案为$3+\frac {s}{ n\choose 3}$

发表于

加一条边形成一个环，环上的边可以少走一次
k=1时直接找直径
k=2时先找一条直径，连一条边，此时如果再要经过这个环上的边，答案要加2，所以将之前找的边置为-1再找一次直径（简单证明：1)如果答案包含一条直径：注意到第一次找直径的时候可能存在多条。假如存在一条直径与第一次选的直径没有边交集，第二次就会选择那一条；假如所有直径都与它有边交集，注意到有交集的直径都是相同的（不管是点交集还是边交集），不然存在更长的链，所以随便选的那一条没有问题。2)答案不包含直径。这是不可能的。如果选的两条都不经过直径，则将一条换成直径更优；如果选的有一条经过直径，则换成直径更优；如果两条都经过直径，可以换成一条直径加一个环，答案不会更劣。）

阅读全文 »

发表于

cf上用random_shuffle挂了
看来随机化还是要好好了解一下

头文件从c++11起

time相关：
std::time
定义于头文件
std::time_t time( std::time_t* arg );

CLOCKS_PER_SEC
定义于头文件

#define CLOCKS_PER_SEC /implementation defined/
展开成 std::clock_t 类型表达式，值等于每秒 std::clock() 所返回的时钟计次数（不必是编译时常量）。

std::clock
定义于头文件
std::clock_t clock();
返回进程从关联到程序执行的实现定义时期开始，所用的粗略处理器时间。为转换结果为秒，可将它除以 CLOCKS_PER_SEC 。

ftime()
定义于头文件
函数定义：void ftime(struct timeb *tp);
函数说明：ftime()将目前日期由tp所指的结构体返回。

1
2
3
4
5
6
struct timeb{
    time_t time;   /* 为1970-01-01至今的秒数*/
    unsigned short millitm; /* 千分之一秒即毫秒 */
    short timezone;  /* 为目前时区和Greenwich相差的时间，单位为分钟 */
    short dstflag;   /* 为日光节约时间的修正状态，如果为非0代表启用日光节约时间修正 */
};

c&c++03的随机化：
std::srand
定义于头文件
void srand( unsigned seed );
注意：
通常来说，应该只播种一次随机数生成器，在程序开始出，任何到 rand() 的调用前。不应重复播种，或每次冀愿生成新一批随机数时重播种。
标准实践是使用以 time(0) 为种子调用的结果。然而 time() 返回 time_t 值，而不保证 time_t 是整数类型。尽管实践中，主流实现都定义 time_t 为整数类型，且此亦为 POSIX 所要求。
1.srand(time(0)); //time();
2.srand(tim.time*1000+tim.millitm); //ftime();

RAND_MAX（保证此值至少为 32767）
win下32767，linux下2147483647

std::rand
定义于头文件
int rand();
返回 0 与 RAND_MAX （包含 0 与 RAND_MAX ）的随机数。
推荐用 C++11 的随机数生成设施替换 rand() 。 (C++11 起)

random_shuffle
定义于头文件
基于rand()
类似的实现：

1
2
3
4
5
6
7
template<typename T> IL void random_shuffl(T first,T last)
{
	int n=last-first;
	for(int i=1;i<n;++i){
		swap(*(first+i),*(first+rand()%(i+1)));	
	}
}

由于rand()有可能太小，移动的偏差可能很小（cf上的测试，3e6的数列，每个值平均移动2%，期望移动是1/3）
自己手写random_shuffle:

1
2
3
4
5
6
7
8
9
10
11
IL int ra()
{
	return (rand()<<15)+rand();	
}
template<typename T> IL void random_shuffl(T first,T last)
{
	int n=last-first;
	for(int i=1;i<n;++i){
		swap(*(first+i),*(first+ra()%(i+1)));	
	}
}

c++11起可以使用mt19937作为更优质的随机数生成器替代rand()
定义于头文件
mt19937:32位梅森缠绕器
mt19937_64:64位梅森缠绕器
成员函数：

构造与播种：

  • (构造函数)：构造引擎 (公开成员函数)
  • seed：设置引擎的当前状态 (公开成员函数)

生成：

  • operator()：令引擎状态向前并返回生成值 (公开成员函数)

特征：

  • min[静态]：获取输出范围中的最小可能值 (公开静态成员函数)
  • max[静态]：获取输出范围中的最大可能值 (公开静态成员函数)

例：

1
2
3
4
5
mt19937 mt;
mt.seed(/*随机数种子*/); // 或者在定义时mt19937 mt(/*随机数种子*/);
mt.min();mt.max();      // 0 2^32-1
mt();                   // 返回[min(),max()]中的随机数
//mt19937_64就是[0,2^64-1]的随机数生成器

发表于

退役了就学学数论吧
退役后的第一场cf（话说已经半年没打cf了
536f(1106)题是矩乘+bsgs

发现我什么都不会
先贴一些基础的模块吧

求原根：
一个数m有原根的充要条件是m=1,2,4,p^e,2p^e, 其中p为奇素数， e为正整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
IL int primitive_rt(int p)//p是奇素数 
{
	int phi=p-1;//p不是素数就改成求phi
	vector<int> fact;
	for(int i=2;i*i<=phi;++i){
		if(phi%i==0){
			fact.pb(i);
			while(p%i==0)	phi/=i;	
		}
	}
	if(phi>1)	fact.pb(phi);
	phi=p-1;
	for(int i=2;i<p;++i){
		bool ok=1;
		for(int j=0;j<fact.size();++j){
			if(ksm(i,phi/fact[j],p)==1){
				ok=0;break;	
			}
		}
		if(ok)	return i;
	}
	return -1;
}

求（一个）离散对数：
//求所有的把map改成map即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
IL int bsgs(int a,int b,int p)//calc x which a^x=b(mod p), (a,p)=1
{
	unordered_map<int,int> ma;
	ma.clear();
	int t=round(sqrt(p))+1;
	//多求一些x不影响答案 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp]=i;
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=1;
	for(int i=0;i<=t;++i){
		int j=ma.find(tmp)==ma.end()?-1:ma[tmp];
		if(j>=0&&i*t-j>=0){
			return i*t-j;	
		}
		tmp=LL(tmp)*c%p;	
	}
	return -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
IL int exbsgs(int a,int b,int p)//a和p不一定互质
{
	a%=p;b%=p;
	if(b==1)	return 0;
	int v=1,d,cnt=0;
	while((d=gcd(a,p))>1){
		if(b%d)	return -1;
		b/=d;p/=d;++cnt;
		v=LL(v)*a/d%p;
		if(v==b)	return cnt;	//去掉也是对的 
	}
	unordered_map<int,int> ma;
	ma.clear();
	int t=round(sqrt(p))+1;
	//多求一些x不影响答案 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp]=i;
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=v;
	for(int i=0;i<=t;++i){
		int j=ma.find(tmp)==ma.end()?-1:ma[tmp];
		if(j>=0&&i*t-j>=0){
			return i*t-j+cnt;	
		}
		tmp=LL(tmp)*c%p;	
	}
	return -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
43
int ans[100008],ta;
IL void solve(int a,int b,int p)//calc all x which x^a=b(mod p)
{
	int g=primitive_rt(p);
	a=ksm(g,a,p); 
	unordered_map<int,vector<int> > ma;
	ma.clear();
	int t=round(sqrt(p))/2+1;//调块大小过 
	int tmp=b;
	for(int i=0;i<=t;++i){
		ma[tmp].pb(i);
		tmp=LL(tmp)*a%p;
	}
	int c=ksm(a,t,p);
	tmp=1;
	ta=0;
	int up=p/t+1;//调过块大小要改up 
	for(int i=0;i<=up;++i){
		if(ma.find(tmp)!=ma.end()){
			vector<int> v=ma[tmp];
			for(int j=0;j<v.size();++j){
				int x=i*t-v[j];
				if(x>=0&&x<p-1){
					ans[++ta]=x;	
				}
			}
		}
		tmp=LL(tmp)*c%p;	
	}
	if(ta==0){
		puts("No Solution");	
		return;
	}
	for(int i=1;i<=ta;++i){
		ans[i]=ksm(g,ans[i],p);	
	}
	sort(ans+1,ans+ta+1);
	ta=unique(ans+1,ans+ta+1)-ans-1;
	for(int i=1;i<=ta;++i){
		printf("%d ",ans[i]);	
	}
	putchar('\n');
}