[bzoj2527][Poi2011]Meteors_整体二分_树状数组
Meteors bzoj-2527 Poi-2011
题目大意：题目链接。
注释：略。
想法：
首先答案可以离线，且具有单调性。
这里的单调性就是随着时间的推移，每个国家收集的陨石数增加。
不难想到整体二分，对时间进行二分。
但是有一个问题，就是一个国家出现了多次，这样的话我们用链表把他们记录到一起即可，二分的时候传链头。
这个题就是用树状数组+差分实现区间加。
先把$[l,mid]$的操作都用树状数组加上。然后枚举当前还没有答案的国家：每一个都访问整条链加一起跟自己需要的$k$判断一下扔进左区间还是右区间即可。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mod 1000000000000000
#define N 300010
using namespace std; typedef long long ll;
ll tree[N];
int n,m;
struct Node {int x,y,val;}q[N];
int head[N],nxt[N];
int a[N],t[N],w[N],ans[N];
inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}
inline int lowbit(int x) {return x&(-x);}
void update(int x,ll val) {for(int i=x;i<=m;i+=lowbit(i)) (tree[i]+=val)%=mod;}
ll query(int x) {ll ans=0; for(int i=x;i>=1;i-=lowbit(i)) (ans+=tree[i])%=mod; return ans;}
void solve(int x,int y,int l,int r)
{
if(x>y) return;
if(l==r)
{
for(int i=x;i<=y;i++) ans[a[i]]=l;
return;
}
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)
{
if(q[i].x<=q[i].y) update(q[i].x,q[i].val),update(q[i].y+1,-q[i].val);
else update(q[i].x,q[i].val),update(m+1,-q[i].val),update(1,q[i].val),update(q[i].y+1,-q[i].val);
}
int tl=x,tr=y;
for(int i=x;i<=y;i++)
{
if(!w[a[i]]) t[tl++]=a[i];
else
{
ll c=0,vc=0;
for(int j=head[a[i]];j;j=nxt[j])
{
c+=query(j);
if(c>=mod) vc+=c/mod,c%=mod;
else if(c<0) vc+=c/mod-1,c=(c%mod+mod)%mod;
}
if(vc||c>=w[a[i]]) t[tl++]=a[i];
else w[a[i]]-=c,t[tr--]=a[i];
}
}
for(int i=x;i<=y;i++) a[i]=t[i];
for(int i=l;i<=mid;i++)
{
if(q[i].x<=q[i].y) update(q[i].x,-q[i].val),update(q[i].y+1,q[i].val);
else update(q[i].x,-q[i].val),update(m+1,q[i].val),update(1,-q[i].val),update(q[i].y+1,q[i].val);
}
solve(x,tr,l,mid); solve(tl,y,mid+1,r);
}
int main()
{
n=rd(),m=rd();
for(int i=1;i<=m;i++)
{
int x=rd();
nxt[i]=head[x]; head[x]=i;
}
for(int i=1;i<=n;i++) w[i]=rd(),a[i]=i;
int k=rd();
for(int i=1;i<=k;i++) q[i].x=rd(),q[i].y=rd(),q[i].val=rd();
solve(1,n,1,k+1);
for(int i=1;i<=n;i++)
{
if(ans[i]>=1&&ans[i]<=k) printf("%d\n",ans[i]);
else puts("NIE");
}
return 0;
}
小结：整体二分的裸题。我们发现整体二分都通常和树状数组一起搭配使用。
投递科锐国际等公司10个岗位