【CSP 202303-4】星際網絡Ⅱ 【離散化+線段樹】

題目鏈接

http://118.190.20.162/view.page?gpid=T162

題意

一個網絡地址由 $n$ ($n \leq 512$ ，且是16的倍數)位二進制位組成（形如 xxxx:xxxx: .... :xxxx），有若干用戶需要申請一些網絡地址。

有三種操作：

申請。給出一個用戶編號，和要查詢的地址區間[L, R]，若全都沒有被申請過，或者之前有一部分（不能是全部）被此用戶申請過，輸出YES，否則輸出NO
單點查詢。查詢某地址p，返回申請者的編號，沒有人申請過返回0
區間查詢。查詢地址區間[L, R]是否全部被某用戶申請過，若是返回申請者編號，否返回0

一共有 $q(q \leq 50000)$ 次操作

思路

20分做法

$n \leq 16，q \leq 200$，暴力枚舉即可

100分做法

~~別問，問就是其他做法我不會~~

因為網絡地址的范圍很大（$ \leq 2^{512}$），而詢問的數量是比較可觀的，因此可以想到離散化。

這題的網絡地址有一個特點，就是如果當作字符串讀入的話，字符串的字典序和地址按照大小排列的順序一致；還有一點需要注意，如果離散化之前的區間是[1,2],[4,5],離散化之后會變成[1,2],[3,4],從不連續變成了連續的，所以在離散化的時候需要把區間右端點+1的位置也一起排序，注意+1導致的地址進位問題。

具體步驟是先把網絡地址以字符串的形式全部讀入，直接用sort排好序，然后用lower_bound函數查找，用得到的下標給地址重新賦值

    cin >> n >> q;
    for(int i = 1; i <= q; i++) {
        cin >> op[i];
        if(op[i] == 1) {
            cin >> id[i] >> l[i] >> r[i];
            tem[++cnt] = l[i]; tem[++cnt] = r[i];
            if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
        }
        else if(op[i] == 2) {
            cin >> s[i];
            tem[++cnt] = s[i];
        }
        else {
            cin >> l[i] >> r[i];
            tem[++cnt] = l[i]; tem[++cnt] = r[i];
            if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
        }
    }
    sort(tem + 1, tem + cnt + 1);
    int k = unique(tem + 1, tem + cnt + 1) - tem - 1;
    build(1, 1, k);
    for(int i = 1; i <= q; i++) {
        if(op[i] == 1) {
            L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
            R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
            int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
            if(cnt == 0 || mn == mx && mn == id[i] && cnt < R[i] - L[i] + 1) {
                cout << "YES\n";
                upd(1, 1, k, L[i], R[i], id[i]);
            }
            else cout << "NO\n";
        }
        else if(op[i] == 2) {
            L[i] = lower_bound(tem + 1, tem + k + 1, s[i]) - tem;
			int ans = qry_max(1, 1, k, L[i], L[i]);
            cout << ((ans > 0 && ans <= k) ? ans : 0) << endl;
        }
        else {
            L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
            R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
            int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
            if(mn == mx && cnt == R[i] - L[i] + 1 && mn > 0) cout << mn << endl;
            else cout << 0 << endl;
        }
    }

這樣就把范圍很大的地址映射到1e5量級了。

因為操作涉及到區間，區間查詢、區間修改、單點查詢，很容易想到線段樹這一數據結構。

用t[rt]代表一個樹上結點，v表示這個結點內被申請了的地址個數，mn mx代表申請了這塊地址范圍的申請人編號的最小值、最大值，lazy就是懶標記

操作一：
區間查詢
YES的情況：v == 0 || (v < r - l + 1 && mn == mx && mn == id)，然后還要upd這個區間的值為id
否則是NO

操作二:
單點查詢p位置的編號

操作三：
區間查詢
有答案的情況：mn == mx && mn > 0 && v == r - l + 1
否則是0

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, q, op[N], id[N], cnt, L[N], R[N];
string l[N], r[N], s[N], tem[N << 1];
struct SegTree{
    int v;   // 區間內被用過的值的個數
    int lazy;
    int mn, mx;  // 區間內最小 最大id
}t[N << 2]; 

void push_up(int rt) {
    t[rt].v = t[rt * 2].v + t[rt * 2 + 1].v;
	t[rt].mn = min(t[rt * 2].mn, t[rt * 2 + 1].mn);
    t[rt].mx = max(t[rt * 2].mx, t[rt * 2 + 1].mx);
}

void build(int rt, int l, int r) {
    t[rt].lazy = 0; 
    if(l == r) {
        t[rt].v = 0;
        t[rt].mn = 1e9; t[rt].mx = -1e9;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt * 2, l, mid);
    build(rt * 2 + 1, mid + 1, r);
    push_up(rt);
}

void push_down(int rt, int lenl, int lenr) {
    if(t[rt].lazy) {
        t[rt * 2].v = lenl;
        t[rt * 2 + 1].v = lenr;
        t[rt * 2].lazy = t[rt].lazy;
        t[rt * 2 + 1].lazy = t[rt].lazy;
        t[rt * 2].mn = t[rt * 2].mx = t[rt].lazy;
        t[rt * 2 + 1].mn = t[rt * 2 + 1].mx = t[rt].lazy;
        t[rt].lazy = 0;
    }
}

void upd(int rt, int l, int r, int L, int R, int v) {
    if(l > r || l > R || L > r) return;
    if(L <= l && r <= R) {
        t[rt].v = r - l + 1;
        t[rt].mn = t[rt].mx = v;
        t[rt].lazy = v;
        return;
    }
    int mid = (l + r) >> 1;
    push_down(rt, mid - l + 1, r - mid);
    upd(rt * 2, l, mid, L, R, v);
    upd(rt * 2 + 1, mid + 1, r, L, R, v);
    push_up(rt);
}

int qry_min(int rt, int l, int r, int L, int R) {
    if(l > r || l > R || L > r) return 1e9;
    if(L <= l && r <= R) return t[rt].mn;
    int mid = (l + r) >> 1;
    push_down(rt, mid - l + 1, r - mid);
    return min(qry_min(rt * 2, l, mid, L, R), qry_min(rt * 2 + 1, mid + 1, r, L, R));
}

int qry_max(int rt, int l, int r, int L, int R) {
    if(l > r || l > R || L > r) return -1e9;
    if(L <= l && r <= R) return t[rt].mx;
    int mid = (l + r) >> 1;
    push_down(rt, mid - l + 1, r - mid);
    return max(qry_max(rt * 2, l, mid, L, R), qry_max(rt * 2 + 1, mid + 1, r, L, R));
}

int qry(int rt, int l, int r, int L, int R) {
    if(l > r || l > R || L > r) return 0;
    if(L <= l && r <= R) return t[rt].v;
    int mid = (l + r) >> 1;
    push_down(rt, mid - l + 1, r - mid);
    return qry(rt * 2, l, mid, L, R) + qry(rt * 2 + 1, mid + 1, r, L, R);
}

inline bool s_f(string s) {
    for(auto ch : s) {
        if(ch == ':') continue;
        if(ch != 'f') return 0;
    }
    return 1;
}

inline string nex(string s) {
    bool f = 0;
    for(int i = s.length() - 1; i >= 0; i--) {
        if(s[i] == ':') continue;
        if(s[i] == 'f') s[i] = '0';
        else if(s[i] >= 'a') s[i] += 1, f = 1;
        else if(s[i] == '9') s[i] = 'a', f = 1;
        else s[i] += 1, f = 1;
        if(f) break;
    }
    return s;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> q;
    for(int i = 1; i <= q; i++) {
        cin >> op[i];
        if(op[i] == 1) {
            cin >> id[i] >> l[i] >> r[i];
            tem[++cnt] = l[i]; tem[++cnt] = r[i];
            if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
        }
        else if(op[i] == 2) {
            cin >> s[i];
            tem[++cnt] = s[i];
        }
        else {
            cin >> l[i] >> r[i];
            tem[++cnt] = l[i]; tem[++cnt] = r[i];
            if(!s_f(r[i])) tem[++cnt] = nex(r[i]);
        }
    }
    sort(tem + 1, tem + cnt + 1);
    int k = unique(tem + 1, tem + cnt + 1) - tem - 1;
    // cout << "K: " << k << endl;  ////
    build(1, 1, k);
    for(int i = 1; i <= q; i++) {
        if(op[i] == 1) {
            L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
            R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
//            cout << L[i] << ' ' << R[i] << endl;  //////
            int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
//            cout << cnt << ' ' << mn << ' ' << mx << endl;  ///
            if(cnt == 0 || mn == mx && mn == id[i] && cnt < R[i] - L[i] + 1) {
                // cout << ans.size() << ' ';
                cout << "YES\n";
                upd(1, 1, k, L[i], R[i], id[i]);
            }
            else cout << "NO\n";
        }
        else if(op[i] == 2) {
            L[i] = lower_bound(tem + 1, tem + k + 1, s[i]) - tem;
//            cout << L[i] << endl;  //////
			int ans = qry_max(1, 1, k, L[i], L[i]);
            cout << ((ans > 0 && ans <= k) ? ans : 0) << endl;
        }
        else {
            L[i] = lower_bound(tem + 1, tem + k + 1, l[i]) - tem;
            R[i] = lower_bound(tem + 1, tem + k + 1, r[i]) - tem;
//            cout << L[i] << ' ' << R[i] << endl; ////
            int cnt = qry(1, 1, k, L[i], R[i]), mn = qry_min(1, 1, k, L[i], R[i]), mx = qry_max(1, 1, k, L[i], R[i]);
//            cout << cnt << ' ' << mn << ' ' << mx << endl;  ///
            if(mn == mx && cnt == R[i] - L[i] + 1 && mn > 0) cout << mn << endl;
            else cout << 0 << endl;
        }
    }
    return 0;
}

posted @ 2023-05-21 20:40 starlightlmy 閱讀(541) 評論(0) 收藏舉報

刷新頁面返回頂部

starlight_

acmer ^ ^

【CSP 202303-4】星際網絡Ⅱ 【離散化+線段樹】

題目鏈接

題意

思路

20分做法

100分做法

code

公告