首页 > 代码库 > BZOJ 1828
BZOJ 1828
program bzoj1828;const maxn=100001; check=10000000; type node=record l,r,s,a:longint;end;var t:array [0..maxn*5] of node; a,b,c:array [0..maxn] of longint; n,m,i,ans,mini:longint; procedure swap(var x,y:longint);begin x:=x xor y; y:=x xor y; x:=x xor y;end;procedure qsort(l,r:longint);var i,j,mia,mib:longint;begin i:=l; j:=r; mia:=a[(l+r) shr 1]; mib:=b[(l+r) shr 1]; while i<=j do begin while (b[i]<mib) or (b[i]=mib) and (a[i]<mia) do inc(i); while (b[j]>mib) or (b[j]=mib) and (a[j]>mia) do dec(j); if i<=j then begin swap(a[i],a[j]); swap(b[i],b[j]); inc(i); dec(j); end; end; if i<r then qsort(i,r); if j>l then qsort(l,j); end; function min(x,y:longint):longint;begin if x<y then exit(x) else exit(y);end;procedure build(l,r,i:longint);var mid:longint;begin t[i].l:=l; t[i].r:=r; if l=r then begin t[i].s:=c[l]; exit; end; mid:=(l+r)>>1; build(l,mid,i<<1); build(mid+1,r,i<<1+1); t[i].s:=min(t[i<<1].s,t[i<<1+1].s); end;procedure pass(i,add:longint); var lch,rch:longint; begin lch:=i shl 1; rch:=lch+1; inc(t[lch].s,add); inc(t[rch].s,add); inc(t[lch].a,add); inc(t[rch].a,add); t[i].a:=0; end; procedure change(l,r,add,i:longint); var mid:longint; begin if (t[i].l=l)and(t[i].r=r) then begin inc(t[i].s,add); inc(t[i].a,add); exit; end; if t[i].a<>0 then pass(i,t[i].a); mid:=(t[i].l+t[i].r)>>1; if r<=mid then change(l,r,add,i<<1) else if l>mid then change(l,r,add,i<<1+1) else begin change(l,mid,add,i<<1); change(mid+1,r,add,i<<1+1); end; t[i].s:=min(t[i<<1].s,t[i<<1+1].s); end; function getans(l,r,i:longint):longint; var mid,ans1,ans2:longint; begin if t[i].a<>0 then pass(i,t[i].a); if (t[i].l=l)and(t[i].r=r) then exit(t[i].s); ans1:=check; ans2:=check; mid:=(t[i].l+t[i].r)>>1; if r<=mid then ans1:=getans(l,r,i<<1) else if l>mid then ans2:=getans(l,r,i<<1+1) else begin ans1:=getans(l,mid,i<<1); ans2:=getans(mid+1,r,i<<1+1); end; exit(min(ans1,ans2)); end; begin read(n,m); for i:=1 to n do read(c[i]); build(1,n,1); for i:=1 to m do read(a[i],b[i]); sort(1,m); for i:=1 to m do begin mini:=getans(a[i],b[i],1); if mini>0 then begin inc(ans); change(a[i],b[i],-1,1); end; end; writeln(ans); end.
BZOJ 1828
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。