搞了很久，题解区有线段树爆改pushup高妙做法说下cdq分治先将点都按横坐标从小到大排序，cdq分治，那我们现在只需要考虑分治过程中\([l,mid]\)和\([mid+1,r]\)互相形成的合法点对，显然左边的横坐标都小于右边的横坐标。能够发现，如果右边有一个点插在一对本来合法的点之间，那么那对合法

MyBlogsP10432[JOISC2024Day1]滑雪2感觉是挺好的观察性质题，vp的时候场切了。首先酒店一定是建在最低的某一个点。把高度离散化之后，把点扔到对应的位置。可以发现高度为\(i\)的层的所有点，如果能接上一层的连接器那一定会尽量接上（因为到了下一层它本身也可以贡献一个空

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

感觉我太滞后了Day1T1Fish3我们可以做的操作是单点加\(D\)和后缀加\(1\)，考虑把这个操作放在差分数组上，则操作变成了：单点加\(1\)。\(i\)处加\(D\)，\(i+1\)处\(-D\)。需要最小化第二种操作的使用次数，发现只有对于所有差分数组中的负数是不得不用第二种操作的，而对于

Day1T1Cultivation发现任何的两个操作之间时没有偏序关系的，也就是我们可以任意调整操作之间的顺序。那么本质不同的操作，可以用\(l,r,u,d\)四个数表示，分别表示向左/右/上/下移动的次数。假设我们已经确定了\(u,d\)，则会出现\(O(n)\)类本质不同的行，而对于每一行，都会给\(l,r

LOJ传送门考虑若已求出钦定\(k\)个升高的排列数量\(f_k\)，那么二项式反演就可以求出恰好\(k\)个升高的排列数量\(g_k\)，即：\[g_k=\sum\limits_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i\]考虑求\(f_i\)。相当于钦定原序列构成了\(n-k\)个上升段。相当于把\(n\)个

JOISC2018loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1简单题。根据颜色段均摊的结论，每个点到根的路径上颜色段的总和是\(O(n\logn)\)的，于是直接每次暴力找颜色段即可。复杂度\(O(n\log^2n)\)。提交记录D1T2又是计算几何。我们需要画出一条闭合折线，并且

JOISC2017loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1开场放大。首先，对于一个点，它最后覆盖的一定是一个矩形，这就意味着如果我们知道了\(u,d,l,r\)操作各用了多少次，他们之间的顺序是不重要的，我们可以直接当做把一种操作做完再做剩下的操作，这样就可以做到\(O(

JOISC2016loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1一开始把题目看错了，还写了棵线段树。把询问离线，倒着扫一遍，就变成了求最长不上升子序列，用树状数组维护即可。提交记录D1T2来自Kubic的神仙做法。考虑Filp一个位置和剩下所有位置，记录每个数作为答案

JOISC2015loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1简单题。因为\(k\)很小，考虑依次确定最后第\(i\)位是什么。我们倒序考虑所有操作，维护最后第\(i\)位当前在第几位，就可以一直推下去。提交记录D1T2直接暴力复杂度就是\(O(k4^k)\)的，可以通过。提交

JOISC2014loj上有几乎全部的题目，写了题意的就是loj上没有的。D1T1想到了最短路的做法，不过可能还需要整体二分，复杂度至少有2log。有复杂度更优秀的贪心做法。把边按时间倒序加边，然后从终点开始dfs来更新每个点可以的最晚出发时间，每条边走之后肯定就不会再让答案变优了，

Day1T1Examination三维数点板子题，直接cdq分治+树状数组，时间复杂度\(O(n\log^2n)\)。Day1T2Meetings对于一个大小为\(n\)的树，我们可以在\(n-2\)的询问中得到某一条我们选定的链\((x,y)\)上的所有节点的集合\(S_0\)，以及在断掉这条链之后，得到的若干连通块集合\(S_1,

Day1T1Building4首先有一个\(O(n^2)\)的DP：记\(f_{i,j,0/1}\)表示已经填了前\(i\)位，其中有\(j\)位选择了A序列，当前第\(i\)位是选自A序列还是B序列是否可行。通过打表或推理发现，对于\(f_{i,j,0/1}\)中的每一个\((i,0/1)\)，为\(1\)的\(j\)是一个连续段，这

题意给定\(n\)个点，求平面上，曼哈顿距离最近的\(k\)点对。Sol仔细想想就会发现，曼哈顿距离不好做最近\(k\)点对。考虑转成切比雪夫距离。\(x'=x+y,y'=x-y\)。二分答案，每次\(check\)一个\(dis\)，询问距离小于\(dis\)的点对是否有\(k\)个。\(check\)是平凡

Day\(\mathbb{P}_1+\mathbb{P}_2+\mathbb{P}_3+\mathbb{P}_4+\mathbb{P}_5+\mathbb{P}_6\)。放到二维平面上考虑，点\((x,y)\)表示\(x\)时刻在\(y\)位置上，那么第\(i\)顾客的路径可以看成起点为\((t_i,a_i)\)，终点为\((t_i+|b_i-a_i|,b_i)\)的线段\(P_i\)。注意到一个

最终形态一定是\(n\)个点形成的一个大环。故每个点的入度一定为\(1\)，我们考虑保留每个点入度中\(c_i\)最大的边，剩下的删除，此时原图一定变成一堆链加一些环。对于环，我们是需要拆开的，此时我们可以枚举环上每个点，考虑将其反悔，反悔代价为环边代价减去其次大入边（最大入边一定为

[JOISC2021Day2]道路の建設案(RoadConstruction)题意给定图上\(n\)个点，求前\(k\)小曼哈顿距离点对距离。题解很好的一道题。首先有一个\(O(nlog^2n)\)的做法，个人感觉还是很有启发性的。一般对于第\(k\)小的处理方法是二分，二分第\(k\)小的距离是多少。然后统

  朴素的DP形式是定义\(f_{i,j,A/B}\)表示前\(i\)个元素选择了\(j\)个\(A\)的可达性.\(\mathcalO(n^2)\).交换状态与值域,定义\(f_{i,A/B,A/B}\)表示前\(i\)个元素中的最后一个元素(即\(i\))选择了\(A/B\),在最大化\(A/B\)的数量的目标下求得的\(

試験/Examination直接三维偏序。#include<iostream>#include<cstdio>#include<cstring>#include<numeric>#include<algorithm>usingnamespacestd;constintN=100005;intn,Q;intv[N*6],cnt;structQuery{inta,b,c;intv,i

ビルの飾り付け4/Building4令\(f_{i,0/1,j}\)表示到第\(i\)位，第\(i\)位选的是\(A_i/B_i\)，\(1\simi\)选了\(j\)个\(A_i\)是否合法。可以发现，对于一个\(f_{i,0/1,j}\)，合法的\(j\)一定是一段区间，那么就完了。#include<iostream>#include<cstdio>#include<c

题目真的很好！！！所以来写一写。但都是一句话题解，因为我实在很懒。打*的是没独立做出来的。慢慢补，不急2023Day1T1TwoCurrencies签到题。主席树上二分就行。$O((n+Q)\logn)$。*2023Day1T2FestivalsinJOIKingdom2还不会。2023Day1T3Passport走遍$1\simn$显然

[JOISC2014]電圧题解赛时都想到了我也不知道为啥自己没敢写首先题意可以转化为，我们去掉一个边后，剩下的图可以黑白染色，同时保证去掉的边两端的点颜色相同，问这样的边数。换句话说，去掉一条边后，剩下的图应该是一个二分图。然后我们很容易想到线段树分治来处理这种问题。每次只有

洛谷传送门LOJ传送门为了方便，设\(a_0=a_{n+1}=\infty\)。考虑拎出来所有区间\([l,r]\)使得\(\sum\limits_{i=l}^ra_i<\min(a_{l-1},a_{r+1})\)。那么\([l,r]\)中的所有鱼都不能吃到\([l,r]\)外面的鱼。那么\([1,n]\)中能吃掉所有鱼的鱼，一定不被

[JOISC2016]雇佣计划题解这里补充一篇自己的\(n\logn\)做法。本蒟蒻打了两棵线段树，并且进行了繁琐的分类讨论，完全被标算的树状数组吊打qwq题意：给定一个序列\(a\)，有两种操作：将\(c\)位置权值改为\(d\)；给定一个权值\(b\)，定义集合\(S=\{i|a_i\geb\}\)，对于

记录一下JOISC2023的做题记录Day1T1TwoCurrencies给定一棵树，在边上有总计\(m\)个检查站，经过一个检查站需要叫\(1\)枚金币或者若干枚银币。\(Q\)次询问，问一个人有\(X\)枚金币和\(Y\)枚银币，能否从\(u\)走到\(v\)，同时回答最多可以留下多少枚金币。发现一定是