【BZOJ2527】MET-Meteors（整体二分）

题面

BZOJ权限题，良心洛谷链接

题解

其实我也不会做

看了zsy博客才会做。。。

这题如果直接爆算做显然行不通

如果只有单次询问，我们就可以二分答案

但是询问太多。。

不会二分。。

怎么办？

我们来想想瓶颈在哪里

如果每次都进行一次单次二分

我们就需要不停的计算前缀和

但是其实再进行别的二分的时候我们已经算过了

这里就算重了

怎么解决？

那我们就不让他算重：

我们把所有询问一起二分

这样每次计算完之后

所有的询问就被分成了两部分：

一部分是当前二分值有解

另一部分是无解

这样就可以解决重复计算的问题了

因为要反复计算前缀和

所以使用树状数组来计算就行了

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

#define MAX 320000

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

struct Rain{int l,r;ll w;}r[MAX];

ll c[MAX];

int n,m,ans[MAX],K;

int lowbit(int x){return x&(-x);}

void Add(int x,int w){while(x<=m)c[x]+=w,x+=lowbit(x);}

ll getsum(int x){ll ret=0;while(x)ret+=c[x],x-=lowbit(x);return ret;}

vector<int> a[MAX];

struct Query{int id;ll p;}p[MAX],p1[MAX],p2[MAX];

void Fall(int t,int opt)

{

	if(r[t].l>r[t].r)Add(1,opt*r[t].w);

	Add(r[t].l,opt*r[t].w),Add(r[t].r+1,-opt*r[t].w);

}

void Work(int l,int r,int L,int R)

{

	if(L>R)return;

	if(l==r)

	{

		for(int i=L;i<=R;++i)ans[p[i].id]=l;

		return;

	}

	int mid=(l+r)>>1;

	ll tot;

	int t1=0,t2=0;

	for(int i=l;i<=mid;++i)Fall(i,1);

	for(int i=L;i<=R;++i)

	{

		tot=0;

		for(int j=0,l=a[p[i].id].size();j<l;++j)tot+=getsum(a[p[i].id][j]);

		if(tot>=p[i].p)p1[++t1]=p[i];

		else p[i].p-=tot,p2[++t2]=p[i];

	}

	for(int i=l;i<=mid;++i)Fall(i,-1);

	for(int i=1;i<=t1;++i)p[i+L-1]=p1[i];

	for(int i=1;i<=t2;++i)p[i+L+t1-1]=p2[i];

	Work(l,mid,L,L+t1-1);

	Work(mid+1,r,L+t1,R);

}

int main()

{

	n=read();m=read();

	for(int i=1;i<=m;++i)a[read()].push_back(i);

	for(int i=1;i<=n;++i)p[i].p=read(),p[i].id=i;

	K=read();

	for(int i=1;i<=K;++i)r[i].l=read(),r[i].r=read(),r[i].w=read();

	++K;r[K]=(Rain){1,m,1e9};

	Work(1,K,1,n);

	for(int i=1;i<=n;++i)ans[i]==K?puts("NIE"):printf("%d\n",ans[i]);

	return 0;

}