首页 > 代码库 > 整体二分初步
整体二分初步
部分内容引自myt论文：树状数组延伸和离线优化（CDQ、整体二分和莫队）
大致思路
1.确定答案范围[L,R],mid=L+R>>1;
2.算出答案在[L,mid]内的操作对答案在[mid+1,R]内的操作的贡献;
3.将答案在[L,mid]内的操作放入队列Q1，solve(Q1,L,mid)
将答案在[mid+1,R]内的操作放入Q2,solve(Q2,mid+1,R)
伪代码
divide(hd,tl,l,r){ if(hd>tl) exit if(l==r){ for(i->hd to tl) if(queue[i].type==‘Ask‘) ans[queue[i].pos]->l exit } int mid->(l+r)/2 for(i->hd to tl){ if(queue[i].type==‘Add‘ , queue[i].r<=mid) add(queue[i].l,1) add(queue[i].r+1,-1) if(queue[i].type==‘Del‘ , queue[i].r<=mid) add(queue[i].l,-1) add(queue[i].r+1,1) if(queue[i].type==‘Ask‘) tmp[i]->ask(queue[i].r)-ask(queue[i].l-1) } int l1->0,l2->0 for(i->hd to tl){ if(queue[i].type==‘Ask‘){ if(queue[i].added+tmp[i]>=queue[i].k) dq1[++l1]->queue[i] else queue[i].added->queue[i].added+tmp[i] dq2[++l2]->queue[i] } else { if (queue[i].y<=mid) dq1[++l1]->queue[i]; else dq2[++l2]->queue[i]; } } for(i->1 to l1) queue[head+i-1]->dq1[i] for(i->1 to l2) queue[head+l1+i-1]->dq2[i] divide(hd,hd+l1-1,l,mid) divide(hd+l1,tl,mid+1,r)}
例题思路：动态区间第K小
1～N个数，M个操作，操作分为2种：
1）将x位置的数改为y;求[x,y]内的第K小数
STEP1：将修改操作分解为2个子操作：去掉原先的数a，插入一个新数b。
设此后所有操作数为K
STEP2：新建一个树状数组C和2个队列Q1、Q2，c[i]存储的是小于等于mid的数的个数。
STEP3：确定答案范围[L,R]，同时二分答案mid=L+R>>1
然后遍历1～K个操作：
（1）若是修改操作，且插入/删去的数<=mid，add(opt.x, +1 or -1)&&塞入Q1，否则若大于mid，不更新&&塞入Q2
（2）若是询问操作，且sum(opt.y)-sum(opt.x-1)<=opt.k，塞入Q1，否则，opt.k=opt.k-[sum(opt.y)-sum(opt.x-1)]&&塞入Q2
STEP4：还原更新
STEP5：solve(Q1,L,mid);solve(Q2,mid+1,R)
整体二分初步
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。