首页 > 代码库 > 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