题目大意

给定一棵树，每个节点上有一个大写字母，共q次询问，每次询问包含两个参数X，L，表示求这个树中（由底向上）的字符串有多少和从X向上L的字母拼接成的字符串相同。

题解

广义后缀自动机模板题。

实际上就是求一个子串在所有的字符串中出现的次数，也就是endpos集大小。

注意在找这个具体的字符串对应的状态节点时，要倍增的在后缀树中往上跳。

剩下的就真的只是模板。

代码

#include <bits/stdc++.h>
using namespace std;
struct SAM_node{
	int len,endpos,trans[26],link;
};
const int maxn = 3e5+5;
int tr[maxn][26],tot = 0,trie_id[maxn],sam_pos[maxn],cnt[maxn],root;
string s;
int n,q;
int x,l;
struct SAM{
	SAM_node s[maxn<<1];
	int h[maxn<<1],next[maxn<<1],to[maxn<<1];
	int siz,sum,f[maxn<<1][21];
	void add(int u,int v){
		to[sum] = v;next[sum] = h[u];h[u] = sum++;
		return;
	}
	void init(){
		siz = 1;
		sum = 0;
		memset(h,-1,sizeof(h));
		return;
	}
	int extend(int last,int c,int num){
		int z = ++siz;
		int p = last;
		s[z].len = s[p].len + 1;
		s[z].endpos = num;
		while(p && !s[p].trans[c]){
			s[p].trans[c] = z,p = s[p].link;
		}
		if(!p)
			s[z].link = 1;
		else{
			int x = s[p].trans[c];
			if(s[x].len == s[p].len + 1)
				s[z].link = x;
			else{
				int y = ++siz;
				s[y] = 

题目大意

给出一个字符串序列，字符串仅由-和+组成，一开始有个初始的值x为0，-表示x = x-1，+表示x = x+1。

每次询问给出一个l和r，表示忽视[l,r]区间内的字符串，剩下的操作进行执行，求问x在操作过程中不同的值的个数。

题解

一开始看成区间内不同数的个数了，十分钟打完板子才发现不对。

虽然不是区间内不同数的个数，但是也是一道线段树的题目，且看下面的分析。

首先我们注意到，数x每次无论变大还是变小，每次变化的绝对值一定为1。这样我们就能够用x到达的最大值mx减去x的最小值mi，之后加上1，即为最终的答案。

于是我们只需要维护某一段区间操作使x能够变到的最大值和最小值分别是多少。

但是这样会出现一个问题，区间合并的时候应该怎么做。因为左侧区间得出的最终值一定会影响右侧区间的结果，所以这给我们的合并造成了一定的麻烦的影响。

但是影响是能解决的，因为产生影响的只有区间操作产生的对于这个区间的x最终结果的影响，所以我们只需要记录一下区间操作对x的最终结果的影响就好了。

这样我们就需要记录以下三个参数：

struct tree{
    int l,r,rval,mx,mi;
    tree operator + (const tree &x)const{
        tree res;
        res.mx = max(mx,rval + x.mx);
        res.mi = min(mi,rval + x.mi);
        res.rval = rval + x.rval;
        return res;
    }
    void init(){
        mx = 0;
        mi = INF;
        rval = 0;
    }
}tr[maxn<<2];

重载的operator +，就是区间的合并操作。

然后我们用线段树求解即可，具体求解方法就是，分别求出忽视的区间的左边和右边的操作区间的影响（struct结构），然后进行合并即可。

注意最小值小于0或者最大值大于0的情况，需要给答案+1，因为一开始x就是0。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int t

题目大意

求矩阵C的个数，满足A×C = B·C。其中×表示矩阵乘（模数为2，也即矩阵的异或乘），·表示矩阵元素与。

题解

博主在正式赛的时候执着于找规律，最后才看到高斯消元，所以最后就白给了，拿了个铜滚粗了。

其实没必要去算什么规律的，我们直接设C的元素为c₁₁ ……c_nn,然后直接按照两种操作的定义展开即可。

之后我们可以发现c中的元素的每一列都构成了一组n元的异或方程组，而不同列之间的元素是没有相互影响的。这样我们就可以应用高斯消元，求解自由元的个数，计算出每一列自由元个数x_i，最后结果就是Πx_i。算法的总复杂度是O(n⁴)的

但是这个题目的数据是N ≤ 200，所以算法O(n⁴)的时间复杂度是无法接受的，但是我们又无法做到在指数级上进行优化，所以考虑常数优化。考虑到异或方程组的行间计算实际上都是异或操作，所以我们可以考虑用bitset代替自己写的数组式矩阵。这样最终算法的时间复杂度为O(n⁴/64)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll quick_pow(ll x,ll y){
	ll res = 1;
	while(y){
		if(y & 1)
			res = res * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
const int maxn = 205;
int a[maxn][maxn],b[maxn][maxn];
bitset<maxn>bs[maxn],bd[maxn],t;
int n;
ll ans;
void swap(bitset<maxn> &x,bitset<maxn> &y){
	t.reset();
	t |= y;
	y.reset();
	y |= x;
	x.reset();
	x |= t;
	return;
}
int Guass(){
	int maxrow,row = 0,col = 0,num = 0;
	for(row = 0;row < n && col < n;row++,col++){
		maxrow = row;
		for(int i = row + 1;i < n;++i){

题目大意

给出一个模式串n为01串，求问长度为m的所有文本串中有多少长度为n的子串能做到与模式串近似匹配。

近似匹配的意思为：最多只有一个字符与模式串不同。

题解

我们是无法在短时间内强行进行近似匹配的，所以只能转化成完全匹配来做。

最多只有一个字符与模式串不同，这样我们就可以把模式串写成n+1个不同的模式串，即原模式串每个字符都变换一次，作为一个新的模式串。

多模式串匹配问题，一定是AC自动机。

我们把所有的模式串合起来建立一个AC自动机，在上面跑DP就可以了。

我们设dp[i][j]表示当前遍历文本串的第i位，到达AC自动机状态j的方案数。

当然这样空间是不够用的，所以需要用滚动数组优化掉第一维的空间。

对于上一位的状态j，假设当前位到达状态为next[j][k]，k为枚举的第i位的字符；

若当前状态为终结状态，则总方案数ans += dp[i-1&1][j] * (1ll << (m-i))

若当前状态非终结状态，则有转移dp[i&1][next[j][k]] += dp[i-1&1][j];

直接DP即可。

代码

#include <bits/stdc++.h>
const int maxn = 2e3 + 5;
using namespace std;
typedef long long ll;
int nex[maxn][2], fail[maxn], ed[maxn], flag[maxn];
int root, p;
inline int newnode() {
    for (int i = 0; i < 2; ++i) {
        nex[p][i] = -1;
    }
    ed[p++] = 0;
    return p - 1;
}
inline void init() {
    p = 0;
    root = newnode();
}
inline void insert(char *buf) {
    int now = root;
    for (int i = 0; buf[i]; ++i) {
        if (nex[now][buf[i]-'0'] == -1) 
            nex[now][buf[i]-'0'] = newnode();
        now = nex[now][buf[i]-'0'

题解

其实就是每个字符串的endpos集的大小，无非就是同长度取max而已

我们注意到，如果一个字符串在st状态中出现，其必在trans决定的后续状态中继续出现。且每次在st状态中新出现的字符串，一定是以转移过来的节点的字符串做前缀的。

所以我们把每个非clone节点的位置的值设为1，clone节点的位置的值设为0，直接用后缀链link构成的DAG上跑拓扑DP就可以了。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6+5;
char ss[maxn];
typedef long long ll;
int len;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],trans[maxn][26],maxlen[maxn];
    queue<int>q;
    vector<int>g[maxn];
    int indeg[maxn];
    ll ans1;
    ll ans[maxn],endpos[maxn];
    int last;
    void init(){
        last = tot = 1;
        return;
    }
    int extend(int ch){
        int x,y,z = ++tot;
        int p = last;
        endpos[z] = 1;
        maxlen[z] = maxlen[last] + 1;
        while(p && !trans[p][ch])
            trans[p][ch] = z,p = link[p];
        if(!p){
            link[z] = 1;
        }
        else{
            x = trans[p][ch];
            if(maxlen[p] + 1 == maxlen[x])
                link[z] = x;
            else{
                y = ++tot;
            

题目大意

维护一个多重集合，支持三种操作：

• 1 ： 加入一个x
• 2 ： 删除一个x
• 3 ： 询问当前在多重集中，是否存在两个数a，b，使得x能与a，b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法，但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况：

1. x为唯一最大边，则要a,b都小于x，于是只需要找比x更小的两个前驱作为a,b，判断a+b>x是否成立即可。
2. x不是唯一最大边，假设b≥a，于是我们需要b≥x && b - a < x，而b-a最小的条件一定是b确定的情况下，a是b的一个非严格前驱，这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单，直接用multiset维护、查询就行了，只需要注意一下边界问题。

第二种情况比较麻烦，没法用STL做，所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值，排序的键值为当前数的大小，查询答案的时候，找到x的后缀节点，然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否＜x即可。

需要注意考虑边界问题。

最后提示的一点，s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;

题目大意

给出一个长为n的数列A,一个长为m的数列B

求问A中有多少个长度为m的子区间S，满足S中的元素全都不小于B中下标对应的元素

题解

说实话真的还是对bitset的应用不熟悉。

这题bitset只是最后用来优化的。

首先我们假定一个tmp数组，其中tmp[i][j]表示对Ai是否≥Bj。

如果一个长度为m的子区间要成为满足题目条件的S，那么和tmp[i]数组有什么关系？

一定是要求：对于区间内每一个i及其对应位置的j，tmp[i][j]都为1.这是显然的。

考虑如何优化这个问题。

首先，大小关系其实本质上来说只有m+1种，也就是对于tmp[i]的取值最多有m+1种，所以我们可以将B数组内的数全部排序，然后用m+1个bitset（假设为s）逐位去置1，然后九不需要算tmp数组了，我们需要取用tmp的时候，只需要找到最后一个小于等于A[i]的B[j]（这里的B已经排序好了），然后取s[j]就可以了。而且bitset也会在我们接下来的做法中发挥很重要的作用。预处理这些bitset的复杂度是O(m²/W)的（W为bitset优化的效果）

之后考虑如何去搞这个题。

新设一个新的m位bitset，假设为cur_i，其中cur_i[j] = 1当且仅当对于所有的k∈[j，m]，A_i+k-j >= B_k，这样只需要求有多少cur_i[1] = 1即可。

首先可以确定A数组的后m-1个数是肯定不可以作为区间点的，毕竟区间长度都不够，所以我们可以按照下面的公式来做：

cur_i = ((cur_i+1 >> 1) | I_m) & s_posi。posi表示最后一个小于等于A[i]的B[posi]。

这样通过右移位来进行对齐,可以达到我们预期的效果。

而且，我们可以不用开n个cur，只需要开一个进行滚动就可以了。

最终的时间复杂度是O(nm/W)

代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>PI;
const int maxn = 150005;
const int maxm = 40005;
PI a[maxn],b[maxm];
bitset<maxm>s[maxm];
bitset<maxm>cur,upd;
const int INF = 1e9+7;
int n,m;
int p;
int main(){
    ios_ba

题目大意

对S串做两次f变换，得到一个字符串集A，求A中本质不同的字符串数量。

题解

其实不管是观察，还是拿样例手算，最后一定能得出一个结论：

其实两次f变换和一次f变换的作用是一样的。

所以只需要看一下一次f变换就行了。

f其实是对子串的变换，后面被变换的字符只跟其前面的字典序比他大的字符有关。

先看题目要求，求A中本质不同的字符串数量。

前面说了A实际上是S的所有子串做了变换而已。所以也就是本质不同的类子串数量（这个说法大概可以吧）。所以很自然想到这是一个后缀自动机。

但是这里的要求的并不是简单的子串，需要做变化。

前面说了，被变换的字符只跟其前面的字典序比他大的字典序最大的字符有关，只要出现一个比他大的字符就要重新更新字符串。

于是我们可以这样搞：

我们考虑将原串倒过来，然后按照题目的要求去建一个Trie，具体建法比较麻烦，如果当前字符的上一个比他大的字符没有出现，则需要从根开始往下重新建一条链，否则就继续往下建，复杂度最大为O(10n)，但实际上肯定到不了。

然后对Trie静态建广义后缀自动机，直接跑本质不同子串数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e6+5;
string s;
char ss[maxn];
int len;
int son[maxn][10],fa[maxn],cl[maxn];
int now = 1;
int root = 1;
struct SAM{
    int tot;
    int pos[maxn],link[maxn],maxlen[maxn],trans[maxn][10];
    queue<int>q;
    ll ans;
    void init(){
        tot = 1;
        return;
    }
    int extend(int ch,int last){
        int x,y,z = ++tot;
        int p = last;
        maxlen[z] = maxlen[last]+1;
        while(p && !trans[p][ch])
            trans[p][ch] = z

题解

我记得当年我在考场上做这个题的时候想出了很多奇奇怪怪的思路……反正就是不会处理上下界的问题，然后就这个题爆零了

实际上我已经想明白是上下界的费用流了，但是并不会有上下界的情况，所以只能想各种奇技淫巧。

所以，此题的正解就是无源汇有上下界的最小费用可行流。

对于无源汇的网络流问题，我们通常会设置虚拟源点S和虚拟汇点T。然后再在图上进行构建。

对于这个题也是一样，只是因为有上下界所以我们需要对图进行一下改进。

我们考虑一条边一定会流下界那么多的流，这样整张图的残量网络就构成了一个流量不平衡的图。我们需要构建另外一张流量不平衡的图，使得原始图和我们构建的图互补成为一张流量平衡的图。

我们考虑对于原图中进行统计，一个点每流出1流量，度数du[x]-1，流入1流量，度数du[x]+1。

如果最终一个点的度数<0（流出大于流入），则其在互补图中流入就要大于流出，这样我们就需要给他添加一些流出渠道来疏通这些多余的流入流量，这样就从点x向虚拟汇点T连一条容量为-du[x]的边。反之同理。

如果我们能找到一个流满足新加的边都满流,这个流在原图上的部分就是我们需要的与原图互补的附加流。

那么怎样找出一个新加的边都满流的流呢?可以发现假如存在这样的方案,这样的流一定是我们所建出的图的S-T最大流,所以跑S到T的最大流即可.如果最大流的大小等于S出发的所有边的流量上限之和(此时指向T的边也一定满流,因为这两部分边的流量上限之和相等)，则说明此图是有可行流的.

在此题中也是如此，只是原图上的边加上了费用而已，而新加的边费用为0，直接跑有上下界最大费用可行流即可。

代码

#include <bits/stdc++.h>
using namespace std;
int T,S,E;
const int maxn = 205;
const int INF = 2e9;
struct edge{
    int fr,to,next,cap,dis;
}e[maxn<<3];
int h[maxn];
int cnt = 0;
void add(int u,int v,int cap,int d){
    e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = cap;e[cnt].dis = d;e[cnt].next = h[u];h[u] = cnt++;
    e[cnt].fr