初学树状数组

解题思路:树状数组

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N=15005,M=32005;

int a[N],b[M],n;

int lowbit(int i){return (-i)&i;}

void add(int i,int z)

{

for(;i<=M;i+=lowbit(i))

b[i]+=z;

}

int sum(int i)

{

int s=0;

for(;i>0;i-=lowbit(i))

s+=b[i];

return s;

}

int main()

{

int x,y;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>x>>y;//y其实作用不大

x++;//确保x>0，因为树状数组是从一开始

a[sum(x)]++;//因为y是升序，只要算前面横坐标小于等于当前x的星星的数目就可以知道级数（并且星星是没有重叠的），就是sum（x）

add(x,1);//add放后面防止把当前的星星加上

}

for(int i=0;i<n;i++)

cout<<a[i]<<endl;

return 0;

}