首页 > 其他分享 >【CSP 202303-4】星际网络Ⅱ 【离散化+线段树】

【CSP 202303-4】星际网络Ⅱ 【离散化+线段树】

时间：2023-05-21 20:44:35浏览次数：58  
标签：rt cnt tem int 线段 mid 202303 ++ CSP

题目链接

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

题意

一个网络地址由 \(n\) (\(n \leq 512\) ，且是16的倍数)位二进制位组成（形如 xxxx:xxxx: .... :xxxx），有若干用户需要申请一些网络地址。

有三种操作：

  1. 申请。给出一个用户编号，和要查询的地址区间[L, R]，若全都没有被申请过，或者之前有一部分（不能是全部）被此用户申请过，输出YES，否则输出NO
  2. 单点查询。查询某地址p，返回申请者的编号，没有人申请过返回0
  3. 区间查询。查询地址区间[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;
}

标签：rt,cnt,tem,int,线段,mid,202303,++,CSP
From： https://www.cnblogs.com/re0acm/p/17419132.html

相关文章

  • CSP-J2021试题题解
    1.分糖果原题：https://www.luogu.com.cn/problem/P7909原代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;lln,l,r;intmain(){ cin>>n>>l>>r; if(r%n==n-1)cout<<n-1; elseif(l%n==n-1)cout<<n-1; elseif(......
  • 线段树学习笔记
    让我们来一步一步理解！ 1.向上更新voidpush_up(intrt){//向上更新sum[rt]=sum[rt<<1]+sum[rt<<1|1];} 2.向下更新voidpush_down(intrt,intm){if(add[rt]){//若有标记,则将标记向下移动一层add[rt<<1]+=add[rt];add[rt......
  • CSP-J2022山东补赛题解
    1.植树节原题：https://www.luogu.com.cn/problem/U285015代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1e6+255;inta[N],n,x,y,maxb=-1e9,ans=-1e9;intmain(){ cin>>n; for(inti=1;i<=n;i++){ cin>>x&g......
  • CSP-J2019试题题解
    1.数字游戏原题：https://www.luogu.com.cn/problem/P5660代码：#include<bits/stdc++.h>#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;strings;intmain(){ cin>>s;intnum=0; fo......
  • Luogu P5664 [CSP-S2019] Emiya 家今天的饭
    发现“每种主要食材至多在\(\lfloor\frac{k}{2}\rfloor\)个菜中被使用”有一个性质，在不合法的情况下绝对只有\(1\)个主要食材的个数\(>\lfloor\frac{k}{2}\rfloor\)，因为\(k-\lfloor\frac{k}{2}\rfloor-1\le\lfloor\frac{k}{2}\rfloor\)然后就能发现算不合法......
  • CSP-J2020试题
    1.优秀的拆分原题：https://www.luogu.com.cn/problem/P7071代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintN=1e4+255;lln,x=0,power[N];intmain(){ cin>>n; if(n%2==1)cout<<"-1"; else{ while(n){ ......
  • 线段树均摊复杂度
    GSS4-CanyouanswerthesequeriesIV操作\(1\)：\(a_i=\sqrt{a_i},i\in[l,r]\)操作\(2\)：询问\(\sum_{i=l}^ra_i\)开根号无法使用tag的方式维护，因为开根号后不确定减去多少，无法维护\(\suma_i\)。\(a_i=2^{\loga_i}\)，每次开根号后\(\loga_i\)会减半，操作\(\log\l......
  • CSP-J2022试题题解
    1.乘方原题：https://www.luogu.com.cn/problem/P8813代码：#include<bits/stdc++.h>#definelllonglongusingnamespacestd;constintXN=1e9;lla,b,ans=1;intmain(){ cin>>a>>b; for(inti=1;i<=b;i++){ ans*=a; if(ans>XN){ cout......
  • P2495 [SDOI2011] 消耗战 线段树合并做法
    看到题解里面有一个线段树合并做法！感觉很厉害，但是题解和代码都不是很详细所以补充一下不妨假设\(dp_u\)表示\(u\)及其子树内把所有关键点都切断的最小代价，那么不难有\[\begin{equation}dp_u=\begin{cases}+\infty&u是关键点\\\sum_{v\in\operatorname{son}(u)}\m......
  • 线段树维护矩阵
    对于一些只有单点修改且维护的信息具有递推性的题目，由于运算具有结合律，可以将两区间合并写成矩阵乘法的形式，省去一些麻烦的讨论。前置知识：广义矩阵乘法对于一个\(n\timesm\)的矩阵\(A\)和一个\(m\timest\)的矩阵\(B\)，定义广义矩阵乘法：\[C_{i,j}=\bigoplus_{k=1}^{m}A_......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99