小衣同学的博客

由于gcd只会缩成因子，所以对于所有

不妨枚举l，注意到 gcd(a[l,r]),gcd(b[l,r]),gcd(a[r+1,n]),gcd(b[r+n]) 有一个不同的 r 只有 O(log) 个。求换完之后的gcd(a1,a2,...,an)+gcd(b1,b2,...,bn)的最大值。操作：选择区间[l,r]，将a的[l,r]区间和b的[l,r]区间的数一一对应互换。每次给定n(n<=2e5)和两个长为n的数组a，b(1<=ai,bi<=1e9)当然枚举r也可以，这里是枚举r然后二分那log种的，复杂度O(nlog^3)，

也就是需要满足，t[i][1]到t[i][n]这一行，除去t[i][j]以外，其他n-1个数两两不重复。也就是最早前dis[j]个按钮时，i是可以访问j的，此时把无向边也当成有向边做，最多也就加3n条边。2. 恰好只有一组数出现了两次，如1 2 2 4 5，此时只能空t[i][2]/t[i][3]，dp[i][j]表示初始局面空出来的是j槽，按了i按钮后，空出来的是dp[i][j]槽，所以，基于这个数据范围，很自然暴力的做法就是，离线询问，从前0个处理到前l个，

dp[i][j]表示当前选了i个数和为j的方案数，做个完全背包，将所有合法的y的状态求和即可。然后发现第i个数是fib[i]，10个数，所以是不超过fib[10]的斐波那契数列。问题转换成，有x种数，其中第i种数是fib[i]，在其中选n个数，假设他们的和是y。最少的斐波那契数可以dp预处理出来，当然贪心一步，直接从最大的转移递推出来也是对的。如果用最少个斐波那契数之和去表示y的时候，用了m个数，那么y就是合法的。可以把一个数都换成1和2，比如一个3可以换成1个1、1个2。

如果(ai,bi)在栈中遇到相同的(aj,bi)，就合并成一坨，新的这坨的是(ai+aj-now,bi)所以可以模拟这个最后一段加入的过程，维护一个单调栈，只有出现两面包夹的情况才合并。其实并不是一个难题，赛中d2花了太久时间，导致没时间写这个了，补一下写篇题解。而对于新来一个数(ai,bi)来说，如果前面的清完的时间比当前短就弹栈，那么就是维护一个单减栈，使得栈底的最大，栈底也就是最耗时的那个时间。对于栈顶来说，无法再使次栈顶弹掉，所以肯定是小于次栈顶的，对于每个时刻，输出栈底最耗时的即可。

v3往u上的mp上挂的时候，维护的是v3为子树根，存在一个点p的类型是x，p到v的路径是没用过的最大代价和，也就是③，再加上u下其他子树的dp值之和，也就是1+2，得到1+2+③。所以，mp[v][x]表示v为子树根，存在一个点p的类型是x，p到v的路径是没用过的最大代价和，用于辅助转移。于是，now[u]表示对mp[u]上所有点打的全局子树加标记，now[v]表示对mp[v]的。把v往u上挂的时候，v需要加上sum-dp[v]，加上now[v]，再减去now[u]

比如需要减去的是gcd=2，lcm=y的方案，就等价于减去gcd=1,lcm=y/2的方案。dp[i][S]表示约数里当前选了i个数，当前所有质因子的状态有没有覆盖住最高幂次，由于lcm+gcd=x，有lcm/gcd+1=x/gcd，还有lcm/gcd>=1。显然如果gcd>1，让gcd和lcm同除以gcd即可，所以可以认为gcd=1，但是，这个只能限制住lcm的限制，不能限制住gcd=1，所以容斥。用gcd=1的，减去gcd>1的，枚举大于1的具体是几，枚举gcd，gcd一定是x的因子，

（6）否则，记las的两个父亲为f1、f2（也就是上图的点6、点7），如果能往f1后面续，就往f1后面续，否则往f2后面续。新来的点3，可以接在点4后，也可以接在点5后，也可以接在点6后，也可以接在点7后，因为在链中间的点后面续新的点，都可以看成是在交点后面续新的点，不影响两条链的性质。而此时应该是10->9->6->3->2，另一条链8->7->5->4->1。而这种情况的出现，说明前面有一个只询问了1次的点，也就是在点5下面的点4，可以发现，在点5形成Y字型，后接点4之后，新来的点3并没有续到点4上，

dp[i][j][1]表示颜色和最大严格不同（也就是和dp[i][j][0]的颜色不同）时次大的(和,颜色)n(n<=2e5)个球在同一行，第i个球颜色是ci(ci<=n)，值是vi(vi<=1e9)dp[i][j][2]，其中dp[i][j][0]表示前i个删了j个后最大(和,颜色)但是仔细观察发现，实际前驱颜色只需要两种，即产生最大贡献的颜色，产生次大贡献的颜色。暴力是O(n*k*k)的，枚举当前颜色是什么，枚举上一个颜色是什么。同时需要保证转移后，次大的颜色仍然不能和最大的颜色相同。

这个等价于a.se+b.fi>b.se+a.fi，即a.se-a.fi>b.se-b.fi。当min（a.fi，a.se+b.fi）＞min（b.fi，b.se+a.fi），a在前。先选x＞0 y＞0的，选完之后选x＜0 y＞0的，先选x绝对值小的后大的，然后选x＜0 y＜0的，顺序不太显然，但是可以考虑比较法决定哪个在前，然后按这个排序一下就过了，其实打开min符号的话，可以发现是良序的，考虑第二个串和第三个串的顺序时，手玩发现，一个单独的串里的前缀最小值x，前缀和为y。前缀和-前缀最小值大的在前面。

否则有两个点等于w，说明都可以，把其中一个填w，剩下一个当自由点。4. 从大到小考虑权值w，类似拓扑排序，把度为0的点加到队列里，初始没有被边覆盖的点是度为0的点，后续删掉max边之后且没有填值的点是度为0的点，当前度为0的点是自由点。3. 如果同一个权值w对应的边不少于2条，这些边应该有一个公共点i，否则无解，如果up[i]<w也无解，否则给这个点i赋初值w。从大到小考虑权值w的过程中，对于没有限制的，乘上当前自由点的个数，并令当前自由点数减1。检查所有权值w的边，对于当前边两个端点u，v。

比如1+23*45*56+7，mul[4]表示45*56的值，而mul[3]表示23*45*56的值。还需要处理一个形如2345*(3+34+345+3456)的东西，并加上2+23+234。sum[i]形如(3+34+345+3456)+(2+23+234+2345)，sum2[i]形如2+23+234+2345*(3+34+345+3456)，由4+45+456需要得到3+34+345+3456时，加上3333即可，不妨称3+34+345+3456这样的段，叫3456这个数的前缀贡献。

定义f(u)为满足v

令a[1]=huai,a[2]=huai+1，a[3]=huai+2，a[4]=hao，a[5]=hao+1,a[6]=hao+2，而a[2]和a[3]两坏情况是翻转不过来的，说明a[2]和a[3]只能是一好一坏，那么a[1]一定是坏。b[1]询问2、3、5，b[2]询问2、3、6，b[3]询问3，5，6，b[4]询问2、5、6。注意到a[1]-a[3]的询问结果是0，说明a[2]和a[3]要么一好一坏，要么两坏，同理，a[5]和a[6]要么一好一坏，要么两好，即a[5]和a[6]至少有一个好。

操作的本质，相当于把[1,x]原来的数和[1,q]询问中出现的数放在一起，想求[1,x]的和，也就是求得总和和最小的q个值的和即可，无需关注具体位置。另两棵，B线段树维护冒泡序列的位置，C线段树维护权值线段树当前有哪些值。对于一个数x，记其左侧<=x的数的个数为y，那么其rank为y+1。考虑主要维护三棵树，一棵A线段树是原始序列中不在冒泡序列里的，线段树上每个位置的初始值是其左侧小于等于这个数的数的个数，查询的时候，按照值域，在两棵树叠在一起的树上一起跑即可。

于是就有，dp[S][i]表示(当前选了a序列前bit[S]个数)，当前选择的b的集合是S，也就是B在新序列的位置和A的位置不再前后相邻，D在新序列的位置和A的位置不再前后相邻。当前a的最后一个数对应的b中的数选的是第i个时，二者只考虑这些数时完全相同的最小代价。也就是取一段连续的a的区间[l,r]，往b当前的集合中，没取并且也连续的一段区间里放。选择a的第i个的时候，需要考虑a的第i-1个选的是什么，从而判断二者是否前后相邻。首先，考虑如果a的位置和b的位置在排列的位置上一一映射上了，

①如果b[i]一开始是1，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-(pre+1)+suf-1。②如果b[i]一开始是0，那么翻之前为pre+suf，翻了[1,i]之后，总的1的个数为i-pre+suf。对于n>=2的情况，先问32次询问[2,n]，这样[L,n]对应[2,n]，[1,R]对应[1,n]计[1,i-1]的1的个数为pre，当前无法确定第i位是什么，但是已知[i,n]的个数为suf。那么，如果询问[1,i]的时候，[i+1,n]中01的个数相同，就无法区别是否翻转，

第i个怪物有stri(1

删除of子串和of子串后面紧跟着的i个字符，其中i∈[0,k]，删完之后串后面的部分会接上来。那么先删完这一段，再用这个of，考虑[i+1,r]删完后最少剩几个字符，还可以减k。非连续是指，先删后面的一段of，再删前面的of，导致第二次删的在原串中不一定连续。3. 减k之后，一开始没考虑s[l]=='o'时dfs(l+1,r)，③ 串最左侧是o，中间第i个字符是f，但o和f之间这一段可以被删完，1. 如果s[l]不为'o'，舍弃当前字符，考虑[l+1,r]每次操作，你可以选择当前串中的一个of子串，

因为dfs树只有2n条边，向下搜的时候link A&cut B，向上搜的时候cut A&link B。n(n<=1e5)个点，m(m<=5e5)条边，第i条边的代价是ci(1<=ci<=1e3)之前的断边时，是把要断的点splay到根，再切断两个son(w和u、w和v)的联系。q(0<=q<=16)个限制，第i个限制给出ui,vi，要求这两条边至少选一条，所以每次加(u,v)之前先找到树上最大的边，将代价减掉，再将当前边加上，所以新开一个点w，u连w，w连v，点权=边权。将其改为dfs，复杂度。

只有x-f[j]>0(减去一个f[j]后可能会导致d为0，=0就不合法了)且x-f[j]>=l，才是需要考虑x-f[j]的。有n(2<=n<=3e3)把枪，第i把枪有两个参数fi和di(1<=fi<=2e3,1<=di<=1e9)区间是从[pi,pi+k]逐步往下枚举的，最终枚举到[pi-k,pi]，考虑区间的并，长度为2k。也就是正好可以落在[pi-k,pi+k]内的数，记为tmp，n-tmp就是需要修改的数的个数。对于n个长为k的区间，暴力统计是O(n*n*k)的，用差分干掉一个n，做到O(n*k)

1. 最大化最小值，首先考虑二分，二分答案v，将(a[p]^a[i])

Nebius Welcome Round (Div. 1 + Div. 2) E. Routing(状压dp/找到一个无向图简单环，使得所有点到环的距离不超过1)

AtCoder Beginner Contest 289 G. Shopping in AtCoder store(离线凸包/在线凸包上二分/在线动态开点李超树)

NIKKEI Programming Contest 2019-2 C.Swaps(思维题/置换)

2022 China Collegiate Programming Contest (CCPC) Guangzhou Onsite I. Infection(树形dp)

The 2022 CCPC Guangzhou Onsite M. XOR Sum(数位dp 数位背包)

题目n(1<=n<=1e6)只蚂蚁，在一根杆上，杆左端点0，右端点1e9+1，n只蚂蚁第i只的初始位置在ai，输入保证di=0代表当前向左爬，di=1代表当前向右爬左端点有一个柱子，被撞a(1<=a<=1e9)次后消失，被撞<=a次的时候都会把蚂蚁往反方向弹右端点有一个柱子，被撞b(1<=b<=1e9)次后消失，被撞<=b次的时候都会把蚂蚁往反方向弹思路来源乱搞AC题解L为左右端点距离，考虑时间每过2*L是一个循环，这时

题目t(t<=50)组样例，每次给定一个长度为2*n的序列，且每个1到n的数恰好出现两次，圆环上等距离分布着1到2*n这2*n个点，数值相同的点要么在环内连边，要么在环外连边，问给定的序列是否可以连边，使得边两两不交，如果可以输出yes，否则输出no自己的一点想法官方给出的题解，已经被找出了反例1 4 1 2 3 2 4 3 1 4队友请教了一下@泛白老哥，得出了一个主席树的做法自己又仔细想了想，感觉这个主席树，好像不太有必要所以，根据这个主席树，手撸了.

题目给一个模数m(2<=m<=1e6)开始有数1，记为h1，还有数2，记为h2(0<=h1,h2<m)每一天，数i，都会变成(xi*hi+yi)%m其中x1,x2,y1,y2是四个给出的系数，也满足在[0,m)之间现在有两个目标，a1和a2，也都在[0,m)之间想要某一天，h1变成a1，h2变成a2，问最少的天数是多少题目保证初始h1不等于a1，h2不等于a2思路来源乱搞AC题解首先找到h1第一次变成a1，h2第一次变成a2的天数，分别

题目t(t<=1e4)组样例，每次给出n(n<=2e5)个点，点号[0,n-1]的一棵树，对于每一个k从[0,n+1]，求树上路径满足路径点集合的mex恰为k的无序点对数保证sumn<=2e5思路来源乱搞AC题解如果mex>=1，则这条路径一定要包含0如果mex>=2，则这条路径一定要包含0、1如果mex>=3，则这条路径一定要包含0、1、2则注意到mex=i能成立，必须[0,i-1]在一条链上，所以对0号点dfs，时刻维护以0

题目给一棵n(n<=5e5)个点的树，问是否存在节点x，使得以x为根时，树恰为二叉搜索树如果不存在输出-1，否则增序输出所有可能的节点x思路来源乱搞AC题解大概能树形dp搞吧，但是不会于是变成了一道一堆特判冲过去的题首先特判一些情况，①存在度数>=4的点的时候无解，②n<=2必有解(此时根的度为1)注意到，③答案可能的节点，一定是最小值和最大值之间的这条链上的节点，不然必有一个值的大小关系和最值是矛盾的，所以枚举这条链上的点u，u最多相邻三个

题目t(t<=8)组样例，每次给出一棵n(n<=1e5)个点的树，q(q<=1e5)组询问，每次给出一对(a,b)，询问即对于n个点来说，每个点到点a和点b中两个点距离的较小值为该点的贡献，求贡献和sumn<=5e5，sumq<=5e5思路来源乱搞AC题解考虑a和b之间的所有点d，记c是ab路径上的中点，如果知道这些点d到a的距离和，如图，蓝色之和，如果知道这些点d到b的距离和，如图，粉色之和，如果知道这些点d到c的距离和，如图，

题意题目即求k(k<=1e5)个串的最长公共子串的长度，字符集大小1e5，k个串的总长度不超过1e5思路来源乱搞AC题解大概是一个poj3294的后缀数组原题，首先将k个串用k-1个特殊字符(这里用1e5+1)连接到一起，注意不能用k个，不然会导致二分的答案长度+1，这样构造的新串长度2e5考虑二分答案长度x，忽略height<x的，将height>=x的尺取，然后，判断尺取的每一段，起始下标的并是否为k对于每个字符，bel[i]记录第i个字