题目描述
- 在 IPxxaf 协议中,一个地址由 𝑛 位二进制位组成,其中 𝑛 是 16 的倍数。
日常表示一个地址时,采用类似 IPv6 协议的十六进制表示法,每 44 位用 :
隔开。
如 𝑛=32 时,地址为 2a00:0001
,即表示一个二进制为 0010 1010 0000 0000 0000 0000 0000 0001
的地址。
1 id l r
:表示用户 𝑖𝑑 申请地址在 𝑙∼𝑟 范围内(包含 𝑙 和 𝑟,下同)的一段连续地址块。
在地址申请操作中,管理员需要先检查地址是否可用。
如果用户申请的地址全部未被分配,则检查通过;若地址中存在已经分配给其他用户的地址,则检查失败。
但有一种特殊情况:申请的地址中没有已经分配给其他用户的地址,但含有一些先前已分配给该用户本人的地址。
此时可以认为检查通过,但若申请的地址先前已全部分配给该用户则检查失败。
如果上述检查通过,则管理员向用户返回 YES
,并将申请的地址分配给该用户;若不通过,则向用户返回 NO
,同时不改变现有的地址分配。
-
2 s
:检查地址 𝑠 被分配给了哪个用户。若未被分配,则结果为 0。 -
3 l r
:检查 𝑙∼𝑟 范围内的所有地址是否完整地分配给了某个用户。若是,回答该用户的编号;若否,回答 0。
输入格式
第一行,2 个正整数 𝑛,𝑞。
接下来 𝑞 行,每行一个操作,格式如上所述,其中的 𝑖𝑑 为正整数,𝑙,𝑟,𝑠 均为 IPxxaf 地址串,其中十六进制均用数字和小写字母表示。
输出格式
输出 𝑞 行,每行一个非负整数或字符串,表示此次操作的结果。
其中,对于操作 1,输出 YES
或 NO
;对于操作 2,3,输出一个非负整数。
数据范围
对于所有数据,𝑛≤512,𝑞≤5×10^4,𝑛 为 16 的倍数,𝑖𝑑≤𝑞,对于操作 1,3 保证 𝑛𝑢𝑚(𝑙)≤𝑛𝑢𝑚(𝑟)。
输入样例
32 12
1 1 0001:8000 0001:ffff
2 0001:a000
3 0001:c000 0001:ffff
1 2 0000:0000 000f:ffff
2 0000:1000
1 1 0001:8000 0001:8fff
1 2 0000:0000 0000:ffff
2 0000:1000
1 1 0002:8000 0002:ffff
3 0001:8000 0002:ffff
1 1 0001:c000 0003:ffff
3 0001:8000 0002:ffff
输出样例:
YES
1
1
NO
0
NO
YES
2
YES
0
YES
1
算法
离散化+线段树
- 首先是地址的表示。地址较长且一开始不确定,但可以知道n是16的倍数,因此我们考虑将地址以四位十六进制为一个单元划分,每四位转化成一个十进制int数,最后以数组的方式存储。读取方式如下:
void read(vector<int>&num){
num=vector<int>(n/16,0);
string s;
cin>>s;
for(int i=0;i<s.size();i+=5)
for(int j=0;j<4;j++){
num[i/5]=num[i/5]*16+hexToDex(s[i+j]);
}
v.push_back(num);//加入离散化
}
2.实现地址的存储之后,我们考虑要对地址进行的一些操作如何实现。
- 首先是加一操作,就是模拟正常的加法:从最低位单元开始,如果是0~65534,直接加1;如果是65535(0xffff)则置0,后一位加1,进行相同判断。
- 其次是两个地址之间的大小比较,这里合理利用了vector容器的默认比较规则:从索引0对应的元素开始比较,若一样再向后比较,这与数的大小比较完全相符。
3.接下来才是正式开始解题。离散化是把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。在这里我们要离散化的对象包含:
- 操作1、2、3的区间端点
- 操作1区间的右端点加1得到的值
为什么要第二个对象呢,因为我们要保证修改的区间之间的相邻关系在离散化之后不会改变。例如,[1,2][4,5]
在离散化前不相邻,离散化后变为[1,2][3,4]
相邻;
4.线段树不是算法,应该是一种工具。能把一些对于区间(或者线段)的修改、维护,从O(N)
的时间复杂度变成O(logN)
。关于线段树,应该注意一些点:
- 线段树的构造
- 线段树与离散化的关系
- 线段树中懒标记的目的,pushup和pushdown函数的作用
这里不展开赘述,请大家仔细阅读参考文献。
本题的思路在于采用地址的离散索引构造线段树,并维护结点中的几个变量,分别是:
l
:区间左端点r
:区间右端点cnt
:该区间内有多少个地址(离散值)被分配mx
:该区间地址用户id的最大值mn
:该区间地址用户id的最小值st
:懒传播标记,用于记录该区间已经全部被某用户占有(st=id)
对于三个操作:
-
1 id l r
: -
查询区间 [ l , r ] 的cnt,mx,mn;
-
全部未分配,即 cnt=0,此时操作成功;
-
余下情况是已经被分配过了(此时 mx,mn 均不为 ∞ ),此时判断是不是仅分配给该用户,即 mx = mn = id ,否则操作失败; 余下情况是已经被分配过了,且仅分配给了该用户,此时判断是否全部分配给了该用户,即cnt=r−l+1,满足则操作失败,否则操作成功;
-
操作成功后给区间 [ l , r ]赋值,对于cnt 来说,区间的值均为 1 ;对于 mx,mn 来说,区间的值均为 id。
-
2 s
:仅需要判断区间 [ s , s ] 的cnt 值是否为 1 即可知是否分配给了用户,如果分配给了用户,输出 mx 或者 mn 均可,否则输出 0 。 -
3 l r
:先判断是否全部进行了分配,即区间 [ l , r ] 的cnt 是否满足 cnt=r−l+1,然后再判断是否分配给了同一个用户,即 mx=mn,如果满足输出 mx 或者 mn 均可,否则输出 0 。
时间复杂度
$$ O(nqlog(q)) $$
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int op[N],id[N];
vector<int> l[N],r[N];
int n,q;
vector<vector<int>> v;
int hexToDex(char c){
int d=0;
if(c>='0'&&c<='9') d='0';
else d='a'-10;
return c-d;
}
void read(vector<int>&num){
num=vector<int>(n/16,0);
string s;
cin>>s;
for(int i=0;i<s.size();i+=5)
for(int j=0;j<4;j++){
num[i/5]=num[i/5]*16+hexToDex(s[i+j]);
}
v.push_back(num);//加入离散化
}
struct seg_node{
int l,r,cnt,mx,mn,st;
//st是懒传播标记!!!
};
seg_node tr[N<<2];//N个结点最大需要4*N长度的数组
void pushup(int i){
tr[i].cnt=tr[i<<1].cnt+tr[i<<1|1].cnt;
tr[i].mx=max(tr[i<<1].mx,tr[i<<1|1].mx);
tr[i].mn=min(tr[i<<1].mn,tr[i<<1|1].mn);
}
void build(int l,int r,int i=1){
tr[i].l=l,tr[i].r=r;
tr[i].cnt=0;
tr[i].mx=INT_MIN,tr[i].mn=INT_MAX;
tr[i].st=INT_MIN;
if(l==r) return;
int mid=l+r>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
pushup(i);
}
void pushdown(int i){
//执行懒传播
if(tr[i].st!=INT_MIN){
tr[i<<1].st=tr[i<<1|1].st=tr[i].st;
tr[i<<1].mx=tr[i<<1|1].mx=tr[i].st;
tr[i<<1].mn=tr[i<<1|1].mn=tr[i].st;
tr[i<<1].cnt=tr[i<<1].r-tr[i<<1].l+1;
tr[i<<1|1].cnt=tr[i<<1|1].r-tr[i<<1|1].l+1;
tr[i].st=INT_MIN;
}
}
int getMax(int l,int r,int i=1){
if(l<=tr[i].l&&tr[i].r<=r) return tr[i].mx;
int mid=tr[i].l+tr[i].r>>1;
int ans=INT_MIN;
pushdown(i);
if(l<=mid) ans=max(ans,getMax(l,r,i<<1));
if(r>=mid+1) ans=max(ans,getMax(l,r,i<<1|1));
return ans;
}
int getMin(int l,int r,int i=1){
if(l<=tr[i].l&&tr[i].r<=r) return tr[i].mn;
int mid=tr[i].l+tr[i].r>>1;
int ans=INT_MAX;
pushdown(i);
if(l<=mid) ans=min(ans,getMin(l,r,i<<1));
if(r>=mid+1) ans=min(ans,getMin(l,r,i<<1|1));
return ans;
}
int getCnt(int l,int r,int i=1){
if(l<=tr[i].l&&tr[i].r<=r) return tr[i].cnt;
int mid=tr[i].l+tr[i].r>>1;
int ans=0;
pushdown(i);
if(l<=mid) ans+=getCnt(l,r,i<<1);
if(r>=mid+1) ans+=getCnt(l,r,i<<1|1);
return ans;
}
void modify(int l,int r,int id,int i=1){
if(l<=tr[i].l&&tr[i].r<=r){
tr[i].st=id;
tr[i].cnt=tr[i].r-tr[i].l+1;
tr[i].mx=tr[i].mn=id;
return;
}
pushdown(i);
int mid=tr[i].l+tr[i].r>>1;
if(l<=mid) modify(l,r,id,i<<1);
if(r>=mid+1) modify(l,r,id,i<<1|1);
pushup(i);
}
void solve(){
cin>>n>>q;
v.push_back(vector<int>(n/16,-1));//空出0
for(int i=0;i<q;i++){
cin>>op[i];
if(op[i]==1){
cin>>id[i];
read(l[i]);
read(r[i]);
vector<int> rAddOne=r[i];
if(rAddOne!=vector<int>(n/16,65535)){
int j=rAddOne.size()-1;
while(rAddOne[j]==65535) rAddOne[j]=0;//进位
rAddOne[j]++;
}
v.push_back(rAddOne);
}else if(op[i]==2){
read(l[i]);
r[i]=l[i];//都是s
}else{
read(l[i]);
read(r[i]);
}
}
//排序去重,离散化
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
//建立线段树
build(0,v.size()-1);
//求解
for(int i=0;i<q;i++){
//将地址映射为离散化的索引值,采用lower_bound的原因是有序时二分法效率高
int L=lower_bound(v.begin(),v.end(),l[i])-v.begin();
int R=lower_bound(v.begin(),v.end(),r[i])-v.begin();
int cnt=getCnt(L,R);
int max=getMax(L,R);
int min=getMin(L,R);
if(op[i]==1){
if(cnt==R-L+1||(max!=id[i]&&max!=INT_MIN)||(min!=id[i]&&min!=INT_MAX))
cout<<"NO"<<endl;
else{
cout<<"YES"<<endl;
modify(L,R,id[i]);
}
}else if(op[i]==2){
cout<<(cnt?max:0)<<endl;
}else{
if(cnt==R-L+1&&max==min) cout<<max<<endl;
else cout<<0<<endl;
}
}
}
int main(){
solve();
return 0;
}