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

用二分+离散化+树状数组需要注意的地方!!

Posted by wzc1995 at 2012-09-22 20:54:05 on Problem 2761
用二分+离散化+树状数组需要注意的地方!!
1、离散化后的答案一定要映射回原数组,样例太特殊了!!
2、询问边界的处理:
ask[0].st=ask[1].st;
ask[0].ed=ask[1].st-1;(极其容易忽略的地方)
for(int i=1;i<=q;i++)
{
	for(int j=ask[i-1].st;j<ask[i].st;j++) updata(a[j],-1);
	for(int j=ask[i-1].ed+1;j<=ask[i].ed;j++) updata(a[j],1);
}
3、二分边界的处理
int l=1,r=n;
while(l<=r)
{
	int mid=(l+r)>>1;
	if(query(mid-1)<ask[i].k) l=mid+1;//一定查询小于它的个数,否则处理起来很麻烦
	else r=mid-1;
}
贡献了若干WA。。

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