学步园

精巧的树状数组：

#include<algorithm><br /> #include<iostream><br /> #include<cstdio><br /> using namespace std;<br /> int c[32001];<br /> int out[15001];<br /> int N=32001;<br /> int lowbit(int x)<br /> {<br /> return x&(x^(x-1));<br /> }<br /> void Modify(int i,int x)<br /> {<br /> while(i<=N)<br /> {<br /> c[i]+=x;<br /> i+=lowbit(i);<br /> }<br /> }<br /> int sum(int n)<br /> {<br /> int sum=0;<br /> while(n>0)<br /> {<br /> sum+=c[n];<br /> n-=lowbit(n);<br /> }<br /> return sum;<br /> }<br /> int main()<br /> {<br /> int n;<br /> scanf("%d",&n);<br /> int i,x,y;<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%d%d",&x,&y);<br /> x+=1;<br /> Modify(x,1);<br /> out[sum(x)-1]++;<br /> }<br /> for(i=0;i<n;i++)<br /> printf("%d/n",out[i]);<br /> return 0;<br /> }