最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

CSP20230319-4 星际网络II 题解

来源：博客园

〇、题目

题目描述

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

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

在IPxxaf协议中，一个地址由 \(n\) 位二进制位组成，其中 \(n\) 是 \(16\) 的倍数。日常表示一个地址时，采用类似IPv6协议的十六进制表示法，每 \(4\) 位用 :隔开。如 \(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\sim r\) 范围内（包含 \(l\) 和 \(r\)，下同）的一段连续地址块。

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

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

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

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

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

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

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

输入格式

从标准输入读入数据。

第一行，\(2\) 个正整数 \(n,q\)。

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

输出格式

输出到标准输出。

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

其中，对于操作 \(1\)，输出 YES或 NO；对于操作 \(2\)，输出一个非负整数。

样例输入1

32 121 1 0001:8000 0001:ffff2 0001:a0003 0001:c000 0001:ffff1 2 0000:0000 000f:ffff2 0000:10001 1 0001:8000 0001:8fff1 2 0000:0000 0000:ffff2 0000:10001 1 0002:8000 0002:ffff3 0001:8000 0002:ffff1 1 0001:c000 0003:ffff3 0001:8000 0002:ffff

样例输出1

YES11NO0NOYES2YES0YES1

样例解释

第 \(4\) 个操作时，由于用户 \(2\) 申请的部分地址已被分配给用户 \(1\)，因此申请不通过；

第 \(6\) 个操作时，由于用户 \(1\) 申请的全部地址已被分配给用户 \(1\)，因此申请不通过；

第 \(11\) 个操作时，用户 \(1\) 申请的部分地址已被分配给用户 \(1\)，其余地址尚未被分配，申请通过；

数据范围

对于所有数据，\(n\leq 512,q\leq 5\times10^4\)，\(n\) 为 \(16\) 的倍数，\(id\leq q\)，对于操作 \(1,3\) 保证 \(num(l)\leq num(r)\)。

测试点编号\(n\leq\)\(q\leq\)特殊性质
\(1\sim4\)\(16\)\(200\)无
\(5\sim6\)\(64\)\(200\)无
\(7\sim9\)\(512\)\(200\)无
\(10\sim11\)\(16\)\(20000\)无
\(12\sim13\)\(64\)\(50000\)无
\(14\sim16\)\(512\)\(50000\)所有操作 1 的 \(id\) 互不相同
\(17\sim20\)\(512\)\(50000\)无

一、思路

首先看到这个离谱的 IP 表示方法，我们就想把它离散化。

这个东西有一个好处：因为长度相等而且数字的 ASCII 码小于字母的，所以我们可以直接比较字符串。

在离散化的时候，注意到他要判断是否连续，所以在离散化的时候要注意当前 IP 和上一个是否相邻。

于是整个问题就转化为了给你一个不超过 \(2\times 10^5\) 大小的数组，进行区间涂色和查询。

这个时候有一个类似于哈希的思路：给每个颜色一个权值 \(w_i\)，记一个区间的和 \(Sum_{l,r}\) 为这个区间内所有点的颜色的 \(w_i\) 之和。

那么这时一个区间 \(l,r\) 的颜色如果都是 \(i\)（或者没有颜色），那么显然 \(Sum_{l,r}\) 一定是 \(i\) 的倍数。

但是我们发现有可能 出现 \(x\times w_1=y\times w_2\) 的情况，这个时候可能和就没法代表一个固定的东西了。

为了避免上面情况的发生，因为 \(x\) 和 \(y\) 实际上只能是长度，不超过 \(2\times 10^5\)。于是，我们很容易想到选取大于 \(2\times 10^5\) 的 \(2\times 10^5\) 个质数作为 \(w_i\) 即可，大约 \(4\times 10^6\) 就可以筛出这么多。

那既然 \(Sum_{l,r}\) 能固定了，就可以解决三种操作了：

  1. 如果 \(w_{id}\nmid Sum_{l,r}\) 或者 \(Sum_{l,r}=(r-l+1)\times w_{id}\)，那么答案就是 NO，否则就是 YES，然后直接区间把颜色改为 \(w_{id}\)。
  2. 单点查询颜色。
  3. 记录区间颜色权值的最小值（或者最大值） \(Min_{l,r}\)，而显然在一个区间颜色都相等的情况下一定有 \(Sum_{l,r}=(r-l+1)\times Min_{l,r}\)（因为所有颜色都是一样的），这个时候就输出 \(Min_{l,r}\) 对应的颜色，否则就是 \(0\)。

直接线段树维护即可。

这个思路是不是十分抽象，我也觉得这很抽象。这个奇妙的思路来源于 小 H。OrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrzOrz

二、代码

#includeusing namespace std;int n,q;struct op{//离散化所以要记录操作int opt;string x,y;int l,r;int user;}opts[50005];string plusone(string s){int w;//IP地址+1s[w=s.length()-1]++;while(w>=0&&s[w]=="g"){s[w]="0";if(s[w-1]==":") s[w-2]++,w-=2;else s[w-1]++,w--;}if(s[w]==58) s[w]="a";return s;}struct LSH{//离散化set s;int cnt;unordered_map toNum;inline void pls(string str){s.insert(str);}inline void run(){auto it=s.begin(),ti=s.end();//ti是it的上一个for(;it!=s.end();it++){if(it!=s.begin()){if(ti==s.end()) ti=s.begin();else ti++;if(plusone(*ti)!=(*it)) cnt++;}toNum[*it]=++cnt;}}inline int gNum(string s){return toNum[s];}}lsh;bitset<4000005> isnp;int pr[400005],prcnt;int W[200005],anscnt;map ni;void shai(int n){//筛出足够多的质数isnp[1]=1;for(int i=2;i<=n;i++){if(!isnp[i]){pr[++prcnt]=i;if(i>200000) W[++anscnt]=i,ni[i]=anscnt;//记录一下倒过来是什么if(anscnt>=200000) return;}for(int j=1;j<=prcnt&&1ll*i*pr[j]<=n;j++){isnp[i*pr[j]]=1;if(i%pr[j]==0) break;}}}#define ll long longll MIN(ll a,ll b){return a==0?b:b==0?a:a>1)struct node{//下面是线段树ll sum,mn,lazy,len;node operator +(node b){return {sum+b.sum,MIN(mn,b.mn),0,len+b.len};}node operator =(ll b){return {sum=b*len,mn=b,lazy=b,len};}}tr[800005];void build(int p,int l,int r){if(l==r){tr[p]={0,0,0,1};return;}build(ls,l,mid);build(rs,mid+1,r);tr[p]=tr[ls]+tr[rs];}void pushdown(int p){if(tr[p].lazy) tr[ls]=tr[p].lazy,tr[rs]=tr[p].lazy,tr[p].lazy=0;}void chg(int p,int l,int r,int L,int R,ll c){if(l>=L&&r<=R){tr[p]=c;return;}pushdown(p);if(L<=mid) chg(ls,l,mid,L,R,c);if(R>mid) chg(rs,mid+1,r,L,R,c);tr[p]=tr[ls]+tr[rs];}ll qsum(int p,int l,int r,int L,int R){if(l>=L&&r<=R) return tr[p].sum;ll ans=0;pushdown(p);if(L<=mid) ans+=qsum(ls,l,mid,L,R);if(R>mid) ans+=qsum(rs,mid+1,r,L,R);return ans;}ll qmin(int p,int l,int r,int L,int R){if(l>=L&&r<=R) return tr[p].mn;ll ans=0;pushdown(p);if(L<=mid) ans=MIN(ans,qmin(ls,l,mid,L,R));if(R>mid) ans=MIN(ans,qmin(rs,mid+1,r,L,R));return ans;}int main(){shai(4000000);cin>>n>>q;for(int i=1;i<=q;i++){cin>>opts[i].opt;if(opts[i].opt==1) cin>>opts[i].user>>opts[i].x>>opts[i].y;else if(opts[i].opt==2) cin>>opts[i].x;else cin>>opts[i].x>>opts[i].y;lsh.pls(opts[i].x);if(opts[i].opt!=2) lsh.pls(opts[i].y);}lsh.run();for(int i=1;i<=q;i++) opts[i].l=lsh.gNum(opts[i].x),(opts[i].opt!=2)&&(opts[i].r=lsh.gNum(opts[i].y));n=lsh.cnt;//相当于一共就这么多节点build(1,1,n);for(int i=1;i<=q;i++){int op=opts[i].opt,l=opts[i].l,r=opts[i].r,id=opts[i].user;//按照思路写出来非常轻松if(op==1){ll sum=qsum(1,1,n,l,r);if((sum%W[id])||sum/W[id]==r-l+1) cout<<"NO"<

三、总结

题目很抽象，思路也很抽象（

不过感觉似乎这个 trick 在一些题上能派上小用场。

关键词：