HEBYBo - Online C++0x Compiler & Debugging Tool

/*
    BÀI TOÁN: Đếm giao điểm của N đoạn ngang và M đoạn dọc.
    KỸ THUẬT: Sweep Line (Quét) + Fenwick Tree (BIT) + Nén toạ độ.
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// --- PHẦN 1: CẤU TRÚC DỮ LIỆU & HẰNG SỐ ---

// Định nghĩa thứ tự ưu tiên xử lý khi cùng toạ độ X
// 1. OPEN:  Mở đoạn ngang ra (để đoạn dọc sau đó có thể cắt trúng)
// 2. QUERY: Tính toán giao điểm với đoạn dọc
// 3. CLOSE: Đóng đoạn ngang lại (hết tác dụng)
const int OPEN = 1;
const int QUERY = 2;
const int CLOSE = 3;

struct Event {
    int x, type;        // Toạ độ X quét qua, loại sự kiện
    int y_low, y_high;  // Phạm vi Y (nếu là ngang thì low=high)

    // Hàm so sánh để sort: X tăng dần -> Type tăng dần
    bool operator<(const Event& other) const {
        if (x != other.x) return x < other.x;
        return type < other.type;
    }
};

// --- PHẦN 2: FENWICK TREE (Cây BIT) ---
// Dùng để đếm số đoạn ngang đang hoạt động trong khoảng Y

vector<int> bit;
int max_val; // Kích thước tối đa của trục Y sau khi nén

// Cập nhật: Thêm val vào vị trí idx (val là +1 hoặc -1)
void update(int idx, int val) {
    for (; idx <= max_val; idx += idx & -idx) {
        bit[idx] += val;
    }
}

// Lấy tổng: Đếm số lượng từ 1 đến idx
int get(int idx) {
    int sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
        sum += bit[idx];
    }
    return sum;
}

// --- PHẦN 3: NÉN TOẠ ĐỘ (Coordinate Compression) ---
// Giúp xử lý khi toạ độ Y lên tới 1 tỷ, đưa về phạm vi [1...N]

void nen_toa_do(vector<Event>& events) {
    // 1. Thu thập tất cả các giá trị Y xuất hiện
    vector<int> y_values;
    for (auto& e : events) {
        y_values.push_back(e.y_low);
        y_values.push_back(e.y_high);
    }

    // 2. Sắp xếp và lọc trùng
    sort(y_values.begin(), y_values.end());
    y_values.resize(unique(y_values.begin(), y_values.end()) - y_values.begin());

    // 3. Thay thế Y cũ bằng số thứ tự (Rank)
    for (auto& e : events) {
        // Tìm vị trí của y trong mảng đã sort (+1 để chỉ số bắt đầu từ 1 cho BIT)
        e.y_low = lower_bound(y_values.begin(), y_values.end(), e.y_low) - y_values.begin() + 1;
        e.y_high = lower_bound(y_values.begin(), y_values.end(), e.y_high) - y_values.begin() + 1;
    }

    // Cập nhật kích thước cho BIT
    max_val = y_values.size();
    bit.assign(max_val + 1, 0); // Khởi tạo BIT toàn số 0
}

// --- PHẦN 4: CHƯƠNG TRÌNH CHÍNH (MAIN) ---

int main() {
    // Tăng tốc độ nhập xuất
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int n; // Số đoạn ngang
    if (!(cin >> n)) return 0;

    vector<Event> events;

    // Nhập N đoạn ngang: y cố định, x từ x1 -> x2
    for (int i = 0; i < n; i++) {
        int x1, x2, y;
        cin >> x1 >> x2 >> y;
        if (x1 > x2) swap(x1, x2); // Đảm bảo x1 < x2

        // Tạo 2 sự kiện: Bắt đầu và Kết thúc
        events.push_back({x1, OPEN, y, y});
        events.push_back({x2, CLOSE, y, y});
    }

    int m; // Số đoạn dọc
    cin >> m;
    // Nhập M đoạn dọc: x cố định, y từ y1 -> y2
    for (int i = 0; i < m; i++) {
        int x, y1, y2;
        cin >> x >> y1 >> y2;
        if (y1 > y2) swap(y1, y2); // Đảm bảo y1 < y2

        // Tạo 1 sự kiện: Truy vấn
        events.push_back({x, QUERY, y1, y2});
    }

    // BƯỚC 1: Nén toạ độ Y (để dùng được BIT)
    nen_toa_do(events);

    // BƯỚC 2: Sắp xếp sự kiện theo trục X (Sweep Line)
    sort(events.begin(), events.end());

    // BƯỚC 3: Quét và xử lý
    long long ans = 0; // Biến đếm kết quả (dùng long long vì giao điểm có thể rất nhiều)

    for (const auto& e : events) {
        if (e.type == OPEN) {
            // Có thêm 1 đoạn ngang ở độ cao y -> Đánh dấu vào BIT
            update(e.y_low, 1);
        }
        else if (e.type == CLOSE) {
            // Đoạn ngang ở độ cao y kết thúc -> Xoá khỏi BIT
            update(e.y_low, -1);
        }
        else { // QUERY
            // Đoạn dọc quét từ y_low đến y_high
            // Tính xem trong khoảng đó có bao nhiêu đoạn ngang đang active
            ans += get(e.y_high) - get(e.y_low - 1);
        }
    }

    cout << ans << endl;

    return 0;
}