首页 > 代码库 > Nested Segments

Nested Segments

2024-07-17 00:38:53   220人阅读

题目链接

  • 题意：
    给n个区间，任意两个区间要么完全包含，要么相离。m个查询，每次输入一个整数，输出这个数属于哪个区间，如果有多个区间，选长度最小的
     (1 ≤ n ≤ 10e5)、区间短点值(1 ≤ ai < bi ≤ 10e9)、(1 ≤ m ≤ 10e5)、查询值(1 ≤ cj ≤ 10e9)
  • 分析：
    离散化加set输出答案。离散化的时候，将[a, b]加入数组中时，插入a-1，a，b，b+1；同时，将m个查询也离散化，加入数组中（这里也可以不插入，处理会稍稍麻烦点）
const int MAXN = 1100000;

struct Seg
{
    int l, r;
    bool operator< (const Seg& rhs)const
    {
        return r - l < rhs.r - rhs.l;
    }
} ipt[MAXN];

VI split;
int ans[MAXN], q[MAXN];
set<int> st;
set<int>::iterator it;
int main()
{
    int n, m;
    while (~RI(n))
    {
        split.clear();
        CLR(ans, -1);
        FE(i, 1, n)
        {
            RII(ipt[i].l, ipt[i].r);
            split.push_back(ipt[i].l);
            split.push_back(ipt[i].r);
            split.push_back(ipt[i].l - 1);
            split.push_back(ipt[i].r + 1);
        }
        RI(m);
        REP(i, m)
        {
            RI(q[i]);
            split.push_back(q[i]);
        }
        sort(all(split));
        split.erase(unique(all(split)), split.end());
        FE(i, 0, split.size())
            st.insert(i);
        st.insert(INF);
        FED(i, n, 1)
        {
            int l = lower_bound(all(split), ipt[i].l) - split.begin();
            int r = lower_bound(all(split), ipt[i].r) - split.begin();
            it = st.lower_bound(l);
            while (*it <= r)
            {
                ans[*it] = i;
                st.erase(it++);
            }
        }
        REP(i, m)
        {
            int id = lower_bound(all(split), q[i]) - split.begin();
            WI(ans[id]);
        }
    }
    return 0;
}


联系
我们