高度由习惯堆积

分类 数据结构:线段树 下的文章

ZJOI2017 树状数组

题目loj题目链接思路研究代码发现,她的树状数组实际上询问的是$[l-1,r-1]$的抑或和,所以题目的询问实际上就可以转化为$l-1$上的元素与$r$上的元素相同的概率。一开始想的是,线段树维护每一个元素是$1$的概率是多少,然后进行数学运算,得到答案,然后发现,两点之间的概率不是相互独立的。比如说修改了$[l,r]$的区间,那么如果这次修改的结果是$l$,那么$r$在此次收到的影响就必然...

LOJ2710 election

题目有一个长度为$N$的字符串$S[1…N]$,它仅由C和T两种字母组成。现在有$Q$个查询,每个查询包含两个整数$L$和$R$,表示:设新字符串 $S'=S[L…R]$,至少在$S'$中要删除多少个字符,才能保证:对于$S'$的每一个前缀与每一个后缀,其C的数量都不小于T的数量。思路28pts有一个显然的贪心,对于一段区间,先扫描前缀,遇到不合法的点就删掉,再扫描后缀,把不合法的点删掉,这...

HDU6155 Subsequence Count

题目给出一个长度为n的01串S,有Q个操作:1.翻转区间[l,r](0变1,1变0)2.求区间[l,r]有多少不同的子串思路这是一道好题,首先考虑没有修改操作的dp状态,则$dp[i][j]$表示到了第$i$个位置,结尾为$j$的串的方案数则我们可以得到以下递推关系:$$ dp[i][j]=dp[i-1][0]+dp[i-1][1]+1,j==S[i]\\ dp[i][!j]=dp[i-1]...
February 17, 2019

BZOJ1858 序列操作

题目Starria最近收到了一个01串5种操作,以下修改均对于区间[x,y]0 x y 全部赋值为01 x y 全部赋值为12 x y 取反,即0变1,1变03 x y 区间内总共有多少个14 x y 询问区间内最多有多少个连续的1对于每一种询问操作,Starria都需要给出回答,聪明的程序员们,你们能帮助他吗?思路如果没有2,这就是一道线段树水题。如果没有4,这就是一道bitset水题。可...