抽象。
P3527 [POI2011] MET-Meteors
Byteotian Interstellar Union 有 \(n\) 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 \(m\) 份（第 \(m\) 份和第 \(1\) 份相邻），第 \(i\) 份上有第 \(a_i\) 个国家的太空站。
这个星球经常会下陨石雨。BIU 已经预测了接下来 \(k\) 场陨石雨的情况。
BIU 的第 \(i\) 个成员国希望能够收集 \(p_i\) 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。
sol
考虑一个函数 \(work(l,r,ql,qr).\)
函数表示欲要处理 \(ans[a[l]],ans[a[l+1]],ans[a[l+2]],\cdots,ans[a[r]].\)
现在已经可以确定这些 \(ans\) 是可以在 \(ql,qr\) 之间的。
然后考虑把整个区间 \(a\) 划分成两个区间 \([l,x],(x,r],\) 然后这两个区间的 \(ans\) 分别可以确定在 \([ql,qmid],(qmid,qr]\) 之间。然后继续递归下去。
先降下 \([ql,qmid]\) 之间的流星雨，然后处理一下流星雨的树状数组，逐个国家判断之的流星雨降落数量和 \(p[a[i]]\) 的关系。
然后如果小于用一个指针划分到左边，否则用指针划分到右边。
最后注意 \(l\) 的区间分治过程中要回溯（把之前降下的流星雨给升回去）。
然后最后为了判断无解情况要多加一次流星雨。
程式
#include <bits/stdc++.h>
#define Add emplace_back
typedef long long ll;
using std::cin;
using std::cout;
const int N=3e5+10;
ll a[N],b[N],c[N];
int p[N],ans[N];
int n,m,k;
inline int lb(int x){ return x&-x; }
inline void add(int x,int k){ while(x<=m) c[x]+=k, x+=lb(x); }
inline ll qry(int l){
ll ans=0;
while(l) ans+=c[l], l-=lb(l);
return ans;
}
inline void addr(int l,int r,int k){ add(l,k), add(r+1,-k); }
struct rrr{ int l,r,v; } rain[N];
inline void upd(int i,int zf){
if(rain[i].l<=rain[i].r) addr(rain[i].l,rain[i].r,rain[i].v*zf);
else addr(1,rain[i].r,rain[i].v*zf), addr(rain[i].l,m,rain[i].v*zf);
}
std::vector<int> v[N];
void work(int l,int r,int ql,int qr){
if(ql==qr||l>r) {
for(int i=l;i<=r;++i) ans[a[i]]=ql;
return;
}
int midc=(l+r)>>1,midq=(ql+qr)>>1;
for(int i=ql;i<=midq;++i) upd(i,1);
int lft=l,rgt=r;
for(int i=l;i<=r;++i){
ll R=0;
for(int x:v[a[i]]){
R+=qry(x);
if(R>=p[a[i]]) break;
}
if(R>=p[a[i]]) b[lft++]=a[i];
else b[rgt--]=a[i];
}
for(int i=l;i<=r;++i) a[i]=b[i];
work(lft,r,midq+1,qr);
for(int i=ql;i<=midq;++i) upd(i,-1);
work(l,rgt,ql,midq);
}
// l r country ql qr rain
int main(){
std::ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
for(int i=1,tmp;i<=m;++i) cin>>tmp, v[tmp].Add(i);
for(int i=1;i<=n;++i) cin>>p[i],a[i]=i;
cin>>k;
for(int i=1;i<=k;++i) cin>>rain[i].l>>rain[i].r>>rain[i].v;
work(1,n,1,k+1);
for(int i=1;i<=n;++i){
if(ans[i]>k) cout<<"NIE\n";
else cout<<ans[i]<<"\n";
}
return 0;
}