传送门 发现翻转奇数次的数变成111，翻转偶数次的数变成000，于是只需知道每个数翻转了几次，就知道它最终的值，使用单点查询，区间修改的普通线段树即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646...

传送门 算是一道非常经典的题，首先，看见等差数列就要下意识地想到差分，考虑把原序列转换为差分序列，发现查询操作就转化为查询前缀和，在区间[l,r][l,r][l,r]加上等差数列就相当于区间[l+1,r][l+1,r][l+1,r]加上公差，在lll上加上首项，最需要注意的是加上等差数列的操作不影响rrr后面的数，于是在r+1r+1r+1 的位置要减去k+d×(r−l)k+d \times ...

传送门 建议先做这道题，有一些套路是一模一样的。 考虑如何dpdpdp，dp[i][j]dp[i][j]dp[i][j]表示现在扫到第iii个数，用了jjj段区间，最大的总价值，cnt(l,r)cnt(l,r)cnt(l,r)表示在区间[l,r][l,r][l,r]中不同的数的个数。 考虑在区间[1,p][1,p][1,p]分段，很容易列出dpdpdp方程： dp[i][j]=max⁡{dp...

传送门 题解 一看数据范围就知道是线段树 不过怎样区间翻转是一个问题 这里的思想非常巧妙 记录最长不上升子序列的长度 在区间翻转的时候,交换最长不上升子序列的长度和最长不下降子序列的长度即可. 还有合并区间时需要用到一点dp\rm dpdp的思想 代码有点丑神犇勿喷 codecodecode: 123456789101112131415161718192021222324252627282...

传送门 题面大意： 长度为nnn的数列，支持两种操作： 1.1.1.修改某个位置的值 2.2.2.询问区间[l,r][l,r][l,r]里选出至多kkk个不相交的子段和的最大值。 一共有mmm个操作 解法： 暴力 dpdpdp+滚动数组（在本地卡进2s2s2s） 模拟赛的时候有人用这个方法AAA了 dp[i][j][p]dp[i][j][p]dp[i][j][p]表示进行到a[i]a[...

设FFF为斐波那契数列，不妨设F−1=1F_{-1}=1F−1​=1 整个数列也就是F−1=1,F0=0,F1=1,F2=1,F3=2,F4=3,F5=5,F6=8,....F_{-1}=1,F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2,F_{4}=3,F_{5}=5,F_{6}=8,....F−1​=1,F0​=0,F1​=1,F2​=1,F3​=2,F4​=3,F5​=...

传送门 线段树的神奇操作 考虑维护区间和，区间最大值。 取模的时候，若当前区间的最大值小于Mod\rm ModMod 你就会发现这个区间的所有数都不会变，直接return\rm returnreturn ，不用继续维护。 记得开long\rm longlong long\rm longlong，我被long\rm longlong long\rm longlong孙了很久 12345678...

传送门 一眼看上去：这不就是最短路的模板吗？ 两眼：边权太大了，怎么开的下？ 考虑还是用Dijkstra\rm DijkstraDijkstra解决，每个点开一棵线段树，存储二进制的状态 我们要实现的功能: 1.给二进制数加上2k2^k2k，这可以看成把kkk位后所有连续的111变成0，再把所有连续111后的那一个000变成111 2.比较两个二进制数的大小，先比较高位，再比较低位。 但是用...

题面 构建一个序列aaa,满足mmm条限制. 限制形如<l,r,q><l,r,q><l,r,q>: a[l]a[l]a[l]&a[l+1]a[l+1]a[l+1]&…&a[r−1]a[r-1]a[r−1]&a[r]=qa[r]=qa[r]=q;(此处&为位运算的and\rm andand操作). 题解 我们发现：...

传送门 考虑dpdpdp，但是这个dpdpdp该怎么ddd呢？ 如果走路的时候能往右就往右，实在不行（有障碍物或往上走会产生新的方法）才向上 （也就是尽可能向低处走），我们就可以做到路径不“重复”。 于是dpdpdp就呼之欲出： F[i][j]=F[i−1][j]F[i][j]=F[i-1][j]F[i][j]=F[i−1][j] 一般情况 F[i][j]=0F[i][j]=0F[i][j]...