标签归档:树状数组

[bzoj 3262] 陌上花开

Description

有n朵花,每朵花有三个属性:花形(s)、颜色(c)、气味(m),又三个整数表示。现要对每朵花评级,一朵花的级别是它拥有的美丽能超过的花的数量。定义一朵花A比另一朵花B要美丽,当且仅当Sa>=Sb,Ca>=Cb,Ma>=Mb。显然,两朵花可能有同样的属性。需要统计出评出每个等级的花的数量。

继续阅读

[codeforces 740D] Alyona and a tree

Description

Alyona has a tree with n vertices. The root of the tree is the vertex 1. In each vertex Alyona wrote an positive integer, in the vertex i she wrote ai. Moreover, the girl wrote a positive integer to every edge of the tree (possibly, different integers on different edges).

Let's define dist(v, u) as the sum of the integers written on the edges of the simple path from v to u.

The vertex v controls the vertex u (v ≠ u) if and only if u is in the subtree of v and dist(v, u) ≤ au.

Alyona wants to settle in some vertex. In order to do this, she wants to know for each vertex v what is the number of vertices u such that vcontrols u.

继续阅读

[bzoj 2819] Nim

Description

著名游戏设计师vfleaking,最近迷上了Nim。普通的Nim游戏为:两个人进行游戏,N堆石子,每回合可以取其中某一堆的任意多个,可以取完,但不可以不取。谁不能取谁输。这个游戏是有必胜策略的。于是vfleaking决定写一个玩Nim游戏的平台来坑玩家。
为了设计漂亮一点的初始局面,vfleaking用以下方式来找灵感:拿出很多石子,把它们聚成一堆一堆的,对每一堆编号1,2,3,4,...n,在堆与堆间连边,没有自环与重边,从任意堆到任意堆都只有唯一一条路径可到达。然后他不停地进行如下操作:

1.随机选两个堆v,u,询问若在v到u间的路径上的石子堆中玩Nim游戏,是否有必胜策略,如果有,vfleaking将会考虑将这些石子堆作为初始局面之一,用来坑玩家。
2.把堆v中的石子数变为k。

由于vfleaking太懒了,他懒得自己动手了。请写个程序帮帮他吧。

继续阅读

AIO2008 Solution

Ladybugs

You really like ladybugs. This is fortunate, as dozens of ladybugs have recently taken up residence in your garden. Every day they emerge into the sunlight and climb your garden fence. The fence is a series of regularly spaced posts which gleam brightly in the sun. The ladybugs settle into their favourite resting spots atop these posts.

\includegraphics[width=12cm]{ladybug}

Winter is nigh and you wish to protect the ladybugs from the rain. You set out to construct a rain shelter using a single length of ribbon propped up with toothpicks. To protect all the ladybugs, the ribbon must be long enough to cover all their favourite resting spots. Ribbon is not cheap, so you wish to use the shortest length of ribbon you possibly can. A ribbon of length k will cover precisely k adjacent fence posts.

For example, on the fence in the diagram above there are two ladybugs sitting on fence post 3 and one ladybug on each of 2, 6, 7 and 9. The ribbon rain shelter must cover all the posts from 2 through to 9 inclusive, so the shortest possible length of ribbon that covers all the ladybugs is 8.

Your task is to write a program to calculate the minimum length of ribbon that will cover all the ladybugs.

继续阅读

[bzoj 1901]Zju2112 Dynamic Rankings

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

继续阅读