题解 P4064 【[JXOI2017]加法】

其实不需要树状数组的…… 很有意思的一道二分题 熟练的诸位想必马上反应出二分答案了吧…… 因为题目中是要求最大化整个序列的最小值，那么我们可以二分这个最小值 显然这个最小值的取值范围是在$[min(A_{i}),min(A_{i})+ma]$之间，然后就可以二分了~ 现在我们二分了一个答案mid出来，我们呢要判断这个mid合不合法 我们发现每个点需要被覆盖的次数不一样，有些点甚至完全不需要被覆盖，我们需要决策出一个最小的方案 那么我们怎么决策呢？当然是贪心了 大概的思路是，**我们只有在不得不使用一次加法的时候才去使用加法，否则不使用** 另外，我们希望**后边的决策不会影响前边的决策** 这样的话我们才可以放心的使用贪心 那么我们可以这样做，把一个线段拆成一个左端点和一个右端点，和我们的序列点一起排序，最后形成一个长度为$n+2m$的决策序列 现在我们从左到右的扫这个决策序列，保证同一位置的左端点在序列点前，右端点在序列点后 如果这个点是一个左端点，我们插入一个线段到某个数据结构中存储 如果这个点是一个决策点，我们计算它的值还需要加几次到达mid，然后查找我们的数据结构里有多少合法的线段 显然有一个贪心策略是，因为现在排好序了，所以扫到这个序列点时，**前边的序列已经全部合法**，因此数据结构中现存线段的左端点在哪里变得毫无意义，我们只需要优先选择右端点最远的点进行加法就可以了 所以我们优先选择数据结构中最远的右端点，进行若干次区间加操作即可 现在让我们来看右端点，如果直白的想一下的话，我们会觉得这个点的作用是删除一个线段，但是我们发现前面指的某种数据结构**明显是一个堆**，而且我们呢也不需要真的插入一个线段，插入一个右端点足矣。 那么我们会发现我们完全可以使用惰性删除法，就是说在检查这个堆的时候，我们呢可以检测这个右端点是否在这个决策点的左边，如果在左边我们认为堆为空，可以return false了 发现好像没有右端点什么事？ 但是右端点本来就不是用来删除的啊……，还记得我们需要进行区间加操作吗？ 好像需要维护一个线段树/树状数组，真是麻烦 我们都知道二维扫描线可以将二维问题变成一个一维问题，用一维数据结构来维护，那么我们现在要解决的问题是一个一维区间加问题，我们当然可以用一个一维扫描线，把这个一维问题变成一个零维问题，用零维数据结构——一个变量来维护 具体来讲，当你需要进行一次区间加操作的时候，并不进行区间加，而是仅仅在一个临时变量flow上+a，同时标记上这个区间已选，我们每次扫到一个决策点的时候先把它的值+flow，对应着这个点承受的区间加操作 之后当我扫到一个右端点时，我们要"删除"这个区间，我们检查一下这个区间有没有被选中，如果被选了，我们就把flow-a，代表这个区间加已经结束，如果没被选就什么也不做 所以我们就这样愉快的消掉了一个数据结构，全程只需要一个priority_queue就行了 算法复杂度$O((n+m)log(n+m)log(ma))$，大致是$O(nlog^{2}n)$的(实际上跑的飞起) 上代码~ ```C #include<cstdio> #include<algorithm> #include<queue> using namespace std;const int N=2*1e5+10;typedef long long ll; int n;int m;ll a;int k;int T; struct opt//操作结构体 { ll val;int tp;int pos;//val对于序列点是点值，对于线段点是编号 friend bool operator <(opt a,opt b){return a.pos+a.tp/3.0<b.pos+b.tp/3.0;} }op[3*N];int cnt;int book[N];int r[N];ll lf=0x7f7f7f7f;ll ri; struct data{int v;friend bool operator <(data a,data b){return r[a.v]<r[b.v];}}; priority_queue <data> pq;//这里写了一个O(1)的清空函数 inline void clear(priority_queue <data>& pq){priority_queue <data> emp;swap(emp,pq);} inline bool jud(ll mid) { ll flow=0;int tot=0; for(int i=1;i<=cnt;i++) { if(op[i].tp==0){pq.push((data){op[i].val});}//插入左端点 else if(op[i].tp==1) { ll ned=mid-op[i].val-flow;if(ned<0)continue;//如果比mid大可以continue了 ll ch=(ned+a-1)/a;if(tot+ch>k){return false;}//如果超了限制的话可以拍false了 for(;!pq.empty()&&ch;pq.pop()) { int v=(pq.top()).v; if(r[v]<op[i].pos){return false;}//如果此时堆为空也可以拍false了 else {book[v]=1;flow+=a;ch--;tot++;}//区间+a }if(ch>0){return false;}//如果没加完也可以拍false了 }else{flow-=book[op[i].val]*a;}//检查下这个区间有没有被选中 }return true;//如果全部通过就return true } inline void solve() { scanf("%d%d%d%d",&n,&m,&k,&a); for(int i=1;i<=n;i++)//插入序列点 {int t;scanf("%lld",&t);op[++cnt]=(opt){t,1,i};lf=min(lf,(ll)t);} for(int i=1;i<=m;i++)//插入线段点 { scanf("%d",&r[i]);op[++cnt]=(opt){i,0,r[i]}; scanf("%d",&r[i]);op[++cnt]=(opt){i,2,r[i]}; }sort(op+1,op+cnt+1);ri=lf+m*a;//计算左右区间 while(lf!=ri)//二分答案，记得清空 { ll mid=(lf+ri+1)/2;if(jud(mid)){lf=mid;}else {ri=mid-1;} clear(pq);for(int i=1;i<=m;i++){book[i]=0;} }printf("%lld\n",lf);cnt=0;lf=0x7f7f7f7f;//清空一些东西 } int main(){scanf("%d",&T);for(int z=1;z<=T;z++){solve();}return 0;}//拜拜程序~ ```