BZOJ 3888 Usaco 2015 Jan Stampede 模擬

題目大意

給出一些奶牛，一個人在原點觀察，牛和牛之間又互相遮擋的關系，給出每頭牛的運行方式和位置，問這個人最終會看到多少頭牛。

思路

知道了運行方式，我們就知道這頭牛在什麼時間段會遮擋住人的視線，然後從高到低弄個東西維護一下覆蓋什麼的，這個題就變成了POJ的Mayor’s posters。
注意下時間點和時間段的區別就行了。

CODE

#define _CRT_SECURE_NO_WARNINGS

#include 
#include 
#include 
#include 
#define MAX 100010
using namespace std;
#define LEFT (pos << 1)
#define RIGHT (pos << 1|1)

struct 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 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;
}