为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
URAL/1028
来自NOCOW
< URAL
我用的是线段树--by cagngee http://www.cgang.tk
var i,j,k,m,n,l:longint; st:array[1..500000]of longint; ans:array[0..15000]of longint; now:longint; procedure ins(i,x,y:longint); var mid:longint; begin if x=y then inc(now,st[i]) else begin mid:=(x+y)div 2; if k<=mid then ins(i*2,x,mid) else begin ins(i*2+1,mid+1,y); inc(now,st[i*2]); end; end; inc(st[i]); end; begin readln(n); for i:=1 to n do begin readln(k,j); now:=0; ins(1,0,32000); inc(ans[now]); end; for i:=0 to n-1 do writeln(ans[i]); end.
所有支持logn插入&询问的数据结构. 平衡化二叉搜索树(BBST).树状数组(BIT).线段树(SegmentTree).等等.
合并排序也可
#include <iostream> using namespace std; long n; long k; long ans=-1; long i,j,p; struct data { long x,y,n; }xx,a[20000],b[20000]; long c[20000]; void merge (long l,long r) { long x,y,z=0; if (l==r-1) { if (a[l].x>a[r].x) { xx=a[l]; a[l]=a[r]; a[r]=xx; } else a[r].n++; return; } if (l<r) { merge(l,(l+r)/2); merge((l+r)/2+1,r); } else return; x=l; y=(l+r)/2+1; if ((l==0)&&(r==2)) { z=0; } for (z=0;z<=r-l;z++) { if (x>(l+r)/2) { a[y].n+=(x-l); b[z]=a[y]; y++; continue; } if (y>r) { b[z]=a[x]; x++; continue; } if (a[x].x<=a[y].x) { b[z]=a[x]; x++; continue; } else { a[y].n+=(x-l); b[z]=a[y]; y++; continue; } } x=l; for (z=0;z<=r-l;z++) { a[x]=b[z]; x++; } } int main () { cin>>n; for (i=0;i<n;i++) { cin>>a[i].x>>a[i].y; a[i].n=0; } merge(0,n-1); for (i=0;i<n;i++) c[a[i].n]++; for (i=0;i<n;i++) cout<<c[i]<<endl; return (0); }
树状数组解法 By JackDavid127
#include <stdio.h> const int MaxX=32001,MaxN=15000; int c[MaxX+1]={0},sum[MaxN+1]={0}; int n; int Lowbit(int x){ return x&(-x); } void Inc(int x){ while (x<=MaxX){ c[x]++; x+=Lowbit(x); } } int Sum(int x){ int ans=0; while (x>=1){ ans+=c[x]; x-=Lowbit(x); } return ans; } int main(){ int i,x,y; scanf("%d",&n); for (i=1;i<=n;i++){ scanf("%d%d",&x,&y); x++;y++; sum[Sum(x)]++; Inc(x); /* for (int j=1;j<=n;j++) printf("%d ",c[j]); printf("\n"); */ } for (i=0;i<n;i++) printf("%d\n",sum[i]); return 0; }
//改下上面这个程序的排版 #include <stdio.h> #define lowbit(x) (x&(-x)) const int MAXN = 15000, MAXX = 32001; int n,x,y,i; int l[MAXN+1]; int c[MAXX+1]; int main() { freopen("stars.in","r",stdin); freopen("stars.out","w",stdout); scanf("%d",&n); for (i=0; i<n; i++) { scanf("%d%d",&x,&y); (x++,++y); int level=0, tmp=x; while (tmp>0) {level+=c[tmp]; tmp-=lowbit(tmp);} while (x<=MAXX) {c[x]++; x+=lowbit(x);} l[level]++; } for (i=0; i<n; i++) printf("%d\n",l[i]); }
//头一次试图把sbt封装起来……写长了.不过还是很快的 program PP1028; const maxn=15000; type pnode=^node; node=record data:longint; size:longint; lch,rch:pnode; end; SizeBalancedTree=class(TObject) private root,null:pnode; procedure lrotate(var x:pnode); procedure rrotate(var x:pnode); procedure maintain(var t:pnode;const flag:boolean); procedure TreeInsert(var t:pnode;v:longint); function TreeDelete(var t:pnode;v:longint):longint; function TreeSelect(var t:pnode;k:longint):longint; function TreeFind(var t:pnode;v:longint):boolean; function TreeRank(var t:pnode;v:longint):longint; function TreeSucc(var t:pnode;v:longint):longint; function TreePred(var t:pnode;v:longint):longint; public constructor Create; procedure insert(v:longint); function delete(v:longint):longint; function select(k:longint):longint; function find(v:longint):boolean; function rank(v:longint):longint; function succ(v:longint):longint; function pred(v:longint):longint; end; var tree:SizeBalancedTree; x,y,ans:array[0..maxn]of longint; n,i:longint; constructor SizeBalancedTree.Create; begin new(null); null^.data:=0; null^.size:=0; null^.lch:=null; null^.rch:=null; root:=null; end; procedure SizeBalancedTree.lrotate(var x:pnode); var y:pnode; begin y:=x^.rch; x^.rch:=y^.lch; y^.lch:=x; y^.size:=x^.size; x^.size:=x^.lch^.size+x^.rch^.size+1; x:=y; end; procedure SizeBalancedTree.rrotate(var x:pnode); var y:pnode; begin y:=x^.lch; x^.lch:=y^.rch; y^.rch:=x; y^.size:=x^.size; x^.size:=x^.lch^.size+x^.rch^.size+1; x:=y; end; procedure SizeBalancedTree.maintain(var t:pnode;const flag:boolean); begin if t=null then exit; if not flag then if t^.lch^.lch^.size>t^.rch^.size then rrotate(t) else if t^.lch^.rch^.size>t^.rch^.size then begin lrotate(t^.lch); rrotate(t); end else exit else if t^.rch^.rch^.size>t^.lch^.size then lrotate(t) else if t^.rch^.lch^.size>t^.lch^.size then begin rrotate(t^.rch); lrotate(t); end else exit; maintain(t^.lch,false); maintain(t^.rch,true); maintain(t,false); maintain(t,true); end; procedure SizeBalancedTree.TreeInsert(var t:pnode;v:longint); begin if t=null then begin new(t); t^.data:=v; t^.size:=1; t^.lch:=null; t^.rch:=null; end else begin inc(t^.size); if v<t^.data then TreeInsert(t^.lch,v) else TreeInsert(t^.rch,v); maintain(t,v>=t^.data); end; end; function SizeBalancedTree.TreeDelete(var t:pnode;v:longint):longint; var tmp:pnode; begin if t=null then exit; dec(t^.size); if(v=t^.data)or((v<t^.data)and(t^.lch=null))or((v>t^.data)and(t^.rch=null)) then begin TreeDelete:=t^.data; if(t^.lch=null)or(t^.rch=null) then begin if t^.lch=null then begin tmp:=t; t:=tmp^.rch; dispose(tmp); end; if t^.rch=null then begin tmp:=t; t:=tmp^.lch; dispose(tmp); end; end else t^.data:=TreeDelete(t^.lch,t^.data+1); end else if v<t^.data then TreeDelete:=TreeDelete(t^.lch,v) else TreeDelete:=TreeDelete(t^.rch,v); end; function SizeBalancedTree.TreeSelect(var t:pnode;k:longint):longint; begin if k=t^.lch^.size+1 then begin TreeSelect:=t^.data; exit; end; if k<=t^.lch^.size then TreeSelect:=TreeSelect(t^.lch,k) else TreeSelect:=TreeSelect(t^.rch,k-1-t^.lch^.size); end; function SizeBalancedTree.TreeFind(var t:pnode;v:longint):boolean; begin if t=null then begin TreeFind:=false; exit; end; if v<t^.data then TreeFind:=TreeFind(t^.lch,v) else TreeFind:=(v=t^.data)or TreeFind(t^.rch,v); end; function SizeBalancedTree.TreeRank(var t:pnode;v:longint):longint; begin if t=null then begin TreeRank:=1; exit; end; if v<t^.data then TreeRank:=TreeRank(t^.lch,v) else TreeRank:=t^.lch^.size+1+TreeRank(t^.rch,v); end; function SizeBalancedTree.TreeSucc(var t:pnode;v:longint):longint; var tmp:longint; begin if t=null then begin TreeSucc:=v; exit; end; if v>=t^.data then TreeSucc:=TreeSucc(t^.rch,v) else begin tmp:=TreeSucc(t^.lch,v); if tmp=v then tmp:=t^.data; TreeSucc:=tmp; end; end; function SizeBalancedTree.TreePred(var t:pnode;v:longint):longint; var tmp:longint; begin if t=null then begin TreePred:=v; exit; end; if v<=t^.data then TreePred:=TreePred(t^.lch,v) else begin tmp:=TreePred(t^.rch,v); if tmp=v then tmp:=t^.data; TreePred:=tmp; end; end; procedure SizeBalancedTree.insert(v:longint); begin TreeInsert(root,v); end; function SizeBalancedTree.delete(v:longint):longint; begin delete:=TreeDelete(root,v); end; function SizeBalancedTree.select(k:longint):longint; begin select:=TreeSelect(root,k); end; function SizeBalancedTree.find(v:longint):boolean; begin find:=TreeFind(root,v); end; function SizeBalancedTree.rank(v:longint):longint; begin rank:=TreeRank(root,v); end; function SizeBalancedTree.succ(v:longint):longint; begin succ:=TreeSucc(root,v); end; function SizeBalancedTree.pred(v:longint):longint; begin pred:=TreePred(root,v); end; procedure swap(var a,b:longint); var c:longint; begin c:=a; a:=b; b:=c; end; procedure qsort(m,n:longint); var i,j:longint; begin if(m+1=n)and((x[m]>x[n])or((x[m]=x[n])and(y[m]>y[n]))) then begin swap(x[m],x[n]); swap(y[m],y[n]); exit; end; if m<n then begin i:=m-1; j:=random(n-m)+m; swap(x[j],x[n]); swap(y[j],y[n]); for j:=m to n-1 do if(x[j]<x[n])or(((x[j]=x[n])and(y[j]<y[n]))) then begin inc(i); swap(x[i],x[j]); swap(y[i],y[j]); end; swap(x[i+1],x[n]); swap(y[i+1],y[n]); qsort(m,i); qsort(i+2,n); end; end; begin assign(input,'in.txt'); assign(output,'out.txt'); reset(input); rewrite(output); readln(n); for i:=1 to n do readln(x[i],y[i]); randomize; qsort(1,n); tree:=SizeBalancedTree.Create; for i:=1 to n do begin ans[i]:=tree.rank(y[i]); tree.insert(y[i]); end; fillchar(x,sizeof(x),0); for i:=1 to n do inc(x[ans[i]]); for i:=1 to n do writeln(x[i]); close(input); close(output); end.
