整体二分+洛谷P3527 [POI2011]MET-Meteors

た入场券 2023-08-17 16:49 136阅读 0赞

这个题写完之后，感受到了很多收获。二分好题。  
题意：给定一个环，每个节点有一个所属国家，k次事件，每次对\[l,r\]区间上的每个点点权加上一个值，求每个国家最早多少次操作之后所有点的点权和能达到一个值

AC码

#include<bits/stdc++.h>
    using namespace std;
    const int M=6e5;
    #define ll long long
    struct Node{int l,r,id;ll v;}q[M],p1[M],p2[M];
    int n,m,k,ans[M];
    ll sum[M],mx[M];
    vector<ll> G[M];
    void add(int x,ll v){ for(;x<=m;x+=x&-x) sum[x]+=v;}
    ll ask(int x){ll anss=0;for(;x;x-=x&-x) anss+=sum[x];return anss;}
    void ef(int s,int t,int l,int r){
        if(s>t)return ;
        if(l==r){
            for(int i=s;i<=t;i++)if(q[i].id>k)ans[q[i].id-k]=l;
            return ;
        }
        int mid=l+r>>1,s1=0,t1=0;
        for(int i=s;i<=t;i++){
            if(q[i].id<=mid){
                if(q[i].l<=q[i].r)add(q[i].l,q[i].v),add(q[i].r+1,-q[i].v);
                else add(1,q[i].v),add(q[i].r+1,-q[i].v),add(q[i].l,q[i].v);
                p1[++s1]=q[i];
            }else if(q[i].id<=k){
                p2[++t1]=q[i];
            }else{
                ll tmp=0;
                for(int j=0;j<G[q[i].id-k].size();j++){
                    tmp+=ask(G[q[i].id-k][j]);
                    if(tmp>q[i].v)break;
                }
                if(tmp>=q[i].v)p1[++s1]=q[i];
                else q[i].v-=tmp,p2[++t1]=q[i];
            }
        }
        for(int i=s;i<=t;i++)
            if(q[i].id<=mid)
                if(q[i].l<=q[i].r)add(q[i].l,-q[i].v),add(q[i].r+1,q[i].v);
                else add(1,-q[i].v),add(q[i].r+1,q[i].v),add(q[i].l,-q[i].v);
        for(int i=1;i<=s1;i++)q[s+i-1]=p1[i];
        for(int i=1;i<=t1;i++)q[s+s1+i-1]=p2[i];
        if(s1)ef(s,s+s1-1,l,mid);
        if(t1)ef(s+s1,t,mid+1,r);
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int x,i=1;i<=m;i++)scanf("%d",&x),G[x].push_back(i);
        for(int i=1;i<=n;i++)scanf("%d",&mx[i]);
        scanf("%d",&k);
        for(int i=1;i<=k;i++)scanf("%d%d%lld",&q[i].l,&q[i].r,&q[i].v),q[i].id=i;
        for(int i=1;i<=n;i++)q[i+k].id=i+k,q[i+k].v=mx[i];
        ef(1,k+n,1,k+1);
        for(int i=1;i<=n;i++)ans[i]<=k?printf("%d\n",ans[i]):puts("NIE");
        return 0;
    }