树状数组 – Tgotp-Blog

4378: [POI2015]Logistyka

容易发现,一个位置对于答案的贡献最多为s,

那么序列能分的次数的就是 \lfloor\frac{\sum_{i=1}^{n} min(a[i],s)}{c}\rfloor

我第一次写用的splay,每次查询找到第一个大于等于s的位置,然后左右分别考虑。。。

然而splay常[......]

Read more

5436: 三元组

没有限制a <= b <= c的话可以fft搞

限制的话具体见:三元组

c++代码如下:

 

3881: [Coci2015]Divljak

根据fail的性质克制,对于s建ac自动机后,查询t包含的串即为经过每个点的所有fail的权值和。

即fail会经过的点都被当前t所包含,那么建立fail树以后,就是查询s所在位置的子树有多少个点被不同t所经过。

用dfs序树状数组维护即可...

c++代码如下:
[crayon[......]

Read more

3790: 神奇项链

容易发现,处理回文串的时候得到的答案是可以去更新答案的,
即 令 f[i] 表示处理前 i 个最小由几个回文串构成,
那么,对于第i个位置,他由 [i-p[i],n]能更新的就是 前  [1,i+p[i]-1]
因为前后缀相同能直接放在一起,容易正确[......]

Read more

1633: [Usaco2007 Feb]The Cow Lexicon 牛的词典

令f[i]表示前i个字符中最多匹配多长,那么对于每个位置暴力匹配即可。

树状数组维护一下前i个当中最大的f[j]

c++代码如下:

 

1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费,

那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w);

考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响,所以还需对f[j]取min j < a[i].e[......]

Read more

#2323. 「清华集训 2017」小Y和地铁

发现若按照l排序后进行操作,那么两个点会新增的换乘站只与以前安放线段的上下位置有关,所以只有四种情况:
1.下出上进

2.下出下进

3.上出下进

4.上出上进。

分类讨论即可

c++代码如下:

&n[......]

Read more

1103: [POI2007]大都市meg

一开始以为是删除一段点之间的边,结果只会删相邻两条边,

直接跑dfs序,然后树状数组维护就好了。

c++代码如下:

 

1227: [SDOI2009]虔诚的墓主人

容易发现:

1.对于一个点,若他上下左右分别有常青树x,y,z,w个,他所产生得贡献为c[x][k] * c[y][k] * c[z][k] * c[w][k]

2.只有当他上下左右均有 >= k棵树时,此点才会产生贡献。

观察n,m <= 1e9 , w <=[......]

Read more

2141: 排队

题目大意:

求出每次更改后当前序列的逆序对个数。

考虑每次更改只会有两个点变化,且变化的个数只会与两数之间的数有关。

考虑分块处理(当然可以树套树),对于当前点所在块暴力更新,对于中间的块维护树状数组求出比他大的以及比他小的数。solved

送上对拍程序:
[crayon-[......]

Read more