2472_체인점

모든 q에 대해 a > x && b > y && c > z인 아이가 하나라도 있는지 확인하는 걸 어떻게 빠르게 할수있나 싶어서 

한참 고민하다가 질문검색에서 솔루션을 봤는데

세그먼트 트리를 사용하는 새로운 방식(?)을 안 느낌이었다.

진짜 다들 똑똑한듯...

우리가 비교해야하는 변수가 3개뿐이어서 가능한 방법인 것 같다.

1. 일단 A와의 거리를 기준으로 정렬해준다. 이러면 앞에 나오는 A가 자신보다 작거나 같다는 것은 확실해진다.

2. B와의 거리를 좌표압축을 하여 세그먼트 트리상의 인덱스로 넘긴다.

3. C와의 거리는 세그먼트 트리에 저장되는 값이 된다. 

4. 이 때 거리가 0 ~ 자신의 거리 - 1 인 인덱스에 있는 애들 중에 MIN값을 추출해왔을 때

   자신의 C보다 작다면 자신은 매장을 설치할 수 없는 구역이 된다.

   1번을 통해 A가 작고, 2번을 통해 B가 자신보다 작은 애들 중에서 3번을 통해 자기보다 C까지 작은 애가 존재한다는 뜻이기 때문이다.

A를 정렬했을때, 만약 (1, 2, 3)의 거리를 갖는 애가 먼저 나오고 (1, 4, 5)란 거리를 갖는 애가 뒤에 나오게 되면

A와의 거리가 같아서 매장 설치가 가능하지만 저 과정에선 불가능하다고 나오므로

A를 정렬할때 A값이 같다면 B값이 더 큰 게 앞으로 나오게 해주면 된다!

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <string.h>
#include <string>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
#define INF 2000000000
 
int N, M, T;
int u, v, w, q, apt[3];
vector<vector<pair<int, int>>> adj;
ll dist[3][100001], visit[100001];
ll seg[150001 * 4];
vector<ll> Bdist;
vector<int> sortedByA;
bool can[100001];
 
//질문검색 참고
//A기준으로 정렬, B까지의 거리는 INDEX, C까지의 거리는 원소값
 
void update(int node, int x, int y, int l, int r, ll val) {
    if (x > r || y < l) return;
    if (l <= x && y <= r) {
        if (seg[node] == 0) seg[node] = val;
        else seg[node] = min(seg[node], val);
        return;
    }
 
    int mid = (x + y) >> 1;
    update(node * 2, x, mid, l, r, val);
    update(node * 2 + 1, mid + 1, y, l, r, val);
    seg[node] = min((seg[node * 2] ? seg[node * 2] : INF), (seg[node * 2 + 1] ? seg[node * 2 + 1] : INF));
}
 
ll query(int node, int x, int y, int l, int r) {
    if (x > r || y < l) return INF;
    if (l <= x && y <= r) return (seg[node] ? seg[node] : INF);
    int mid = (x + y) >> 1;
    return min(query(node * 2, x, mid, l, r), query(node * 2 + 1, mid + 1, y, l, r));
}
 
int getNewDist(int idx) {
    return lower_bound(Bdist.begin(), Bdist.end(), dist[1][sortedByA[idx]]) - Bdist.begin();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    cin >> N;
    cin >> apt[0] >> apt[1] >> apt[2];
    cin >> M;
    adj.resize(N + 1);
    
 
    for (int i = 0; i < M; ++i) {
        cin >> u >> v >> w;
        adj[u].push_back({ v, w });
        adj[v].push_back({ u, w });
    }
 
    //다익스트라 
    for (int i = 0; i < 3; ++i) {
        priority_queue<pair<ll, int>> pq;
        fill(dist[i], dist[i] + N + 1, INF);
        fill(visit, visit + N + 1, 0);
        pq.push({ 0, apt[i] });
        dist[i][apt[i]] = 0;
        int cur = 0;
        while (!pq.empty()) {
            do {
                cur = pq.top().second;
                pq.pop();
            } while (!pq.empty() && visit[cur]);
            if (visit[cur]) break; visit[cur] = 1;
 
            for (auto& next : adj[cur]) {
                if (dist[i][next.first] > dist[i][cur] + next.second) {
                    dist[i][next.first] = dist[i][cur] + next.second;
                    pq.push({ -dist[i][next.first], next.first });
                }
            }
        }
    }
 
    for (int i = 1; i <= N; ++i) {
        Bdist.push_back(dist[1][i]);
        sortedByA.push_back(i);
    }
 
    sort(sortedByA.begin(), sortedByA.end(), [&](int a, int b) {
        if (dist[0][a] == dist[0][b]) return dist[1][a] > dist[1][b]; 
        //A값이 같고 B, C가 자기 보다 작은 애가 앞에 나온다면 CANNOT으로 처리가 되니까 B값은 큰거 기준으로 정렬
        return dist[0][a] < dist[0][b];
    });
    
    //좌표압축
    sort(Bdist.begin(), Bdist.end());
    Bdist.resize(unique(Bdist.begin(), Bdist.end()) - Bdist.begin());
 
    for (int i = 0; i < N; ++i) {
        int A = sortedByA[i];
        int curB = getNewDist(i);
        ll C = query(1, 0, Bdist.size(), 0, curB-1);
        update(1, 0, Bdist.size(), curB, curB, dist[2][A] + 1); 
        //0은 INF가 되어야하므로 +1해서 업데이트 (거리가 0인애가 있을 수 있으므로)
        if (C < dist[2][A] + 1) continue; //자기 c거리랑 비교
        can[A] = 1;
    }
 
    cin >> T;
 
    for (int i = 0; i < T; ++i) {
        cin >> q;
        if (can[q]) cout << "YES\n";
        else cout << "NO\n";
    }
}