abc309f <线段树 + 离散化 + 双指针>

标签：begin temp abc309f int tr 维度 向量

F - Box in Box

// https://atcoder.jp/contests/abc309/tasks/abc309_f
// <线段树 + 离散化 + 双指针> [unique + lower_bound + erase + lambda + vector]
// 总体思路: 将每个三元组记录为如 a[3] 的3维向量, 依次考虑每个向量, 检查是否存在一个向量完全比它'小'
// 将向量按照第一维度 a[0] 从小到大排序, 则当考虑第i个向量时, 可能比它'小'的仅可能是前i-1个向量; 如此处理第一维度;
// 至于第二三维度, 使用线段树维护前i-1个向量的情况,
// 其中线段树下标u为第二维度, 此维度需要先进行离散化, 
// tr[u].val 为前i-1个向量中, 第二维度为u(离散化后索引)的向量, 第三维度的最小值为 val;
// 如此, 当前第i个向量为a, 其第二维度离散化后为t1=find(a[1]), 则前i-1个向量中, 第二维度比a小的向量在线段树中下标为 1~t1-1, 
// 因此可查询query(1, 1, t1-1), 得到前i-1个向量(由于事先排序, 因此满足第一维度小于a)中, 第二维度小于t1(向量a离散化后的索引), 的第三维度的最小值,
// 如果此查询值小于a的第三维度a[2], 则Yes;
// 当完成第一位度相同若干向量的检查后, 将这些向量更新到线段树中... 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;
const int N = 2e5 + 10, INF = 0x3f3f3f3f;

struct Node
{
    int l, r, val;
}tr[N*3*4];  // 1. 注意 *3是每个向量有3个维度, *4是线段数要求

void push_up(int u)
{
    tr[u].val = min(tr[u<<1].val, tr[u<<1|1].val);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        // tr[u].val = INF;
        // tr[u].l = tr[u].r = l;
        tr[u] = {l, r, INF};  // 2. 习惯这种结构体赋值方式, 更简洁(注意顺序)
    }
    else
    {
        tr[u].l = l; tr[u].r = r;
        int mid = l + r >> 1;
        build(u<<1, l, mid), build(u<<1|1, mid+1, r);
        push_up(u);
    }
}

int query(int u, int l, int r)
{
    // 3. 将线段数写成结构体的形式而非数组似乎更简洁
    if (l > tr[u].r || r < tr[u].l) return INF;  // 4. 将越界写在前面, 这样下面就不需要讨论范围了
    if (l <= tr[u].l && r >= tr[u].r) return tr[u].val;
    int mid = tr[u].l + tr[u].r >> 1;
    int res = min(query(u<<1, l, r), query(u<<1|1, l, r));
    return res;
}

void modify(int u, int x, int val)
{
    if (tr[u].l > x || tr[u].r < x) return;  // 将越界写在前面, 这样下面就不需要讨论范围了 (if x <= mid ...)
    if (tr[u].l == tr[u].r)
    {
        tr[u].val = min(tr[u].val, val);
        return;
    }
    modify(u<<1, x, val); modify(u<<1|1, x, val);
    push_up(u);
}

void solv()
{
    int n;
    cin >> n;
    vector<vector<int>> a(n+1, vector<int>(3));  // 5. 习惯这种写法, 确实好用
    vector<int> temp;
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 0; j < 3; j ++)
        {
            cin >> a[i][j];
            temp.push_back(a[i][j]);
        }
        sort(a[i].begin(), a[i].end());  // 6. 向量3个维度升序排序
    }
    temp.push_back(0);  // 7. 前面补0, 使得离散化后下标从1开始, 方便线段树的下标

    // 8. 离散化常用操作, 排序+去重+二分查找
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    auto find = [&] (int x) -> int {
        return lower_bound(temp.begin(), temp.end(), x) - temp.begin();  // 9. lambda写法, 注意末尾分号
    };

    sort(a.begin(), a.end(), [&] (vector<int> &a, vector<int> &b) {  // 10. 简洁的sort ~
		return a[0] < b[0];
    });

    build(1, 1, temp.size()-1);

    for (int i = 1; i <= n; i ++)  // 按向量第一维度, 从小到大考虑
    {
        int j = i;
        while (j <= n && a[i][0] == a[j][0])  // j 指针遍历所有第一维相同的向量
        {
            int t1 = find(a[j][1]);  // t1 获得离散化后的索引
            if (query(1, 1, t1-1) < a[j][2])  // 如果前i-1个第一维满足要求的向量中, 存在第二三维度也满足要求的向量
            {
                cout << "Yes" << endl;
                return;
            }
            j ++;
        }
        for (int k = i; k < j; k ++)  // 将本轮遍历到的第一维度相同的向量更新到线段树
        {
            int t1 = find(a[k][1]);
            modify(1, t1, a[k][2]);
        }
        i = j-1;
    }
    cout << "No" << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签：begin,temp,abc309f,int,tr,维度,向量
From： https://www.cnblogs.com/o2iginal/p/17538524.html