JOISC2020Day4A首都JOIAtCoderLuogu考虑一条链的情形。如图，将每个城市视为一条线段，容易发现交错（有交但不包含）的若干线段必须全部合并才能符合条件。但如果这么写会出错，原因是线段有包含关系，外层线段需要统计内层线段的答案，但内层线段不需要统计外层线段的答案。如果设内

P7215[JOISC2020]首都考虑对于颜色\(c_i\)，若在此颜色集合内所有节点之间的路径上出现了其他颜色(如\(c_j\))，那我们则不得不将这两种颜色合并在一起，操作数加一。即对于颜色\(c_i\)，若设其为首都，其答案(操作数)为所有颜色为\(c_i\)的节点之间的路径上的颜色种类

会发现题目的坐标其实是平面直角坐标系。我们按\(y\)坐标从小到大考虑所有的星星，假设当前考虑到了星星\(i\)。我们先计算出之前所有能够影响到\(i\)的星星的代价和为\(cost\)（可以用树状数组维护）。然后分类讨论。若\(c_i\lecost\)，那么肯定直接将\(i\)直接涂黑，因为它更

P7219[JOISC2020]星座3笛卡尔树+整体dp（线段树合并维护dp）考虑转化题意，不存在矩形为星座，即对于每个极大矩形中都只有一颗星星。而观察题目的方格，对于两个位置是否能够成为一个矩形，只和两个位置的区间最大值（小白船的位置）有关①。图中的红蓝矩形即为两个极大矩形。将删除星

[JOISC2020]最古の遺跡3好难的题。首先考虑给出\(h\)怎么求\(A\)，设\(h'_i\)为\(i\)位置剩下的高度，没了就\(=0\)。方便起见，我们把原序列翻转一下，那么题目的操作就是，每种高度的最靠左的位置不变。我们从左到右依次求解，先令\(h'_i=h_i\)，若\(h'_i\)在\(j<i\)的\(

现在Bitaro准备用扫帚打扫房间。我们认为扫帚是放置在房间里的一条线段，并且将这条线段的长度称为扫帚的宽度。由于Bitaro很有条理，所以他只会用以下的两种方式打扫房间：Bitaro将扫帚平行于\(y\)轴放置，一端位于原点。然后他会垂直向右移动扫帚，直到不能移动为止。如果扫帚的

[JOISC2020]最古の遺跡3题目背景JOI教授是一名研究IOI王国的历史学家。题目描述他发现了一行古代石柱的废墟及一份古代文献。古代文献上的记载如下：刚建造完成的时候，有\(2\timesN\)个石柱，对于\(1\lek\leN\)均有两个石柱高度为\(k\)，同时记第\(i\)个石柱的高度

\(\text{ByDaiRuiChen007}\)ContestLinkA.Building4ProblemLink题目大意给\(2n\)个数对\((a_i,b_i)\)，构造一个非降序列\(c_i\)满足\(\forall1\lei\len,c_i\in\{a_i,b_i\}\)，且\(c_i=a_i\)的位置恰好有\(n\)个。数据范围：\(n\le5\times10^5\)。思路

P6891[JOISC2020]ビルの飾り付け4题目传送门Problem给定长度为\(2n\)（\(1\len\le5\times10^5\)）的序列\(A\)，\(B\)。要求构造一个单调不降的序列\(C\)。每个\(C_i\)从\(A_i\)和\(B_i\)中选取，且\(A\)，\(B\)中都恰好选取\(n\)个。Solution最直接的想法显然是dp

1.P6891[JOISC2020]ビルの飾り付け4本题如果按照最直接的方式dp时空都是\(O(n^2)\)。可以用一个常用的优化：交换下标和值，用dp数组维护一个集合（可以证明是一个区间，于是用左右端点表示）。2.P7216[JOISC2020]美味しい美味しいハンバーグ正解是2-SAT，但是太麻烦，码量大难想。其

JOISC2020Day1建筑装饰4Building4我们发现\(A\)的个数是连续的，所以我们只需要DP出最大的\(A\)的个数和最大的\(B\)的个数，若两者都\(\gen\)那么就有解。然后再从后往前推出方案即可。https://qoj.ac/submission/109314*JOISC2020Day1汉堡肉HamburgSteak我们

考虑给你\(h\),怎么整体得到最后的\(a\)这里感觉不能去想让一个位置\(x\)留下来的冲要条件，不然可能就做不出来了。自然的想法：从$2n$到\(1\)遍历每个\(h_i\),然后从\(h_i\)到\(1\)找第一个没有标记的值\(x\),此时\(i\)能留下来，如果找不到\(x\)，那么\(i\)无法留下来

不想写题解了，把写在草稿纸上的东西整理了一下感谢crashed大佬的题解与对本人问题的回答，没有他我就不会搞懂这道神仙计数题。

【JOISC2020】治疗计划DescriptionJOI村庄有\(N\)个房屋，编号为\(1\)到\(N\)，每个房屋住有一个村民，第\(i\)个房屋居住编号为村民\(i\)。现在，这\(N\)个房屋里的

题目点这里看题目。分析观察一下部分分，前三个subtasks都比较简单。仔细思考一下，发现之后的难点都在于\(x,y\)两个坐标分离处理，这导致我们无法轻易地找出需要被修改

题面传送门实在没东西写了，随便拉一道题凑数。首先看这个东西就感觉只和两个点有关，事实上也是这样。关于最大值的问题肯定要把笛卡尔树建立出来，然后最大值变成两个点的LC