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

Re:第一个树状数组..留爪..说说思路..

Posted by saintqdd at 2011-04-15 10:12:23 on Problem 2828
In Reply To:第一个树状数组..留爪..说说思路.. Posted by:zzyzzy12 at 2011-03-20 23:24:05
> 前面很多也提到了..就是先都读完(ki,xi)..再从后往前添加..
> 添加时..譬如添加的ki=5..那么他的位置就是从第一个开始..数到第6个空的位置(没被占的位置)..然后填上这个数..这个位置标记已占..而且这个数的位置就确定了..不再动..
> 这是最朴素的思路..加上树状数组..那就是优化查找该点位置的查找..初始化..a[1..n]都为1..则每次对c[i]求和的就是到该点前有多少个空位..
> 那如何通过c数组来找到我们需要的位置呢?...使用二分查找的方法..譬如现在要插入的这个人为(ki,xi)..那么我们就二分查找(ki--n)这个范围..因为他的位置至少不会小于ki..
> 我的方法不一定是很好的~~~2500MS..比较慢了..
我的1750ms,也不快

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