题目链接 Rooter's Song

题意  有n个舞者站在x轴上或y轴上，每个人有不同的出发时间。x轴上的舞者垂直x轴正方向移动，y轴上的舞者垂直y轴正方向移动。

当x轴的舞者和y轴的舞者相遇时，他们会互换运动轨迹。求每个舞者的最后位置。

把所有会发生碰撞的舞者塞到一起，按照坐标大小升序排序。

对于某个在x轴上的舞者， 计算他右边的舞者个数，和他上面的舞者个数（即y轴会和他碰撞的所有舞者个数）

对于某个在y轴上的舞者， 计算他上面的舞者个数，和他右边的舞者个数（即x轴会和他碰撞的所有舞者个数）

然后根据这些信息计算出每个舞者的碰撞次数，再求出每个舞者最后的位置。

时间复杂度$O(Mlogn)$    $(M = max(w, h))$

#include

using namespace std;

#define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i)

typedef long long LL;

const int N = 4e5 + 10;
const int d = 1e5;

struct node{
int pos, id;
friend bool operator < (const node &a, const node &b){
return a.pos < b.pos;
}
};

int n, w, h, op, p, t, mx, s;
vector X[N], Y[N];
int flag[N], ans[N], b[N], c[N];

int main(){

scanf("%d%d%d", &n, &w, &h);  
mx = 0;

rep(i, 1, n){  
    scanf("%d%d%d", &op, &p, &t);  
    b\[i\] = op, c\[i\] = p;  
    if (op == 1) X\[p - t + d\].push\_back({p, i});  
    else Y\[p - t + d\].push\_back({p, i});  
    mx = max(mx, p - t + d);  
}

rep(i, 0, mx){  
    sort(X\[i\].begin(), X\[i\].end());  
    sort(Y\[i\].begin(), Y\[i\].end());  
}

rep(i, 0, mx){  
    s = (int)X\[i\].size();  
    t = (int)Y\[i\].size();

    if (s == 0 || t == 0) continue;

    rep(j, 0, s - 1){  
        int nx  = s - j - 1, ny = t;  
        int num;  
        if (nx < ny) num = 2 \* nx + 1;  
        else num = ny \* 2;  
        if (num & 1) flag\[X\[i\]\[j\].id\] = 2; else flag\[X\[i\]\[j\].id\] = 1;  
        if (flag\[X\[i\]\[j\].id\] == 1) ans\[X\[i\]\[j\].id\] = X\[i\]\[j + num / 2\].pos;  
        else ans\[X\[i\]\[j\].id\] = Y\[i\]\[num / 2\].pos;  
    }

    rep(j, 0, t - 1){  
        int nx  = s, ny = t - j - 1;  
        int num;  
        if (ny < nx) num = 2 \* ny + 1;  
        else num = nx \* 2;  
        if (num & 1) flag\[Y\[i\]\[j\].id\] = 1; else flag\[Y\[i\]\[j\].id\] = 2;  
        if (flag\[Y\[i\]\[j\].id\] == 2) ans\[Y\[i\]\[j\].id\] = Y\[i\]\[j + num / 2\].pos;  
        else ans\[Y\[i\]\[j\].id\] = X\[i\]\[num / 2\].pos;

    }  
}

rep(i, 1, n) if (!flag\[i\]){ flag\[i\] = b\[i\];  ans\[i\] = c\[i\];}  
rep(i, 1, n) if (flag\[i\] == 1) printf("%d %d\\n", ans\[i\], h);  
        else printf("%d %d\\n", w, ans\[i\]);  
return 0;  

}