[CCF-CSP] 202303-4 星际网络II

题目描述

随着星际网络的进一步建设和规模的增大，一个新的问题出现在网络工程师面前——地址空间不够用了！原来，星际网络采用了传统的IPv6协议，虽然有 21282128 级别的可用地址数量，但面对广袤无垠的宇宙和爆炸式增长的网络用户数，如此庞大的地址空间也面临了用尽的那一天。

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终，经过2333年的不懈努力，西西艾弗星的工程师们设计出了一种新的协议——“西西艾弗IP协议”，又称IPxxaf。

在IPxxaf协议中，一个地址由 n 位二进制位组成，其中 n 是 1616 的倍数。日常表示一个地址时，采用类似IPv6协议的十六进制表示法，每 44 位用 : 隔开。如n=32 时，地址为 2a00:0001 ，即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001 的地址。注意不会出现IPv6中省略每组的前导 0 或用 :: 省略一段 0 的情况。

为方便起见，记 num(s) 为地址 s 按高位在前、低位在后组成的 n 位二进制数，称一段“连续的地址“为 num(s) 成一段连续区间的一系列地址。

西西艾弗星的网络管理员负责地址的分配与管理。最开始，整个地址空间都是未分配的。用户可以随时向管理员申请一些地址：

1 id l r：表示用户id 申请地址在 l∼r 范围内（包含 l 和 r，下同）的一段连续地址块。

在地址申请操作中，管理员需要先检查地址是否可用。如果用户申请的地址全部未被分配，则检查通过；若地址中存在已经分配给其他用户的地址，则检查失败。

但有一种特殊情况：申请的地址中没有已经分配给其他用户的地址，但含有一些先前已分配给该用户本人的地址。此时可以认为检查通过，但若申请的地址先前已全部分配给该用户则检查失败。

如果上述检查通过，则管理员向用户返回 YES，并将申请的地址分配给该用户；若不通过，则向用户返回 NO，同时不改变现有的地址分配。

网络管理员要定期检查地址的分配情况，具体而言有如下两种操作：

2 s：检查地址 s 被分配给了哪个用户。若未被分配，则结果为 00。

3 l r：检查 l∼r 范围内的所有地址是否完整地分配给了某个用户。若是，回答该用户的编号；若否，回答 00。

在整个网络的运行过程中，共出现了 q 次申请地址和检查地址分配的操作。作为西西艾弗星的一名重要的网络技术顾问，你要帮网络管理员依次处理每个操作，并回答相应的结果。

输入格式

从标准输入读入数据。

第一行，22 个正整数 n,q。

接下来 q 行，每行一个操作，格式如上所述，其中的 id 为正整数，l,r,s 均为IPxxaf地址串，其中十六进制均用数字和小写字母表示。

输出格式

输出到标准输出。

输出 q 行，每行一个非负整数或字符串，表示此次操作的结果。

其中，对于操作 11 ，输出 YES 或 NO；对于操作 2,32,3，输出一个非负整数。

思路

很明显就是一个区间修改、区间查询的题目，因此可以用线段树来解决这个问题。

离散化操作：预处理所有查询中涉及到的IP地址，升序排序，用编号来表示。这里注意与上一个IP地址的连贯性，如果刚好等于上一个IP地址的下一个，就不用管；否则的话，中间跳过的IP地址，我们也要给他们留一个位置。如果没有这一步的话，后面的区间查询会少查询一段。

用线段树维护区间和，表示这个区间被占用的IP个数，用mx和mn表示占用这个区间的用户的最大id与最小id。

对于查询1：我们要查询[l,r]这个区间被占用的IP个数sum，如果sum<区间长度且这个区间没有被占用或者仅被用户id占用，查询成功，否则查询失败。

对于查询2：我们要查询[l,l]这个区间占用的用户id。

对于查询3：我们要查询[l,r]这个区间被占用的IP个数sum，如果sum=区间长度且这个区间仅被一个用户占用，输出用户编号，否则输出0。

代码

#include <bits/stdc++.h>
#define N 50010
#define INF 0x3f3f3f3f
using namespace std;int n,qq,cnt;
map<string,int> mp;//离散化
struct query{//查询int op,id;string l,r;
}q[N];
struct node{//线段树int l,r,sum,mx,mn,add;
}tr[N<<4];void pushup(int u){//向上更新tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
}
void build(int u,int l,int r){//建树tr[u]={l,r,0,-INF,INF,0};if(l==r){tr[u].mx=-INF;tr[u].mn=INF;return;}int mid=l+r>>1;build(u<<1,l,mid);build(u<<1|1,mid+1,r);pushup(u);
}
void upd(int u,int c){//单点更新tr[u].sum=tr[u].r-tr[u].l+1;tr[u].mx=max(tr[u].mx,c);tr[u].mn=min(tr[u].mn,c);tr[u].add=c; 
}
void pushdown(int u){//延迟标记if(tr[u].add){upd(u<<1,tr[u].add);upd(u<<1|1,tr[u].add);tr[u].add=0;}
}
void update(int u,int l,int r,int c){//区间更新if(l<=tr[u].l&&tr[u].r<=r) upd(u,c);else{pushdown(u);int m=tr[u].l+tr[u].r>>1;if(l<=m) update(u<<1,l,r,c);if(r>m) update(u<<1|1,l,r,c);pushup(u);} 
}
int qsum(int u,int l,int r){//查询区间和if(l>r) return 0;if(l<=tr[u].l&&tr[u].r<=r) return tr[u].sum;int ans=0;pushdown(u);int m=tr[u].l+tr[u].r>>1;if(l<=m) ans+=qsum(u<<1,l,r);if(r>m) ans+=qsum(u<<1|1,l,r);return ans;
}
int qmx(int u,int l,int r){//查询区间最大值if(l>r) return -INF;if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mx;int ans=-INF;pushdown(u);int m=tr[u].l+tr[u].r>>1;if(l<=m) ans=max(ans,qmx(u<<1,l,r));if(r>m) ans=max(ans,qmx(u<<1|1,l,r));return ans;
}
int qmn(int u,int l,int r){//查询区间最小值if(l>r) return INF;if(l<=tr[u].l&&tr[u].r<=r) return tr[u].mn;int ans=INF;pushdown(u);int m=tr[u].l+tr[u].r>>1;if(l<=m) ans=min(ans,qmn(u<<1,l,r));if(r>m) ans=min(ans,qmn(u<<1|1,l,r));return ans;
}
bool judge(string now,string pre){//判断IP地址是否连贯int c=1;for(int i=pre.size()-1;i>=0;i--){if(c==0) break;if(pre[i]==':') continue;if(pre[i]=='9') pre[i]='a',c=0;else if(pre[i]=='f') pre[i]='0',c=1;else pre[i]=pre[i]+c,c=0;}if(now==pre) return true;return false;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>qq;for(int i=1;i<=qq;i++){cin>>q[i].op;if(q[i].op==1){cin>>q[i].id>>q[i].l>>q[i].r;mp[q[i].l]=1,mp[q[i].r]=1;}else if(q[i].op==2){cin>>q[i].l;mp[q[i].l]=1;}else{cin>>q[i].l>>q[i].r;mp[q[i].l]=1,mp[q[i].r]=1;}}string pre="0000";for(int i=1;i<n/16;i++) pre+=":0000";for(auto it=mp.begin();it!=mp.end();it++){//离散化if(it->first!=pre&&!judge(it->first,pre)) ++cnt;//不连贯要空一个位置it->second=++cnt;pre=it->first;}build(1,1,cnt);for(int i=1;i<=qq;i++){if(q[i].op==1){int l=mp[q[i].l],r=mp[q[i].r],id=q[i].id;int sum=qsum(1,l,r),fg;if(sum==0) fg=1;else if(sum<r-l+1){int mx=qmx(1,l,r),mn=qmn(1,l,r);if(mx==mn&&mx==id) fg=1; else fg=0;}else fg=0;if(fg){cout<<"YES"<<endl;update(1,l,r,id);}else cout<<"NO"<<endl;}else if(q[i].op==2){int l=mp[q[i].l];if(qsum(1,l,l)==0) cout<<0<<endl;else cout<<qmx(1,l,l)<<endl;}else{int l=mp[q[i].l],r=mp[q[i].r],id=q[i].id;int sum=qsum(1,l,r);if(sum==r-l+1){int mx=qmx(1,l,r),mn=qmn(1,l,r);if(mx==mn) cout<<mx<<endl; else cout<<0<<endl;}else cout<<0<<endl;}}return 0;
}