题目大意
给出一些奶牛，一个人在原点观察，牛和牛之间又互相遮挡的关系，给出每头牛的运行方式和位置，问这个人最终会看到多少头牛。
思路
知道了运行方式，我们就知道这头牛在什么时间段会遮挡住人的视线，，然后从高到低弄个东西维护一下覆盖什么的，这个题就变成了POJ的Mayor’s posters。 注意下时间点和时间段的区别就行了。
CODE;Cow{int x,y,c;int st,ed;bool operator <(const Cow &a)const {return y > a.y;}void Read() {scanf(“%d%d%d”, &x, &y, &c);x *= -1;st = c * (x – 1);ed = st + c;}}src[MAX];int cows;pair<int,int *> xx[MAX << 1];int cnt,t;int tree[MAX << 4];inline void PushDown(int pos){if(tree[pos]) {tree[LEFT] = tree[pos];tree[RIGHT] = tree[pos];tree[pos] = 0;}}void Modify(int l, int r, int x, int y, int c, int pos){if(l == x && y == r) {tree[pos] = c;return ;}PushDown(pos);int mid = (l + r) >> 1;if(y <= mid) Modify(l, mid, x, y, c, LEFT);else if(x > mid) Modify(mid + 1, r, x, y, c, RIGHT);else {Modify(l, mid, x, mid, c, LEFT);Modify(mid + 1, r, mid + 1, y, c, RIGHT);}}inline int Ask(int l, int r, int x, int pos){if(l == r) return tree[pos];PushDown(pos);int mid = (l + r) >> 1;if(x <= mid) return Ask(l, mid, x, LEFT);return Ask(mid + 1, r, x, RIGHT);}bool v[MAX];int main(){cin >> cows;for(int i = 1; i <= cows; ++i)src[i].Read();sort(src + 1, src + cows + 1);for(int i = 1; i <= cows; ++i) {xx[++cnt] = make_pair(src[i].st, &src[i].st);xx[++cnt] = make_pair(src[i].ed, &src[i].ed);}sort(xx + 1, xx + cnt + 1);for(int i = 1; i <= cnt; ++i) {if(i == 1 || xx[i].first != xx[i – 1].first)t += 2;*xx[i].second = t;}for(int i = 1; i <= cows; ++i)Modify(1, t, src[i].st, src[i].ed , i, 1);for(int i = 1; i <= t; ++i)v[Ask(1, t, i, 1)] = true;int ans = 0;for(int i = 1; i <= cows; ++i)ans += v[i];cout << ans << endl;return 0;}
一个人，一条路，人在途中，心随景动，
