令\(S\)为题面的\(S'\)。首先考虑刻画出\(\texttt{()}\)对应的折线。首先如果\(S\)本身合法，那么直接DP算一下就行了。否则考虑不合法的情况，考虑反转\((l,r]\)合法的情况的判定。令\(s_i\)为前\(S_{1\simi}\)的前缀和的值。那么有：\(s_r-s_l=\frac{s_n}

考虑把这个停车位当作栈来考虑，每次可以取出栈顶放到另一个栈，并且要保证另一个栈\(sz\le2\)，且当\(sz=2\)时要保证栈顶栈底都是同一种元素。令\((x,y)\)表示\(x\)为栈顶\(y\)为栈底，\((0,x)\)表示栈中元素只有\(x\)。考虑对于\((x,y)\)，连一条\(x\toy\)的边，若

记事件\(A\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\)」，事件\(B\)为「当\(s_i=\texttt<\)时\(p_i<p_{i+1}\)，且存在\(s_j=\texttt>\)，满足\(p_i<p_{i+1}\)。所求即\(n(A)-n(B)\)。\(n(A)\)是好求的，相当于部分定序排列，记每个递增段的长度为\(a_1

\(\mu\)取值即所选边权的中位数。把每条边拆成两条（黑边和白边），边权分别为\(\mu-w_i\)和\(w_i-\mu\)，要求黑边和白边各选\(\left\lfloor\dfrac{n-1}2\right\rfloor\)条，求最大生成树。可以直接wqs二分，时间复杂度\(\mathcalO(nm\logw~\alpha(n))\)。把所有边的边权

由题述，\(X\)满匹配，根据Hall定理，有对于任意一个有\(k\)个妹子的集合，她们能配对的男生的人数\(\gek\)。把每个妹子看作她所连接的两个（可能是同一个）男生间的无向边，则每个连通块必然是树或基环树。问题转化为给每条无向边定向，满足每个点的入度不超过\(1\)，求最大边权和。对

审题一条链每条边有通行时间上下界限制通过一条边需要\(1\)单位时间站在当前节点时间减少\(1\)耗费\(1\)单位代价\(q\)次询问要么更改一条边的通信时间上下界要么询问在\(b\)时刻在城市\(a\)，\(d\)时刻到达城市\(c\)的最小代价思想做题准备

因为最后的比较方式是字典序，可以明确肯定是贪心的先让第一个数尽量大，然后是第二个数尽量大，以此类推。考虑到如果选出了第一个数，那么按照其\(\text{dfs}\)的方式，相当于是把根到这个树的链删掉了，变成了许多颗子树，然后在按照\(\text{dfs}\)遍历这几个子树的顺序依次在子树中类似

题意简述给定一个数列，支持以下操作：查询\(k\)在区间内的排名（区间内比\(k\)小的数的个数\(+1\)）查询区间内排名为\(k\)的值修改某一位值上的数值查询\(k\)在区间内的前驱（前驱定义为严格小于\(k\)，且最大的数，若不存在输出-2147483647）查询\(k\)在区间内的

考虑到这一条链肯定是单调递增或者单调递减更优。因为若不是单调的可以考虑把这个链拆成多个单调的链。因为若最大最小值不在链的两端，明显把两端不需要的可以拆出去；否则例如链的顶比底大，则肯定存在\(x>x'<y'>y\)，\(x,y\)为链的两端，那么\(x-x'+y-y'\)的收益明显

LibreOJ#535.「LibreOJRound#6」花火\(n\)个烟火排成一排，从左到右高度分别为\(h_1,h_2,\cdots,h_n\)，这些高度两两不同。每次Yoko可以选择两个相邻的烟火交换，这样的交换可以进行任意多次。每次Yoko还可以选择两个不相邻的烟火交换，但这样的交换至多进行一次。你的任务

模拟赛考的题，但是模拟赛没有打，哈哈，摆烂。考场上想到大致做法了，没继续推，去打GPofTokyo了。首先发现操作都在查询前面，所以我们只需要预处理出答案即可。我们先记\(b_i\)表示对\(i\)进行的操作的总和，那么容易写出\(a_i\)的式子：\[a_i=\sum_{j|i}b_j\cdot\frac{i

简要题意给出一个长度为\(n\)的序列\(a\)。你需要选出它的一个子集\(S\)。使其满足对于任意两个元素\(i,j\)。满足：\[\gcd(i,j)\cdot\gcd(i+1,j+1)\neq1\]输出满足条件的子集大小的最大值。\(1\leqn\leq500,1\leqa_i\leq10^{18}\)思路这道题比CodeforcesGym1

链接难度：\(\texttt{?}\)有一颗\(n\)个点的树，每个点有权值\(x_i\)，定义一条简单路径的权值为\(f(a_1\toa_2\to...\toa_k)=\frac{x_{a_1}\timesx_{a_2}\times...\t

第三部分图论第1章最小生成树#10064「一本通3.1例1」黑暗城堡#10065「一本通3.1例2」北极通讯网络#10066「一本通3.1练习1」新的开始#10067「一本通

题意修改一条边意味着，删掉一条边，并加入一条新的边。给出一棵树，对于每个点，求出使它变成重心的最小修改边数。分析先找到重心，对于不是重心的一个点\(i\)，有两种方法，一是

分块九讲一些闲话忽然好想学分块~~LOJ我来了！！！题目link（聊天记录来源于群hello,LibreOJ）