首页 > 代码库 > [Poi2011]Meteors 题解
[Poi2011]Meteors 题解
题目大意:
给定一个环,每个节点有一个所属国家,k次事件,每次对[l,r]区间上的每个点点权加上一个值,求每个国家最早多少次操作之后所有点的点权和能达到一个值。
思路:
整体二分(二分答案),对于每个国家,如果在m次事件后到达目标则放在左边,否则放在右边(用下标映射)。区间加用树状数组维护。
反思:
整体二分不熟练。二分计算时算到mid,now表示当前已经经历了几次事件(可进可退)。快速排序用的也是整体二分。
代码:
1 #include<cstdio> 2 #define ll long long 3 const int M=300005; 4 int n,m,i,k,now,a[M],p[M],s[M],e[M],id[M],di[M],nex[M],fir[M],ans[M]; 5 ll c[M];//now表示当前已经经历了几次事件 6 7 int read() 8 { 9 int x=0; char ch=getchar(); 10 while (ch<48 || ch>57) ch=getchar(); 11 while (ch>47 && ch<58) x=(x<<1)+(x<<3)+ch-48,ch=getchar(); 12 return x; 13 } 14 15 void add(int x,int y) { for (;x<=m;x+=x&-x) c[x]+=y; } 16 ll sum(int x) { ll ans=0; for (;x;x^=x&-x) ans=ans+c[x]; return ans; } 17 18 void solve(int L,int R,int l,int r) 19 { 20 if (L>R) return; 21 if (l==r) { for (;L<=R;++L) ans[id[L]]=l; return; } 22 int mid=l+r>>1,i,j,x=L-1,y=R+1; ll tot; 23 while (now<mid) 24 if (s[++now]<=e[now]) add(s[now],a[now]),add(e[now]+1,-a[now]); 25 else add(s[now],a[now]),add(1,a[now]),add(e[now]+1,-a[now]); 26 for (;now>mid;--now) 27 if (s[now]<=e[now]) add(s[now],-a[now]),add(e[now]+1,a[now]); 28 else add(s[now],-a[now]),add(1,-a[now]),add(e[now]+1,a[now]); 29 for (i=L;i<=R;++i) 30 { 31 for (j=fir[id[i]],tot=0;j && (tot=tot+sum(j))<p[id[i]];j=nex[j]); 32 if (tot<p[id[i]]) di[--y]=id[i]; else di[++x]=id[i]; 33 } 34 for (i=L;i<=R;++i) id[i]=di[i]; 35 solve(L,x,l,mid),solve(y,R,mid+1,r); 36 } 37 38 int main() 39 { 40 n=read(),m=read(); 41 for (i=1;i<=m;++i) nex[i]=fir[k=read()],fir[k]=i; 42 for (i=1;i<=n;++i) p[i]=read(),id[i]=i; 43 for (k=read()+1,i=1;i<k;++i) s[i]=read(),e[i]=read(),a[i]=read(); 44 s[k]=1,e[k]=m,a[i]=1000000000,solve(1,n,1,k); 45 for (i=1;i<=n;++i) 46 if (ans[i]==k) puts("NIE"); 47 else printf("%d\n",ans[i]); 48 return 0; 49 }
[Poi2011]Meteors 题解
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。