分析
一个整体二分的经典题
每次二分得到两个答案区间,然后把现在的国家分别看属于哪个答案区间,递归求解即可
代码
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<cctype> #include<cmath> #include<cstdlib> #include<queue> #include<ctime> #include<vector> #include<set> #include<map> #include<stack> using namespace std; int n,m,k,now,t1[300100],t2[300100],d[300100]; int sum[300100],id[300100],L[300100],R[300100],w[300100],Ans[300100]; vector<int>wh[300100]; inline int lb(int x){return x&(-x);} inline int q(int x){int res=0;while(x)res+=d[x],x-=lb(x);return res;} inline void add(int x,int s){while(x<=m)d[x]+=s,x+=lb(x);} inline bool ck(int x){ int res=0; for(int i=0;i<wh[x].size();i++){ res+=q(wh[x][i]); if(res>=sum[x])return 1; } return 0; } inline void update(int x,int s){ add(L[x],s),add(R[x]+1,-s); if(R[x]<L[x])add(1,s); } inline void work(int x,int y,int le,int ri){ if(x>y||le>ri)return; int mid=(le+ri)>>1,l1=0,l2=0; if(le==ri){ for(int i=x;i<=y;i++)Ans[id[i]]=le; return; } while(now<mid)now++,update(now,w[now]); while(now>mid)update(now,-w[now]),now--; for(int i=x;i<=y;i++) if(ck(id[i]))t1[++l1]=id[i]; else t2[++l2]=id[i]; for(int i=1;i<=l1;i++)id[x+i-1]=t1[i]; for(int i=1;i<=l2;i++)id[x+l1+i-1]=t2[i]; if(l1)work(x,x+l1-1,le,mid); if(l2)work(x+l1,y,mid+1,ri); } int main(){ int i,j,x; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ scanf("%d",&x); wh[x].push_back(i); } for(i=1;i<=n;i++)scanf("%d",&sum[i]),id[i]=i; scanf("%d",&k);k++; for(i=1;i<k;i++)scanf("%d%d%d",&L[i],&R[i],&w[i]); L[k]=1,R[k]=m,w[k]=1e9+7; work(1,m,1,k); for(i=1;i<=n;i++) if(Ans[i]==k)puts("NIE"); else printf("%d\n",Ans[i]); return 0; }