devbox
小小林熬夜学编程
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

CCF-CSP认证 202303 500分题解_ccf教师认证题目

作者：小小林熬夜学编程 | 2024-03-09 17:14:20

赞

踩

ccf教师认证题目

202303-1 田地丈量（矩形面积交）

矩形面积交=x轴线段交长度*y轴线段交长度

线段交长度，相交的时候是min右端点-max左端点，不相交的时候是0

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int n,a,b,ans,x,y,x2,y2;
  4. int f(int l1,int r1,int l,int r){
  5. 	return max(0,min(r1,r)-max(l1,l));
  6. }
  7. int main(){
  8. 	cin>>n>>a>>b;
  9. 	for(int i=1;i<=n;++i){
  10. 		cin>>x>>y>>x2>>y2;
  11. 		ans+=f(0,a,x,x2)*f(0,b,y,y2);
  12. 	}
  13. 	cout<<ans<<endl;
  14. 	return 0;
  15. }

202303-2 垦田计划（二分）

二分最终答案x（x>=k），判断降到x天资源是否够

够的话就往小里二分，否则往大里二分，

当然贪心也可以做，排序之后，把最耗时的天数逐个压低，使得后缀和前面持平

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1e5+10;
  5. int n,m,k,t[N],c[N],mx;
  6. bool ok(int x){
  7. 	ll sum=0;
  8. 	for(int i=1;i<=n;++i){
  9. 		if(t[i]<=x)continue;
  10. 		sum+=1ll*(t[i]-x)*c[i];
  11. 		if(sum>m)return 0;
  12. 	}
  13. 	return 1;
  14. }
  15. int main(){
  16. 	cin>>n>>m>>k;
  17. 	for(int i=1;i<=n;++i){
  18. 		cin>>t[i]>>c[i];
  19. 		mx=max(mx,t[i]);
  20. 	}
  21. 	int l=k,r=mx;
  22. 	while(l<=r){
  23. 		int mid=(l+r)/2;
  24. 		if(ok(mid))r=mid-1;
  25. 		else l=mid+1;
  26. 	}
  27. 	cout<<l<<endl;
  28. 	return 0;
  29. }

202303-3 LDAP（模拟+栈+bitset）

主要是要解决表达式嵌套的问题，

与栈实现计算器时维护一个符号栈、一个数值栈类似

这里维护了两个栈，一个符号栈op，一个bitset集合栈stk，集合求交、或，由bitset完成

当遇到&或|时，将符号压栈；当遇到)时，将bitset压栈；()内正常读取，求bitset即可

当同一个符号对应两个bitset在栈内（num[c]=2）时，将两个bitset运算为一个bitset

其余部分map乱搞，q[i][j]表示DN=i用户的j属性值，

p(i,j)表示i属性值为j的有哪些用户，has[i]表示i属性有哪些用户，

i:j操作时，p[i][j]即为所求；i~j操作时，has[i]内去掉p[i][j]即为所求

to[i]记录了第i个用户对应的DN值，输出时按DN从小到大排序即可

实际耗时3s多，12s绰绰有余

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int,int> P;
  5. const int N=2502;
  6. int n,m,sz,id,k,c,d,x,y,num[N],to[N],f[N];
  7. map<int,int>q[N];
  8. map<P,vector<int>>p;
  9. map<int,vector<int>>has;
  10. char s[N],op[N];
  11. bitset<N>stk[N*2],res;
  12. bitset<N>cal(int l,char x,int r){
  13. 	bitset<N>ans;
  14. 	for(auto &v:p[P(l,r)]){
  15. 		ans.set(v);
  16. 	}
  17. 	if(x=='~'){
  18. 		for(auto &v:has[l]){
  19. 			ans.flip(v);
  20. 		}
  21. 	}
  22. 	return ans;
  23. }
  24. int main(){
  25. 	scanf("%d",&n);
  26. 	for(int i=1;i<=n;++i){
  27. 		scanf("%d%d",&id,&k);
  28. 		to[i]=id;
  29. 		for(int j=1;j<=k;++j){
  30. 			scanf("%d%d",&x,&y);
  31. 			q[i][x]=y;
  32. 			has[x].push_back(i);
  33. 			p[P(x,y)].push_back(i);
  34. 		}
  35. 	}
  36. 	scanf("%d",&m);
  37. 	for(int i=1;i<=m;++i){
  38. 		scanf("%s",s);
  39. 		sz=strlen(s);
  40. 		c=d=0;
  41. 		for(int j=0;j<sz;){
  42. 			if(s[j]=='&' || s[j]=='|'){
  43. 				op[++c]=s[j++];
  44. 			}
  45. 			else if(s[j]=='('){
  46. 				j++;
  47. 			}
  48. 			else if(s[j]==')'){
  49. 				num[c]++;
  50. 				if(num[c]==2){
  51. 					d--;
  52. 					if(op[c]=='&')stk[d]=stk[d]&stk[d+1];
  53. 					else stk[d]=stk[d]|stk[d+1];
  54. 					num[c--]=0;
  55. 				}
  56. 				j++;
  57. 			}
  58. 			else{
  59. 				int cur=j,l=0,r=0;
  60. 				while(cur<sz && (s[cur]!=':' && s[cur]!='~')){
  61. 					l=l*10+(s[cur]-'0');
  62. 					cur++;
  63. 				}
  64. 				char x=s[cur++];
  65. 				while(cur<sz && s[cur]!=')'){
  66. 					r=r*10+(s[cur]-'0');
  67. 					cur++;
  68. 				}
  69. 				stk[++d]=cal(l,x,r);
  70. 				j=cur;
  71. 			}
  72. 		}
  73. 		int e=0;
  74. 		for(int j=1;j<=n;++j){
  75. 			if(stk[d].test(j)){
  76. 				f[++e]=to[j];
  77. 			}
  78. 		}
  79. 		sort(f+1,f+e+1);
  80. 		for(int j=1;j<=e;++j){
  81. 			printf("%d%c",f[j]," \n"[j==e]);
  82. 		}
  83. 		if(!e)puts("");
  84. 	}
  85. 	return 0;
  86. }

202303-4 星际网络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]相邻的情形

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=15e4+10,M=5e4+10,K=170,B=32,INF=0x3f3f3f3f;
  5. struct segtree{
  6. 	int n;
  7. 	struct node{int l,r,v,c,mn,mx;}e[N<<2];
  8. 	#define l(p) e[p].l
  9. 	#define r(p) e[p].r
  10. 	#define v(p) e[p].v
  11. 	#define c(p) e[p].c
  12. 	#define mn(p) e[p].mn
  13. 	#define mx(p) e[p].mx
  14. 	void up(int p){
  15. 		v(p)=v(p<<1)+v(p<<1|1);
  16. 		mn(p)=min(mn(p<<1),mn(p<<1|1));
  17. 		mx(p)=max(mx(p<<1),mx(p<<1|1));
  18. 	}
  19. 	void bld(int p,int l,int r){
  20. 		l(p)=l;r(p)=r;c(p)=0;
  21. 		if(l==r){v(p)=0;mn(p)=INF;mx(p)=-INF;return;}
  22. 		int mid=l+r>>1;
  23. 		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
  24. 		up(p);
  25. 	}
  26. 	void psd(int p){
  27. 		if(c(p)){
  28. 			v(p<<1)=r(p<<1)-l(p<<1)+1;
  29. 			mn(p<<1)=min(mn(p<<1),c(p));
  30. 			mx(p<<1)=max(mx(p<<1),c(p));
  31. 			c(p<<1)=c(p);
  32. 			v(p<<1|1)=r(p<<1|1)-l(p<<1|1)+1;		
  33. 			mn(p<<1|1)=min(mn(p<<1|1),c(p));
  34. 			mx(p<<1|1)=max(mx(p<<1|1),c(p));
  35. 			c(p<<1|1)=c(p);
  36. 			c(p)=0; 
  37. 		}
  38. 	}
  39. 	void init(int _n){n=_n;bld(1,1,n);}
  40. 	void chg(int p,int ql,int qr,int v){
  41. 		if(ql>qr)return;
  42. 		if(ql<=l(p)&&r(p)<=qr){
  43. 			v(p)=r(p)-l(p)+1;
  44. 			mn(p)=min(mn(p),v);
  45. 			mx(p)=max(mx(p),v);
  46. 			c(p)=v;
  47. 			return;
  48. 		}
  49. 		psd(p);
  50. 		int mid=l(p)+r(p)>>1;
  51. 		if(ql<=mid)chg(p<<1,ql,qr,v);
  52. 		if(qr>mid)chg(p<<1|1,ql,qr,v);
  53. 		up(p);
  54. 	}
  55. 	int cnt(int p,int ql,int qr){
  56. 		if(ql<=l(p)&&r(p)<=qr)return v(p);
  57. 		int mid=l(p)+r(p)>>1,res=0;
  58. 		psd(p);
  59. 		if(ql<=mid)res+=cnt(p<<1,ql,qr);
  60. 		if(qr>mid)res+=cnt(p<<1|1,ql,qr);
  61. 		return res;
  62. 	}
  63. 	int amn(int p,int ql,int qr){
  64. 		if(ql<=l(p)&&r(p)<=qr)return mn(p);
  65. 		int mid=l(p)+r(p)>>1,res=INF;
  66. 		psd(p);
  67. 		if(ql<=mid)res=min(res,amn(p<<1,ql,qr));
  68. 		if(qr>mid)res=min(res,amn(p<<1|1,ql,qr));
  69. 		return res;
  70. 	}
  71. 	int amx(int p,int ql,int qr){
  72. 		if(ql<=l(p)&&r(p)<=qr)return mx(p);
  73. 		int mid=l(p)+r(p)>>1,res=-INF;
  74. 		psd(p);
  75. 		if(ql<=mid)res=max(res,amx(p<<1,ql,qr));
  76. 		if(qr>mid)res=max(res,amx(p<<1|1,ql,qr));
  77. 		return res;
  78. 	}
  79. }seg;
  80. int n,m,q,op,c;
  81. array<int,B>f[N];
  82. auto cal(string s){
  83. 	int d=0;
  84. 	array<int,B>ans={0};
  85. 	for(auto &y:s){
  86. 		if(y==':'){
  87. 			d++;
  88. 			continue;
  89. 		}
  90. 		int &v=ans[d];
  91. 		if('a'<=y && y<='f')v=v*16+(y-'a')+10;
  92. 		else v=v*16+(y-'0');
  93. 	}
  94. 	return ans;
  95. }
  96. auto add_one(array<int,B>y){
  97. 	y[n/16-1]++;
  98. 	for(int i=B-1;i;--i){
  99. 		if(y[i]>=65536){
  100. 			y[i]-=65536;
  101. 			y[i-1]++;
  102. 		}
  103. 	}
  104. 	return y;
  105. }
  106. int g(array<int,B>v){
  107. 	int x=lower_bound(f,f+c,v)-f;
  108. 	return x+1;
  109. }
  110. struct ask{
  111. 	int op,x;
  112. 	string s,t;
  113. 	void rd(){
  114. 		cin>>op;
  115. 		if(op==1)cin>>x;
  116. 		cin>>s;
  117. 		f[c++]=cal(s);
  118. 		if(op==2)t=s;
  119. 		else{
  120. 			cin>>t;
  121. 			f[c++]=cal(t);
  122. 			f[c]=add_one(f[c-1]);
  123. 			c++;
  124. 		}
  125. 	}
  126. 	void sol(){
  127. 		int l=g(cal(s)),r=g(cal(t)),w=seg.cnt(1,l,r);
  128. 		int mn=seg.amn(1,l,r),mx=seg.amx(1,l,r);
  129. 		if(op==1){
  130. 			if(!w || (w<r-l+1 && mn==mx && mn==x)){
  131. 				seg.chg(1,l,r,x);
  132. 				cout<<"YES"<<endl;
  133. 			}
  134. 			else{
  135. 				cout<<"NO"<<endl;
  136. 			}
  137. 		}
  138. 		else if(op==2){
  139. 			cout<<(mn==INF?0:mn)<<endl;
  140. 		}
  141. 		else{
  142. 			cout<<(w==r-l+1 && mn==mx?mn:0)<<endl;
  143. 		}
  144. 	}
  145. }e[M];
  146. int main(){
  147. 	ios::sync_with_stdio(0);
  148. 	cin.tie(0);cout.tie(0);
  149. 	cin>>n>>q;
  150. 	for(int i=1;i<=q;++i){
  151. 		e[i].rd();
  152. 	}
  153. 	sort(f,f+c);
  154. 	c=unique(f,f+c)-f;
  155. 	seg.init(c+5);
  156. 	for(int i=1;i<=q;++i){
  157. 		e[i].sol();
  158. 	}
  159. 	return 0;
  160. }

202303-5 施肥（分治+线段树+树状数组）

n,m<=3000乱搞一下就ok，数据范围再小的就不提了

虽然事后发现，n,m<=3000的暴力，我是用的O(nmlogn)，而官解是O(n^2+nm)

特殊性质的分也比较好判断，这样75分就到手了，然后就不会了，就去嫖了官解

这个做法本质是对O(n^2+nm)的暴力套了个分治，

虽然出题人说，两个满分，分别是用李超树和分块过的，感觉很神秘

理解了好久，花若干时间写完代码之后，交上去wa成sb，

对拍拍出来问题之后，交上去又T了，把回收改成区间删除才过

复杂度O((n+m)logm)也就是一个log，但是貌似被我实现成了两个log，感谢出题人不杀之恩

开了四棵线段树，树状数组常数比较小，最后也过了，讲一下中间遇到的各个做法

60分题解（O(n^2+nm)暴力）

按右端点增序枚举，假设当前枚举到的右端点为R，此时只能选右端点<=R的线段

记a[i]为对于i来说，只能选右端点<=R的线段时，能覆盖i的最大的左端点

那么，固定右端点R时，若[L,R]是一组解，一定有对于任意L<=i<=R，L<=a[i]

换言之，为了覆盖[L,R]中间的值，采用的线段，其左端点不能比L更靠左

所以，就可以一边枚举右端点，一边将线段插入，

插入一条线段[i,R]时，涉及到一段区间a值的动态修改，本质是区间[i,R]的a值和i取max

若i<j<=R，a[j]<a[i]，那么，为了覆盖区间[i,R]，实际左端点也需至少取到a[j]的位置

所以，实际计算贡献的时候，需要考虑后缀对当前值的影响，

维护后缀最小值，可以搞个单调栈，也可以逐项维护

后缀的数组，实际是形如1 1 1 3 3 10 10 10 10的分段阶梯数组，

值即为左端点的值，贡献为左端点出现的种类数

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> P;
  4. typedef long long ll;
  5. const int N=2e5+10;
  6. int n,m,l,r,a[N],suf[N];
  7. ll ans;
  8. vector<int>f[N];
  9. int main(){
  10. 	scanf("%d%d",&n,&m);
  11. 	for(int i=1;i<=m;++i){
  12. 		scanf("%d%d",&l,&r);
  13. 		f[r].push_back(l);
  14. 	}
  15. 	for(int i=1;i<=n;++i){
  16. 		for(auto &v:f[i]){
  17. 			for(int j=v;j<=i;++j){
  18. 				a[j]=max(a[j],v);
  19. 			}
  20. 		}
  21. 		suf[i]=a[i];
  22. 		ans+=(suf[i]>0);
  23. 		for(int j=i-1;j>=1;--j){
  24. 			suf[j]=min(suf[j+1],a[j]);
  25. 			if(suf[j]!=suf[j+1] && suf[j])ans++;
  26. 		}
  27. 	}
  28. 	printf("%lld\n",ans);
  29. 	return 0;
  30. }

75分题解（特殊性质）

特殊性质：不存在区间的相互包含关系

就是一堆相交区间，如果把两两相交的区间合并成一个连通块，

则组成若干个连通块，且连通块内是偏序的，

一定可以选一段连续的区间，取到左区间的左端点和右区间的右端点

所以，连通块内有x个区间时，对答案的贡献是x*(x+1)/2

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef pair<int,int> P;
  4. typedef long long ll;
  5. const int N=2e5+10;
  6. int n,m,c,mx;
  7. vector<int>f[N],st[N];
  8. set<int>cur;
  9. map<P,bool>vis;
  10. ll ans,now[N];
  11. struct node{
  12. 	int l,r;
  13. }e[N],x;
  14. bool operator<(node a,node b){
  15. 	return a.r<b.r;
  16. }
  17. int main(){
  18. 	scanf("%d%d",&n,&m);
  19. 	for(int i=1;i<=m;++i){
  20. 		scanf("%d%d",&x.l,&x.r);
  21. 		//e[++c]=x;
  22. 		if(!vis[P(x.l,x.r)])e[++c]=x;
  23. 		vis[P(x.l,x.r)]=1;
  24. 	}
  25. 	m=c;
  26. 	sort(e+1,e+m+1);
  27. 	if(n>3000){
  28. 		for(int i=1;i<=m;){
  29. 			int j=i,mx=e[j].r;
  30. 			while(j+1<=m && e[j+1].l<=mx+1){
  31. 				j++;
  32. 				mx=max(mx,e[j].r);
  33. 			}
  34. 			int sz=j-i+1;
  35. 			ans+=1ll*sz*(sz+1)/2;
  36. 			i=j+1;
  37. 		}
  38. 		printf("%lld\n",ans);
  39. 	}
  40. 	else{
  41. 		for(int i=1;i<=m;++i){
  42. 			st[e[i].l].push_back(e[i].r);
  43. 		}
  44. 		for(int i=1;i<=n;++i){
  45. 			if(st[i].empty())continue;
  46. 			cur.clear();
  47. 			for(auto &v:st[i])cur.insert(v);
  48. 			for(int j=1;j<=m;++j){
  49. 				if(e[j].l<i)continue;
  50. 				if(cur.lower_bound(e[j].l-1)!=cur.end()){
  51. 					int x=*cur.lower_bound(e[j].l-1);
  52. 					if(x<=e[j].r)cur.insert(e[j].r);
  53. 				}
  54. 			}
  55. 			ans+=cur.size();
  56. 		}
  57. 		printf("%lld\n",ans);
  58. 	}
  59. 	return 0;
  60. }

100分题解（分治+线段树+树状数组）

官解里有提到并查集维护区间并，没太想明白，所以开了四棵线段树

分治之后，左区间[l,mid]，右区间[mid+1,r]，

考虑如何统计跨左右区间的答案，即满足l<=L<=mid且mid+1<=R<=r的(L,R)答案

先定义点术语，方便下面描述：

左半区间：[l,mid]

右半区间：[mid+1,r]

左内区间：被完整包含于[l,mid]内的区间

右内区间：被完整包含于[mid+1,r]内的区间

跨域区间：左端点位于[l,mid]，右端点位于[mid+1,r]的区间

从x走到y：存在一个区间[x,y]，或存在若干个区间覆盖在一起，使得左端点是x，右端点y

若(L,R)合法， 换言之，从左端点L走到右端点R，有两种情况，

1. 存在跨域区间[L,R]，一步从L走到R

2. ①L通过左内区间走若干步，走到[l,mid]内最靠右的位置，记为a[L]

②对称后，是相遇问题，R通过右内区间走若干步，走到[mid+1,r]最靠左的位置，记为a[R]

③L通过一个跨域区间（跨域区间左端点在[L,a[L]+1]内），走到[mid+1,r]内最靠左位置，记为b[L]

④R通过一个跨域区间（跨域区间右端点在[a[R]-1,R]内），走到[l,mid]内最靠右位置，记为b[R]

⑤[L,b[L]]和[b[R],R]两个区间，需要满足覆盖在一起后是[L,R]，

因为，b[L]<=mid<mid+1<=b[R]，所以，区间相交是自然满足的 

还需满足b[L]<=R且L<=b[R]，这是一个静态二维数点问题，可用树状数组或cdq分治解决

①-②步用了一棵线段树seg，区间查询，单点更新

左半边递减遍历维护最大值，右半边递增遍历维护最小值

③用了一棵线段树lseg，单点更新，维护左端点在[l,mid+1]内，右端点在右半区间的右端点最小值

④用了一棵线段树rseg，单点更新，维护右端点在[mid,r]内，左端点在左半区间的左端点最大值

[l,mid+1]是因为[L,a[L]+1]，比如，[1,2]和[3,4]也可以覆盖[1,4]；[mid,r]同理

因为③④区间有交集，且和①②维护的信息不同，所以各开了一棵线段树

外层已经是分治了，内层就不cdq分治了，⑤这里采用树状数组的方式解决

形如(L,b[L])和(b[R],R)的二维点对，按第一维排增序，

第一维相同时，先插入再查询，左半边插入到b[L]位置，右半边查询区间[b[R],R]

由于b[R]<=mid<b[L]恒成立，所以直接查sum(R)就可以

此外，注意到1和2的①②③④的情况，都不一定存在，所以需要分别判一下不存在的情况，

当然，如果用INF和-INF配合max min之后，能统一写法的话最好

分治为了使复杂度正确，每次使用完线段树之后需要手动回收，

对树状数组手动-1，撤销操作；对线段树[l,r]段区间删除打标记，

由于维护的是最大最小值，删除后，最大值为-INF，最小值为INF

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define SZ(x) (int)x.size()
  5. #define fi first
  6. #define se second
  7. const int N=2e5+10,INF=0x3f3f3f3f;
  8. int n,m,l,r,a[N],b[N];
  9. vector<int>L[N],R[N];
  10. ll ans;
  11. struct segtree{
  12. 	int n;
  13. 	struct node{int l,r,c,mn,mx;}e[N<<2];
  14. 	#define l(p) e[p].l
  15. 	#define r(p) e[p].r
  16. 	#define c(p) e[p].c
  17. 	#define mn(p) e[p].mn
  18. 	#define mx(p) e[p].mx
  19. 	void up(int p){
  20. 		mn(p)=min(mn(p<<1),mn(p<<1|1));
  21. 		mx(p)=max(mx(p<<1),mx(p<<1|1));
  22. 	}
  23. 	void bld(int p,int l,int r){
  24. 		l(p)=l;r(p)=r;c(p)=0;
  25. 		if(l==r){mn(p)=INF;mx(p)=-INF;return;}
  26. 		int mid=l+r>>1;
  27. 		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
  28. 		up(p);
  29. 	}
  30. 	void init(int _n){n=_n;bld(1,1,n);}
  31. 	void chg(int p,int x,int v){
  32. 		if(l(p)==r(p)){mn(p)=min(mn(p),v);mx(p)=max(mx(p),v);return;}
  33. 		int mid=l(p)+r(p)>>1;
  34. 		psd(p);
  35. 		chg(p<<1|(x>mid),x,v);
  36. 		up(p);
  37. 	}
  38. 	void psd(int p){
  39. 		if(c(p)){
  40. 			mn(p<<1)=INF;
  41. 			mx(p<<1)=-INF;
  42. 			c(p<<1)=c(p);
  43. 			mn(p<<1|1)=INF;
  44. 			mx(p<<1|1)=-INF;
  45. 			c(p<<1|1)=c(p);
  46. 			c(p)=0; 
  47. 		}
  48. 	}
  49. 	void del(int p,int ql,int qr){
  50. 		if(ql<=l(p)&&r(p)<=qr){
  51. 			mn(p)=INF;
  52. 			mx(p)=-INF;
  53. 			c(p)=1;
  54. 			return;
  55. 		}
  56. 		psd(p);
  57. 		int mid=l(p)+r(p)>>1;
  58. 		if(ql<=mid)del(p<<1,ql,qr);
  59. 		if(qr>mid)del(p<<1|1,ql,qr);
  60. 		up(p);
  61. 	}
  62. 	int amn(int p,int ql,int qr){
  63. 		if(ql<=l(p)&&r(p)<=qr)return mn(p);
  64. 		int mid=l(p)+r(p)>>1,res=INF;
  65. 		psd(p);
  66. 		if(ql<=mid)res=min(res,amn(p<<1,ql,qr));
  67. 		if(qr>mid)res=min(res,amn(p<<1|1,ql,qr));
  68. 		return res;
  69. 	}
  70. 	int amx(int p,int ql,int qr){
  71. 		if(ql<=l(p)&&r(p)<=qr)return mx(p);
  72. 		int mid=l(p)+r(p)>>1,res=-INF;
  73. 		psd(p);
  74. 		if(ql<=mid)res=max(res,amx(p<<1,ql,qr));
  75. 		if(qr>mid)res=max(res,amx(p<<1|1,ql,qr));
  76. 		return res;
  77. 	}
  78. }seg,lseg,rseg;
  79. struct BitPre{
  80. 	int n,tr[N];
  81. 	void init(int _n){
  82. 		n=_n;
  83. 		memset(tr,0,(n+1)*sizeof(*tr));
  84. 	}
  85. 	void add(int x,int v){
  86. 		for(int i=x;i<=n;i+=i&-i)
  87. 		tr[i]+=v;
  88. 	}
  89. 	int ask(int x){
  90. 		if(x<0)return 0;
  91. 		int ans=0; 
  92. 		for(int i=x;i;i-=i&-i)
  93. 		ans+=tr[i];
  94. 		return ans;
  95. 	}
  96. }tr;
  97. bool ok(int x){
  98. 	return x!=INF && x!=-INF;
  99. }
  100. bool in(int x,int l,int r){
  101. 	return l<=x && x<=r;
  102. }
  103. void cdq(int l,int r){
  104. 	if(l==r)return;
  105. 	int mid=(l+r)/2;
  106. 	cdq(l,mid);cdq(mid+1,r);
  107. 	for(int i=mid;i>=l;--i){
  108. 		a[i]=-INF;b[i]=INF;
  109. 		for(auto &v:L[i]){
  110. 			if(v>r)continue;
  111. 			if(v<=mid)a[i]=max(a[i],v);
  112. 			else b[i]=min(b[i],v);//有无需本侧的情况
  113. 			if(v>=mid)rseg.chg(1,v,i);
  114. 		}
  115. 		if(ok(a[i])){
  116. 			a[i]=max(a[i],seg.amx(1,i,min(mid,a[i]+1)));
  117. 			seg.chg(1,i,a[i]);
  118. 		}
  119. 	}
  120. 	for(int i=mid+1;i<=r;++i){
  121. 		a[i]=INF;b[i]=-INF;
  122. 		for(auto &v:R[i]){
  123. 			if(v<l)continue;
  124. 			if(v>=mid+1)a[i]=min(a[i],v);
  125. 			else b[i]=max(b[i],v);
  126. 			if(v<=mid+1)lseg.chg(1,v,i);
  127. 		}
  128. 		if(ok(a[i])){
  129. 			a[i]=min(a[i],seg.amn(1,max(mid+1,a[i]-1),i));
  130. 			seg.chg(1,i,a[i]);
  131. 		}
  132. 	}
  133. 	vector<array<int,3>>all;
  134. 	for(int i=mid;i>=l;--i){
  135. 		if(ok(a[i])){ // [i,a[i]+1]
  136. 			int v=lseg.amn(1,i,a[i]+1);
  137. 			if(in(v,mid+1,r)){
  138. 				b[i]=min(b[i],v);
  139. 			}
  140. 		}
  141. 		if(in(b[i],mid+1,r))all.push_back({i,0,b[i]});
  142. 	}
  143. 	for(int i=mid+1;i<=r;++i){
  144. 		if(ok(a[i])){ // [a[i]-1,i]
  145. 			int v=rseg.amx(1,a[i]-1,i);
  146. 			if(in(v,l,mid)){
  147. 				b[i]=max(b[i],v);
  148. 			}
  149. 		}
  150. 		if(in(b[i],l,mid))all.push_back({b[i],1,i});
  151. 	}
  152. 	sort(all.begin(),all.end());
  153. 	for(auto &w:all){
  154. 		int op=w[1],ub=w[2];
  155. 		if(op==0)tr.add(ub,1);
  156. 		else ans+=tr.ask(ub);//左[l,a[l]]右[a[r],r]，满足l<=a[r]<=a[l]+1且a[r]-1<=a[l]<=r，a[l]<=mid<mid+1<=a[r]显然成立
  157. 	}
  158. 	seg.del(1,l,r);lseg.del(1,l,r);rseg.del(1,l,r);
  159. 	for(auto &w:all){
  160. 		int op=w[1],ub=w[2];
  161. 		if(op==0)tr.add(ub,-1);
  162. 	}
  163. }
  164. int main(){
  165. 	scanf("%d%d",&n,&m);
  166. 	seg.init(n);lseg.init(n);rseg.init(n);tr.init(n);
  167. 	for(int i=1;i<=m;++i){
  168. 		scanf("%d%d",&l,&r);//重复无所谓
  169. 		L[l].push_back(r);
  170. 		R[r].push_back(l);
  171. 	}
  172. 	cdq(1,n);
  173. 	printf("%lld\n",ans);
  174. 	return 0;
  175. }
  176. /*
  177. 9 4
  178. 1 4
  179. 1 8
  180. 3 9
  181. 2 5
  182. */

写在最后

感觉数据结构有点多了，写起来比较疲惫

四五题连放两个数据结构，有点不太像之前csp的风格

反观之前的第三题大模拟，本次变成中模拟了

anyway，完结， 撒花！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/215704
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号