| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
用二分+离散化+树状数组需要注意的地方!!用二分+离散化+树状数组需要注意的地方!!
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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator