POI2011 流星 Meteors
题目传送门
题意
\(Byteotian\)星际联盟,最近在附近的星系发现了一颗新的行星。尽管这颗行星由于奥妙重重的流星雨不适合人类居住，但是这给我们带来了一个非常有趣的研究对象。\(BIU\)的\(n\)个成员国为了采集这些陨石的样本，将它们的空间站发射到了这颗行星的轨道附近。\(BIU\) 将这颗星球的轨道分为\(m\)份（编号从\(1\)到\(m\)，且第\(m\)份和第\(1\)份相邻），第\(i\)份上部署了第\(A_i\)个国家的太空站。\(BIU\)已经准确地预测了接下来\(k\)场陨石雨的情况。\(BIU\)的第\(i\)个成员国希望能够收集\(P_i\)单位的陨石样本。你的任务是判断对于每个国家，在第几次陨石雨之后，才能收集足够的陨石。
题解
一道整体二分裸题，第一次写整体二分，发现也不是特别难写，就是常数似乎大了点。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+500;
typedef long long ll;
int n,nw,m,k;
struct Rain {
int l,r,v;
}r[N];
int ans[N],P[N];
vector<int>Q,G[N];
namespace BIT {
ll t[N];
int lowbit(int x) {return x&-x;}
void Add(int x,int v) {
for(int i=x;i<=m;i+=lowbit(i)) t[i]+=v;
}
ll Sum(int x) {
ll ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=t[i];
return ans;
}
}
void Update(int pos,int v) {
if(r[pos].l<=r[pos].r) {
BIT::Add(r[pos].l,v*r[pos].v);BIT::Add(r[pos].r+1,-v*r[pos].v);
}
else {
BIT::Add(r[pos].l,v*r[pos].v);BIT::Add(m+1,-v*r[pos].v);
BIT::Add(1,v*r[pos].v);BIT::Add(r[pos].r+1,-v*r[pos].v);
}
}
void Calc(int pos) {
while(nw<pos) Update(nw+1,1),nw++;
while(nw>pos) Update(nw,-1),nw--;
}
void Solve(vector<int>Que,int l,int r) {
if(!Que.size()) return ;
if(l==r) {
for(int i=0;i<(int)Que.size();i++) ans[Que[i]]=l;
return ;
}
vector<int>Q1,Q2;
Q1.clear();Q2.clear();
int mid=(l+r)>>1;
Calc(mid);
for(int i=0;i<Que.size();i++) {
int o=Que[i];
ll ret=0;
for(int j=0;j<(int)G[o].size();j++) {
int p=G[o][j];
ret+=BIT::Sum(p);
if(ret>=P[o]) break;
}
if(ret>=P[o]) Q1.push_back(o);
else Q2.push_back(o);
}
Solve(Q1,l,mid);
Solve(Q2,mid+1,r);
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1,x;i<=m;i++) {
scanf("%d",&x);
G[x].push_back(i);
}
for(int i=1;i<=n;i++) scanf("%d",&P[i]),Q.push_back(i);
scanf("%d",&k);
for(int i=1;i<=k;i++) scanf("%d%d%d",&r[i].l,&r[i].r,&r[i].v);
nw=0;
Solve(Q,1,k+1);
for(int i=1;i<=n;i++) {
if(ans[i]==k+1) puts("NIE");
else printf("%d\n",ans[i]);
}
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/10445639.html
