区间形态的扩展 luogu3205 [HNOI2010] 合唱队 队列的形成方式是不断往左或往右扩展。 考虑区间 DP。发现对于一个区间 $[i,j]$，最后一个元素的来源会对转移产生影响，所以设 $f(i,j,0/1)$ 为考虑区间 $[i,j]$，其中最后一个元素是从左边还是右边加入的方案数。 转移很简单$$f(i,j,0) = [a_i &l…

luogu8551 Bassline 题目的限制翻译过来就是 $[x,y]$ 中任意位置都被覆盖了相同次数。 用差分求出每个点被覆盖的次数，双指针求极长的满足条件的位置即可。 #include<bits/stdc++.h> using namespace std; #define int long long #define uint u…