首页 > 代码库 > Codeforces 460C 二分结果+线段树维护
Codeforces 460C 二分结果+线段树维护
发现最近碰到好多次二分结果的题目，上次多校也是，被我很机智的快速过了，这个思想确实非常不错。在正面求比较难处理的时候，二分结果再判断是否有效往往柳暗花明。
这个题目给定n个数字的序列，可以操作m次，每次要操作w个连续的数字，每次的操作将使得该段连续数字的数都+1，最后求整个序列最小值的最大值
求最小值最大，明显的二分结果的题目，我一开始还是在ACdream那个群里看到这个题，说是二分+线段树的题目，我就来做了一下。。首先二分部分很容易，下界就是初始序列的最小值，上界就是 下界+m，至于怎么判断这个就要想一下，我一开始还觉得不用线段树，因为我每次枚举完结果，对整个序列扫一遍，对不符合要求的数+到正好符号要求不就行了。
不过这个里面因为是要+连续一段，你普通的找到一个不符合条件的数，然后对他以及他之后的w-1个数都进行一次加法，很耗时啊，所以这个就是为什么要用线段树，其实我觉得用扫描线估计也可以，对某个起始点设置+1，起始点+w-1设置为-1，然后用个东西维护，++--的，估计也可以。反正最后用的线段树，普通的区间增，单点查询。
一开始还担心复杂度，不过还行的感觉，每次二分都要重新建树，这里就是 logN*N*logN,对二分结果进行判断，需要单点查询以及区间更新，这里是2*logN*logN，所以总的就是
logN*logN*（N+2)的复杂度，N最大为10的五次方，logN不超过20
#include <iostream>#include <cstdio>#include <cstring>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define LL __int64using namespace std;const int N = 100000+10;int n,m,w;LL d[N<<2],flag[N<<2],A[N];LL mini;void up(int rt){ d[rt]=min(d[rt<<1],d[rt<<1|1]);}void build(int rt,int l,int r){ flag[rt]=0; if (l>=r){ d[rt]=A[l]; //cout<<l<<" "<<A[l]<<endl; return; } int mid=(l+r)>>1; build(lson); build(rson); up(rt);}void pushdown(int rt,int l,int r){ if (flag[rt]==0) return; d[rt<<1]+=flag[rt]; d[rt<<1|1]+=flag[rt]; flag[rt<<1]+=flag[rt]; flag[rt<<1|1]+=flag[rt]; flag[rt]=0;}LL query(int loc,int rt,int l,int r){ if (l==r) return d[rt]; int mid=(l+r)>>1; pushdown(rt,l,r); if (loc<=mid) return query(loc,lson); else return query(loc,rson);}void update(LL val,int L,int R,int rt,int l,int r){ if (L<=l && r<=R){ d[rt]+=val; flag[rt]+=val; return; } pushdown(rt,l,r); int mid=(l+r)>>1; if (L<=mid) update(val,L,R,lson); if (R>mid) update(val,L,R,rson); up(rt);}bool judge(LL x){ LL tmp=m; for (int i=1;i<=n;i++){ LL now=query(i,1,1,n); // cout<<"Test "<<i<<endl; // cout<<now<<endl; if (now<x){ if (x-now>tmp) return 0; else { update(x-now,i,min(i+w-1,n),1,1,n); tmp-=x-now; } } } return 1;}int main(){ while (scanf("%d%d%d",&n,&m,&w)!=EOF) { mini=-1; for (int i=1;i<=n;i++){ scanf("%I64d",&A[i]); //cout<<i<<" "<<A[i]<<endl; if (mini==-1) mini=A[i]; else mini=min(A[i],mini); } LL L=mini,R=mini+(LL)m,mid; while (L<R){ build(1,1,n); mid=R-(R-L)/2; // cout<<L<<" "<<mid<<" "<<R<<endl; if (judge(mid)) {L=mid;} else {R=mid-1;} } printf("%I64d\n",L); } return 0;}
Codeforces 460C 二分结果+线段树维护
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。