5480_전함

계속 전함을 segment tree에 넣을 생각만 하고 있어서, 전함을 w 가 큰 거 부터 넣는다.

끝나는 지점에 w를 넣고 시작지점-1 에 -w를 넣어서 레이저를 x부터 N까지 합을 구해볼까 등등..

근데 이것저것 다 고민해도 삭제가 가장 걸림돌이 되었다.

그러다가 레이저는 기준점이 하나잖아? 라는 생각에서 레이저를 segment tree에 넣으면 모든게 챡챡 풀린다는 것을 깨달았다.

1. 레이저가 x점기준, y점기준으로 들어오니까 각각을 나눠서 세그먼트트리를 2개를 만든다.

2. 세그먼트 트리는 좌표를 (좌표압축해야함) 표현하고 있고 안에 들어있는 값은 그 좌표를 뚫는 레이저의 가장 작은 인덱스이다. (가장 먼저나오니까)

3. 각각의 전함의 x1 - x2 를 x좌표 세그트리에 넣어서 그 사이를 뚫는 레이저의 가장 작은 인덱스를 찾는다.

4. y좌표도 마찬가지로 진행한다.

5. 둘 중에 더 작은 값이 그 전함을 파괴시키는 레이저의 인덱스이다. 그 레이저의 w maximum값을 갱신해준다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string.h>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
#define INF 1000000000
 
struct P {
    int x, y, xx, yy, w;
};
 
int N, K, L, x, y, xx, yy, w;
vector<P> point;
vector<pair<int, int>> lazer;
vector<int> Y, X, W;
int segy[4 * 100005], segx[4*100005];
 
 
void updateX(int node, int x, int y, int l, int r, int val) {
    if (x > r || y < l) return;
    if (l <= x && y <= r) {
        if (segx[node] == 0) segx[node] = val;
        return;
    }
 
    int mid = (x + y) >> 1;
    updateX(node * 2, x, mid, l, r, val);
    updateX(node * 2 + 1, mid + 1, y, l, r, val);
 
    segx[node] = min((segx[node * 2] ? segx[node*2] : INF), (segx[node * 2 + 1] ? segx[node*2+1] : INF));
}
 
int queryX(int node, int x, int y, int l, int r) {
    if (x > r || y < l) return INF;
    if (l <= x && y <= r) return segx[node] ? segx[node] : INF;
    int mid = (x + y) >> 1;
    return min(queryX(node * 2, x, mid, l, r), queryX(node * 2 + 1, mid + 1, y, l, r));
}
 
void updateY(int node, int x, int y, int l, int r, int val) {
    if (x > r || y < l) return;
    if (l <= x && y <= r) {
        if (segy[node] == 0) segy[node] = val;
        return;
    }
 
    int mid = (x + y) >> 1;
    updateY(node * 2, x, mid, l, r, val);
    updateY(node * 2 + 1, mid + 1, y, l, r, val);
 
    segy[node] = min((segy[node * 2] ? segy[node * 2] : INF), (segy[node * 2 + 1] ? segy[node * 2 + 1] : INF));
}
 
int queryY(int node, int x, int y, int l, int r) {
    if (x > r || y < l) return INF;
    if (l <= x&& y <= r) return segy[node] ? segy[node] : INF;
    int mid = (x + y) >> 1;
    return min(queryY(node * 2, x, mid, l, r), queryY(node * 2 + 1, mid + 1, y, l, r));
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        point.clear(); lazer.clear();
        X.clear(); Y.clear(); W.clear();
        memset(segy, 0, sizeof(segy));
        memset(segx, 0, sizeof(segx));
 
        cin >> N >> K >> L;
        W.resize(L + 1, 0);
 
        for (int i = 0; i < K; ++i) {
            cin >> x >> y >> xx >> yy >> w;
            if (y > yy) swap(y, yy);
            if (x > xx) swap(x, xx);
            point.push_back({ x, y, xx, yy, w });
        }
 
        for (int i = 0; i < L; ++i) {
            cin >> x >> y;
            lazer.push_back({ x, y });
            if (y == 0) { //x축과 나란하게 = y점기준
                Y.push_back(x);
            }
            else { //y축과 나란하게 = x점기준
                X.push_back(x);
            }
        }
 
        Y.push_back(0); X.push_back(0);
        sort(Y.begin(), Y.end()); sort(X.begin(), X.end());
        Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
        X.resize(unique(X.begin(), X.end()) - X.begin());
 
        int Ysz = Y.size(), Xsz = X.size();
        
        for (int i = 0; i < L; ++i) {
            auto l = lazer[i];
            if (l.second == 0) {
                int tmp = lower_bound(Y.begin(), Y.end(), l.first) - Y.begin();
                updateY(1, 0, Ysz, tmp, tmp, i+1);
            }
            else {
                int tmp = lower_bound(X.begin(), X.end(), l.first) - X.begin();
                updateX(1, 0, Xsz, tmp, tmp, i+1);
            }
        }
 
        for (auto batt : point) {
            x = lower_bound(X.begin(), X.end(), batt.x) - X.begin();
            xx = lower_bound(X.begin(), X.end(), batt.xx) - X.begin();
            if (xx != Xsz && batt.xx < X[xx]) xx--;
            int getx = queryX(1, 0, Xsz, x, xx);
 
            y = lower_bound(Y.begin(), Y.end(), batt.y) - Y.begin();
            yy = lower_bound(Y.begin(), Y.end(), batt.yy) - Y.begin();
            if (yy != Ysz && batt.yy < Y[yy]) yy--;
            int gety = queryY(1, 0, Ysz, y, yy);
 
            int mylazer = min(getx, gety);
            if (mylazer == INF) continue;
            W[mylazer] = max(W[mylazer], batt.w);
        }
 
        for (int i = 1; i <= L; ++i) {
            cout << W[i] << '\n';
        }
    }
 
}