链接：
?id=2352
题目大意：
在坐标上有n个星星，如果某个星星坐标为(x, y), 它的左下位置为：(x0,y0)，x0<=x 且y0<=y。如果左下位置有a个星星，就表示这个星星属于level x
按照y递增，如果y相同则x递增的顺序给出n个星星，求出所有level水平的数量。
思路：
由于输入的顺序，对于第i颗星星，它的等级是之前输入的星星中，横坐标x小于等于i星横坐标的那些星星的总数量（前面的y一定比后面的y小）。
所以是查询+更新操作
查询0~x 坐标的所有星星的和，再把x坐标的星星数加1
正好符合树状数组的用法，要注意，树状数组是对数列从坐标1开始的一列数，，所以输入的时候把x++，因为树状数组用位运算实现，所以必须从1开始，否则会在代码中add操作中出现死循环
//312K141MS#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int MAXN = 32005;const int N = 15005;#define lowbit(x) (x&(-x))int tree[MAXN];int ans[N];int sum(int i){int s=0;while(i>0){s+=tree[i];i-=lowbit(i);}return s;}void add(int i){while(i<=MAXN-1){ //防止正好算出了MAXN，因为tree的下标最大也只有MAXN-1tree[i]++;i+=lowbit(i); //i>0 否则死循环}}int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){int x,y;scanf("%d%d",&x,&y);ans[sum(++x)]++;add(x);}for(int i=0;i<n;i++)printf("%d\n",ans[i]);return 0;}当然线段树也可以完成更新和查询操纵，毕竟是看家本领…只不过时间和空间上的复杂度比树状数组要大常系数
//984K235MS#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define LL(x) (x<<1)#define RR(x) (x<<1|1)#define MID(a,b) (a+((b-a)>>1) )#define M 32222struct node{int l,r;int sum;int mid(){return MID(l,r);}};struct Segtree{node tree[M<<2];void build(int l,int r,int rt){tree[rt].l=l,tree[rt].r=r;if(l==r) return ;int m=tree[rt].mid();build(l,m,LL(rt));build(m+1,r,RR(rt));}void up(int rt){tree[rt].sum=tree[LL(rt)].sum+tree[RR(rt)].sum;}void update(int rt,int pos){if(tree[rt].l==tree[rt].r){tree[rt].sum++;return;}int m=tree[rt].mid();if(pos<=m) update(LL(rt),pos);else update(RR(rt),pos);up(rt);}int query(int st,int ed,int rt){if(st>tree[rt].r||ed<tree[rt].l) return 0;if(st<=tree[rt].l&&tree[rt].r<=ed){return tree[rt].sum;}return query(st,ed,LL(rt))+query(st,ed,RR(rt));}}seg;int main() {int n;int ans[20000];seg.build(0,32000,1);scanf("%d",&n);memset(ans,0,sizeof(ans));for(int i=0; i<n; i++) {int x,y;scanf("%d%d",&x,&y);ans[seg.query(0,x,1)]++;seg.update(1,x);}for(int i=0; i<n; i++)printf("%d\n",ans[i]);return 0;}
知已知彼，百战百胜。
