前缀和算法差分算法（5）——思维提升

1.5 思维提升

本节的题目都有一定难度，是算法的提升训练，可以选择不做

1.5.1 P10837 云音泛

这道题可以这么想：将一个花的时间改变，就可以将这朵花移到无穷远处没有花栽种的时间，这样的收益总会是最大的。

那么，如何找到收益最大的一朵花呢？要使收益最大，首先要弄清楚收益的来源。一朵花移到无穷远处，增加的符合题目要求的时间增加的来源是什么？不难想到，原先有且只有两朵花开放的时间就变成了只有一朵花开放。

这样，问题就转变为了：找到一个长度为mmm的区间，使其中有且只有两朵花开放的时间点最多。

因为数字总量较少，所以可以使用离散化解决空间问题，这就不用考虑了。接下来需要思考如何找到有且只有两朵花开放的时间。在O(n)O(n)O(n)的时间范围内，这一章学到的差分算法无疑是最佳选择。用差分计算出每个时间点有多少花开。

完成之后，接下来需要考虑的是如何统计这些区间中有多少222，这就需要一些做题经验了，建议仔细思考。

答案是使用前缀和算法。pre[i]pre[i]pre[i]表示前iii个数中有多少222，这样问题就迎刃而解了。最后的难点在于离散化。离散化虽然不在普及组的大纲中但是也非常建议掌握。通过离散化可以简化不少数据大而数量少的题目。

代码位置：1\problems\P10837.cpp

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;#define_for(i,n)for(inti=0;i<n;i++)#define_rep(i,a,b)for(inti=a;i<b;i++)#defineendl'\n'constintmaxn=2e5+10;;ll xs[maxn*3];intdiff[maxn*3];// 区间结构体structseg{ll l,r;intcnt;}s[maxn*3];ll pre1[maxn*3],pre2[maxn*3];pair<ll,ll>rose[maxn];inttotx,tots;intn;ll m;intfindl(ll x){intl=0,r=tots;while(l<r){intmid=(l+r)>>1;if(s[mid].l>=x)r=mid;elsel=mid+1;}returnl;}intfindr(ll x){intl=0,r=tots;while(l<r){intmid=(l+r)>>1;if(s[mid].r<=x)l=mid+1;elser=mid;}returnl-1;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;totx=0;_for(i,n){ll t;cin>>t;ll l=t;ll r=t+m-1;rose[i].first=l;rose[i].second=r;xs[totx++]=l;xs[totx++]=r+1;}// 离散化排序去重sort(xs,xs+totx);totx=unique(xs,xs+totx)-xs;memset(diff,0,sizeof(diff));_for(i,n){ll l=rose[i].first;ll r=rose[i].second;intpl=lower_bound(xs,xs+totx,l)-xs;intpr=lower_bound(xs,xs+totx,r+1)-xs;diff[pl]++;diff[pr]--;}ll ans0=0;intcur_cnt=0;tots=0;_for(i,totx-1){cur_cnt+=diff[i];ll l=xs[i];ll r=xs[i+1]-1;if(l>r)continue;s[tots].l=l;s[tots].r=r;s[tots].cnt=cur_cnt;ll len=r-l+1;if(cur_cnt==1)ans0+=len;tots++;}// 预处理前缀和pre1[0]=0;pre2[0]=0;_for(i,tots){pre1[i+1]=pre1[i];pre2[i+1]=pre2[i];ll len=s[i]