bzoj千题计划149:bzoj2527: [Poi2011]Meteors

时间:2022-02-23 22:32:56

http://www.lydsy.com/JudgeOnline/problem.php?id=2527

整体二分

区间加,单点查,树状数组维护差分序列

注意 累积可能会爆long long,所以一满足要求就break

#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 300001 #define lowbit(x) x&-x typedef long long LL; int m,k; int tot,front[N],nxt[N],to[N]; struct node
{
bool ty;
int l,r,id;
int num,cur;
}e[N<<],tmp1[N<<],tmp2[N<<]; int need[N],ans[N]; LL have[N]; LL c[N+]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int x,int y)
{
to[++tot]=y; nxt[tot]=front[x]; front[x]=tot;
} void change(int x,int y)
{
while(x<=m)
{
c[x]+=y;
x+=lowbit(x);
}
} LL query(int x)
{
LL sum=;
while(x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
} void solve(int head,int tail,int l,int r)
{
if(head>tail) return;
if(l==r)
{
for(int i=head;i<=tail;++i)
if(!e[i].ty) ans[e[i].l]=l;
return;
}
int mid=l+r>>;
for(int i=head;i<=tail;++i)
{
if(e[i].ty && e[i].id<=mid)
{
if(e[i].l<=e[i].r)
{
change(e[i].l,e[i].num);
change(e[i].r+,-e[i].num);
}
else
{
change(e[i].l,e[i].num);
change(,e[i].num);
change(e[i].r+,-e[i].num);
}
}
else if(!e[i].ty)
{
have[e[i].l]=;
for(int j=front[e[i].l];j;j=nxt[j])
{
have[e[i].l]+=query(to[j]);
if(have[e[i].l]>=e[i].num) break;
} }
}
for(int i=head;i<=tail;++i)
{
if(e[i].ty && e[i].id<=mid)
{
if(e[i].l<=e[i].r)
{
change(e[i].l,-e[i].num);
change(e[i].r+,e[i].num);
}
else
{
change(e[i].l,-e[i].num);
change(,-e[i].num);
change(e[i].r+,e[i].num);
}
}
}
int ll=,rr=;
for(int i=head;i<=tail;++i)
{
if(!e[i].ty)
{
if(e[i].cur+have[e[i].l]>=e[i].num) tmp1[++ll]=e[i];
else
{
e[i].cur+=have[e[i].l];
tmp2[++rr]=e[i];
}
}
else
{
if(e[i].id<=mid) tmp1[++ll]=e[i];
else tmp2[++rr]=e[i];
}
}
for(int i=;i<=ll;++i) e[head+i-]=tmp1[i];
for(int i=;i<=rr;++i) e[head+ll+i-]=tmp2[i];
solve(head,head+ll-,l,mid);
solve(head+ll,tail,mid+,r);
} int main()
{
int n;
read(n); read(m);
int x,y,z;
for(int i=;i<=m;++i)
{
read(x);
add(x,i);
}
for(int i=;i<=n;++i) read(need[i]);
read(k);
for(int i=;i<=k;++i)
{
read(e[i].l);
read(e[i].r);
read(e[i].num);
e[i].ty=true;
e[i].id=i;
}
k++;
e[k].l=;
e[k].r=m;
e[k].num=1e9;
e[k].ty=true;
e[k].id=k;
for(int i=;i<=n;++i)
{
e[k+i].l=i;
e[k+i].num=need[i];
}
solve(,n+k,,k);
for(int i=;i<=n;++i)
{
if(ans[i]==k) puts("NIE");
else cout<<ans[i]<<'\n';
}
}