The 2021 ICPC Asia Taipei Regional Programming Contest C Community Service

题目描述

https://codeforces.com/gym/103443/problem/C

简要题意：现在有一个长度为 $n$ 的序列和 $m$ 个操作，操作有两种：第一种操作给定区间 $[l,r]$，表示添加一条覆盖 $[l,r]$ 的线段；第二种操作给定区间 $[l,r]$，求与给定区间有交点的最后一次添加的区间，并将其删除

$n\le 10^6,m\le 2\times 10^5$

Solution

我们考虑线段树，注意到在线段树上寻找与区间 $[l,r]$ 有交点的所有区间的复杂度是 $O(\log n)$ 的，那么我们现在只有两个要维护的东西

一个是子树内最大区间和该点的最大区间，那么我们可以在线段树上每个节点维护一个 $set$，但是注意到区间的权值即为其加入顺序，那么我们可以使用栈来维护，同时使用延迟删除的技巧

时间复杂度 $O(n\log n)$

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define maxn 1000010
#define maxm 200010
#define ll long long
using namespace std;

int n, m, l[maxm], r[maxm];
char s[maxm][20];
bool vis[maxn];

inline int get(vector<int> &vec) {
    if (!vec.size()) return 0;
    return vec.back();
}    

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    vector<int> vec, v;
} T[maxn * 4];
void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ; 
    T[i].v.push_back(v); int m = l + r >> 1; 
    if (L <= l && r <= R) return T[i].vec.push_back(v);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}

int ans; 
void query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return ; int m = l + r >> 1;
    while (T[i].vec.size() && vis[T[i].vec.back()]) T[i].vec.pop_back();
    while (T[i].v.size() && vis[T[i].v.back()]) T[i].v.pop_back();
    ans = max(ans, get(T[i].vec));
    if (L <= l && r <= R) return ans = max(ans, get(T[i].v)), void();
    query(lc, l, m, L, R); query(rc, m + 1, r, L, R); 
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int opt, x, y; cin >> opt;
        if (opt == 1) {
            cin >> s[i] >> x >> y; ++x; ++y; l[i] = x; r[i] = y;
            update(1, 1, n, x, y, i); 
        } else {
            cin >> x >> y; ++x; ++y;
            ans = 0; query(1, 1, n, x, y);
            if (!ans) cout << ">_<" << "\n";
            else cout << s[ans] << "\n", vis[ans] = 1; 
        }
    }
    return 0; 
}