题意就不说了，中文题面，我觉得题目应该讲的够清楚了。 先分享一下我做这道题的辛酸路程吧看完这道题后，我的第一想法就是先预处理出以每个点作为左端点然后得到一个右端点的范围使得它们构成的区间是合法的。以这一步好像是和出题人题解里说的是一样的。然后对于一个询问要如何快速的回答呢？起初我脑补了一个主席树来求区间内大于k的数的和之类的东西，但是发现好像需要分类讨论，然后想了想那样写起来巨麻烦就把这个想法叉了（也许是我太菜了，没想到好的处理方法QAQ）。接下来的一个小时时间里我还陆续脑补了几个假算法但是也都被我自己叉了...然后又看了一遍题目发现好像并没有要求强制在线？而我却一直在想用一个在线做法去做....

题意：给出一个长度为n的序列，k个位置，代表序列里这些位置上的数是固定的。每次可以修改序列里没被固定的一个数，问最少几次修改可以使得整个序列变成严格递增的，或者不可能。 两个小结论 1、把一个序列A变成非严格单调递增(单调不下降的)，至少需要修改的数个数为序列A的总长度减去A的最长不下降子序列长度。2、把一个序列变成严格单调递增的，至少需要修改的数个数，构造序列B[i]=A[i]-i,答案为序列总长度减去B的最长不下降子序列长度。 思路：这道题如果把固定一些数这个条件去掉的话就是看成上面结论2一样的问题了，但是仔细观察可以发现k个数将整个序列分为了k+1个部分，因为k个数是固定的，所以这k+...

比赛的时候想到是dsu on tree了，但是没想到如何去高效的维护答案，赛后听了大佬的做法后，恍然大悟。然而后面还是调了半天才调处来...看来我对树上启发式合并的理解还不够深刻。新学了一个卡常小技巧，枚举子树的时候之前是用dfs去遍历的，但是其实可以预处理整棵树的dfs序，之后只要枚举dfs序就可以了。 #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define X first #define Y second #define ...

PS:昨天晚上,已经学了两三天的后缀自动机的我，大致有点明白但是还是不是特别明白...心情有点烦躁。于是索性就去整理了一下自己有哪些还是不会的算法，于是便发现了dsu on tree和线段树合并这两个算法是我很久以前就想学的，但是因为时间有限还是一直拖到了现在...今天下午来实验室，打算先学dsu on tree，就先在网上看了几篇博客后，大致就懂了，还去特地做掉了cf上大佬们推荐的所谓的模板题发现的确不难，是个套路算法-_-。ac那题后，我点开了standing，发现那道题几乎我的每个好友都做了。(心想看来的确是模板题实锤了)这时发现我的一个队友以前也做了这道题，点开了她的代码后，发现为啥和...

题意： 给定一个正整数序列a1,…,an。你可以进行若干次操作，每次操作可以选择一个满足ai=i的位置i，将其删去。删去后，左右两边会自动拼合到一起（也就是右边所有数下标都会相应地变化）。 你想要最大化删去的元素数量。 但是这个问题太简单了，所以你需要回答q次询问。每次询问给定两个正整数x,y，求如果将序列的前x个数和后y个数变成n+1（也就是强制它们不得被删去），新的序列里最多能删掉多少个数呢？ 注意，每次询问是独立的，也就是说询问后，序列会复原。 数据范围：1≤n,q≤3×105，1≤ai≤n，x,y≥0,x+y<n。 题解 先不考虑多次询问。只针对一个给定的序列，如何求答案呢？ 我...

看题面很显然的一道数据结构题，但是对于2和3操作我想了一会没有啥思路，网上看了大佬的博客，发现只需要维护线段树上的每个结点的左右儿子是否交换就行了，在纸上模拟了几遍就想通了。唉，这就是思维的差距吧... AC代码 // Author: Feng #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define pii pair<int,int> #define pll pair<ll, ll> #define p...

先通过前(n+1)项，插值求出f(n+1)，然后通过这(n+2)项来插值求出f(x)的前缀和函数S(x)，答案为S(r)-S(l-1)。 // Author: Feng #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define pii pair<int,int> #define pll pair<ll, ll> #define pli pair<ll, int> #define pb push...

题目让我们求出将八数码复原的最小步数并且输出出具体方案，这是一道搜索题，因为数据范围很小。但是这道题可以借助两个算是比较高级的知识来优化，A* 算法和康托展开，A*是因为加入评估函数后可以大大的加快搜索速度。这道题的评估函数便是每个数当前所在位置和那个数最终所在位置的曼哈顿距离总和。而这里因为棋盘上的每个状态不是像一般的问题那样是某个点或是某个数，而是一个全排列的不同排列方式，不太容易记录每个状态，当然可以用普通的哈希去做，但是因为这里是全排列的缘故，所以借助康托展开和逆康托展开是十分适合这道题的，效率上是线性的，因此时间上也是会更占优。 // Author: Feng #include&lt...

题意：给你n个字符串，每个字符串s[i]都有相应的花费代价cost[i]。问用这些已有的串拼出一个给定的T串的最小花费是多少。 思路：已知有n个模式串，再给出一个匹配串。很标准的一道AC自动机的题，花费最小的话也很容易想到用dp来做，dp[i]代表能拼出T[1~i]的最小花费,转移方程 dp[i]=min(dp[i],dp[i-len(s[i])]+cost[i])。但是不能直接用匹配串跑一个裸的AC自动机，这里需要用到trans指针优化，否则会卡在一组数据上。（好菜啊...学了两天的AC自动机终于把这题补掉了 AC代码 #include<bits/stdc++.h> using ...

问题：给定一个字符串，随机取一个子串，求元音(a,e,i,o,u,y)字母占子串长度比的期望是多少？ 思路：比赛的时候我一直想的是如何计算原字符串中每个元音字母对最后答案的贡献，但是想了好久都没理清其中的关系，最后还是靠队友手模所有情况找出了规律... 后面到网上看了大佬们的博客后才发现这题是要枚举区间长度的贡献值。这里总结一下一般求全区间的解的做法，单独元素算贡献，枚举某个点结尾或开始的总贡献，枚举区间长度贡献。 所以这道题我们只要计算出f[i]代表长度为i的区间的元音字母总个数。这个可以通过前缀和线性的递推出。最后答案就是∑(f[i]/i)/n(n+1)/2 。 AC代码 #includ...

给定一个长度为N的浮点数数组a。请找出其中乘积最大的子数组。例如，给定数组{-2.5, 4, 0, 3, 0.5, 8, -1}，则取出的最大乘积子数组为{3, 0.5, 8}。也就是说，在上述数组中，3 , 0.5和8这三个数是连续的，而且乘积是最大的。 思路： 设计状态代表以结尾的子数组中，乘积的最小值，代表以结尾的子数组中，乘积的最大值。赋初值状态转移方程为 因为当时，以结尾的子数组的最大乘积必定由前一个数结尾的最大乘积转移而来,因为无论前一个数的最大乘积是正是负，乘上一个正数后它依最大或最小的性质保持不变。最小乘积的转移同理。当0时,以结尾的子数组的最大乘积的转移就有两种可能了，如果前...

快速排序 int a[N];//待排序数组 inline void swap(int& x, int& y) { int tmp = x; x = y; y = tmp; } void quick_sort(int l, int r) { if (l >= r)return; swap(a[l], a[(l + r) / 2]); int i = l, j = r, x = a[l]; while (i < j) { while (i < j && a[j] >= ...

题意：给你一个长度为n的数组a,（1<=n<=1e5 ,1<=a[i]<=200 or a[i]=-1）。a[i]=-1代表i这个位置的数是未知的否则已知，对于每个未知的数你可以把它设置成1-200之间的任意整数。问你有几种设置方法可以使得整个序列满足：a[1]<=a[2],a[n]<=a[n-1],当 2<=i<=n-1时 a[i]<=max(a[i-1],a[i+1])。答案取模998244353。 思路：问题转化一下，其实题目要求的就是你构造出来的序列里的每个数它的边上至少有一个数比它大。然后再看数据范围，每个数都在1-200之间，很...

  Splay这个名字在我很早的时候就听说过了，是寒假的时候在lyd的蓝书上学平衡树章节的时候，他在那一章节的最后强力推荐的一种平衡树。"Splay(伸展树)灵活多变，应用广泛，能够很方便地支持各种动态的区间操作，是用于解决复杂问题的一个重要的高级数据结构。"(原话)。 当时就使我就对splay满怀期待,但是碍于各种原因一直没有专门花一块时间去搞懂它就一直拖着（主要是我懒）。这次刚好借算法作业的机会算是完整的去了解它一次了。 Splay简介： 它是通过一种通过splay（伸展）操作来实现平衡的一种平衡二叉查找树。而这个操作就基于一种叫rotate（旋转）的操作来实现的。 S...