P3527 [POI2011]MET-Meteors

\(\mathcal Link\)

做法一：分块

认为 \(n,m,k\) 同阶。

对操作分块，将 \(s\) 个操作分成一个块，每次扫一个整块，用差分算出已收集的量。然后依次扫每个国家，判断是否收集满了，是的话就倒着扫一遍找到位置，不超过 \(s\) 次。

复杂度 \(\mathcal O\left(\dfrac{n^2}s+ns\right)\)。令 \(s=\sqrt n\)，复杂度为 \(\mathcal O(n\sqrt n)\)

做法二：整体二分 （感谢 @Alex_Wei）

将所有询问拉出来二分，用差分做到不带 \(\log\) ，但要对下标离散化，直接用桶即可。

要注意和可能会爆 long long，所以要与 inf 取 min。

复杂度 \(\mathcal O(n\log n)\)

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
	x=0;int w=0;char c=GetC();
	for(;!isdigit(c);w|=c=='-',c=GetC());
	for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
	if(w) x=-x;
	return in;
}
const int N=3e5+5,INF=1e9;
using ll=long long;
int bel[N],a[N];
struct OPT{int l,r,x,id;}op[N];
int cnt=0;
int n,m,k;
int q[N];
int ans[N];
vector<int> v[N];
int ql[N],qr[N];
ll t[N];
ll cur[N];
void solve(int l,int r,int L,int R,int range){// ans in [l,r],queries from L to R
	if(l==r){
		for(int i=L;i<=R;++i) ans[q[i]]=op[l].id;
		return ;
	}
	int mid=(l+r)>>1;
	for(int i=1;i<=range;++i) t[i]=0;
	for(int i=L;i<=R;++i)
		for(auto it:v[q[i]]) ++t[it];
	for(int i=2;i<=range;++i) t[i]+=t[i-1];
	for(int i=L;i<=R;++i)
		for(auto &it:v[q[i]]) it=t[it];
	for(int i=l;i<=r;++i){
		op[i].l=t[op[i].l-1]+1;
		op[i].r=t[op[i].r];
	}
	range=t[range];
	for(int i=1;i<=range;++i) t[i]=0;
	for(int i=l;i<=mid;++i){
		t[op[i].l]+=op[i].x;
		t[op[i].r+1]-=op[i].x;
	}
	for(int i=2;i<=range;++i) t[i]+=t[i-1];
	int lcnt=0,rcnt=0;
	for(int i=L;i<=R;++i){
		cur[i]=0;
		for(auto it:v[q[i]]) cur[i]+=t[it];
		if(cur[i]>=a[q[i]]) ql[++lcnt]=q[i];
		else qr[++rcnt]=q[i],a[q[i]]-=cur[i];
	}
	for(int i=1;i<=R-L+1;++i){
		if(i<=lcnt) q[L+i-1]=ql[i];
		else q[L+i-1]=qr[i-lcnt];
	}
	solve(l,mid,L,L+lcnt-1,range);
	solve(mid+1,r,L+lcnt,R,range);
}
int main(){
	io>>n>>m;
	for(int i=1;i<=m;++i) 
		io>>bel[i],v[bel[i]].push_back(i);
	for(int i=1;i<=n;++i) 
		io>>a[i];
	io>>k;
	for(int i=1;i<=k;++i){
		int l,r,x;io>>l>>r>>x;
		if(l<=r) op[++cnt]=(OPT){l,r,x,i};
		else{
			op[++cnt]=(OPT){l,m,x,i};
			op[++cnt]=(OPT){1,r,x,i};
		}
	}
	++cnt;
	op[cnt]={1,n,INF,cnt};
	for(int i=1;i<=n;++i) q[i]=i;
	solve(1,cnt,1,n,m);
	for(int i=1;i<=n;++i){
		if(ans[i]==cnt) puts("NIE");
		else printf("%d\n",ans[i]);
	}
	return 0;
}