Category Archives: 树状数组

ACdream 1103 瑶瑶正式成为CEO (树链剖分,费用流)

一颗n个点的有向边树,这个基础上添加了m条有向边,变成一个DAG。每条边都有ai, bi, ci, di,di …

HDU 4918 Query on the subtree (树分治,BIT)

给出一棵树,两种操作:1. u x 将点u的权值改成x;2. u d 计算距离点u不超过d的点的权值和 先不考 …

2016 ACM/ICPC Asia Regional Dalian Online

首先总结下这次大连网赛,总算了却了一直的担忧,把名额最少的大连打下来了。这场网赛给我的感觉就是“痛并快乐着”, …

CodeForces 547E Mike and Friends (AC自动机,BIT)

给出n个字符串,计算字符串k在[l, r]的字符串中总共出现多少次。 首先我们将这n个字符串插入到AC自动机中 …

2016 Multi-University Training Contest 4

1001 – Another Meaning 给出A串和B串,可以选择A串中被B串匹配的任意位置打 …

FZU 2224 An exciting GCD problem (乱搞)

f(l, r)表示区间[l, r]所有数字的公约数, 询问区间[l, r]任意对(i, j), f(i, j) …

ZOJ 2112 Dynamic Rankings (树状数组套可持久化线段树)

计算区间第k大数,存在动态修改区间某个点的数. 用树状数组套上一个主席树,主席数维护的是区间不同数子的个数,用 …

Codeforces Round #169 (Div. 2) E Little Girl and Problem on Trees (动态BIT)

一颗树,两种操作,1.将距离点v小于d的点点权+x;2.询问点v的点权;树除了根节点其他节点都只有一个儿子,等 …

hdu 4605 Magic Ball Game (离线,BIT)

一棵二叉树,每次询问:一个小球从根节点开始往下掉,如果小球的值x>w[i]则往左右的概率分别是1/8,7 …

hdu 5372 Segment Game (离散化,树状数组)

题意:n个操作,每次插入一个线段,或删除一个已存在的线段,每次插入后输出当前插入的线段能完整覆盖存在的几条线段 …