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