题目大意
给定一个序列a，要求你每个元素都选出不超过ai的值，使得选出的元素序列满足不严格上凸（上凸、非严格单调皆可），且总和最大，求问每个位置上选出的元素是多少。
题解
此题有一个暴力的easy version版本，只需要枚举每个位置为最大值点位置pos（也就是该点处选择的元素大小为apos）暴力计算即可。
但是当数据量变大到5*105数量级时，我们没有办法枚举位置暴力计算。
但是可以注意到，枚举每个位置为最大值点位置pos这一步仍然是不可避免地，这是解题的核心，于是很容易想到，我们需要在较短时间内算出当每个位置为最大值点位置时，所选出的最优序列的元素大小总和。我们不能用暴力的版本每一次枚举都用O(n)的时间复杂度来算。
我们考虑用一种类似于前缀和和后缀和的形式来计算上述提到的我们需要计算的。前缀和和后缀和相加减去此位置本身所得的值，即在当前位置为最大值点位置时，所选出的最优序列的元素总和的大小。最优前缀和与最优后缀和的计算模式大致相同，直接来看最优前缀和pre的计算方法吧。
假设当前枚举到的位置为pos(pos>1)，考虑两种情况：
1.apos>=apos-1，这时选取当前位置为最大值点时，不会对pos-1为最大值点时的最优前缀和的值产生影响，直接转移：pre[pos] = pre[pos-1];
2.apos<apos-1，这时选取当前位置为最大值点时，就不能用pos-1为最大值点时的最优前缀和的值来进行转移，因为这时pos-1位置不能选取其最大值了。这时候需要考虑我们不会对哪个位置之前的选值有影响，很明显是pos位置前第一个小于等于apos的元素所在的位置。
最优后缀和也类似考虑。
在第一种情况下，我们无需考虑什么东西，可以直接转移。重点在第二种情况，如何寻找pos之前第一个小于等于apos的元素所在的位置，这个操作的复杂度会影响到我们整体的算法复杂度。
据说有可以把这个操作整体复杂度做到O(1)的做法，但是这里并没有想到，于是选择nlogn的线段树做法。
首先对数组离散化，对离散化后的权值建一棵线段树，线段树节点上的值为其子树中元素的最大值，元素表示的是当前节点代表的区间的各个离散化后的值中出现的最晚的位置（最大）是哪个位置。
从开始向后逐个计算。
如果在第一种情况，直接转移，并将当前的位置pos更新到到线段树对应着当前位置元素的离散化后的值的权值叶节点。
如果在第二种情况，假设当前
题目大意
一开始有一个所有数全都为0的n*m的矩阵。
一共有q次操作，每次操作读入x，y，c，将坐标为(x,y)处的值改为c。
问每一次操作后连通块的个数是多少。
如果两个相邻的格子数字相同，我们认为这两个格子属于同一个连通块。
询问中的c的值保证单调不减。
题解
询问连通块个数的题目一般来说肯定需要用并查集。
但是有一个问题是普通的并查集并不支持删除操作。
因为改变值，实际上相当于是先删除一个值再添加另一个值。所以必定会涉及到删除操作。
此题也不能用可持久化并查集，因为操作并不是“回溯”，而是单纯的删除。
并查集询问连通块个数的时候一般都是静态询问，但是这个题明显是一个动态维护，难度更高。
首先解决动态维护的问题吧。
我们可以去整一个add数组，里面记录当前操作后连通块个数相较于之前发生了什么样的变化。
后面就是如何计算这个add数组的问题了，先考虑删除问题。
删除是并查集无法完成的操作，但是添加可以，我们可以把删除看作是反向添加，用一个反向添加的并查集来表示删除的元素构成的连通块个数，用对应时间点的添加的连通块个数减去删除的连通块个数即为这个时间点操作后的答案。
具体在实施的时候，不能单纯对矩阵的方格建立并查集。我们需要对于不同的数字情况下分别对方格建立并查集，这样来操作，否则删除的时候会出现问题。
当添加一个元素的时候，扫描其周围四个点与其颜色相同的点的个数num，并查集个数改变量为1-num。
此题思路看代码可能会更加清晰，因为确实跟平常的并查集题目并不相像。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 305;
const int maxc = 2e6+5;
int n,m,q;
int f[maxn*maxn];
int find(int x){
if(f[x] != x)f[x] = find(f[x]);
return f[x];
}
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
typedef pair<int,int> PI;
vector<PI>add[maxc],del[maxc];
int a[maxn][maxn],dif[maxc];
void calc(const vector<PI> &p,int flag){
Input
5 5 a ab abab ababab b 1 5 1 3 5 1 1 5 2 1 5 3 1 4 5
Output
7 5 6 3 6
题目大意
给出n个字符串，q次询问，每次询问l，r，k，求问
字符串l——r中，包含字符串k（字符串k作为子串）的字符串个数是多少。
题解
多模式串匹配肯定是AC自动机
但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题，而不是经典的某个串能匹配多少个已经给出的串的问题。
AC自动机的Trie树中，某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说，他的所有祖先节点加上他本身构成了一个字符串。
而对于AC自动机建立的fail树来说，一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点，那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串，也就是完成了一个子串匹配。
于是我们可以借助这一点性质，来求解能匹配ac自动机中第k个字符串的字符串个数，方法是：
沿着当指向当前节点的fail路径的反方向走，每走到一个节点ans+1，最终无路可走时，得到的就是答案。（包括这个字符串本身）。、
但是这个题还有在区间[l,r]的字符串的限制。
考虑到普通的线段树没法做到这种询问，所以我们应该想到这个题可以用可持久化线段树来做。
可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳，我们可以利用这个时间戳去求区间的一个值。
但是这是一个AC自动机上的问题，准确的来说是fail树上的问题，如何建线段树？
对于树上问题，可以先想树链剖分，其本质就是求DFS序，所以我们也可以对fail树构建DFS序，然后在此基础依次添加每个串，构建可持久化线段树。
根据上面的fail树上的性质来说，通过fail路径的反方向路径构成的fail树，某个节点的子节点都是原先的fail指针指向当前节点的节点，也是我们要统计路径时走向的节点。
某个节点的子树，代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。
我们根据fail路径来构建DFS序，在此基础上建立可持久化线段树。在建立可持久化线段树的过程中，每添加一个字符串，都要对这个字符串在AC自动机Trie树上
题目大意
维护一个集合支持：
1.1. 添加一个模式串。
2.2. 删除一个串。
3.3. 给出一个串，询问有多少个子串在集合中出现过，多次出现多次计算。
题目要求使用fflush(stdout)方法强制在线。
题解
更新了AC自动机内存池回收写法的模板。
多模式串匹配算法，明显的AC自动机的题目。
但是众所周知，AC自动机不支持动态的插入操作以及删除操作（Trie树是支持动态插入的，但是AC自动机里面的fail指针是不支持的，插入字符串只能重新暴力重构fail指针）。
于是考虑建立多个AC自动机，但是很遗憾的是，如果每一次添加or删除操作我们都去建立一个AC自动机，那么查询的时候时间复杂度会炸掉，但是多个AC自动机的做法又不可避免。
所以我们就要想如何优化。
首先将插入和删除分开建AC自动机组是没有任何异议的。最终答案就是在插入的AC自动机组中的答案减去在删除的AC自动机组中的答案。
根据二进制加法（二进制堆的启发式合并）的启发，我们对属于同一种操作的AC自动机进行二进制分组。
我们在动态维护该种操作的时候，将新来的模式串新建一个AC自动机，并设置其数量为1，表示该AC自动机中带有的模式串的数量。
当当前的AC自动机中的模式串数量和前一个AC自动机中模式串数量相等的时候，我们就将两个AC自动机暴力合并。
能证明这样每个字符串最多被加入AC自动机并重构fail的次数在log2n次。
每次查询的时候，只需要将某种操作的AC自动机组中的全体AC自动机全部扫一遍就行了。
注意合并的时候回收空间。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
typedef long long ll;
int st[maxn<<1];
int cnt;
struct trie_node{
int next[26],fail,end,sum,ac[26];
}tr[maxn<<1];
struct AC_auto{
int root;
inline int newnode(){
int p = st[cnt];
for(in
题目大意
有n个节点的有根树，根为1，每条边有权值，点对(u,v)的路径长度为从u到v路径上所有权值的异或值，认为点对(u,v)与(v,u)表示两个路径，总共有n2个点对路径（自己到自己也算一个），求问其中路径长度第k小的路径长为多少。
题解
n的范围是很大的，不可能通过枚举计算。
两点(u,v)之间的路径长度,可以通过lca转化为：
(u,lca) xor (v,lca) = (u,lca) xor (lca,root) xor(lca,root) xor (v,lca) = (u,root) xor (v,root);
所以可以将每个点到根节点的路径异或长度预处理出来，之后再进行下面的操作。
建立一个01Trie，我们可以有办法求得路径异或长度不超过某个值val的路径数目。
对于当前位bit，我们去检查小于之前已经决定的答案ans加1<<bit的值的个数。也即当前的二进制位上的数为0的个数。
如果这个个数size小于k，说明答案应该是大于等于ans + (1<<bit)的，于是就决定当前的二进制位为1，k -= size，进入当前层表示为1的子树内再向下搜寻。
否则就直接进入当前层表示为0的子树内再向下搜寻。
整个搜寻答案的过程是O(62·n)的。加二分实际上是没意义的。
最后的一个问题就是，空间明显不允许我们开这样一个完整的Trie，所以需要动态建立每一层的Trie节点，用到什么建什么，不用的不管，搜寻下一层的时候要将上一层的节点表示清空。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll k;
int id;
const int maxn = 1e6+5;
ll v[maxn];
int pre[maxn];
int tot = 0;
ll siz[maxn];
int son[maxn][2];
int a[maxn],b[maxn];
void init(){
for(int i = 1;i <= n;++i)
son[i][0] = son[i][1] = 0,siz[i] = 0;
tot = 0;
}
int new_tag(int now,int ch){
if(!son[now][ch])
son[now]
Input
5 1 2 2 3 3 3 2 5 3 2 5 2 1 5 5
Output
2 3 1
题目大意
给出一个序列，有m组询问。
每一组询问有三个参数l，r，w，问区间[l,r]中所有由连续w个元素组成的子序列中的最小值中的最大值是多少。
题解
看到题目里面的最小值最大，肯定能意识到应该是用二分+check去验证元素的（因为其他能想到的方法基本都是暴力，复杂度太高，这题数据范围在105级别没法用的）。
然后问题就在于这个check如何去操作。
如果我们当前二分一个值mid，怎么检查区间l-r中是否所有的连续的w个元素中的最小值中的最大值是mid呢？
这个没法做到，我们只能去确定，是否存在连续w的区间的数全部大于等于mid。
我们假设当前二分到的值为mid，大于等于mid的数都设为1，小于mid的数都设为0，那么问题就变成了询问区间内[l,r]上最长的连续为1的子序列长度len是否大于w的问题。
但是我们注意到一些问题，序列中的数比较大，直接二分的话常数会大些，而且也没有办法对每次二分的mid建一棵线段树去check，时间上会炸掉。
这种情况下我们可以考虑将序列中的值从大到小排序，保留其原先所在的位置下标，对排完序之后的值，我们可以直接用序列进行二分。
而在排完序的情况下，可以注意到，以当前位置的值为check的值时，其构建的线段树就是上一个位置对应的check所用的线段树上在当前位置的值在原序列中的下标对应的位置插入1。
这个修改只有一次，因此可以建立可持久化线段树进行check。
当前二分的位置为mid时，对root[mid]对应的线段树进行check，检索是否可行就可以了。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
int n,q;
struct height{
int h;
int id;
}a[maxn];
int rt[maxn];
int u,v;
const int INF = 1e9+7;
struct tree{
int l,r;
int lc,rc;
int suml,sumr,sum,len;
}tr[maxn*25];
int cnt = 0;
void push_up(int now){
tr[now].len = t
题解
每条边的权值都是根据每个点的定值通过二进制异或得出的。
如果有两个点的数二进制高k位相等，那么我们如果要想要把这两个点的边加入最小生成树，那么花费的代价是与高k位无关的。
假设在第k+1位发生分歧，则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。
这明显是个递归过程，而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。
于是所有的答案统计全部都在01trie上。
接下来看kruskal算法的核心：每一次将最小边权的边试图加入最小生成森林。
所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。
假如一个叶节点上有k个点(k > 2)，那么对应的建边方案就是kk-2种。
当从叶节点向上走的时候，假设某节点的父亲节点的两个子树上都有点存在（即两个子树都非空），那么我们肯定要用边把这两个子树连起来，连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。
细节不是很好解释，不过这种思路是二进制异或时一种常见的贪心思路，可以看代码理解一下。
这个题不需要并查集，因为当刚向上走到某个点时，如果其两个子树都非空，那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
ll ans = 1;
while (y){
if (y & 1)
ans = ans * x % MOD;
x = x * x % MOD;
y >>= 1;
}
return ans;
}
void insert(int &d, int dep, int v){
if (!d)
d = ++sz;
题解
树上点对距离问题，非常经典的点分治问题。
点分治的基本思路：
对于当前的树（子树），求出其重心，统计过重心的合法路径数，然后以重心为分隔点，分别递归对删除该重心后的子树进行求解（继续求重心、统计，再进行递归）。
重心的概念：若一个点为树的重心，那么其作为根的时候，其子树的大小的最大值最小。
重心的性质：重心分割出的子树的大小不会超过now_n/2，可以用来证明其时间复杂度为O(logn * 统计的时间)。
此题要求距离小于等于k的路径数目，如果把每一种都算出来累加复杂度是相当高的。
可以使用树状数组，不过要注意树状数组的0号位对答案是不会造成任何影响的，所以在统计入树状数组的时候要稍微处理一下。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct edge{
int to,next,val;
}e[maxn<<1];
int siz[maxn],mx[maxn],vis[maxn],dis[maxn];
int c[maxn*100],tmp[maxn];
int n,rt;
int h[maxn];
int lowbit(int x){
return x & -x;
}
void update(int now,int d){
while(now <= n * 100 - 2){
c[now] += d;
now += lowbit(now);
}
return;
}
int query(int now){
int ret = 0;
while(now > 0){
ret += c[now];
now -= lowbit(now);
}
return ret;
}
int cnt = 0,num = 0,sum = 0;
void add(int u,int v,int d){
e[cnt].to = v;e[cnt].val = d;e[cnt].next = h[u];h[u] = cnt++;
return;
}
void get_root(int now,int fa){
siz[now] = 1;mx[n
#include <bits/stdc++.h>
const int maxn = 2e5 + 5;
using namespace std;
struct Trie{
int nex[maxn][26], fail[maxn], end[maxn];
int root, p;
inline int newnode() {
for (int i = 0; i < 26; ++i) {
nex[p][i] = -1;
}
end[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]-'a'] == -1)
nex[now][buf[i]-'a'] = newnode();
now = nex[now][buf[i]-'a'];
}
end[now]++;
}
inline void build() {
queue<int> que;
fail[root] = root;
for (int i = 0; i < 26; ++i) {
if (nex[root][i] == -1)
nex[root][i] = root;
else {
fail[nex[root][i]] = root;
que.push(nex[root][i]);
}
}
while (!que.empty()) {
int
题目大意
一开始有一个初始顺序的排列[1,n]，一共有m次操作，每次将数ai从序列中取出，放到最开头的位置生成一个新的排列。
求问在所有过程中每一个数最小的下标位置和最大的下标位置。
题解
最小的下标位置是非常容易求得的，这很明显，因为如果从来没有被放到开头，那么答案一定是i，否则答案就是1。
需要思考的点在于求最大的下标位置。
这个数据范围不允许进行模拟，链表也不行（链表的单个操作、查询效率极差）。
先来考虑一种特殊情况1：
假设当前所有的数字都已经被放置到第一位过了，在满足这种条件后的最大的下标位置怎么求。
明显元素之间一开始的位置在哪里已经完全互不影响了。
如果一个数再被要求放到第一位，那么这个操作之前的下标位置可能就会影响答案。
而这个下标位置是什么？我们想什么样的操作会影响这个下标位置。很明显只有在上一次此数被放到第一位的时间之后，不同的数字放置到第一位才会使得这个数字的位置向后推移。也就是说，这个下标位置，就是当前未操作时刻和上一次这个数被放到第一位以后的时刻，这之间的不同数字的个数再+1，也就是区间内不同数的个数。
树状数组可以离线询问区间内不同数的个数。由于这道题的特殊性，我们无需对询问区间进行右端点优先排序，直接操作查询即可。
然后再考虑剩下的情况2：
如果一个数之前没有被放置在第一位的经历该如何计算？
这样在它被第一次放置到第一位的命令执行以前，其最大下标位置是之前的时刻被放置在第一位的大于此数的数字的个数 + 此数最初的坐标值。问题变成了维护区间内出现的不同数字的个数，需要用另外一个树状数组进行维护，只需要再每个数字第一次被放置在第一位时维护一次，查询一次即可。
在问题的最后，这样不一定已经求得最大值，因为对于每一个数字，最后可能有影响到最大值的问题但是没有查询更新。
所以在最后我们就要：
对于在操作序列中出现过的数字，我们执行情况1的查询一次。
对于未在操作序列中出现过的数字，我们执行情况2的查询一次。
代码
#include <bits/stdc++.h>
const int maxn = 3e5+5;
using namespace std;
map<int,int>mp;
int tr[maxn],a[maxn],ans[maxn],c[maxn];
int n,m;
int lowbit(int x){
return x & (-x);
}
void add(int x,i