zcmimi's blog

arrow_back前缀和共23篇文章

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

  1. 区间加
  2. 求序列最大前缀和

区间加,相当于前缀和加上一个等差数列

而等差数列加上一个等差数列还是等差数列

考虑将每个位置的前缀和转化为一个一次函数kx+b

分块,对每个块维护一个上凸壳单调栈,可以二分找到最大值

avatar
zc
2020-06-13 11:22:00
查看原题

点击跳转

逆推

若当前区间[l,r]和为x,考虑如何得到和为x-2的区间:

  1. a_l=2 \rightarrow [l+1,r]
  2. a_r=2 \rightarrow [l,r-1]
  3. a_l=a_r=1 \rightarrow [l+1,r-1]

这样我们求出区间 最大奇数和 与 最大偶数和,就可以预处理出所有x的答案了

avatar
zc
2020-03-23 16:44:00
查看原题

点击跳转

很妙的一道题

对每位置i分别统计[l,i],l\in [1,i]的方案数

S_i表示\sum_{j=1}^i [H_i \ge X],pre为位置i-1的方案数,now为位置i的方案数

H_i\ge x,now=pre+\sum_{j=1}^i [S_j=S_i],这些位置是位置i-1不能满足而位置i可以满足的

H_i\le x,now=pre-\sum_{j=1}^i [S_j=S_{i-1}],这些位置是位置i不能满足而位置i-1可以满足的

这样就可以\Theta(n)解决了呢

记得开long long,S_0先赋值为n,防止负数re

avatar
zc
2020-03-23 00:30:00
查看原题

点击跳转

先离散化,然后用树状数组统计两边的数目,比较即可

avatar
zc
2020-03-20 12:57:00
查看原题

点击跳转

带 套 路 题

\sum_{i=1}^n\sum_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j) \\ =\sum_{d=1}^n \mu^2(d) d \sum_{i=1}^n\sum_{j=1}^n(i+j)^k[\gcd(i,j)=d] \\ =\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k[\gcd(i,j)=1]

S(n)=\sum_{i=1}^n\sum_{j=1}^n(i+j)^k

=\sum_{d=1}^n \mu^2(d) d^{k+1} \sum_{i=1}^{\left \lfloor \frac nd \right \rfloor}\sum_{j=1}^{\left \lfloor \frac nd \right \rfloor}(i+j)^k \sum_{x|i,x|j} \mu(x) \\ =\sum_{d=1}^n \sum_{x=1}^{\left \lfloor \frac nd \right \rfloor}\mu^2(d) d^{k+1} \mu(x) x^k S(\left \lfloor \frac n{dx} \right \rfloor)

T=dx

=\sum_{T=1}^n \sum_{d|T} \mu^2(d) d^{k+1} \mu(\frac Td) (\frac Td)^k S(\left \lfloor \frac nT \right \rfloor) \\ =\sum_{T=1}^n S(\left \lfloor \frac nT \right \rfloor) T^k \sum_{d|T} d \mu^2(d)\mu(\frac Td)

如何快速求令S(n)?

设:

F(n)=\sum_{i=1}^n i^k

G(n)=\sum_{i=1}^n F(i)

那么

S(n)=\sum_{i=n+1}^{2n}F(i)-\sum_{i=1}^nF(i) \\ =G(2n)-2G(n)

筛出F的前缀和,然后筛S(n)

优化:

因为模数是质数,根据欧拉定理: 对于互质的a,n满足a^{\varphi(n)} \equiv 1\pmod n

可以k=k \mod 998244352

求后半部分

f(n)=\sum_{d|n} d \mu^2(d)\mu(\frac nd)

如何线性求f(n)?

f(n)是若干个积性函数的卷积,所以f(n)也是积性函数

那么f(n)=f(p^k)f(\frac n{p^k})

f(1)=1

f(p^1)=p-1(带入即可得到)

f(p^2)=-p(带入即可得到)

f(p^k)=0(k\ge 3)

d\frac nd中必然有一个有平方因子,所以\mu(d)\mu(\frac nd)必有一项为0

所以f(p^k)=0(k\ge 3)

接下来就可以线性筛f(n)

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们考虑两个断点(设为l,r)符合的条件:

每种颜色的珠子只能出现在其中一条链中

也就是若[l,r]中出现了某种颜色[l,r]也就包含了所有的这种颜色

我们可以记录颜色出现的前缀和

记录前i个位置每种颜色的出现次数,如果位置i是 颜色a[i]的最后一个位置, 就把颜色 a[i] 的结果清零。

这样若两个位置的前缀和相同,就是合法的

可以通过hash来判断,记录所有hash值,排序后统计

两个分割点 l,r 要尽可能满足 r−l 接近 \frac n2

可以用类似双指针的方式维护

这题卡hash,要双hash

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

这题考验的是仔细读题

可以发现修改带查询的只有1000个,这部分直接暴力求就可以了

区间加可以用差分来解决

剩下的部分:

可以预处理出[1,i]的答案ans_i

查询[l,r]的答案就是ans_r-ans_{l-1}

代码很短

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

可以先看一下LG P4868 Preprefix sum,很经典一道题,维护一下后缀和就可以了

这题的话就是把上面那道题变了一下

由于值域太大,我们可以使用 动态开点线段树 或 树状数组+离散化

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

我们可以用倍增求出能控制某个点x的最远的点y的位置

应该将f_xy的点的答案+1

我们可以差分一下,

++ans_{f_x},--ans_{f_y}

然后从下加得到的就是当前点的答案

记得开long long

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

1/3
Search
search