题解 P3527 【[POI2011]MET-Meteors】

· · 题解

​        对于这道题是整体二分的经典例题，我们先抛开整体二分，思考二分怎么做。对于一个询问，因为答案有单调性，如果x时刻为最小可以时刻，则比x小的时刻都不可以，比x大的时刻都可以，所以我们可以进行二分答案，并加以验证。先不说怎样验证，就单是时间复杂度就不能接受，O(nmlog_2n)。

​        如果一个一个进行二分时间复杂度不允许，且这些询问不是强制在线的，我们不妨整体进行二分，我们把所有询问放在一起进行二分。我们设计一个函数solve(l,r,x,y)，表示当前询问序列[x,y]的答案在当前答案[l，r]区间。有一个问题，就是为什么答案在答案区间[l,r]的所有询问会连接在一起，在询问序列的连续一段呢？这个问题放在后面，先置之不理。我们思考，怎样进行二分。

​        二分答案的思想是取出当前答案区间的中间值进行验证，如果比答案小，则让答案的区间的左端点为中间值加一，反之让答案的右端点为中间值。按照二分答案的思想，我们也进行中间值验证。看例题，我们思考怎么验证。

​        对于当前答案区间[l,r]，我们把第[l,mid]场流星雨全部落下，看在当前答案区间[l,r]所属的所有询问是否在第[l,mid]场流星雨下过之后已经收集足够的陨石，如果当前询问已经收集够，我们把它归为答案区间[l,mid]中，反之我们把它归为答案区间[mid+1,r]中，并且对于归为答案区间[mid+1,r]的询问我们需要进行修改，对于其希望要收集的陨石数要减去[l,mid]场流星雨的陨石总数，此处理解一下。

​        现在解决一下上面留下的问题，我们怎么能将答案都在[x,y]区间的所有询问都放在一起呢？我们对于每一次划分，都将这些询问进行拷贝，并且修改，然后重新按左右排布，这样我们就能让这些答案在同一区间的询问在一起了。

​        我们分析一下时间复杂度：我们运用线段树的思想进行分析，我们一共有log_2{r-l+1}层，在这个式子中的r表示答案可能到达的最大值，反之l表示的就是答案可能到达的最小值，在本题中，我们的r=n，l=1，但是下方的代码最开始的传参为r=n+1，这表示前n场流星雨都不能满足这个询问，所以最后落在n+1的所有询问表示不能在所有n个流行雨中的到满足，故输出-1。每一层中我们运用线段树的思想，知道遍历每一层的所有流星雨，一共是线性的时间复杂度，并且每一层正正好好摊分所有m个询问，在每一层中我们每一个询问和流星雨都会运用树状数组，所以总的时间复杂度是O((n+m)log_2{n}log_2{r-l+1})。

#include <cstdio>
#include <algorithm>
using namespace std;
#define N 300010
struct Per {int head,id;long long need;}per[N],per_[N<<1];
int n,m,k,L[N],R[N];long long A[N];int ans[N],nxt[N],to[N],idx;long long tmp[N<<1];
void add(int a,int b) {nxt[++idx]=per[a].head,to[idx]=b,per[a].head=idx;}
void change(int x,long long y) {while(x<=2*m) tmp[x]+=y,x+=x&-x;}
long long find(int x) {long long sum=0;while(x) sum+=tmp[x],x-=x&-x;return sum;}
void solve(int l,int r,int x,int y)
{
    if(l==r) {for(int i=x;i<=y;i++) ans[per[i].id]=l;return;}
    int mid=(l+r)>>1,tl=0,tr=n;
    for(int i=l;i<=mid;i++) change(L[i],A[i]),change(R[i]+1,-A[i]);
    for(int i=x;i<=y;i++)
    {
        long long tmp1=0;
        for(int j=per[i].head;j&&tmp1<=per[i].need;j=nxt[j])
            tmp1+=find(to[j]+m)+find(to[j]);
        if(tmp1>=per[i].need) per_[++tl]=per[i];
        else per_[++tr]=per[i],per_[tr].need-=tmp1;
    }
    for(int i=l;i<=mid;i++) change(L[i],-A[i]),change(R[i]+1,A[i]);
    for(int i=1;i<=tl;i++) per[x+i-1]=per_[i];
    for(int i=n+1;i<=tr;i++) per[x+tl+i-n-1]=per_[i];
    solve(l,mid,x,x+tl-1),solve(mid+1,r,y-tr+n+1,y);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,a;i<=m;i++) scanf("%d",&a),add(a,i);
    for(int i=1;i<=n;i++) scanf("%lld",&per[i].need),per[i].id=i;
    scanf("%d",&k);for(int i=1;i<=k;i++) scanf("%d%d%lld",&L[i],&R[i],&A[i]);
    for(int i=1;i<=k;i++) if(R[i]<L[i]) R[i]+=m; solve(1,k+1,1,n);
    for(int i=1;i<=n;i++) (ans[i]==k+1)?printf("NIE\n"):printf("%d\n",ans[i]);
}