我们不妨将入栈操作看作在这个时间点加1，将出栈操作看作这个时间点-1。那么询问当前时间点的栈顶元素就是找到最大的后缀下标使得这个后缀的和是1即可。我们通过线段树来维护区间后缀值，维护时，需要同时维护这个区间和以及后缀最大值。如果采用是自底向上的线段树即zkw线段树，那么query只要一个函数即可。如果采用常规的自顶向下的线段树，需要先找的合法的右端点，然后找到合法的区间用第二个query来查找答案。 代码： #include <cstdio> #include <algorithm> #include <cstring> #include <stack...

这里介绍一种失了智的算法。这种算法基于插桩原理。我们每隔len插一个庄,我们发现所有长度为len的子串都会和一个桩相交。然后对于每个长度len我们只要能够通过n/lenlog(len)的复杂度算出所有长度为len的SAN值就可以在nloglog的时间复杂度内解决问题。这里有三个子问题：1.如何判断[l1,r1]和[l2,r2]这两个子串是否相等，这里采用字符串哈希O(n)预处理 O(单次取模)查询。2.如何判断过当前桩的所有子串和过前一个桩的子串有递增SAN值的关系，这里采用二分加哈希的方式来解决O(n)预处理 O(log*单次取模)的复杂度，也可以采用两次后缀数组的方式O(nlog)预处理 ...

这是一道典型的网络流题目。我们只要对于每个SPF值向汇点连一条容量为这个SPF值个数的边，然后源点向每头牛连一条容量为1的边，每头牛向每个可用的SPF值连一条容量为1的边，求最大流即可。这里还有一个问题就是如果按照上述方式建图可能或有C*1000条边这个数量级是2e6的有可能TLE，我们需要建边优化。我们发现每头牛的可达SPF值是一个连续的区间有可能有1000个具体节点，我们通过建立一种类似于线段树的网络流模型来使一头牛的可达SPF值为log(1000)个。具体算法是先建立一颗区间为[1,1000]的线段树，然后每个叶子节点[l,l]向汇点连SPF值为l的个数的边，然后每个非叶子节点分别向其左...

没有人写题解我来写一发 A-小蒟和他的乐谱 设当前的音符为x ，((x - 1) % 7 + 7) % 7即为这个数在模7意义下的正模。 判断是不是0，1，2，4，5即可。 然后问题简化为求最长全1段。 复杂度O(n)。 B-小琛和他的学校 我们钦定1为根，那么任意一条边的两个端点就有了深浅。 我们定义u是深度较浅的端点，v是深度较深的端点。 定义sum是学生总量，sz[v]是以v为根的子树点的个数，dp[v]是以v为根的子树的学生的个数。 这条边仅会被如下两种情况使用： 1.以v为根的子树的点发起活动，那么这条边使用...