CCF-CSP真题《202303-4 星际网络II》思路+python，c++满分题解

想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全

试题编号： 202303-4

试题名称：星际网络II

时间限制： 2.0s

内存限制： 1.0GB

问题描述：

问题描述

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

新的通信协议的研发工作交给了著名的网络科技圣地——西西艾弗星。最终，经过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∼r 范围内（包含 l 和 r，下同）的一段连续地址块。

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

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

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

输出格式

输出到标准输出。

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

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

样例输入1

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

样例输出1

YES
1
1
NO
0
NO
YES
2
YES
0
YES
1

样例解释

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

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

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

数据范围

对于所有数据，n≤512, q≤5×104，n 为 16 的倍数，id≤q，对于操作 1,3 保证 num(l)≤num(r)。

测试点编号	n≤	q≤	特殊性质
1∼4	16	200	无
5∼6	64	200	无
7∼9	512	200	无
10∼11	16	20000	无
12∼13	64	50000	无
14∼16	512	50000	所有操作 1 的 id 互不相同
17∼20	512	50000	无

真题来源：星际网络II

感兴趣的同学可以如此编码进去进行练习提交

思路讲解：

这道题属于线段树（离散化、单点询问、区间求和、区间最值）的经典题。线段树维护区间和，用于记录对应区间几个值被用过，且线段树维护最大最小值，用于记录被哪个用户id用过，当最小值=最大值时，表示恰被一个用户用过。首先，将最大32维的数转10进制，压成长为32的array，离散化去重后，找到每个ip地址对应下标映射。

操作1：若[l,r]是否没被用户用过，或[l,r]仅被当前用户用过且没占满，则可行，否则不可行；线段树先查一下这段区间和，等于0表示没被用过，则可行；否则，判一下当前区间最大最小值，若最大最小值相等且区间和小于区间长度，则可行。

操作2：单点询问，查单点最大/最小值即可知道被哪个用户用过，或没用过；

操作3：区间询问，若[l,r]仅被一个用户全用过，则区间和为区间长度，区间最大最小值相等，注意离散化时，需要给右端点+1的值也离散化进去，并考虑+1带来的进位问题，否则，可能会出现[1,2][4,5]在离散化前不相邻，离散化后变为[1,2][3,4]相邻的情形；

c++满分题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=15e4+10,M=5e4+10,K=170,B=32,INF=0x3f3f3f3f;
struct segtree{
	int n;
	struct node{int l,r,v,c,mn,mx;}e[N<<2];
	#define l(p) e[p].l
	#define r(p) e[p].r
	#define v(p) e[p].v
	#define c(p) e[p].c
	#define mn(p) e[p].mn
	#define mx(p) e[p].mx
	void up(int p){
		v(p)=v(p<<1)+v(p<<1|1);
		mn(p)=min(mn(p<<1),mn(p<<1|1));
		mx(p)=max(mx(p<<1),mx(p<<1|1));
	}
	void bld(int p,int l,int r){
		l(p)=l;r(p)=r;c(p)=0;
		if(l==r){v(p)=0;mn(p)=INF;mx(p)=-INF;return;}
		int mid=l+r>>1;
		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
		up(p);
	}
	void psd(int p){
		if(c(p)){
			v(p<<1)=r(p<<1)-l(p<<1)+1;
			mn(p<<1)=min(mn(p<<1),c(p));
			mx(p<<1)=max(mx(p<<1),c(p));
			c(p<<1)=c(p);
			v(p<<1|1)=r(p<<1|1)-l(p<<1|1)+1;		
			mn(p<<1|1)=min(mn(p<<1|1),c(p));
			mx(p<<1|1)=max(mx(p<<1|1),c(p));
			c(p<<1|1)=c(p);
			c(p)=0; 
		}
	}
	void init(int _n){n=_n;bld(1,1,n);}
	void chg(int p,int ql,int qr,int v){
		if(ql>qr)return;
		if(ql<=l(p)&&r(p)<=qr){
			v(p)=r(p)-l(p)+1;
			mn(p)=min(mn(p),v);
			mx(p)=max(mx(p),v);
			c(p)=v;
			return;
		}
		psd(p);
		int mid=l(p)+r(p)>>1;
		if(ql<=mid)chg(p<<1,ql,qr,v);
		if(qr>mid)chg(p<<1|1,ql,qr,v);
		up(p);
	}
	int cnt(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr)return v(p);
		int mid=l(p)+r(p)>>1,res=0;
		psd(p);
		if(ql<=mid)res+=cnt(p<<1,ql,qr);
		if(qr>mid)res+=cnt(p<<1|1,ql,qr);
		return res;
	}
	int amn(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr)return mn(p);
		int mid=l(p)+r(p)>>1,res=INF;
		psd(p);
		if(ql<=mid)res=min(res,amn(p<<1,ql,qr));
		if(qr>mid)res=min(res,amn(p<<1|1,ql,qr));
		return res;
	}
	int amx(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr)return mx(p);
		int mid=l(p)+r(p)>>1,res=-INF;
		psd(p);
		if(ql<=mid)res=max(res,amx(p<<1,ql,qr));
		if(qr>mid)res=max(res,amx(p<<1|1,ql,qr));
		return res;
	}
}seg;
int n,m,q,op,c;
array<int,B>f[N];
auto cal(string s){
	int d=0;
	array<int,B>ans={0};
	for(auto &y:s){
		if(y==':'){
			d++;
			continue;
		}
		int &v=ans[d];
		if('a'<=y && y<='f')v=v*16+(y-'a')+10;
		else v=v*16+(y-'0');
	}
	return ans;
}
auto add_one(array<int,B>y){
	y[n/16-1]++;
	for(int i=B-1;i;--i){
		if(y[i]>=65536){
			y[i]-=65536;
			y[i-1]++;
		}
	}
	return y;
}
int g(array<int,B>v){
	int x=lower_bound(f,f+c,v)-f;
	return x+1;
}
struct ask{
	int op,x;
	string s,t;
	void rd(){
		cin>>op;
		if(op==1)cin>>x;
		cin>>s;
		f[c++]=cal(s);
		if(op==2)t=s;
		else{
			cin>>t;
			f[c++]=cal(t);
			f[c]=add_one(f[c-1]);
			c++;
		}
	}
	void sol(){
		int l=g(cal(s)),r=g(cal(t)),w=seg.cnt(1,l,r);
		int mn=seg.amn(1,l,r),mx=seg.amx(1,l,r);
		if(op==1){
			if(!w || (w<r-l+1 && mn==mx && mn==x)){
				seg.chg(1,l,r,x);
				cout<<"YES"<<endl;
			}
			else{
				cout<<"NO"<<endl;
			}
		}
		else if(op==2){
			cout<<(mn==INF?0:mn)<<endl;
		}
		else{
			cout<<(w==r-l+1 && mn==mx?mn:0)<<endl;
		}
	}
}e[M];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;++i){
		e[i].rd();
	}
	sort(f,f+c);
	c=unique(f,f+c)-f;
	seg.init(c+5);
	for(int i=1;i<=q;++i){
		e[i].sol();
	}
	return 0;
}

运行结果：

文章来源地址https://uudwc.com/A/PmXAO