正解:整体二分
解题报告:
传送门! 还有个双倍经验!(明明是一样的题目为什么你们一个紫一个黑啊喂!
这题首先要想到可以二分嘛,然后看到多组询问肯定就整体二分鸭
那就是基本套路啊,发现是区间修改单点查询,于是就树状数组前缀和维护一波,就差不多辣
其实是个板子题,只是刚学整体二分所以还是写下题解QwQ
然后有几个细节分别港下
第一个是注意到它是个环形的,所以在update的时候记得分情况讨论一下
第二个是关于判断NIE,可以在最后增加一次流星雨,保证这次流星雨之后一定所有国家都能得到足够的流星,输出的时候判断一下就好
最后一个是比较重要的,我发现好几篇题解都被hack辣,,,就是第11个点,如果WA辣,应该就是这个问题,大概港下
首先从数据范围可以发现其实它是可以溢出的,就是假如有3e5场流星雨,每场提供1e9的流星,那在查询的时候就会炸longlong
但是看到它的需求也是<=1e9的,所以可以在算的时候判断一下,如果得到的已经大于1e9就可以直接break辣,只要加一句话就好QwQ
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define gc getchar()
#define ll long long
#define lowbit(x) (x&(-x))
#define rp(i,x,y) for(rg ll i=x;i<=y;++i) const ll N=3e5+,inf=1e9+;
ll n,m,q,as[N],bst[N];
vector<ll>bl[N];
struct node{ll l,r,dat;}quest[N];
struct nd{ll nd,id;}p[N],tmp_l[N],tmp_r[N]; il ll read()
{
rg char ch=gc;rg ll x=;rg bool y=;
while(ch!='-' && (ch>'' || ch<''))ch=gc;
if(ch=='-')ch=gc,y=;
while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void updat(ll x,ll dat){while(x<=m)bst[x]+=dat,x+=lowbit(x);}
il ll query(ll x){ll ret=;while(x)ret+=bst[x],x-=lowbit(x);return ret;}
void solv(ll ct_l,ll ct_r,ll as_l,ll as_r)
{
if(ct_l>ct_r)return;
if(as_l==as_r){rp(i,ct_l,ct_r)as[p[i].id]=as_l;return;}
ll mid=(as_l+as_r)>>,cnt_l=,cnt_r=;
rp(i,as_l,mid)
if(quest[i].l<=quest[i].r)updat(quest[i].l,quest[i].dat),updat(quest[i].r+,-quest[i].dat);
else updat(,quest[i].dat),updat(quest[i].r+,-quest[i].dat),updat(quest[i].l,quest[i].dat);
rp(i,ct_l,ct_r)
{
ll ret=,sz=bl[p[i].id].size();
rp(j,,sz-){ret+=query(bl[p[i].id][j]);if(ret>inf)break;}
if(ret>=p[i].nd)tmp_l[++cnt_l]=p[i];else p[i].nd-=ret,tmp_r[++cnt_r]=p[i];
}
rp(i,as_l,mid)
if(quest[i].l<=quest[i].r)updat(quest[i].l,-quest[i].dat),updat(quest[i].r+,quest[i].dat);
else updat(,-quest[i].dat),updat(quest[i].r+,quest[i].dat),updat(quest[i].l,-quest[i].dat);
rp(i,ct_l,ct_l+cnt_l-)p[i]=tmp_l[i-ct_l+];rp(i,ct_l+cnt_l,ct_r)p[i]=tmp_r[i-cnt_l-ct_l+];
solv(ct_l,ct_l+cnt_l-,as_l,mid);solv(ct_l+cnt_l,ct_r,mid+,as_r);
} int main()
{
n=read();m=read();rp(i,,m)bl[read()].push_back(i);rp(i,,n)p[i]=(nd){read(),i};q=read();rp(i,,q)quest[i].l=read(),quest[i].r=read(),quest[i].dat=read();quest[q+]=(node){,m,1e9};
solv(,n,,q+);rp(i,,n)if(as[i]!=q+)printf("%lld\n",as[i]);else printf("NIE\n");
return ;
}