再再次来到宇宙中心曹县所在的省份参加省队集训。
Day1
模拟赛
T1
原来是简单题/ll
给一个\(m\)次多项式\(f\)，\(a_0\)和\(b,c\)，求
\[a_n=a_{n-1}+f(n)a_{\lfloor\frac{n+b}{c}\rfloor}\]。\(m\leq 20,n\leq 10^{18},b<c-1\)，膜\(1004535809\)。
考虑大力拆\(n\)次 :
\[a_n=a_0+\sum_{i=1}^nf(i)a_{\lfloor\frac{i+b}{c}\rfloor}\]，然后呢?好像没有什么性质。
为了简洁先记\(t(i)=\lfloor\frac{i+b}{c}\rfloor\)，\(r(i)=ic-b\)是最小的使得\(t(r(i))=i\)的数，然后再拆一层，交换求和号 :
\[\begin{aligned} &\sum_{i=1}^nf(i)a_{t(i)}\\ =&\sum_{i=1}^nf(i)\left(a_0+\sum_{j=1}^{t(i)}f(j)a_{t(j)}\right)\\ =&\sum_{i=1}^nf(i)a_0+\sum_{i=1}^nf(i)\sum_{j=1}^{t(i)}f(j)a_{t(j)}\\ =&\sum_{i=1}^nf(i)a_0+\sum_{j=1}^{t(n)}f(j)a_{t(j)}\sum_{i=r(j)}^nf(i) \end{aligned}\]然后就很好玩了。你发现后面的东西看起来就像……呃是一个多项式。
它是\(f(j)(S_f(n)-S_f(r(j)-1))\)，这东西是\(2m+1\)次的。你发现\(t(n)\)是折半的，每一轮多一个\(O(m)\)次，所以递归到最后剩下次数是\(O(m\log n)\)的可以接受。
然后问题就是怎么求这个，显然乱插就可以了。复杂度\(O(m^2\log^3 n)\)。
T2
二分图最小边覆盖，构造方案。简单题。
T3
有一棵未知的\(n\)个点的二叉树，你可以问\(5\times 10^6\)次，每次问一个点对的距离。\(n\leq 10^5\)。
好玩题。
看起来像是\(\log\)，自然想到树分治。
各种分治需要使用\(size\)，但是我们显然搞不定这个东西，所以考虑链分治(长链剖分)。呃这不是根号吗?问题不大，想完再说，再说了总能水到很多分(出题人表示有60)。
先找到最深的点，这个全问一遍就好了。然后我们对于每个点要找到它在这条链上还是在链上某个点的轻子树上。
再把每个点跟最深的点问一遍，因为我们已经知道了深度，由\(\mathrm{dis}(u,v)=\mathrm{dep}(u)+\mathrm{dep}(v)-2\mathrm{dep}(\mathrm{lca}(u,v))\)就可以得到\(\mathrm{lca}(u,v)\)的深度，由于这个\(\mathrm{lca}\)一定在\(1\)的重链上，我们可以确定\(\mathrm{lca}\)。把这个点挂到这个\(\mathrm{lca}\)上，表示它在这个点的轻子树上，当然特判掉它就是这个点的情况。
然后递归每棵轻子树，我们的复杂度就是\(O(n\sqrt{n})\)了!
但是它再怎么说还是60pts。考虑怎么套用到重链剖分。
如果我们已经知道了这棵树的重链剖分结构，那就可以随便做了。所以相当于要动态维护重链剖分。
实际上有两个做法，硬上动态重链剖分(也就是用平衡树维护所有重链，这里只需要挂一个叶子所以比较简单)，或者直接套用lct。啊你说怎么用lct?每次问完access一下摊掉就好了。不过注意维护的时候，每个点不是 在轻子树，而是 在某个子树。
至于怎么证明动态维护这个东西得到的询问次数界还是一个\(\log\)?我也不会，但是感性理解很对。
期望得分20+100+10=130，实际得分20+100+0=120，海星罢。
讲课
非传统!
退火
造计算机
把需要的运算列出来，全都拆成基本运算，然后尝试用给出的运算实现这些基本运算……
对于某些奇怪的函数要敏感。
二分
猜数游戏，告诉你\(\leq\)还是\(>\)。多次询问，你的操作次数只有\(q(\lg(n+1)+0.1)\)。\(n\leq 10^9\)，\(q\)足够大但又不太大。
确定性死定了，因为如果某次问到了多一次的位置，那么一直问这个你就死了。
考虑这个东西听起来很离谱，你发现随机扰动并不可行，因为有些位置多问一次的概率就是更大。
考虑我们所能做的最纯粹的随机，直接找到所有数然后随机一棵决策树，也就是钦定一些点深度大\(1\)。
但是这个太慢了，不过我们可以随机一个区间钦定它深度大\(1\)。
这样的决策树是可以快速计算的，具体方式我也不是很清楚，反正一听就可以快速计算。
不过据说直接这么做还过不了，需要加一些别的奇技淫巧。
无标号树
有一个1e18以内的数，你要把它编码成一个\(100\)个点以内的无标号树，然后解码。
两个做法。基本想法是，先搞一条链，用两个奇怪的东西标记开头结尾，然后往上挂东西来表示信息。
但是直接挂\(2\)进制是不够的。
考虑这个挂东西相当于挂任意无标号有根树，你发现选取\(4\)进制的时候恰好就可以用\(3\)个点表示一位，然后你就过了。事实上选取更大的进制可以得到更大的表示范围，不过那就意义不大了。
另一种做法是，\(2\)进制里面我们不再是用挂上表示\(1\)，而是用挂上表示\(01\)中较少的，再加一个标记表示哪个更少。
图
给你一个\(n\)个点的有标号无向图，你要把它编码成一个不超过\(n+12\)个点的无标号无向图，然后解码。\(n\leq 1000\)。
简单想法是用\(10\)个点表示每一位，有这一位的就连边，这样就存下了编号信息。
然后需要找到这些点。可以找一个度数巨大的点，它跟所有点连边，唯独不和这\(10\)个点连边。那么我们就可以知道这些点是哪些了。
然后要确定它们的顺序。首先肯定需要用一条链串起来，现在需要考虑哪个在前面。
你发现\(1000<1023\)，所以代表最高位的点，连的边一定少的可怜，所以度数更大的那个点就是最低位。
IOI2020 网络站点
有一棵树，你需要写两个程序A,B，A负责对它重编号成一个排列，B每次要接受\(u,v\)和\(u\)的所有邻接点，回答\(u\)走到\(v\)的路径上经过的邻接点是哪一个，这里给出点都是给出A的重编号。部分分是编号在\(n^2\)内即可，当然编号不能重复。
考虑部分分做法显然是直接把括号序压进去。
然后呢?如何优化?
考虑如果记进栈序，就会导致不能区分父亲和最后一个儿子，出栈序相反。
考虑按照奇偶性分层，奇数层记进栈序，偶数层记出栈序。
你发现我们可以根据与邻接点的大小关系判断是奇数层还是偶数层，从而得到所有邻接点的括号。做完了。
太妙了!
Day2
模拟赛
T1
排列计数，对于每个位置有\(\leq a_i\)或者\(\geq a_i\)的限制。\(n\leq 5000\)。
考虑只有 必须在一个前缀里面 的限制的话很好做，那么我们可以把后缀容斥掉，变成\((\leq n)-(\leq a_i-1)\)，然后做一个dp处理就好了。咋dp?你把这两个限制拆开，跟所有限制一起排序，然后就变成，如果有\(c\)个后缀的限制，那么你要加入恰好\(c\)个拆出来的限制。背包一下即可。
另一个做法是奇妙的 延迟选择，并不人类可读。
T2
点分治法法塔，然后多点求值。小z珍惜一下马/cy
T3
A输入一个长\(n\)的01串，输出一个长\(m\)的01串，其中有\(k\)位被指定了。B要根据A输出的串计算原串。\(n+k+50\leq m\)。
这不是人类可想做法，但是是人类可读做法，需要灵机一动。
虽然A,B不能进行交流，但是她们可以获得一些相同的静态信息，比如生成相同的随机数。
考虑我们随机\(m\)个长\(n\)的01串，B按照A输出的串把这些01串\(\mathrm{xor}\)起来得到原串。
有一些位置必须是\(1\)，也就是说有一些串一定存在，当然还有一些串一定不存在，那么要用剩下的串把这个搞成原串。显然线性基。
\(n+k+50\leq m\)这件事说明满秩概率非常高，据说是\(1-\frac{1}{2^{50}}\)。bitset优化即可。
讲课
构造!
01串
给定\(n\)，构造一个长\(2^n\)的循环01串，使得它所有长\(n\)的子串互不相同。\(n\leq 20\)。
考虑把所有长\(n\)的01串建一个点，然后连边，这样就可以跑一个哈密顿回路了!
然而这不是很好，我们可以把长\(n-1\)的01串建成点，这样长\(n\)的01串就是边了(仔细理解一下)，这样就可以跑一个欧拉回路了!
IMO2010 T5
你有\(6\)个盒子，一开始每个盒子有一个硬币。你可以每次选择
-
从盒子\(i\)拿走一个硬币，给盒子\(i+1\)放上两个硬币
-
从盒子\(i\)拿走一个硬币，交换盒子\(i+1,i+2\)
。构造方案使得最后一个盒子有\(2010^{2010^{2010}}\)个硬币。
考虑定义操作1是把\((x,0)\)变成\((0,2x)\)。这太慢了
定义操作2是把\((x,0,0)\)变成\((0,2^x,0)\)，这样有个指数级就可以增长快点了。做法是这样的 :
\[(x,0,0)\rightarrow(x-1,0,4)\rightarrow(x-2,4,0)\rightarrow(x-2,0,8)\rightarrow(x-3,8,0)\rightarrow...\rightarrow(0,2^x,0)\]类似的可以定义操作3是把\((x,0,0,0)\)变成\((0,2^2^2...,0,0)\)，省略号是一共\(x\)个\(2\)， 构造留作练习（
剩下的事情非常简单，只需要凑出一个不小的数，然后用上面的东西(比如可以凑一个\(6\)，\(2^{2^{2^{2^{2^{2}}}}}\)比\(2010^{2010^{2010}}\)大多了)，最后使劲浪费swap造出\((0,0,0,\frac{2010^{2010^{2010}}}{4},0,0)\)，再来两次就做完了。
IMO2020 T3
有\(4n\)个球，每个球有颜色，每种颜色恰好有四个球。把球分成两部分，使得每一部分每种颜色都有两个球，同时两部分编号和相同。
简单题。考虑对于每个球跟它编号加起来是\(4n\)的那个球连边，然后你发现遇到了僵局。
把每种颜色缩起来，然后就变成给边定向，让每种颜色出入度都是\(2\)。
这是经典问题，跑一个欧拉回路，然后对于奇数位置的边顺着定向，偶数位置的逆着定向就好了。
奇偶归并排序
最快的排序网络之一。
我们不能用排序网络实现归并排序，是因为它不得不开一个辅助数组。
但是是否存在某种归并方式可以避免辅助数组呢?
是的。不过这个目前看来最优也只能做到\(O(n\log n)\)归并一次了，好像被证明了下界。
IOI2021 位移寄存器
你有\(100\)个\(2000\)位寄存器，支持mov，位运算和加法，一开始有\(n\)个\(k\)位整数压起来存在寄存器\(0\)，存储格式都是补码，你需要设计一个操作顺序使得最后寄存器\(0\)存着这些数从小到大排序的结果。\(n\leq 100,k\leq 10\)，操作不超过\(4000\)次。
这个看起来确实是造计算机题。
我们几乎不能把这些数先都拆出来，不然就没有多的寄存器用了。
考虑既然没有比较，我们就不比较了，可以尝试直接实现一个 比较器，然后就可以每次提取两个要比较的数，随便写一个简单排序网络。
取\(\min,\max\)就是取\(\abs\)，因为\(2\max(a,b)=a+b+\abs(a-b)\)。
然后就是要实现补码和绝对值。
补码好说，绝对值呢?
考虑用一个掩码提取符号位，然后先减去shift到最低位的符号位，再shift几遍把这个符号位膨胀成\(k\)位(更好的做法是减\(1\)取反再and掩码)，再xor上去实现取反。这就把补码还原了。
有一些步骤是支持并行的，也就是说可以直接在这个压位里面完成，而不需要把操作数提取出来。这样我们就完成了\(O(n)\)甚至\(O(\log^2 n)\)的排序。当然这里操作次数并不松，使用更快的奇偶归并排序要更轻松。
据说比较器写的好可以用奇偶移项卡到1500以内……
更多内容参见Matrix67的博客。
IOI2021 分糖果
有一个序列，一开始全是\(0\)，每个位置有一个\(c_i\)表示它的范围是\([0,c_i]\)，超出这个范围就会自动贴到边界。支持区间加减，问最后这个序列是什么。\(n,q\leq 2\times 10^5\)。
扫描线。问题变成，维护一个操作序列，支持单点修改操作数，查询最后的结果。
考虑我们找到最后一次贴边，然后剩下的部分就是求和了。
这个怎么找?考虑一个事情，就是极差超过\(c_i\)的时候一定贴边。我们找到最短的这样的后缀，那么它的左端点要么是\(\min\)要么是\(\max\)(否则不最短)，这说明在\(\max/\min\)中另一个地方贴边了。要找这个的话二分即可。
IOI2021 钥匙
有一张无向图，每条边有一个颜色，每个点有一把某种颜色的钥匙，需要拿着对应的钥匙才能走过某种颜色的边。求从哪些点出发可以到达的点最少。\(n,m\leq 3\times 10^5\)。
显然传递。
考虑一个类似于Boruvka别乳卡的合并算法，我们从 每个点自己是一个连通块 开始，每次对于每个连通块找一条出边尝试合并，然后用线段树维护连通块里面的钥匙和连通块的出边，合并的时候启发式合并一下。毛咕咕一下，复杂度\(O(n\log^2 n)\)。
IOI2021 地牢游戏
地牢是一个树，每个点有一个敌人，敌人有攻击力\(a_i\)，权值\(b_i\)和指针\(x_i\)。
有一个人从点\(x\)降落，一开始她的能力值是\(w\)，她会和走到的每个点的敌人战斗，如果\(w\geq a_i\)，她的\(w\)会增加\(a_i\)并且她会走到父亲，否则\(w\)增加\(b_i\)并走到\(x_i\)指向的点。多次查询几步走到根。\(n\leq 4\times 10^5,q\leq 5\times 10^4,v\leq 10^7\)。
考虑这么一件事 : 为什么是加上\(a_i\)?
你发现 打败了之前打不败的敌人 这件事只会发生\(\log\)次。
考虑把这个过程分成\(\log\)段，第\(i\)段是能力值在\(2^i\)到\(2^{i+1}\)之前的过程。我们认为上一段就能打赢的敌人是永远打不赢的，它的\(b\)是原来的\(a\)，\(x\)指向父亲，这样问题就变成了 第一次在哪里打赢了。
这个就可以做了，你发现每个点有一条出边，这就是一个内向基环树森林。考虑分成树上和环上两段。
-
对于树上，设\(d\)表示到环的和，那么从\(u\)出发，走到一个点\(v\)的时候，\(v\)不会被干掉当且仅当\(d_u-d_{\mathrm{fa}(v)}+w\leq a_v\)，移项一下就变成维护\(\min\)了，树剖+线段树即可。
-
对于环上，可以先计算转多少圈才会停下，然后算停在哪，可以用线段树维护这个环。
然后我们离线下来统一做这个事情就好了，或者如果你喜欢的话也可以炸空间地实现成在线。复杂度是\(O(n\log v+q\log n\log v)\)。
IOI2018 洋娃娃
你有一个起点，\(m\)个普通点，还有一个普通点组成的长\(n\)的序列，和\(n+\lfloor\lg n\rfloor\)个特殊点。你需要构造一张图，满足 :
-
起点和普通点出度是\(1\)，特殊点出度是\(2\)。
-
从起点出发遍历图，遇到一个普通点就走它的出边，遇到特殊点的话，第奇数次走第一条出边，第偶数次走第二条出边，得到的经过普通点的序列恰好是给定的序列。
度数是\(2\)，容易想到一个完全二叉树的构造，但是这个只在\(n\)是\(2^k-1\)的时候有效。
考虑我们当然可以选择空出一些位置，但是这样会有很多多余的点，最多的时候特殊点需要\(2n\)个左右。
那么就需要考虑砍掉冗余的部分。有这样的构造 : 我们保留右链，但是把右链上挂的一些左子树删去，这样可以保证正确性。你发现这样恰好对应二进制分解。
IOI2018 高速公路
神题。给一张无向无权图和\(a<b\)，有两个未知点\(s,t\)，你每次可以把每条边边权赋成\(a,b\)中的一个，查询\(s,t\)的最短路。你需要在\(50\)次之内找到\(s,t\)。\(n\leq 90000,m\leq 130000\)。
考虑先找到一个\(s,t\)最短路上的点\(u\)，然后从\(u\)出发求bfs序，然后就可以在bfs序上二分找到距离\(u\)更远的那个点，从那个点开始再二分就可以找到另一个。这样做次数是1+17+17+17=52。
怎么砍掉?
考虑不找点而是找边，然后把图按照到这条边哪个端点更近分成两份，\(s,t\)应该分别在两份中。你发现这样做的话，130000这个数特别好，如果有一边达到了65536，另一边一定小于65536，所以我们这样二分就可以砍去两次，也就是1+17+32=50。草/jk
Day3
模拟赛
T1
谷省选计划原题。
T2
将会收录于 模拟费用流。
T3
维护平面，每个横坐标有一条竖着的线段，端点坐标在\(n\)以内，线段上写着\(a_i,b_i\)。支持在最后加入一条线段，查询给出一条横着的直线和一个pair \((x,0)\)，从左往右考虑所有和横线相交的线段，把这个pair \((x,y)\)变成\((ax+b,\max(y,b))\)，求最后的pair。\(m\leq 3\times 10^5,n\leq 10^6\)，膜\(2677114440\)，5s 2GB。
膜合数说明不可逆。
考虑线段树维护横轴，每个点再开一棵线段树维护纵轴。空间爆了。
然后你可以把内层树换成一个vector，然后归并这个东西。现在瓶颈在于\(\log\)次的vector二分，可以用分散层叠优化掉一个\(\log\)。
跟经典的分散层叠不太一样，具体咋做闲了再补（
讲课
CF数据结构题。
CF150E Freezing with Style
给一棵带边权的树，求一条边数在\([l,r]\)之间的路径，使得路径上边权中位数最大，构造方案。
二分之后把边权转成\(\pm 1\)，问题变成求有没有\(>0\)的路径，当然可以点分治+单调队列。这是俩\(\log\)。
考虑二分之后长链剖分!
问题变成，用数据结构维护长链。区间定长性质不错，所以我们设\(k=r-l+1\)，那么要支持 :
-
push_front
-
\(O(1)\)查询一个长度\(<k\)前缀的\(\max\)
-
\(O(1)\)查询一个长度为\(k\)的区间的\(\max\)
-
\(O(m)\)把前\(m\)个元素跟一个数组取\(\max\)
考虑按\(\log\)大小分块然后建立四毛子st表。
四毛子st表是可以push_front的，但是对于第四个操作，如果\(m=o(\log n)\)，需要重构第一块，复杂度是\(O(\log n)\)而不是\(O(m)\)，你就完蛋了。
经典做法是不处理第一块，这样当\(m\)达到\(\Omega(\log n)\)的时候才会发生重构，复杂度就正确了。
CF793F Julia the Snail
数轴，有\(m\)条线段，保证右端点互不相同。
如果你站在一条线段的左端点，你可以走到这条线段的右端点；不管什么时候你都可以往左走。
多次询问如果不能走出\([l,r]\)，最右可以走到哪。\(n,m,q\leq 10^5\)。
讲了无数次/jy
全局询问就是吉老师线段树嘛，也就是说设\(f(i)\)是从\(i\)出发的答案，那么线段\(x,y\)就是把\(\geq x\)的\(f\)都对\(y\)取\(\max\)。
显然要用一个扫描线处理这个\([l,r]\)，按\(r\)从小到大扫就好了。复杂度\(O(n\log n)\)。
呃具体一点，我们扫到一个线段\([x,y]\)的右端点的时候把它插入进线段树，把\([1,x]\)里面\(\geq x\)的都推平成\(y\)。
草，lxl说均摊线段树就是Segment Tree Beats/jy
CF536E Tavas on the Path
扫描线扫\(l\)，然后用静态lct直接做就好了。
CF1476G Minimum Difference
直接带修莫队。
CF1019E Raining Season
树，边权是一次函数\(ax+b\)，对于\(x=1,...,m\)求直径。
考虑一共有\(n^2\)个链，每个的和都是一次函数，然后就变成要求它们的凸壳，或者说把它们归并得到一个下凸函数。
边分治，然后问题是怎么对每个分治块合并两边得到跨过中心边的答案函数。
考虑合并两边的形式是\(\max(f=g+h)\)，那么我们可以直接求\(\max(f)=\max(g)+\max(h)\)，也就是两边取\(\max\)再加起来，就做完了。
最后直接归并所有函数即可。复杂度一个\(\log\)。
CF1109F Sasha and Algorithm of Silence’s Sounds
有一个\(n\times m\)的网格图，问有多少编号区间构成一棵树。\(nm\leq 2\times 10^5\)。
扫描线。
考虑树就是没有环并且连通。
没有环的话，直接用lct维护编号的最大生成树即可。
连通的话，可以用点数减去边数，如果是\(1\)的话就没有环，否则有环。邻接点只有\(O(1)\)个，每一个都是区间加减，没有环保证了每个数\(\geq 1\)，所以线段树维护最小值和最小值个数即可。
然后你发现这两部分可以很自然地合并。
CF1446F Line Distance
给一个平面，有\(n\)个点，两两连直线，问这些线到原点距离\(k\)短的距离是多短。\(n\leq 10^5\)。
肯定二分答案，然后就相当于画一个圆，要求多少连线在圆外。
然后你发现一个事情，我们筛去圆内的点，对于每个点找到两个切点，然后它确定了一段圆弧(当然是劣弧)，两个点的连线与圆相交，当且仅当它们的圆弧有交。离散化BiT维护即可。
CF1172F Nauuo and Bug
lxl表示这个题应该3500/se
有个老兄写了个加法取膜优化，具体就是加起来\(\geq p\)则减去\(p\)，但是她忘掉了序列中可能有\(\geq p\)的数。
每次查询一个区间中从左往右加起来并用这个东西取膜得到的结果。\(n\leq 10^6,m\leq 2\times 10^5,p\leq 10^9\)，可能有负数，4s。
要想线段树，考虑定义\(g(x)\)表示对于一个序列，拿着\(x\)走进去，会减去多少次\(p\)。
你发现这个有单调性，也就是说\(x\)变大，减去的次数不会变小。这启发我们设\(f(x)\)表示要减去\(x\)次最少需要初值是多少。
然后考虑合并，你发现\(g\)很好合并，但是段数是指数级(可持久化平衡树?不说正确性，1e6怎么可能过的去)，而\(f\)是一个\(O(len)\)段的东西，但是合并考虑起来难度略大。
CF1039E Summer Oenothera Exhibition
给一个序列，每次给一个\(k\)，问最少把序列划分成多少段，使得每一段极差不超过\(k\)。\(n\leq 8\times 10^4\)，7s。
如果只有一次查询，我们直接贪心即可。
不过这里面好像有某种结构。设\(f(i)\)表示从\(i\)开始最远一直可以选到\(f(i)-1\)，这个构成了一棵树，直接硬跳即可。
离线排序，那么每个\(f(i)\)会越来越大。
然后考虑怎么凑出根号\(\log\)，我们根号分治，当一个\(f(i)-i\)过大的时候爆力二分跳到哪，这部分最多跳根号次，小的则用lct维护。要得到小的部分的变化只需要每次变化之后二分下一次啥时候变化即可。复杂度\(O(n\sqrt{n}\log n)\)。
CF1491H Yuezheng Ling and Dynamic Tree
父亲序列\(f\)确定了一棵树，满足\(f_i<i\)。支持区间减(对\(1\)取\(\max\))，查询两个点的\(\mathrm{lca}\)。\(n\leq 10^5\)。
看起来就像 弹飞绵羊。
看起来也像上一个题，但是这个题不能带\(\log\)了。
考虑分块，我们每次跳过一整个块，如果某次跳到了同一个点，说明\(\mathrm{lca}\)要么在这个点，要么在上个块。问题变成怎么跳过整个块。
你发现一个块最多整体改根号次就会完全跳到下一块，所以我们爆力处理根号次整体修改即可。
Day4
模拟赛
T1
智障题。
T2
神仙题。
https://www.luogu.com.cn/blog/user19567/yi-dao-tu-lun-ti-ji-ji-yan-sheng
T3
省选计划原题，R11 T3。
讲课
CF1515H Phoenix and Bits
集合，支持值域区间and/or/xor一个数，查询全局不同数个数。
Trie。
xor是简单的。and和or比较复杂，但是是破坏性的，所有操作之后数的种类都不会增加，所以我们可以考虑每次把需要合并的都合并掉，这样均摊复杂度就是对的了。
and/or就是把某些位全搞成一样的。
然后你发现如果一棵子树里某一个需要被推的位同时有0又有1，这一位就可以直接递归下去爆力，否则and/or对这棵子树要么无效，要么等价于xor，打标记就行了。
然后你每次递归下去至少合并掉一个点，复杂度就是\(O(n\log^2 v)\)了。
CF1148H Holy Diver
简单题，据说动态笛卡尔树拍上去就行了。
Wdsr2.7 八云蓝自动机2
正着做(按\(r\)从左往右扫描线)只会根号/ll
考虑时间倒流，或者说按\(l\)从右往左扫描线，问题变成序列上每个位置上挂了一些询问，支持交换序列上两个位置的询问，回答一个序列上区间的所有询问，查询一个时间区间的询问答案之和。
所以线段树维护这些vector，推平的时候把这些询问爆力找出来，去一棵时间轴上维护答案的BiT上改就好了。
Day5
模拟赛
T1
原题ARC100F。
数数。
定义一个序列是好的当且仅当它包含至少一个\([1,k]\)的排列作为区间，给出长\(m\)的序列\(a\)，对于所有长为\(n\)，值域\([1,k]\)的好序列，求它们包含\(a\)的总次数。\(m\leq n\leq 25000,k\leq 400\)。一个部分分是\(a_i\)互不相同。
好的 这个东西很恶心，因为它是 至少一个，这就不如 一个都没有。先算出总方案\((n-m+1)k^{n-m}\)，然后减去那些不好的好了。
考虑如果序列\(a\)没有重复，我们就可以把它重标号成\(1,...,m\)，所以答案只跟\(n,m,k\)有关，你就可以打表了（不是
如果序列\(a\)长度是\(k\)了，它还没有重复，那么直接所有序列都是好的了。
否则考虑它里面第一个和前面重复的位置，以及最后一个和后面重复的位置。你发现一件很有趣的事情，
一个dp，我们设\(f(i,j)\)表示前面已经有一个\(a\)，这个\(a\)后面长度是\(i\)的序列，有多少个满足最后极长的不重段长度是\(j\)，并且之前没有长度是\(k\)的不重段。转移显然（
T2
原题CF1361E。
T3
原题CF1290F，但是我觉得更有AtC那味（
有\(n\)种向量，每种有无限个，两两不平行。求选出一些，从原点首尾相接构成一个凸多边形，这个多边形不超出原点为左下角的\(m\times m\)正方形的方案数。\(n\leq 5,m\leq 10^9,\)
讲课
CF360E Levko and Game
调整法大家都会了，问题是怎么证明这个贪心不是盲目的，也就是说它不会漏掉实际上的最优解。
CF772E Verifing Kingdom
这个三个点跟三叉树(呃有根二叉树)好像很有关系/jy
考虑如果我们问一个点\(u\)的两个儿子\(l,r\)和另一个点\(x\)，会得到 :
-
\(u\)，这说明\(x\)在\(u\)的父亲那边
-
\(l\)，这说明\(x\)在\(u\)的左子树
-
\(r\)，这说明\(x\)在\(u\)的右子树
然后就可以进行树分治搞定了。
CF843E Maximum Flow
CF1270I Xor on Figures
据说这个操作是二维循环卷积的形式/jy
显然每个位置只会操作一次。我们随便找一个基准点把它的\(x,y\)都变成\(0\)，然后考虑所有的操作位置\(u_i,v_i\)
Day7
讲课
雅礼集训2017 Day4 猜数列/CERC2016 Invisible Integers
神仙题。
众所周知，如果限制是 有一个子串是，那么可以在ACAM上状压dp。
考虑对于每个限制建立一个自动机。这个事情是容易的。
然后考虑自动机的交。
你发现把两个同向的限制造出来的自动机合并起来是容易的。具体地，
多边形数点
给一个\(k\)个点的凸多边形和一个\(n\)个点的点集，每次把这个多边形平移并缩放，查询里面有多少个点。\(k\leq 20,n\leq 10^5\)。
考虑把它拆开，变成数一个上凸壳下面的点数，减去一个下凸壳下面的点数。
然后你发现对于每条边的斜率都做一个扫描线就好了。
实际上凹多边形是差不多做的，可以类比叉积算面积。
WF2019 Directing Rainfall(雨落葡萄园)
CodePlus 2018 3月赛 寻找车位
爆炸oj3600 没有人的算术
好玩题。考虑先用bst维护顺序，用线段树维护序列，你发现这个东西是可以直接在bst上二分出全局排名的，但是我们需要动态标号才能直接线段树维护序列，而要想每次\(O(1)\)变化量就必须用实数……呃具体就是递归下去的时候限制出一个标号区间，然后取这个区间的中点作为新的标号。
然后你发现如果出现了链，不光复杂度退化，精度也爆了，所以我们实在需要平衡树。显然想法是根号重构，简单想法是替罪羊，更简单的想法是这个结构也支持旋转。
注意Splay和Treap这些高度不严格的平衡树理论上是不行的，我觉得Splay实践上也不行，但是Treap错误率应该小的可怜。