Bzoj2527 [poi2011]meteors

类似于玄学CDQ分治的玄学整体二分

Posted by yjjr's blog on February 19, 2018

标签:整体二分,树状数组

题目

题目传送门

Description

Byteotian Interstellar Union有N个成员国。现在它发现了一颗新的星球,这颗星球的轨道被分为M份(第M份和第1份相邻),第i份上有第Ai个国家的太空站。

这个星球经常会下陨石雨。BIU已经预测了接下来K场陨石雨的情况。

BIU的第i个成员国希望能够收集Pi单位的陨石样本。你的任务是判断对于每个国家,它需要在第几次陨石雨之后,才能收集足够的陨石。

输入

第一行是两个数N,M。

第二行有M个数,第i个数Oi表示第i段轨道上有第Oi个国家的太空站。

第三行有N个数,第i个数Pi表示第i个国家希望收集的陨石数量。

第四行有一个数K,表示BIU预测了接下来的K场陨石雨。

接下来K行,每行有三个数Li,Ri,Ai,表示第K场陨石雨的发生地点在从Li顺时针到Ri的区间中(如果Li<=Ri,就是Li,Li+1,…,Ri,否则就是Ri,Ri+1,…,m-1,m,1,…,Li),向区间中的每个太空站提供Ai单位的陨石样本。

输出

N行。第i行的数Wi表示第i个国家在第Wi波陨石雨之后能够收集到足够的陨石样本。

如果到第K波结束后仍然收集不到,输出NIE。

数据范围

1<=n,m,k<=3 * 10^5 1<=Pi<=10^9 1<=Ai<10^9

Sample Input

3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2

Sample Output

3
NIE
1

题意

给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值

分析

整体二分的基础练手题

离线操作,对于每个国家来说,答案是可二分的

把所有国家整体二分,用树状数组维护修改操作

然后把已经满足条件的答案放在l->mid,还没满足的放在mid+1->r

之后继续向下分治

code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn=3e5+6;
int n,m,K,T,l[maxn],r[maxn],val[maxn];
int p[maxn],id[maxn],tmp[maxn],ans[maxn];
vector<int> a[maxn];ll t[maxn];
bool mark[maxn];
ll query(int x){ll re=0;for(int i=x;i;i-=i&-i)re+=t[i];return re;}
void modify(int x,int val){if(x>m)return;for(int i=x;i<=m;i+=i&-i)t[i]+=val;}
void opera(int k,int f){
    if(l[k]<=r[k])modify(l[k],f*val[k]),modify(r[k]+1,f*(-val[k]));
    else modify(1,f*val[k]),modify(r[k]+1,f*(-val[k])),modify(l[k],f*val[k]);
}
void solve(int l,int r,int L,int R){
    if(l>r)return;
    if(L==R){
        rep(i,l,r)ans[id[i]]=L;
        return;
    }
    int mid=(L+R)>>1;
    while(T<=mid)T++,opera(T,1);
    while(T>mid)opera(T,-1),T--;
    int cnt=0,now;ll tot;
    rep(i,l,r){
        tot=0;now=id[i];
        for(int j=0;j<a[now].size();j++){
            tot+=query(a[now][j]);
            if(tot>=p[now])break;
        }
        if(tot>=p[now])mark[now]=1,cnt++;else mark[now]=0;
    }
    int l1=l,l2=l+cnt;
    rep(i,l,r)
        if(mark[id[i]])tmp[l1++]=id[i];else tmp[l2++]=id[i];
    rep(i,l,r)id[i]=tmp[i];
    solve(l,l1-1,L,mid);solve(l1,l2-1,mid+1,R);
}
int main()
{
    n=read(),m=read();
    rep(i,1,m){int x=read();a[x].push_back(i);}
    rep(i,1,n)p[i]=read();
    K=read();
    rep(i,1,K)l[i]=read(),r[i]=read(),val[i]=read();
    K++;l[K]=1;r[K]=m;val[K]=inf;
    rep(i,1,n)id[i]=i;
    solve(1,n,1,K);
    rep(i,1,n)
        if(ans[i]!=K)printf("%d\n",ans[i]);else puts("NIE");
    return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr