题解 P3527 【[POI2011]MET-Meteors】
这道题整体二分，这个整体二分很神奇，类似于二分答案
首先，我们要二分每一个国家所需要的次数，同时用树状数组维护区间的陨石数量
如果是分别枚举每一个国家所需的时间，因为要累加，总复杂度是O(nmlgmlgk),会TLE
这时候，便要用整体二分——我们将所有的国家的时间一起二分：
每一次，取一个mid的时间，并计算出区间内每个国家收集的数量，把所有能够完成国家的放在一边，把所有不能的国家放在另一边
然后把左边和右边分为作为一个区间
左区间继续二分mid以下的时间，右区间继续二分mid以上的时间
这样的复杂度就变成了O(nlgnlgk),同时也能求出每一个国家所需的时间
不过有些地方要注意优化，不然会卡常
累计的话树状数组直接暴力算就行了
下面是代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
using namespace std;
#define MAXN 300010
#define LLI long long
int n,m,belong[MAXN],ls[MAXN],rs[MAXN],target[MAXN],k,
val[MAXN],now,cont[MAXN],lt[MAXN],rt[MAXN],ans[MAXN];
LLI tree[MAXN],tc[MAXN];
vector<int>T[MAXN];//每个国家所拥有的空间站
void add(int x,int v){
for(;x<=m;x+=x&-x)
tree[x]+=v;
}//树状数组修改
LLI query(int x){
LLI res=0;
for(;x;x-=x&-x)
res+=tree[x];
return res;
}//树状数组查询
void change(int l,int r,int x){//树状数组区间加
if(l<=r){
add(l,x);add(r+1,-x);
}else{
add(l,x);add(m+1,-x);
add(1,x);add(r+1,-x);
//这里考虑到是环形，所以分为两段区间
}
}
int t;
void read(int&x){x=0;while(t=getchar(),!isdigit(t));while(x=(x<<1)+(x<<3)+t-48,t=getchar(),isdigit(t));}
//快读
void query(int l,int r,int L,int R){
if(l>r)return;if(L>R)return;//这里貌似有一句可以不用写
if(l==r){
for(register int i=L;i<=R;++i)
ans[cont[i]]=l;//如果某个（些）国家二分到了答案，就记录下来
//cont是国家的编号
return;
}
int mid=l+r>>1;
while(now<mid)++now,change(ls[now],rs[now],val[now]);
while(now>mid)change(ls[now],rs[now],-val[now]),--now;
//改变当前树状数组的状态(把状态从某个时间移到另一个时间)
for(int i=L;i<=R;++i){
tc[cont[i]]=0;
for(int j=0;j<T[cont[i]].size();++j)
tc[cont[i]]+=query(T[cont[i]][j]);//累加每个国家的数量
}
int lct=0,rct=0;
for(register int i=L;i<=R;++i)
if(tc[cont[i]]>=target[cont[i]])lt[++lct]=cont[i];//把可以的国家归于左区间
else rt[++rct]=cont[i];//把不可以的国家归于右区间
int mid2=lct;
for(register int i=1;i<=lct;++i)cont[i+L-1]=lt[i];
for(register int i=1;i<=rct;++i)cont[L+lct+i-1]=rt[i];//复制区间
query(l,mid,L,L+mid2-1);
query(mid+1,r,L+mid2,R);//继续二分
}
int main(){
read(n),read(m);
for(register int i=1;i<=m;++i){
read(belong[i]);
T[belong[i]].push_back(i);
}
for(register int i=1;i<=n;++i){
read(target[i]);
cont[i]=i;//国家列表初始化
}
read(k);
for(register int i=1;i<=k;++i){
read(ls[i]);
read(rs[i]);
read(val[i]);
}
++k;ls[k]=1;rs[k]=m;val[k]=0x3f3f3f3f;//在第k+1的时刻设置无限个陨石，即无解的条件
now=0;
query(1,k,1,n);
for(register int i=1;i<=n;++i)
if(ans[i]==k)puts("NIE");
else printf("%d\n",ans[i]);
return 0;
}