Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

Re:这题线段树怎么做?

Posted by totalfrank at 2009-01-20 23:56:05 on Problem 1990
In Reply To:这题线段树怎么做? Posted by:SherlockBourne at 2007-09-25 13:03:50
> 我只想出保存声音最大值和最小值的方法……tle了……
线段树的做法……
首先按x从小到大排序
将x的值插入 节点记录x的sum
然后按v从大到小排序
然后对cow数组扫一遍
由于cow的位置已经确定
所以可以在o(lg(n))时间内确定x前面和后面的距离和(根据节点的sum)
算出总的dis,乘以v即可
然后在线段树中删除这个x
cow数组扫完便得到答案

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator