感觉也比较调理啊......思路也很清晰,但是不知道为什么炸锅了........
by Qiuly @ 2019-01-27 09:39:02
清新版:
```cpp
#include<bits/stdc++.h>
#define ll long long
#define RI register int
#define C printf("\n")
#define A printf("A")
#define lowbit(x) ((x)&(-(x)))
const int N=1e6+2,inf=1e9;
using namespace std;
//template <typename _Tp> inline _Tp max(const _Tp&x,const _Tp&y){return x>y?x:y;}
//template <typename _Tp> inline _Tp min(const _Tp&x,const _Tp&y){return x<y?x:y;}
template <typename _Tp> inline void IN(_Tp&x){
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
if(flag)x=-x;
}
ll c[N];
vector<int> G[N];
int n,m,k,cnt,ans[N],RMB[N];
struct Node{
int l,r,id,type;ll k;
}q[N],q1[N],q2[N];
void add(int x,ll v){for(;x<=m;x+=lowbit(x))c[x]+=v;}
ll sum(int x){ll res=0;for(;x;x-=lowbit(x))res+=c[x];return res;};
inline void solve(int l,int r,int val_l,int val_r){
if(l>r)return;
if(val_l==val_r){
for(int i=l;i<=r;++i){
if(q[i].type==1)ans[q[i].id]=val_l;
}return;
}int mid=(val_l+val_r)>>1,cnt1=0,cnt2=0;
for(int i=l;i<=r;++i){
if(q[i].type==1){
ll ans=0;
for(int j=0;j<G[q[i].id].size();++j){
ans+=sum(G[q[i].id][j]);
if(ans>=q[i].k)break;
}
if(ans>=q[i].k)q1[++cnt1]=q[i];
else q[i].k-=ans,q2[++cnt2]=q[i];
}else{
if(q[i].id<=mid){
if(q[i].type==2)add(q[i].l,q[i].k),add(q[i].r+1,-q[i].k);
else add(1,q[i].k),add(q[i].r+1,-q[i].k),add(q[i].l,q[i].k);
q1[++cnt1]=q[i];
}else q2[++cnt2]=q[i];
}
}
for(int i=l;i<=r;++i){
if(q[i].type==2){add(q[i].l,-q[i].k);add(q[i].r+1,q[i].k);}
else if(q[i].type==3){add(1,-q[i].k);add(q[i].r+1,q[i].k);add(q[i].l,-q[i].k);}
}
for(int i=1;i<=cnt1;++i)q[i+l-1]=q1[i];
for(int i=1;i<=cnt2;++i)q[i+l+cnt1-1]=q2[i];
solve(l,l+cnt1-1,val_l,mid);solve(l+cnt1,r,mid+1,val_r);
}
int main(){
IN(n),IN(m);
for(int x,i=1;i<=m;++i)IN(x),G[x].push_back(i);
for(int i=1;i<=n;++i)IN(RMB[i]);
IN(k);int cnt=0;
for(int i=1;i<=k;++i){
IN(q[++cnt].l),IN(q[cnt].r),IN(q[cnt].k);q[cnt].id=i;
if(q[cnt].r>=q[cnt].l)q[cnt].type=2;else q[cnt].type=3;
}
for(int i=1;i<=n;++i)q[++cnt].k=RMB[i],q[cnt].type=1,q[cnt].id=i;
solve(1,k+n,1,k+1);
for(int i=1;i<=n;++i){
if(ans[i]!=k+1)printf("%d\n",ans[i]);
else printf("NIE\n");
}return 0;
}
```
by Qiuly @ 2019-01-27 09:40:24
~~又是一个萌新怪~~
by __Hacheylight__ @ 2019-01-27 09:47:00