2016 UESTC Training for Data Structures B – 卿学姐与基本法 自己构建了一个和堆有点像的数据结构

Source

2016 UESTC Training for Data Structures  Problem B

My Solution

对很多个区间进行处理，

这里建一个结构体放存放区间，然后把区间放到vector里，根据左边界排序，

然后逐次进行处理使所以区间变成不相交的区间

一直维护这样的区间

至于说像堆， 是因为：

这个也是延迟操作，在查询单时候才进行维护的

维护时，删除vector的那些元素时令那个元素的 了left 成员为INF，然后sort再pop_back()

查询的时候就vector中的元素一个个查询过去了☺

复杂度 不会算，感觉不是很暴力

#include 
#include 
#include 
#include 
using namespace std;
const int maxq = 100000 +8;
const int INF = 0x3f3f3f3f;
struct interval{
    int l,r;
    interval(int x, int y) : l(x), r(y) {}
};

vector val;

bool cmp(const interval& a, const interval& b)
{
    return a.l < b.l;
}

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int N, Q;
    scanf("%d%d", &N, &Q);
    int t, L, R, sz, ans;
    while(Q--){
        scanf("%d%d%d", &t, &L, &R);
        if(t == 1) {
            val.push_back(interval(L, R));
            sort(val.begin(), val.end(), cmp);
            sz = val.size();
            for(int i = 0; i < sz; i++){ if(i != sz-1 && val[i].l == val[i+1].l) {val[i].l = INF; val[i+1].r = max(val[i].r, val[i+1].r);} else if(i != sz-1 && val[i].r >= val[i+1].l) {
                    val[i+1].l = val[i].l; val[i].l = INF; val[i+1].r = max(val[i].r, val[i+1].r);
                }
            }
            sort(val.begin(), val.end(), cmp);
            while(val[sz-1].l == INF){
                val.pop_back();
                sz--;
            }
        }
        else{
            sz = val.size();ans = R - L + 1;
            for(int i = 0; i < sz; i++){
                if(val[i].l <= L && val[i].r >= R) {ans = 0; break;}
                else if(val[i].l >= L && val[i].r <= R) {ans -= (val[i].r - val[i].l +1);} // 里面，左闭右开 else if(val[i].l >= L && val[i].l <= R && val[i].r >= R) {ans -= (R - val[i].l +1);}
                else if(val[i].l <= L && val[i].r >= L && val[i].r <= R) {ans -= (val[i].r - L +1);}
            }
            printf("%dn", ans);
        }

    }
    return 0;
}

据说也可以用线段树^_^

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx