题目就不多说了..原本是找些线段树的题目来练练手.
结果这题..看起来好水..可以用树状数组切掉..
看到这么水的题目不忍心放弃..就开始随便写..
结果交上去TLE..觉得非常新奇..找了段线段树的程序扔上去AC了.(没天理啊..)
仔细观察题目.才发现..当坐标为0的时候..我可怜的树状数组啊..就开始无限的循环下去了.
还好..赶紧解决..可以把所有坐标加个1..也可以对于0的情况特判.
以下为我AC的程序:
#include <stdio.h> #include <memory.h> int n,a[15001],b[15001],ans[15001],tree[60000],t; int Query(int a) { if (!a) return tree[0]; int ans = 0; while (a) { ans += tree[a]; a -= (a & (-a)); } return ans + tree[0]; } void update(int a) { if (!a) { ++ tree[0]; return; } while (a <= 32768) { ++ tree[a]; a += (a & (-a)); } } int main() { freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1; i<=n; ++i) scanf("%d %d",&a[i],&b[i]); for (int i=1; i<=n; ++i) { update(a[i]); t = Query(a[i]); ++ ans[t]; } for (int i=1; i<=n; ++i) printf("%d\n",ans[i]); }
看完了要说点啥么？