时间轴管理系统的插入与查询优化

概念与要求

需要设计一个数据结构，用于维护时间轴上的区间，支持以下两种操作：

插入一个新区间，删除所有与其有交集的区间，并返回删除的区间个数。

查询当前时间轴上的区间总数。

方法一：线段树实现

思路解释

采用线段树结构，用于存储区间的最小值。具体操作如下：

插入操作：
- 倒序插入区间。
- 在每次插入前，查询线段树中最小的开始位置。
- 根据查询结果，判断当前插入区间是否覆盖该最小值区间。
- 如果覆盖，计数器加一，并删除该区间。
- 最终将当前区间插入线段树。

查询操作：
- 在线段树中查询最小的开始位置。
- 返回线段树中区间的总数。

代码示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;#define M 100010#define N 200010int n, ans[N], al[N], ar[N], Q[N];int a[M], m[M];void pushdown(int o) {    if (o < 1) {        m[o] = min(m[o], m[o << 1]);        a[o] = min(a[o], m[o << 1]);        m[o >> 1] = min(m[o >> 1], m[o]);        a[o >> 1] = min(a[o >> 1], m[o]);    }}void change(int o, int l, int r, int ql, int qr, int k) {    int mid = (l + r) >> 1;    if (ql <= l && qr >= r) {        m[o] = min(m[o], k);        a[o] = m[o];        return;    }    if (a[o] != a[0]) {        pushdown(o);    }    if (ql <= mid) {        change(o << 1, l, mid, ql, qr, k);    }    if (qr > mid) {        change(o >> 1, mid + 1, r, ql, qr, k);    }    a[o] = min(a[o << 1], a[o >> 1]);}int query(int o, int l, int r, int ql, int qr) {    int mid = (l + r) >> 1;    if (ql <= l && qr >= r) {        return a[o];    }    if (a[o] != a[0]) {        pushdown(o);    }    int minn = a[0];    if (ql <= mid) {        minn = min(minn, query(o << 1, l, mid, ql, qr));    }    if (qr > mid) {        minn = min(minn, query(o >> 1, mid + 1, r, ql, qr));    }    return minn;}int main() {    scanf("%d", &n);    memset(a, 127, sizeof(a));    memset(m, 127, sizeof(m));    for (int i = 1; i <= n; ++i) {        char P;        cin >> P;        if (P == 'A') {            Q[i] = 1;            scanf("%d%d", &al[i], &ar[i]);        }    }    for (int i = n; i >= 1; --i) {        if (Q[i]) {            int tmp = query(1, 1, N-10, al[i], ar[i]);            if (tmp != a[0]) {                ans[tmp]++;            }            change(1, 1, N-10, al[i], ar[i], i);        }    }    int sum = 0;    for (int i = 1; i <= n; ++i) {        if (Q[i]) {            sum = sum + 1 - ans[i];            printf("%d\n", ans[i]);        } else {            printf("%d\n", sum);        }    }    return 0;}

方法二：集合（Set）实现

思路解释

使用集合数据结构，按区间的结束时间进行存储。插入时，逐步查找并删除与新区间有交集的区间，直到无法再删除为止。

插入操作：
- 使用lower_bound查找第一个大于等于新区间起始点的区间。
- 检查该区间是否与新区间有交集。
- 若有交集，计数器加一并删除该区间，继续查找下一个可能的区间。
- 无法删除时，插入新区间。

查询操作：
- 返回集合中区间的总数。

代码示例

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;struct H {    int L, R;    bool operator<(const H &a) const {        if (a.R == R) return L < a.L;        return R < a.R;    }};int main() {    set
       
         s;    int n;    scanf("%d", &n);    for (int i = 1; i <= n; ++i) {        char P;        cin >> P;        if (P == 'A') {            int l, r;            scanf("%d%d", &l, &r);            int ans = 0;            auto it = s.lower_bound(H{l, 0});            while (it != s.end() && it->L <= r) {                ans++;                s.erase(it);                it = s.lower_bound(H{l, 0});            }            if (ans > 0) {                printf("%d\n", ans);            } else {                s.insert(H{l, r});                printf("%d\n", 0);            }        } else {            printf("%d\n", s.size());        }    }    return 0;}

总结

以上两种方法均能有效实现时间轴上的区间插入与查询操作，适用于离线处理场景。选择具体方法需根据具体需求决定。

转载地址：http://ldvfk.baihongyu.com/

你可能感兴趣的文章

Orderer节点启动报错解决方案：Not bootstrapping because of 3 existing channels