小衣同学的博客

如果端点所在的机器人接不住，而区间所在的机器人能接住，令区间所在的机器人去接，并变成一个端点，原来端点所在的机器人在这段时间可以往左右走，扩大活动范围，变成一个区间。如果两个都能接住，那么谁去接都可以，实际就是1、2两种情况的并，然后发现1、2两个区间是有交的，那么他们的并集仍然是一个区间，所以还是维护一个端点和一个区间。如果端点所在的机器人能接住，而区间所在的机器人接不住，令端点所在的机器人去接，区间机器人只能往在这段时间往左右走，扩大活动范围。不过二分也统一了这种情况，v 大于。所以，按时间顺序增序，

那么，如果l<=r且[l,r]内有下一个vector内必胜(sg=1)的元素，当前局面就必败(sg=0)不能再直接dp[i][j][k]表示数组a的第i个做开始局面时，位置(j,k)为起点时的获胜情况了。对于所有颜色v都处理出这样的位置集合，记为win[v]，表示v作为最后一步时的所有获胜位置。这个位置序列，是一个第一维增序，第二维降序的序列，形如(1,4)(2,3)(3,2)这种。只要能走到win[a[l]]内任意一个元素的都是必败的，否则就是必胜的。那么对于序列a的最后一个元素，考虑所有获胜位置，

那么下一个位置区间，就是由当前位置区间l、r分别加上最慢速度lv、最快速度rv去生成，而历史每次询问出来的lp、rp，可以对lv、rv形成一个新的约束，最终收敛到lp=rp。询问的次数变多时，用限制条件去卡，速度实际是收敛的很快的。所以考虑二分位置p，用一个区间[lp,rp]去控制，100次，很容易想到是二分，但是check很难想。同样地，速度也用一个区间[lv,rv]去控制。两个未知量p、v，因为最后要求最终位置p，不是很能直观地证明，只是能大概感觉，

不妨枚举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)，

前面那段的最大值只能小于等于这一段最小值，后面那段的最小值只能大于等于这段最大值。对于存在逆序的部分，记录下来这一段最左最右的位置，求出这一段最小值和最大值。感觉pyy这个代码写的还是挺巧妙的，也避免了使用线段树求区间最值。分别二分即可，可以线段树二分，也可以在multiset上二分。一段增序（非严格），一段存在逆序的部分，一段增序（非严格）线段树+set或者multiset均可。注意到序列由最多三段拼接而成，灵茶群、propane代码。贴一下灵茶群群友的图，

长为n(n<=2e5)的球序列，第i个球颜色ci，有m(m<=n)个空盒子，编号1-m。首先执行r次，意味着，循环询问，对于每个开头的长为n的序列都询问一次，所以序列扩成二倍。记颜色w的球在盒子里的球为now[w]个，则占了now[w]/k（向上取整）个盒子。位置在p位置之后，但因为和p位置之前放入盒子里的球同色，而能被继续放入的球，一旦确定了不在盒子内的球的位置p，前面在盒子里的同色的球的个数也能确定，然后考虑双指针，双指针维护第一个不在盒子内的球的位置，注意到它是单增的。

给定一个长度为n(n

题目数轴的正轴上有n(n<=2e5)个整点，从点i到j的代价是二者距离差的平方，给定一个你需要从0到，代价不超过，问最少加多少个整点，时限7秒思路来源梁神题解想正解之前不妨考虑朴素怎么做，然后再考虑怎么优化，dp如此，线段树&&二分亦然n个初始整点有n段线段长度距离，考虑给第i段上面加a个点，和给第i段上面加a+1个点，二者相比，加了一个点，有一个对应代价减少的值，记为x，如果能暴力维护优先队列，显然是每次找x最大的值，把a取出来，总代价减去

题目T(T<=2e5)组样例，每次给出一个n(n<=2e5)和一个s(s<=2e14)，n个人需要被发钱，第i个人被发的要求满足在[li,ri]之间(1<=li<=ri<=1e9)总共有s元钱，且保证所有人发下限的钱数时够发，即求最大的x，使得n个人被发的钱的中位数为x，且s元钱够发(不一定要发完s元钱)保证所有样例的n之和不超过2e5思路来源自己搞的，补之前自己wa的没补的题原来不补题重新过几个月再看这个题就会了orz题解首先二分

题目今天是某不愿透露姓名的谈姓大佬的生日，转发这场比赛到三个群就可以，获得以下三种礼包之一。豪华礼包：一个U盘、一个鼠标和一个机械键盘。幸运礼包：一个U盘、两个鼠标。普通礼包：两个U盘、一个鼠标。大佬一共准备了a个U盘、b个鼠标和c个机械键盘。为了给更多的人带来足够多的惊喜，大佬希望相邻的两位领礼包的参赛选手拿到的礼包类型都是不同的。由于大佬正在宴请Final选手，并没有空打理这些，所以想让你告诉他，这些奖品最多可以发出多少份礼包。T(T<=1e5)组样例，a,b,

题目n(1<=n<=1e5)的数组a[]，第i个数为ai(0<=ai<=1e9)，每次操作你可以选以下三种中的一种①选择i，令ai+1，代价为A②选择i，令ai-1，代价为R③选择i,j，令其中一个-1，另一个+1，代价为M0<=A,R,M<=1e4，求最终的数组所有值都相等的最小代价思路来源https://www.cnblogs.com/1024-xzx/p/12926595.htmlhttps://www.cnblogs.com/Kai

题意给n个数，q组询问，每次询问l到r的最大异或和思路来源某cf奆神代码题解本来应该是线性基上分治的这里一发基数+贪心也能过真是神仙代码啊对于每个询问[l,r]，r内放入询问的编号，按r的增序，一边插入线性基一边解答，即固定右端点r的情况下，如果线性基（因为线性基下标<=r）更靠右，显然是更有可能被包含在[l,r]的区间里的这就是贪心了...

题目给定一个数列，1 12 123 1234，无限往后延伸，到10的时候10算两个字符，以此类推q(q<=500)个询问，第i次询问第ki个字符是什么①easy version: ki<=1e9②hard version: ki<=1e18题解相同的思想是，先二分去掉二重前缀，确定k落在一个1到x的段里，把1到x-1前面所有段都减掉再二分一次去掉单重前...

思路来源https://www.jianshu.com/p/4604504a9810题意给n个数，取部分连续和的绝对值，使之与给定的t尽可能接近。输出这部分和的绝对值，左下标和右下标。心得尺取需要排序维护单增的序列，这样才能大了推左端界使之更小，小了推右端界使之更大。前缀和也是可以排序的，由于是绝对值，所以不影响。作差的时候取一下绝对值就可以，预存它们的...

题解维护长为m的树状数组，先将n次区间修改维护到数组上。二分答案为q，每次判断需要升级的次数，是否小于k。我们从左到右遍历塔i，类似manacher/扩展kmp算法一样更新一个当前最右端点nowr，其实是贪心的思想，代表当前存在一个防御塔能更新到nowr，对于不需要更新的点i，跳过即可；需要更新点i的时候，我们就对[i,nowr]区间进行区间更新，显然是最优的。最大...

题意统计每个数的出现次数，设第一次取a个数i，则第二次必须取2*a个数j，第三次4*a个数k，以此类推最大化取出的数的个数总和，即a+2*a+4*a+…。思路来源https://blog.csdn.net/nucleare/article/details/84191237题解枚举第一个取的值a，在有序序列[l,r]里不断二分2*a，找到后就在j处取2*a...

题目n个数，每次找到第一个单增子序列，输出这些数并删除，然后找第二个……至所有数都被找出暴力做肯定会T的吖思路来源https://blog.csdn.net/qq_28954601/article/details/78122766心得博主的题解和代码写的都不错 为博主点赞 注意到第二个序列的尾部一定比第一个序列的尾部的值小，不然第二个序列的尾部的值就被续...

题目给你一个序列a[]其子区间的中位数定义为长度/2+1子区间可以为一个点如5/2+1=3,4/2+1=3等求所有子区间的中位数的中位数思路来源https://www.cnblogs.com/henry-1202/p/9537952.html题解二分最后的中位数mid，把原序列大于等于mid的标为1，小于mid的标为-1如果一段子区间的和大于0，说明1多...

题目给一个数n&lt;=2e5，一个序列a[]，你可以给出一个整数b，使得最小输出sum思路来源https://www.cnblogs.com/Rye-Catcher/p/9255304.htmlhttps://blog.csdn.net/haipai1998/article/details/80891065题解首先对读入的ai，处理成ai-i，然后考虑枚举的b...

题目oxx 和 Xiejiadong 在玩一个双人旋转赛车的小游戏。他们将进行一些比赛。每局比赛必须按顺序进行，胜者会得到该局对应的分数xi。由于 oxx 技艺不精（每局都可以由 Xiejiadong 决定胜负），因此他给自己设置了初始分数k，希望自己能够一直领先 Xiejiadong。不过 Xiejiadong 识破了 oxx 的诡计，现在 Xiejiadong 想知道自...

题目有n(1<=n<=5e4)个花瓶，标号为0到n-1有m(1<=m<=5e4)次操作，操作分为两种①从A花瓶起，向右插入B枝花，即从A向右遍历，有空的花瓶就插进去，如果到n-1号花瓶还没插满就丢弃剩下的花，输出最后的最左和最右的插入花的位置，如果一朵花也插不下输出Can not put any one.②将[A,B]区间的花瓶清空，输出清空...

题意有n个植物，m次移动1格的机会，以下n个数a1-an，代表每一次浇水（其实就是访问），该处的植物会增加防御值ai，初始防御值di=0n个植物分别在坐标轴1，…，n的位置，浇水机的位置初始在0，坐标轴无限长，移动1格会耗费1次机会，从0移动到1上时，会给1这格加上ai，要求最大化最小值di，输出di。题解二分最后的di，判断是否可行。对于每个枚举的...