个人板子总结

acm 板子
个人板子总结
发布日期:   2022-04-22
文章字数:   9.3k

一个自己经常使用的板子的汇总

主要是为了自己在需要用的时候能够很快找到对应的板子而写下本篇。

字符串

字符串小日记

  1. 有种非常妙的思路：后缀转前缀

    具体：把字符串 reverse ，再 insert 到 Trie 树里，可模拟后缀。

  2. 一定要看清楚题目！！！！！！！

    一定要看清楚模式串中间有没有重复的串！！！

  3. 一定要看清楚具体每个字符串的数据范围，一般 MAXX 表示有几个串，但是最后的文本串可能会是 $1e6$ 的。

  4. 感觉字符串的题目一般很难直接抄板子，除了一些固定的步骤， 一般都要从头手打一遍 ，因为每次题目中的要求，条件等等都会变，一定要深度理解算法的思想，到时候做题才能更灵活。

  5. 字符串的题目灵活性太高了，可以试试从多个不同的角度进行思考。感觉很多题目都是会有很多种解法(优化方法)。

  6. 如果有时间的话，一定要多复习复习前面学过的内容，这些东西太容易忘了。

  7. 要多变通，不要死磕一种死方法。

一些常用结论和技巧

  1. 一个长度为 $n$ 的字符串一共有 $\frac{n(n+1)}{2}$ 个子串。

  2. 字符串中重复了的子串的个数等于 $\sum_{i=1}^{n} height[i]$ ，故一个字符串的所有不同子串个数就等于

    $\frac{n(n+1)}{2}-\sum_{i=1}^{n} height[i]$ 。

  3. 多次询问字串 $s(l,r)$ 的出现次数

    二分+$SA$

  4. 最长重复子串（可重叠）

    $ans=\max{height[i]}$

  5. 两个字符串的最长公共子串

    记录每一次的公共子串的长度

    大致思路为下图，对角线即为重复子串。

    img

    1
    2
    3
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            len[i][j]=((a[i]==s[j])?(len[i-1][j-1]+1):(0));

  6. waiting

SAM使用技巧

  1. 在 $SAM$ 中 $len[i]-len[fa[i]]$ 表示 $sam[i]$ 中表示了几个字符串。

  2. 记录每个子串的出现次数(求 $|Right[s]|$ )

    • 在 add 模板中要有初始化 $num[np]=1$ 。
    • 构造出 parent树 。
    • 直接 dfs 。

    例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    vector<int> to[MAXX<<1];
    void dfs(int now){
    	for(int jj:to[now]){
    		dfs(jj);
    		num[now]+=num[jj];
    	}
    }
    for(int i=1;i<=sam_cnt;++i)
        to[sam[i].fa].emplace_back(i);
    dfs(1);

  3. 多少个本质不同的子串

    • 在 $SAM$ 上从根节点开始的每一条路径都是一个子串且不重复，故直接在 $SAM$ 上跑 $DP$ 即可。

    例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    LL ans[MAXX<<1];
    LL dfs(int now){
    	if(ans[now]) return ans[now];
    	for(int i=0;i<26;++i)
    		if(sam[now].ch[i])
    			ans[now]+=dfs(sam[now].ch[i]);
    	return ++ans[now];
    }
    printf("%lld\n",dfs(1)-1);

  4. 两个字符串的本质不同公共子串个数

    • 两个字符串依此插入到同一个 $sam$ 中，但是，每开始一个新的子串，就得将 $las=1$ ，达到从这个字符串的开头开始的效果。
    • $add$ 操作也要加一个标记，在结构体中新加变量 $bool\ vis[2]$ ，用于标记在哪个串中出现过没有。
    • 在 $add$ 函数最后一行加上 for(;np&&!sam[np].vis[jj];np=sam[np].fa) sam[np].vis[jj]=true; ，即可达到标记的效果。
    • 最后遍历一遍 $sam$ 中的每一个点，如果这个点表示的状态的 $vis[0]==true&&vis[1]==true$ ，就 $ans+=sam[i].len-sam[sam[i].fa].len$。

    例子：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    void add(int c,int jj){
    	...
        for(;np&&!sam[np].vis[jj];np=sam[np].fa) sam[np].vis[jj]=true;
    }

    inline void solve(){
    	for(int i=1;i<=2;++i){
    		scanf("%s",s+1);getchar();
    		n=strlen(s+1);
    		las=1;
    		for(int j=1;j<=n;++j)
    			add(s[j]-'a',i-1);
    	}
    	
    	for(int i=1;i<=sam_cnt;++i)
    		if(sam[i].vis[0]&&sam[i].vis[1])
    			ans+=sam[i].len-sam[sam[i].fa].len;
    	
    	printf("%lld\n",ans);
    }

  5. 如果有多个匹配串与一个模式串进行子串匹配，那么可以只对模式串进行建立 $SAM$ ，之后对于每一个匹配串，使用类似于 $trie树$ 的匹配方式进行匹配。之后可以使用动态规划的思想，搞出最长匹配长度。

  6. 对于有 $m$ 次操作且 $m$ 很大且会改变原字符串的情况，我们可以考虑定期重构。

    设 $T=\sqrt n$ ，每 $T$ 次添加或删除字符操作后，就重构 $SAM$ 。对于还没有来得及重构的询问，我们使用字符串 $Hash$ 来进行解决。

    对于对字符串前面添加新字符还是前面删除字符都适用。

KMP模板

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
char l[MAXX],s[MAXX];
int lenl,lens,p[MAXX];

void getpmt(){
	p[1]=0;
	for(int i=1,j=0;i<lens;++i){
		while(j>0&&s[i+1]!=s[j+1])
			j=p[j];
		if(s[i+1]==s[j+1])
			++j;
		p[i+1]=j;
	}
}

void getans(){
	for(int i=0,j=0;i<lenl;++i){
		while(j>0&&l[i+1]!=s[j+1])
			j=p[j];
		if(l[i+1]==s[j+1])
			++j;
		if(j==lens){
			//dosomething
			printf("%d\n",i-j+2);
			//
			j=p[j];
		}
	}
}

KMP求最小循环节

1
2
3
4
//首先要求出p数组（即next数组）
//字符串长度为len
//循环节的长度为
int l=len-p[len];

KMP求所有循环节

1
2
3
4
5
int jj=p[n];
while(jj!=0){
    ans.emplace_back(n-jj);//这里的 n-jj 均为循环节，ans记录所有循环节
    jj=p[jj];
}

前缀函数自动机？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int n;
char s[MAXX];
//fail数组即为pmt数组,ch数组表示转移
int fail[MAXX],ch[MAXX][26];

ch[0][s[1]-'a']=1;
for(int i=2;i<=n;++i){
    for(int j=0;j<26;++j){
        if(s[i]-'a'==j){
            ch[i-1][j]=i;
            fail[i]=ch[fail[i-1]][j];
        }
        else
            ch[i-1][j]=ch[fail[i-1]][j];
    }
}

扩展KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//int z[MAXX],p[MAXX];
void Z(char* s,int n){
	z[1]=n;
	for(int i=2;i<=n;++i) z[i]=0;
	for(int i=2,l=0,r=0;i<=n;++i){
		if(i<=r) z[i]=min(z[i-l+1],r-i+1);
		while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1]) ++z[i];
		if(i+z[i]-1>r) l=i,r=i+z[i]-1;
	}
}

void exkmp(char* a,int n,char* s,int m){
	Z(s,m);
	for(int i=1;i<=n;++i) p[i]=0;
	for(int i=1,l=0,r=0;i<=n;++i){
		if(i<=r) p[i]=min(z[i-l+1],r-i+1);
		while(i+p[i]<=n&&a[i+p[i]]==s[p[i]+1]) ++p[i];
		if(i+p[i]-1>r) l=i,r=i+p[i]-1;
	}
}
//exkmp(a,n,s,m);

字符串 $Hash$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef unsigned long long ull;
//prim 是自己设置的一个素数,具体数值根据情况而定
ull p[MAXX],hashs[MAXX],prim=233;

inline void init(){
    p[0]=1ull;
    for(int i=1;i<MAXX;++i)
        p[i]=p[i-1]*prim;
}
inline ull gethash(int l,int r){
    return hashs[r]-hashs[l-1]*p[r-l+1];
}
inline bool check(int l,int r,ull jj){
    return gethash(l,r)==jj;
}
// for(int i=1;i<=n;++i)
//     hashs[i]=hashs[i-1]*prim+s[i];

Trie树(字典树)

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
/*
Trie树更重要的是思路
碰到题目一般不会直接这样考模板
要灵活变通
*/
class Trie{
private:
	const static int maxid=MAXX*50;
	int trie[maxid][26],id_cnt;
	bool is_word[maxid];
public:
	Trie();
	void insert(char* jj);
	bool find(char* jj);
};
Trie::Trie(){
	for(int i=0;i<maxid;++i)
		for(int j=0;j<26;++j)
			trie[i][j]=0;
	id_cnt=0;
	for(int i=0;i<maxid;++i)
		is_word[i]=false;
}
void Trie::insert(char* jj){
	int now=0,len=strlen(jj+1);
	for(int i=1;i<=len;++i){
		if(trie[now][jj[i]-'a']==0)
			trie[now][jj[i]-'a']=++id_cnt;
		now=trie[now][jj[i]-'a'];
	}
	is_word[now]=true;
}
bool Trie::find(char* jj){
	int now=0,len=strlen(jj+1);
	for(int i=1;i<=len;++i){
		if(trie[now][jj[i]-'a']==0)
			return false;
		now=trie[now][jj[i]-'a'];
	}
	return is_word[now];
}

Border树(next树) 概念及性质

概念

一个字符串长度为 $n$ 。

在 Border 树中，共有 $n+1$ 个节点， $0$ 是这棵有向树的根节点，对于其他每个点 $1 \le i \le n$ ，父节点为 $next[i]$ 。

性质

  1. 每个前缀 $Prefix[i]$ 的所有 $Border$ : 节点 $i$ 到根的链。
  2. 哪些前缀有长度为 $x$ 的 $Border$ : $x$ 的子树。
  3. 求两个前缀的公共 $Border$ 等价于求 $LCA$ 。

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
62
63
64
65
66
67
68
69
70
struct ACAM{
	static const int id_max=MAXX*2;
	struct Node{
		int ch[26],len;
		int fail,las;
		LL val;
		Node(){
			for(int i=0;i<26;++i)
				ch[i]=0;
			len=fail=las=0;
			val=0;
		}
	}trie[id_max];
	int id_cnt;

	ACAM(){
		for(int i=0;i<id_cnt;++i)
			trie[i]=Node();
		id_cnt=0;
	}

	void ins(char s[],LL val){
		int now=0,len=strlen(s+1);
		for(int i=1;i<=len;++i){
			if(trie[now].ch[s[i]-'a'])
				now=trie[now].ch[s[i]-'a'];
			else
				now=trie[now].ch[s[i]-'a']=++id_cnt;
		}
		trie[now].len=len;
		trie[now].val=val;
	}

	void bfs(){
		queue<int> qq;
		for(int i=0;i<26;++i)
			if(trie[0].ch[i])
				qq.emplace(trie[0].ch[i]);
		while(!qq.empty()){
			int now=qq.front();qq.pop();
			for(int i=0;i<26;++i){
				if(trie[now].ch[i]){
					trie[trie[now].ch[i]].fail=trie[trie[now].fail].ch[i];
					qq.emplace(trie[now].ch[i]);
					if(trie[trie[trie[now].fail].ch[i]].len)
						trie[trie[now].ch[i]].las=trie[trie[now].fail].ch[i];
					else
						trie[trie[now].ch[i]].las=trie[trie[trie[now].fail].ch[i]].las;
				}
				else
					trie[now].ch[i]=trie[trie[now].fail].ch[i];
			}
		}
	}

	void solve(char s[]){
		int len=strlen(s+1);
		int now=0;
		for(int i=1;i<=len;++i){
			now=trie[now].ch[s[i]-'a'];
			int jj=now;
			while(jj){
				/*
				do something
				*/
				jj=trie[jj].las;
			}
		}
	}
}ac;

manacher

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
//需事先定义好 char s[MAXX],a[MAXX*2]; 
//和 int ans[MAXX*2]; 
//s串是原字符串，a串用来存改变后的字符串，在该函数里面有实现
//ans存改变后的串的以i为中心的最长的回文串的回文半径 
//返回值为最长回文半径（对于原字符串来说） 
int manacher(){
	int lens=strlen(s+1);
	int len=0;
	a[0]='@';a[1]='#';
	for(int i=0;i<=lens;++i){
		a[len++]=s[i];
		a[len++]='#';
	}
	a[len]='%';
	
	int r=0,mid=0,ret=1;
	ans[0]=1;
	for(int i=1;i<=len;++i){
		if(i<r)
			ans[i]=min(r-i+1,ans[mid*2-i]);
		else
			ans[i]=1;
		while(a[i-ans[i]]==a[i+ans[i]])
			++ans[i];
		if(r<i+ans[i]-1){
			mid=i;
			r=mid+ans[i]-1;
		}
		
		ret=max(ret,ans[i]);
	}
	
	return (ret*2-1)/2;
}

manacher(易于改动版)

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
int manacher(){
	int len=lens*2;
	for(int i=0;i<=len;++i){
		a[i]='#';
		ans[i]=1;
	}
	
	for(int i=1;i<=lens;++i)
		a[i*2-1]=s[i];
	
	int l=1,mid=0;
	int ret=0;
	ans[0]=1;
	for(int i=1;i<=len;++i){
		if(i>mid+l-1){
			int jj=1;
			while(i+jj-1<=len&&i-jj+1>=0&&a[i+jj-1]==a[i-jj+1])
				++jj;
			mid=i;
			l=jj-1;
			ans[i]=jj-1;
		}
		else{
			int j=mid*2-i;
			if(j-ans[j]+1>mid-l+1)
				ans[i]=ans[j];
			else{
				int jj=mid+l-i;
				while(i+jj-1<=len&&i-jj+1>=0&&a[i+jj-1]==a[i-jj+1])
					++jj;
				ans[i]=jj-1;
				if(i+ans[i]>mid+l){
					mid=i;
					l=jj-1;
				}
			}
		}
		ret=max(ret,ans[i]);
	}
	
	return (ret*2-1)/2;
}

PAM

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
struct PamNode{
    int ch[26];
    int num;//该位置为结尾的回文串个数
    int sum;//该节点表示的回文串出现的数量
    int fail,len;
    PamNode(){memset(ch,0,sizeof(ch));num=fail=len=sum=0;}
}pam[MAXX];
int pam_cnt=0,last=0;
char s[MAXX];//the string
inline void init(){
    for(int i=0;i<=pam_cnt;++i)
        pam[i]=PamNode();
    pam[0].len=0;pam[1].len=-1;
    pam[0].fail=1;pam[1].fail=0;
    last=0;pam_cnt=1;
}
inline int getfail(int id,int las){
    while(s[id-pam[las].len-1]!=s[id])
        las=pam[las].fail;
    return las;
}
void add(int id){
    int p=getfail(id,last);
    if(!pam[p].ch[s[id]-'a']){
        pam[++pam_cnt].len=pam[p].len+2;
        int jj=getfail(id,pam[p].fail);
        pam[pam_cnt].fail=pam[jj].ch[s[id]-'a'];
        pam[pam_cnt].num=pam[pam[pam_cnt].fail].num+1;
        pam[p].ch[s[id]-'a']=pam_cnt;
    }
    last=pam[p].ch[s[id]-'a'];
    ++pam[last].sum;
}
void build(){
    init();//init
    int len=strlen(s+1);
    for(int i=1;i<=len;++i){
        add(i);
        //do something or not
    }
    for(int i=pam_cnt;i>1;--i)
        pam[pam[i].fail].sum+=pam[i].sum;
}
/*
scanf("%s",s+1);
build();
*/

SA&&LCP(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
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
int n;
char s[MAXX];
int x[MAXX],y[MAXX],c[MAXX],sa[MAXX];
int rk[MAXX],height[MAXX];
int mn[MAXX],stmin[MAXX][22];

//后缀数组
//需事先定义
//int x[],y[],c[],sa[]; 
void SA(){
	int m='z';
	for(int i=1;i<=n;++i) ++c[x[i]=s[i]];
	for(int i=2;i<=m;++i) c[i]+=c[i-1];
	for(int i=n;i>=1;--i) sa[c[x[i]]--]=i;
	
	for(int k=1;k<=n;k<<=1){
		int num=0;
		for(int i=n-k+1;i<=n;++i) y[++num]=i;
		for(int i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;
		for(int i=1;i<=m;++i) c[i]=0;//init
		for(int i=1;i<=n;++i) ++c[x[i]];
		for(int i=2;i<=m;++i) c[i]+=c[i-1];
		for(int i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
		for(int i=1;i<=n;++i) swap(x[i],y[i]);
		x[sa[1]]=1;num=1;
		for(int i=2;i<=n;++i)
			x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
		if(num==n) break;
		m=num;
	}
}

//需事先定义 
//int rk[],height[];
//int mn[MAXX],stmin[MAXX][22];
void LCP(){
	int h=0;
	for(int i=1;i<=n;++i) rk[sa[i]]=i;//init
	for(int i=1;i<=n;++i){
		if(rk[i]==1) continue;
		if(h) --h;
		int j=sa[rk[i]-1];
		while(i+h<=n&&j+h<=n&&s[i+h]==s[j+h]) ++h;
		height[rk[i]]=h;
	}
	//st表init 
	mn[0]=-1;
	for(int i=1;i<=n;++i){
		mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];
		stmin[i][0]=height[i];
	}
	for(int j=1;j<=mn[n];++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
}

int getstmin(int l,int r){
	int k=mn[r-l+1];
	return min(stmin[l][k],stmin[r-(1<<k)+1][k]);
}

int getlcp(int l,int r){
	if(l==r) return n-l+1;
	return getstmin(min(rk[l],rk[r])+1,max(rk[l],rk[r]));
}

SA&&LCP(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
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
class SuffixArray{
public:
	int n;
	int x[MAXX],y[MAXX],c[MAXX],sa[MAXX];
	int rk[MAXX],height[MAXX];
	int mn[MAXX],stmin[MAXX][22];
	
	void SA(){
		int m='z';
		for(int i=1;i<=m;++i) c[i]=0;
		for(int i=1;i<=n;++i) ++c[x[i]=s[i]];
		for(int i=2;i<=m;++i) c[i]+=c[i-1];
		for(int i=n;i>=1;--i) sa[c[x[i]]--]=i;
		
		for(int k=1;k<=n;k<<=1){
			int num=0;
			for(int i=n-k+1;i<=n;++i) y[++num]=i;
			for(int i=1;i<=n;++i) if(sa[i]>k) y[++num]=sa[i]-k;
			for(int i=1;i<=m;++i) c[i]=0;//init
			for(int i=1;i<=n;++i) ++c[x[i]];
			for(int i=2;i<=m;++i) c[i]+=c[i-1];
			for(int i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i],y[i]=0;
			for(int i=1;i<=n;++i) swap(x[i],y[i]);
			x[sa[1]]=1;num=1;
			for(int i=2;i<=n;++i)
				x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
			if(num==n) break;
			m=num;
		}
	}
	
	void LCP(){
		int h=0;
		for(int i=1;i<=n;++i) rk[sa[i]]=i;//init
		for(int i=1;i<=n;++i){
			if(rk[i]==1) continue;
			if(h) --h;
			int j=sa[rk[i]-1];
			while(i+h<=n&&j+h<=n&&s[i+h]==s[j+h]) ++h;
			height[rk[i]]=h;
		}
		//st表init 
		mn[0]=-1;
		for(int i=1;i<=n;++i){
			mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];
			stmin[i][0]=height[i];
		}
		for(int j=1;j<=mn[n];++j)
			for(int i=1;i+(1<<j)-1<=n;++i)
				stmin[i][j]=min(stmin[i][j-1],stmin[i+(1<<(j-1))][j-1]);
	}
	
	int getstmin(int l,int r){
		int k=mn[r-l+1];
		return min(stmin[l][k],stmin[r-(1<<k)+1][k]);
	}
	
	int getlcp(int l,int r){
		if(l==r) return n-l+1;
		return getstmin(min(rk[l],rk[r])+1,max(rk[l],rk[r]));
	}
};

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
25
struct SamNode{
	int ch[26];
	int len,fa;
	SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<1];
int las=1,sam_cnt=1;

//LL num[MAXX<<1];
void add(int c){
	int p=las;int np=las=++sam_cnt;
//	num[np]=1LL;//此行为计数用，标记出现过几次 
	sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
	if(!p) sam[np].fa=1;
	else{
		int q=sam[p].ch[c];
		if(sam[q].len==sam[p].len+1) sam[np].fa=q;
		else{
			int nq=++sam_cnt;sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
		}
	}
}

区间本质不同子串个数

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
#include<bits/stdc++.h>
#define Inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
const int MAXX=100005;

int n,m,pos[MAXX];
char s[MAXX];

struct SamNode{
	int ch[26];
	int len,fa;
	SamNode(){memset(ch,0,sizeof(ch));len=0;}
}sam[MAXX<<1];
int las=1,sam_cnt=1;
//LL num[MAXX<<1];
void add(int c){
	int p=las;int np=las=++sam_cnt;
//	num[np]=1LL;//此行为计数用，标记出现过几次 
	sam[np].len=sam[p].len+1;
	for(;p&&!sam[p].ch[c];p=sam[p].fa) sam[p].ch[c]=np;
	if(!p) sam[np].fa=1;
	else{
		int q=sam[p].ch[c];
		if(sam[q].len==sam[p].len+1) sam[np].fa=q;
		else{
			int nq=++sam_cnt;sam[nq]=sam[q];
			sam[nq].len=sam[p].len+1;
			sam[q].fa=sam[np].fa=nq;
			for(;p&&sam[p].ch[c]==q;p=sam[p].fa) sam[p].ch[c]=nq;
		}
	}
}
struct Seg{
	LL val[MAXX<<2],tag[MAXX<<2];
	Seg(){memset(val,0,sizeof(val));memset(tag,0,sizeof(tag));}
	void push_down(int rt,int l,int r){
		if(tag[rt]){
			int mid=(l+r)>>1;
			tag[rt<<1]+=tag[rt],tag[rt<<1|1]+=tag[rt];
			val[rt<<1]+=tag[rt]*(mid-l+1);val[rt<<1|1]+=tag[rt]*(r-(mid+1)+1);
			tag[rt]=0;
		}
	}
	void push_up(int rt){
		val[rt]=val[rt<<1]+val[rt<<1|1];
	}
	void add(int l,int r,int rt,int tl,int tr,LL w){
        if(tl>tr) return;
		if(tl<=l&&r<=tr){
			tag[rt]+=w;val[rt]+=w*(r-l+1);return;
		}
		push_down(rt,l,r);
		int mid=(l+r)>>1;
		if(tl<=mid)add(l,mid,rt<<1,tl,tr,w);
		if(tr>=mid+1)add(mid+1,r,rt<<1|1,tl,tr,w);
		push_up(rt);
	}
	LL getsum(int l,int r,int rt,int tl,int tr){
		if(tl<=l&&r<=tr){return val[rt];}
		push_down(rt,l,r);
		int mid=(l+r)>>1;LL ans=0;
		if(tl<=mid)ans+=getsum(l,mid,rt<<1,tl,tr);
		if(tr>=mid+1)ans+=getsum(mid+1,r,rt<<1|1,tl,tr);
		return ans;
	}
}seg;
//add(1,n,1,l,r,v);
struct LCT{
    struct node{
        int fa,left,right,val,cov;
    }s[MAXX<<1];
    inline void pushdown(int i){
        if(s[i].cov){
            if(s[i].left) s[s[i].left].val=s[s[i].left].cov=s[i].cov;
            if(s[i].right) s[s[i].right].val=s[s[i].right].cov=s[i].cov;
            s[i].cov=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    inline int access(int k,int id){
        int temp=0;
        while(k){
            splay(k);
            if(s[k].val){
                // printf("*%d %d %d\n",s[k].val-sam[k].len+1,s[k].val-sam[s[k].fa].len,-1);//
                seg.add(1,n,1,s[k].val-sam[k].len+1,s[k].val-sam[s[k].fa].len,-1);
            }
            s[k].right=temp;
            temp=k;
            k=s[k].fa;
        }
        // printf("*1 %d 1\n",id);//
        seg.add(1,n,1,1,id,1);
        s[temp].val=s[temp].cov=id;
        return temp;
    }
}lct;
struct QQ{
    int l,r,id;
}a[MAXX*2];
bool cmp(QQ jj,QQ kk){return (jj.r<kk.r);}
LL ans[MAXX*2];

inline void solve(){
    scanf("%s\n%d",s+1,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&a[i].l,&a[i].r);
        a[i].id=i;
    }
    n=strlen(s+1);
    sort(a+1,a+m+1,cmp);

    for(int i=1;i<=n;++i){
        add(s[i]-'a');
        pos[i]=las;
    }

    for(int i=2;i<=sam_cnt;++i){
        lct.s[i].fa=sam[i].fa;
    }

    int p=1;
    for(int i=1;i<=n;++i){
        lct.access(pos[i],i);
        while(a[p].r==i)
            ans[a[p].id]=seg.getsum(1,n,1,a[p].l,a[p].r),++p;
    }

    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
}

signed main(){
//	LL t;scanf("%lld",&t);
//	while(t--)
		solve();
	
	return 0;
}

图论

堆优化dijkstra最短路

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
struct rode{
	int to,len;
};
int n,dij[MAXX];
vector<rode> ro[MAXX];

typedef pair<int,int> P;
void dijkstra(int st){
	memset(dij,Inf,sizeof(dij));
    priority_queue<P,vector<P>,greater<P> > q;
    q.emplace(P(0,st));
    dij[st]=0;
    
    while(!q.empty()){
    	P p=q.top();q.pop();
    	int mid=p.second;
    	if(dij[mid]<p.first) continue; //括号条件与(dij[mid]!=p.first)等价 
    	
    	int si=ro[mid].size();
    	for(int i=0;i<si;++i){
    		int too=ro[mid][i].to,lenn=ro[mid][i].len;
    		if(dij[too]>dij[mid]+lenn){
    			dij[too]=dij[mid]+lenn;
    			q.emplace(P(dij[too],too));
			}
		}
	}
    
}

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
27
28
29
30
31
32
33
34
35
struct rode{
	int to,len;
};
int n,in[MAXX],dij[MAXX];
bool vis[MAXX];
vector<rode> ro[MAXX];

bool spfa(int st){
	memset(vis,0,sizeof(vis));
	memset(in,0,sizeof(in));
	memset(dij,Inf,sizeof(dij));
	queue<int> q;
	q.emplace(st);
	vis[st]=true;++in[st];dij[st]=0;
	
	while(!q.empty()){
		int p=q.front();q.pop();
		vis[p]=false;
		int si=ro[p].size();
		for(int i=0;i<si;++i){
			int too=ro[p][i].to,lenn=ro[p][i].len;
			if(dij[too]>dij[p]+lenn){
				dij[too]=dij[p]+lenn;
				++in[too];
				if(in[too]>=n)
					return false;
				if(!vis[too]){
					vis[too]=true;
					q.emplace(too);
				}
			}
		}
	}
	return false;
}

tarjan割点(不是缩点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n,m,dfn[MAXX],low[MAXX],dfn_cnt;
vector<int> to[MAXX];
int root;
set<int> cut;

void tarjan(int now){ //每次调用的时候需要更新root的值 
	dfn[now]=low[now]=++dfn_cnt;
	int si=to[now].size(),flag=0;
	for(int i=0;i<si;++i){
		int jj=to[now][i];
		if(!dfn[jj]){
			tarjan(jj);
			low[now]=min(low[now],low[jj]);
			if(low[jj]>=dfn[now]){
				++flag;
				if(now!=root||flag>1)
					cut.emplace(now);
			}
		}
		else
			low[now]=min(low[now],low[jj]);
	}
}

tarjan桥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef pair<int,int> P;
int n,m,dfn[MAXX],dfn_cnt,low[MAXX];
vector<int> to[MAXX];
set<P> ans;

void tarjan(int now,int last){ //桥 
	dfn[now]=low[now]=++dfn_cnt;
	int si=to[now].size();
	for(int i=0;i<si;++i){
		int jj=to[now][i];
		if(!dfn[jj]){
			tarjan(jj,now);
			low[now]=min(low[now],low[jj]);
			if(low[jj]>dfn[now]){
				ans.emplace(P(min(now,jj),max(now,jj)));
			}
		}
		else if(jj!=last){
			low[now]=min(low[now],dfn[jj]);
		}
	}
}

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
26
27
28
29
30
31
int n,m,dfn[MAXX],low[MAXX],dfn_cnt;
vector<int> to[MAXX];
stack<int> sta;
bool in_sta[MAXX];
vector<int> scc[MAXX];
int scc_cnt,belong[MAXX];

void tarjan(int now){
	dfn[now]=low[now]=++dfn_cnt;
	sta.emplace(now);in_sta[now]=true;
	int si=to[now].size();
	for(int i=0;i<si;++i){
		int jj=to[now][i];
		if(!dfn[jj]){
			tarjan(jj);
			low[now]=min(low[now],low[jj]);
		}
		else if(in_sta[jj])
			low[now]=min(low[now],low[jj]);
	}
	if(dfn[now]==low[now]){
		++scc_cnt;
		int jj=0;
		while(jj!=now){
			jj=sta.top();sta.pop();
			scc[scc_cnt].emplace_back(jj);
			in_sta[jj]=false;
			belong[jj]=scc_cnt;
		}
	}
}

Kruskal(并查集)

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
struct Edge{
	int st,en,len;
};
int n,m,sum,dad[MAXX]; //n个顶点，m条边  sum为生成树的边的权值之和 
Edge a[MAXX];

bool cmp(Edge jj,Edge kk){return jj.len<kk.len;}

inline int root(int jj){
	return dad[jj]==jj?jj:dad[jj]=root(dad[jj]);
}

inline void unit(int jj,int kk){
	dad[root(jj)]=root(kk);
}

void kruskal(){
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;++i)
		dad[i]=i;
	sum=0;
	
	for(int i=1;i<=m;++i){
		if(root(a[i].st)!=root(a[i].en)){
			unit(a[i].st,a[i].en);
			sum+=a[i].len;
		}
	}
}

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
int n,m,root;
int fa[MAXX][22],depth[MAXX];
vector<int> to[MAXX];
int lg[MAXX];

inline void init(){
	for(int i=1;i<MAXX;++i)
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
}

void dfs(int now,int last){
	fa[now][0]=last;depth[now]=depth[last]+1;
	for(int i=1;i<=lg[depth[now]];++i)
		fa[now][i]=fa[fa[now][i-1]][i-1];
	int si=to[now].size();
	for(int i=0;i<si;++i)
		if(to[now][i]!=last)
			dfs(to[now][i],now);
}

int LCA(int jj,int kk){
	if(depth[jj]>depth[kk])
		swap(jj,kk);
	while(depth[jj]<depth[kk])
		kk=fa[kk][lg[depth[kk]-depth[jj]]-1];
	if(jj==kk)
		return jj;
	for(int i=lg[depth[jj]]-1;i>=0;--i)
		if(fa[jj][i]!=fa[kk][i])
			jj=fa[jj][i],kk=fa[kk][i];
	return fa[jj][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
int n,m,e; // n个点和m个点,e条边 
int match[MAXX]; // 第二个集合的点i的匹配点为第一个集合的点match[i] 
bool vis[MAXX]; // 第二个集合的点i是否被访问过 
set<int> to[MAXX]; // 邻接表存图，在这里用set是为了防止重边，平时用vector即可
				   // 这里只记录从左到右的边即可 

bool find(int now){
	for(int jj:to[now]){
		if(!vis[jj]){
			vis[jj]=true;
			if(match[jj]==0||find(match[jj])){
				match[jj]=now;
				return true;
			}
		}
	}
	return false;
}

int Hungarian(){
	int ret=0;
	for(int i=1;i<=n;++i){
		memset(vis,0,sizeof(vis));
		if(find(i)) ++ret;
	}
	return ret;
}

//int ans=HunGaria(); // ans即为最大匹配数

树状数组+树剖

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
//树状数组+树剖
int n;
LL mod,a[MAXX];
vector<int> to[MAXX];
//树状数组
LL c1[MAXX],c2[MAXX];
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int l,int r,int x){
    x %= mod;
    int ad1 = (LL)(l-1)*x%mod;
    int ad2 = (LL)r*x%mod;
    for(int t=l;t<=n;t+=lowbit(t)){
        c1[t] = (c1[t]+x)%mod;
        c2[t] = (c2[t]+ad1)%mod;
    }
    for(int t=r+1;t<=n;t+=lowbit(t)){
        c1[t] = (c1[t]-x)%mod;
        c1[t] = (c1[t]+mod)%mod;
        c2[t] = (c2[t]-ad2)%mod;
        c2[t] = (c2[t]+mod)%mod;
    }
}
inline int qwq(int i){ //qwq
    int res = 0;
    for(int t=i;t>0;t-=lowbit(t)){
        res = (res+(LL)i*c1[t]%mod)%mod;
        res = (res-c2[t])%mod;
        res = (res+mod)%mod;
    }
    return res;
}
inline int query(int l,int r){
    int res = (qwq(r)-qwq(l-1))%mod;
    return (res+mod)%mod;
}
//树剖
int depth[MAXX],num[MAXX],son[MAXX],fa[MAXX];
int top[MAXX],id[MAXX];
void dfs1(int now,int fa){
	depth[now]=depth[::fa[now]=fa]+1;
	num[now]=1;
	int maxnum=0;
	for(int jj:to[now]){
		if(jj==fa) continue;
		dfs1(jj,now);
		num[now]+=num[jj];
		if(num[jj]>maxnum){
			son[now]=jj;
			maxnum=num[jj];
		}
	}
}
int cnt=0;
void dfs2(int now,int t){
	top[now]=t;
	id[now]=++cnt;
	if(a[now])
		add(id[now],id[now],a[now]);
	if(son[now])
		dfs2(son[now],t);
	for(int jj:to[now]){
		if(jj==son[now]||jj==fa[now]) continue;
		dfs2(jj,jj);
	}
}
inline void init(int root){//root为根节点
	dfs1(root,0);
	dfs2(root,root);
}
void addpath(int l,int r,LL jk){//从l到r的最短路上的所有节点都加上jk
	while(top[l]!=top[r]){
		if(depth[top[l]]<depth[top[r]])
			swap(l,r);
		add(id[top[l]],id[l],jk);
		l=fa[top[l]];
	}
	if(depth[l]>depth[r])
		swap(l,r);
	add(id[l],id[r],jk);
}
LL getsum(int l,int r){//求从l到r的最短路上的所有节点的和
	LL ret=0LL;
	while(top[l]!=top[r]){
		if(depth[top[l]]<depth[top[r]])
			swap(l,r);
		ret=(ret+query(id[top[l]],id[l]))%mod;
		l=fa[top[l]];
	}
	if(depth[l]>depth[r])
		swap(l,r);
	ret=(ret+query(id[l],id[r]))%mod;
	return ret;
}
void addtree(int x,LL jk){//x的子树的所有节点都加上jk
	add(id[x],id[x]+num[x]-1,jk);
}
LL getsum(int x){//求x的子树的所有节点的和
	return query(id[x],id[x]+num[x]-1);
}

数论

欧拉筛存(<=nn)的素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int a[MAXX],m;
bool vis[MAXX]; //vis[i]=true; 表示i为合数 

void ola(int nn){
    m=0;
	for(int i=2;i<=nn;++i){
		if(!vis[i])
			a[++m]=i;
		for(int j=1;j<=m&&i*a[j]<=nn;++j){
			vis[i*a[j]]=true;
			if(i%a[j]==0)
				break;
		}
	}
}

快速幂

1
2
3
4
5
6
7
8
9
LL fastpow(LL jj,LL kk){
	LL ret=1;
	while(kk){
		if(kk&1) ret=ret*jj%mod;
		jj=jj*jj%mod;
		kk>>=1;
	}
	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
LL d[70];
inline void init(){
    for(int i=0;i<=62;++i)
        d[i]=0LL;
}
inline void add(LL jj){
    for(int i=62;i>=0;--i){
        if(jj&(1LL<<i)){
            if(!d[i]){
                d[i]=jj;
                break;
            }
            jj^=d[i];
        }
    }
}
inline LL getmax(){
    LL ret=0LL;
    for(int i=62;i>=0;--i)
        ret=max(ret,ret^d[i]);
    return ret;
}
inline LL geimin(){
    for(int i=0;i<=62;++i)
        if(d[i])
            return d[i];
    return 0;
}

模意义下的逆元

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//模意义下的逆元 
const LL mod=1000000007;
LL fastpow(LL jj,LL kk){
	LL ret=1;
	while(kk){
		if(kk&1) ret=ret*jj%mod;
		jj=jj*jj%mod;
		kk>>=1;
	}
	return ret;
}

LL rev(LL jj){
	return fastpow(jj,mod-2);
}
//(1/2)%mod=rev(2)

错位排序公式

1
2
d[1]=0;d[2]=1;
d[i]=(n-1)*(d[i-1]+d[i-2]);

数据结构

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n,c[MAXX];

int lowbit(int jj){return (jj)&(-jj);}

void updata(int jj,int kk){
	while(jj<=n){
		c[jj]+=kk;
		jj+=lowbit(jj);
	}
}

int getsum(int jj){
	int ret=0;
	while(jj>0){
		ret+=c[jj];
		jj-=lowbit(jj);
	}
	return ret;
}

线段树sum

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
struct Seg{
    LL tr[MAXX<<2],lazy[MAXX<<2];
    inline void build(LL* a,int n){
        build(a,1,1,n);
    }
    //sum
    inline void pushup(int now){
        tr[now]=tr[now<<1]+tr[now<<1|1];
    }
    void build(LL* a,int now,int l,int r){
        if(l==r){
            tr[now]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(a,now<<1,l,mid);
        build(a,now<<1|1,mid+1,r);
        pushup(now);
    }
    inline void pushdown(int now,int l,int r){
        if(lazy[now]){
            int mid=(l+r)>>1;
            lazy[now<<1]+=lazy[now];
            lazy[now<<1|1]+=lazy[now];
            tr[now<<1]+=lazy[now]*(mid-l+1);
            tr[now<<1|1]+=lazy[now]*(r-mid);
            lazy[now]=0;
        }
    }
    //add
    void updata(int now,int l,int r,int ll,int rr,LL val){
        if(l>=ll&&r<=rr){
            lazy[now]+=val;
            tr[now]+=val*(r-l+1);
            return;
        }
        pushdown(now,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll)
            updata(now<<1,l,mid,ll,rr,val);
        if(mid<rr)
            updata(now<<1|1,mid+1,r,ll,rr,val);
        pushup(now);
    }
    //sum
    LL getsum(int now,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr)
            return tr[now];
        pushdown(now,l,r);
        LL ret=0;
        int mid=(l+r)>>1;
        if(mid>=ll)
            ret+=getsum(now<<1,l,mid,ll,rr);
        if(mid<rr)
            ret+=getsum(now<<1|1,mid+1,r,ll,rr);
        return ret;
    }
};
//seg.updata(1,1,n,l,r,val);
//seg.getsum(1,1,n,l,r);

线段树sum(包含两种区间修改(*和+))(%mod)

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
LL mod=571373;
struct Seg{
    LL tr[MAXX<<2],lazy1[MAXX<<2],lazy2[MAXX<<2];
    inline void build(LL* a,int n){
        build(a,1,1,n);
        int si=MAXX<<2;
        for(int i=0;i<si;++i)
            lazy1[i]=1,lazy2[i]=0;
    }
    //sum
    inline void pushup(int now){
        tr[now]=tr[now<<1]+tr[now<<1|1];
        tr[now]%=mod;
    }
    void build(LL* a,int now,int l,int r){
        if(l==r){
            tr[now]=a[l];
            return;
        }
        int mid=(l+r)>>1;
        build(a,now<<1,l,mid);
        build(a,now<<1|1,mid+1,r);
        pushup(now);
    }
    inline void pushdown(int now,int l,int r){
        if(lazy1[now]!=1||lazy2[now]){
            int mid=(l+r)>>1;
            lazy1[now<<1]*=lazy1[now];lazy1[now<<1]%=mod;
            lazy1[now<<1|1]*=lazy1[now];lazy1[now<<1|1]%=mod;
            lazy2[now<<1]=lazy2[now<<1]*lazy1[now]+lazy2[now];lazy2[now<<1]%=mod;
            lazy2[now<<1|1]=lazy2[now<<1|1]*lazy1[now]+lazy2[now];lazy2[now<<1|1]%=mod;
            tr[now<<1]=tr[now<<1]*lazy1[now]+lazy2[now]*(mid-l+1);tr[now<<1]%=mod;
            tr[now<<1|1]=tr[now<<1|1]*lazy1[now]+lazy2[now]*(r-mid);tr[now<<1|1]%=mod;
            lazy1[now]=1;lazy2[now]=0;
        }
    }
    //mul
    void updata1(int now,int l,int r,int ll,int rr,LL val){
        if(l>=ll&&r<=rr){
            lazy1[now]*=val;lazy1[now]%=mod;
            lazy2[now]*=val;lazy2[now]%=mod;
            tr[now]*=val;tr[now]%=mod;
            return;
        }
        pushdown(now,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll)
            updata1(now<<1,l,mid,ll,rr,val);
        if(mid<rr)
            updata1(now<<1|1,mid+1,r,ll,rr,val);
        pushup(now);
    }
    //add
    void updata2(int now,int l,int r,int ll,int rr,LL val){
        if(l>=ll&&r<=rr){
            lazy2[now]+=val;lazy2[now]%=mod;
            tr[now]+=val*(r-l+1);tr[now]%=mod;
            return;
        }
        pushdown(now,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll)
            updata2(now<<1,l,mid,ll,rr,val);
        if(mid<rr)
            updata2(now<<1|1,mid+1,r,ll,rr,val);
        pushup(now);
    }
    //sum
    LL getsum(int now,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr)
            return tr[now];
        pushdown(now,l,r);
        LL ret=0;
        int mid=(l+r)>>1;
        if(mid>=ll)
            ret+=getsum(now<<1,l,mid,ll,rr),ret%=mod;
        if(mid<rr)
            ret+=getsum(now<<1|1,mid+1,r,ll,rr),ret%=mod;
        return ret;
    }
}seg;
//seg.updata(1,1,n,l,r,val);
//seg.getsum(1,1,n,l,r);

矩阵线段树(当前为求区间斐波那契之和)

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
const LL mod=1e9+7;
const int nn=2,mm=2;
struct Matrix{
    LL c[nn][mm];
    Matrix(){memset(c,0,sizeof(c));}
    friend Matrix operator+(const Matrix &jj,const Matrix &kk){
        Matrix ret;
        for(int i=0;i<nn;++i)
            for(int j=0;j<mm;++j)
                ret.c[i][j]=(jj.c[i][j]+kk.c[i][j])%mod;
        return ret;
    }
    friend Matrix operator*(const Matrix &jj,const Matrix &kk){
        Matrix ret;
        for(int i=0;i<nn;++i)
            for(int j=0;j<mm;++j)
                for(int k=0;k<mm;++k)
                    ret.c[i][j]+=jj.c[i][k]*kk.c[k][j],ret.c[i][j]%=mod;
        return ret;
    }
}st;

void init(){//斐波那契数列的初始矩阵
    st.c[0][0]=st.c[0][1]=st.c[1][0]=1;
}

Matrix fastpow(Matrix jj,LL kk){
	Matrix ret;
    for(int i=0;i<nn;++i)
        ret.c[i][i]=1;
	while(kk){
		if(kk&1) ret=ret*jj;
		jj=jj*jj;
		kk>>=1;
	}
	return ret;
}

struct Seg{
    Matrix tr[MAXX<<2];
    LL lazy[MAXX<<2];
    inline void build(LL* a,int n){
        build(a,1,1,n);
    }
    //sum
    inline void pushup(int now){
        tr[now]=tr[now<<1]+tr[now<<1|1];
    }
    void build(LL* a,int now,int l,int r){
        if(l==r){
            tr[now]=fastpow(st,a[l]-1);
            return;
        }
        int mid=(l+r)>>1;
        build(a,now<<1,l,mid);
        build(a,now<<1|1,mid+1,r);
        pushup(now);
    }
    //add
    void updata(int now,int l,int r,int ll,int rr,LL val){
        if(l>=ll&&r<=rr){
            lazy[now]+=val;
            tr[now]=fastpow(st,val)*tr[now];
            return;
        }
        pushdown(now,l,r);
        int mid=(l+r)>>1;
        if(mid>=ll)
            updata(now<<1,l,mid,ll,rr,val);
        if(mid<rr)
            updata(now<<1|1,mid+1,r,ll,rr,val);
        pushup(now);
    }
    inline void pushdown(int now,int l,int r){
        if(lazy[now]){
            int mid=(l+r)>>1;
            lazy[now<<1]+=lazy[now];
            lazy[now<<1|1]+=lazy[now];
            tr[now<<1]=fastpow(st,lazy[now])*tr[now<<1];
            tr[now<<1|1]=fastpow(st,lazy[now])*tr[now<<1|1];
            lazy[now]=0;
        }
    }
    //sum
    LL getsum(int now,int l,int r,int ll,int rr){
        if(l>=ll&&r<=rr)
            return tr[now].c[0][0];
        pushdown(now,l,r);
        LL ret=0;
        int mid=(l+r)>>1;
        if(mid>=ll)
            ret+=getsum(now<<1,l,mid,ll,rr),ret%=mod;
        if(mid<rr)
            ret+=getsum(now<<1|1,mid+1,r,ll,rr),ret%=mod;
        return ret;
    }
}seg;
//seg.updata(1,1,n,l,r,val);
//seg.getsum(1,1,n,l,r);

st表(max)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n,a[MAXX];
int mn[MAXX],stmax[MAXX][22];

void init(){
	mn[0]=-1;
	for(int i=1;i<=n;++i){
		mn[i]=((i&(i-1))==0)?mn[i-1]+1:mn[i-1];
		stmax[i][0]=a[i];
	}
	for(int j=1;j<=mn[n];++j)
		for(int i=1;i+(1<<j)-1<=n;++i)
			stmax[i][j]=max(stmax[i][j-1],stmax[i+(1<<(j-1))][j-1]);
}

int getstmax(int l,int r){
	int k=mn[r-l+1];
	return max(stmax[l][k],stmax[r-(1<<k)+1][k]);
}

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
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
struct LCT{
    struct node{
        int fa,left,right,val,sum,lazy;
    }s[MAXX];
    //根据需要维护什么进行改动(大概)
    inline void pushup(int i){
        s[i].sum=s[s[i].left].sum^s[s[i].right].sum^s[i].val;
    }
    inline void pushdown(int i){
        if(s[i].lazy){
            swap(s[i].left,s[i].right);
            if(s[i].left) s[s[i].left].lazy^=1;
            if(s[i].right) s[s[i].right].lazy^=1;
            s[i].lazy=0;
        }
    }
    inline int identify(int i){
        if(s[s[i].fa].left==i) return 0;
        if(s[s[i].fa].right==i) return 1;
        return -1;
    }
    inline void connect(int i,int f,int op){
        s[i].fa=f;
        if(op==1) s[f].right=i;
        if(op==0) s[f].left=i;
    }
    inline void rotate(int x){
        int y=s[x].fa;
        int z=s[y].fa;
        int opy=identify(y);
        int opx=identify(x);
        int u=0;
        if(opx==1) u=s[x].left;
        if(opx==0) u=s[x].right;
        connect(u,y,opx);
        connect(y,x,opx^1);
        connect(x,z,opy);
        pushup(y);
        pushup(x);
    }
    void pushall(int x){
        if(identify(x)!=-1) pushall(s[x].fa);
        pushdown(x);
    }
    inline void splay(int i){
        pushall(i);
        while(identify(i)!=-1){
            int up=s[i].fa;
            if(identify(up)==-1) rotate(i);
            else if(identify(i)==identify(up)) rotate(up),rotate(i);
            else rotate(i),rotate(i);
        }
    }
    //以上为splay的一些基本操作
    //下面是LCT的操作
    //构建一条从根到k的一条重链
    inline int access(int k){
        int temp=0;
        while(k){
            splay(k);
            s[k].right=temp;
            pushup(k);
            temp=k;
            k=s[k].fa;
        }
        return temp;
    }
    inline void makeroot(int k){
        access(k);
        splay(k);
        swap(s[k].left,s[k].right);
        if(s[k].left) s[s[k].left].lazy^=1;
        if(s[k].right) s[s[k].right].lazy^=1;
    }
    inline int findroot(int k){
        access(k);
        splay(k);
        while(s[k].left){
            pushdown(k);
            k=s[k].left;
        }
        splay(k);
        return k;
    }
    //询问或操作从x到y这条链
    //将从x到y这条链单独提出来，并将y变成根
    inline void split(int x,int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    //返回x和y的lca
    inline int lca(int x,int y){
        access(x);
        return access(y);
    }
    //返回以r为根的情况下的x和y的lca
    inline int lca(int r,int x,int y){
        makeroot(r);
        access(x);
        return access(y);
    }
    inline bool link(int x,int y){
        makeroot(x);
        if(findroot(y)==x) return false;
        s[x].fa=y;
        return true;
    }
    inline bool cut(int x,int y){
        if(findroot(x)!=findroot(y)) return false;
        split(x,y);
        if(s[x].fa!=y||s[x].right) return false;
        s[x].fa=s[y].left=0;
        pushup(x);
        return true;
    }
};

$LCT$ 适用场景

  • 可以支持动态维护一个树结构，具体来说就是支持加边和删除边。
  • 可以用来求无根树的lca，就是可以多次随意指定一个根来求lca。
  • 这个东西还可以当作一个动态并查集来使用。即可以加边也可以删边的并查集。

一些技巧

  • 如果给出了固定的树的结构，那么建图可以使用

    1
    2
    3
    for(int i=2;i<=sam_cnt;++i){
        lct.s[i].fa=sam[i].fa;
    }

其他

fread快读

1
2
3
4
5
6
7
8
static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read(){
    int x(0);char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x;
}

数位dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL num[20],dp[20][20];

LL dfs(LL now,bool limit,bool nozero,LL sum,LL d){
    if(!now) return sum;
    if(!limit&&nozero&&dp[now][sum]!=-1) return dp[now][sum];
    LL ret=0LL;
    LL up=limit?num[now]:9;
    for(LL i=0;i<=up;++i)
        ret+=dfs(now-1,limit&&(i==up),nozero||i,sum+(bool)((nozero||i)&&(i==d)),d);
    if(!limit&&nozero) dp[now][sum]=ret;
    return ret;
}

LL getans(LL x,LL d){//从1到x的所有数中数字d出现的次数
    LL p=0LL;
    memset(dp,-1,sizeof(dp));
    while(x){
        num[++p]=x%10;
        x/=10;
    }
    return dfs(p,true,false,0LL,d);
}

二分(左闭右开)

1
2
3
4
5
6
7
8
int l=1,r=n+1,mid;//[l,r)
while(l<r){
    mid=(l+r)/2;
    if(check(mid))
        l=mid+1;
    else
        r=mid;
}

离散化(最终包含重复元素)

1
2
3
4
5
6
7
8
9
10
11
scanf("%d",&n);
for(int i=1;i<=n;++i)
    scanf("%d",&a[i]);

//包含重复元素 
for(int i=1;i<=n;++i)
    s[i]=a[i];//a[]为原数组 
sort(a+1,a+n+1);
int len=unique(a+1,a+n+1)-a-1;//去重之后的数组长度 
for(int i=1;i<=n;++i)
    s[i]=lower_bound(a+1,a+len+1,s[i])-a;//s[]即为离散化之后的数组

离散化(最终不包含重复元素)

1
2
3
4
5
6
7
8
scanf("%d",&n);
for(int i=1;i<=n;++i){
    scanf("%d",&a[i].first);//P a[MAXX]
    a[i].second=i;
}
sort(a+1,a+n+1);
for(int i=1;i<=n;++i)
    s[a[i].second]=i;//s[]即为离散化之后的结果

unordered_map中存pair

1
2
3
4
5
6
7
8
9
struct hashfunc{
    template<typename T, typename U>
    size_t operator() (const pair<T, U> &i) const {
        //根据题目数据写一个hash函数
        return (LL)(i.first)*1000000LL+(LL)(i.second);
    }
};

unordered_map<P,int,hashfunc> dij;

LIS(最长上升子序列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lis[MAXX],len;
int LIS(int a[],int n){
	if(!n) return 0;
	memset(lis,Inf,sizeof(lis));len=1;
	lis[1]=a[1];
	for(int i=2;i<=n;++i){
		int j=lower_bound(lis+1,lis+len+1,a[i])-lis;
		if(j>len)
			lis[++len]=a[i];
		else if(a[i]<lis[j])
			lis[j]=a[i];
	}
	return len;
}
文章作者: Shaun
文章链接: http://shaun-2314.github.io/2022/04/22/template-summary/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Shaun !
acm 板子
评论
  目录