CCF-CSP真题《202303-5 施肥》思路+python，c++满分题解

悠悠 2023-10-13 12:19 41阅读 0赞

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

--------------------

<table> 
 <tbody> 
  <tr> 
   <td>试题编号：</td> 
   <td>202303-5</td> 
  </tr> 
  <tr> 
   <td>试题名称：</td> 
   <td>施肥</td> 
  </tr> 
  <tr> 
   <td>时间限制：</td> 
   <td>2.0s</td> 
  </tr> 
  <tr> 
   <td>内存限制：</td> 
   <td>1.0GB</td> 
  </tr> 
  <tr> 
   <td>问题描述：</td> 
   <td> <h3>问题描述</h3> <p>春天到了，西西艾弗岛上的&nbsp;n&nbsp;块田地需要施肥了。n&nbsp;块田地编号为&nbsp;1,2,⋯,n，按照编号从小到大的顺序排成一列。</p> <p>为了给田地施肥，顿顿准备了&nbsp;m&nbsp;辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第&nbsp;i&nbsp;辆施肥车<strong>只能恰好</strong>从第&nbsp;li&nbsp;块田地开到第&nbsp;ri&nbsp;块田地，并给编号在&nbsp;li&nbsp;与&nbsp;ri&nbsp;之间的田地（包含&nbsp;li&nbsp;和&nbsp;ri）都施一遍肥。其中&nbsp;1≤li&lt;ri≤n。</p> <p>顿顿希望制定一个施肥的计划。首先，他将选定二元组&nbsp;(L,R)(1≤L&lt;R≤n)，并选择<strong>只</strong>给编号在&nbsp;L,R&nbsp;之间（包含&nbsp;L,R）的田地施肥。接着，他会从使用这&nbsp;m&nbsp;辆施肥车中的一部分（或全部）对田地施肥。他想要保证：<strong>编号在&nbsp;L&nbsp;和&nbsp;R&nbsp;之内的田地至少被某一辆施肥车施了一次肥，且编号范围外的田地都没有被施过肥。</strong></p> <p>现在，他想知道，他能够选择多少种不同的二元组&nbsp;(L,R)&nbsp;作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。</p> <h3>输入格式</h3> <p>从标准输入读入数据。</p> <p>第一行输入两个正整数&nbsp;n,m，表示田地的块数和 施肥车的辆数。数据保证&nbsp;2≤n≤2⋅105,1≤m≤2⋅105。</p> <p>接下来&nbsp;m&nbsp;行，第&nbsp;i&nbsp;行输入两个正整数&nbsp;li,ri，表示第&nbsp;i&nbsp;辆施肥车的施肥范围从第&nbsp;li&nbsp;块田地到第&nbsp;ri&nbsp;块田地。数据保证&nbsp;1≤li&lt;ri≤n。</p> <h3>输出格式</h3> <p>输出到标准输出。</p> <p>输出一个正整数，表示顿顿能够选择多少种不同的二元组&nbsp;(L,R)&nbsp;作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。</p> <h3>样例输入1</h3> 
    <blockquote> 
     <p>4 3<br> 1 2<br> 3 4<br> 2 3</p> 
    </blockquote> <h3>样例输出1</h3> 
    <blockquote> 
     <p>6</p> 
    </blockquote> <h3>样例解释</h3> <p>在这组样例中，顿顿可以选择&nbsp;6&nbsp;种不同的二元组&nbsp;(L,R)。</p> <p>第一种：选择&nbsp;(L,R)=(1,2)，并只选取第&nbsp;1&nbsp;个施肥车施肥。</p> <p>第二种：选择&nbsp;(L,R)=(3,4)，并只选取第&nbsp;2&nbsp;个施肥车施肥。</p> <p>第三种：选择&nbsp;(L,R)=(2,3)，并只选取第&nbsp;3&nbsp;个施肥车施肥。</p> <p>第四种：选择&nbsp;(L,R)=(1,4)，并选取第&nbsp;1&nbsp;个和第&nbsp;2&nbsp;个施肥车施肥。</p> <p>第五种：选择&nbsp;(L,R)=(1,3)，并选取第&nbsp;1&nbsp;个和第&nbsp;3&nbsp;个施肥车施肥。</p> <p>第六种：选择&nbsp;(L,R)=(2,4)，并选取第&nbsp;2&nbsp;个和第&nbsp;3&nbsp;个施肥车施肥。</p> <h3>样例2</h3> <p>见题目目录下的&nbsp;<code>2.in</code>&nbsp;与&nbsp;<code>2.ans</code>。</p> <p>这个样例满足&nbsp;n,m≤18。</p> <h3>样例3</h3> <p>见题目目录下的&nbsp;<code>3.in</code>&nbsp;与&nbsp;<code>3.ans</code>。</p> <p>这个样例满足&nbsp;n,m≤50。</p> <h3>样例4</h3> <p>见题目目录下的&nbsp;<code>4.in</code>&nbsp;与&nbsp;<code>4.ans</code>。</p> <p>这个样例满足&nbsp;n,m≤400。</p> <h3>样例5</h3> <p>见题目目录下的&nbsp;<code>5.in</code>&nbsp;与&nbsp;<code>5.ans</code>。</p> <p>这个样例满足&nbsp;n,m≤3000。</p> <h3>样例6</h3> <p>见题目目录下的&nbsp;<code>6.in</code>&nbsp;与&nbsp;<code>6.ans</code>。</p> <p>这个样例满足特殊性质 A。</p> <h3>样例7</h3> <p>见题目目录下的&nbsp;<code>7.in</code>&nbsp;与&nbsp;<code>7.ans</code>。</p> <p>这个样例满足&nbsp;n,m≤200000。</p> <h3>子任务</h3> 
    <table> 
     <thead> 
      <tr> 
       <th>测试点编号</th> 
       <th>n≤</th> 
       <th>m≤</th> 
       <th>特殊性质</th> 
      </tr> 
     </thead> 
     <tbody> 
      <tr> 
       <td>1</td> 
       <td>18</td> 
       <td>18</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>2</td> 
       <td>18</td> 
       <td>18</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>3</td> 
       <td>18</td> 
       <td>18</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>4</td> 
       <td>50</td> 
       <td>50</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>5</td> 
       <td>50</td> 
       <td>50</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>6</td> 
       <td>400</td> 
       <td>400</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>7</td> 
       <td>400</td> 
       <td>400</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>8</td> 
       <td>3000</td> 
       <td>3000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>9</td> 
       <td>3000</td> 
       <td>3000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>10</td> 
       <td>3000</td> 
       <td>3000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>11</td> 
       <td>3000</td> 
       <td>3000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>12</td> 
       <td>3000</td> 
       <td>3000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>13</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td>A</td> 
      </tr> 
      <tr> 
       <td>14</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td>A</td> 
      </tr> 
      <tr> 
       <td>15</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td>A</td> 
      </tr> 
      <tr> 
       <td>16</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>17</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>18</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>19</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td></td> 
      </tr> 
      <tr> 
       <td>20</td> 
       <td>200000</td> 
       <td>200000</td> 
       <td></td> 
      </tr> 
     </tbody> 
    </table><p>特殊性质 A：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意&nbsp;1≤i&lt;j≤m，li&lt;lj,ri&lt;rj&nbsp;或&nbsp;li&gt;lj,ri&gt;rj。</p> </td> 
  </tr> 
 </tbody> 
</table>

**真题来源：**[施肥][Link 1]

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

**思路来源：**[CCF-CSP认证 202303 500分题解][CCF-CSP_ 202303 500]

**c++满分题解：**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define SZ(x) (int)x.size()
    #define fi first
    #define se second
    const int N=2e5+10,INF=0x3f3f3f3f;
    int n,m,l,r,a[N],b[N];
    vector<int>L[N],R[N];
    ll ans;
    struct segtree{
    	int n;
    	struct node{int l,r,c,mn,mx;}e[N<<2];
    	#define l(p) e[p].l
    	#define r(p) e[p].r
    	#define c(p) e[p].c
    	#define mn(p) e[p].mn
    	#define mx(p) e[p].mx
    	void up(int p){
    		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){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 init(int _n){n=_n;bld(1,1,n);}
    	void chg(int p,int x,int v){
    		if(l(p)==r(p)){mn(p)=min(mn(p),v);mx(p)=max(mx(p),v);return;}
    		int mid=l(p)+r(p)>>1;
    		psd(p);
    		chg(p<<1|(x>mid),x,v);
    		up(p);
    	}
    	void psd(int p){
    		if(c(p)){
    			mn(p<<1)=INF;
    			mx(p<<1)=-INF;
    			c(p<<1)=c(p);
    			mn(p<<1|1)=INF;
    			mx(p<<1|1)=-INF;
    			c(p<<1|1)=c(p);
    			c(p)=0; 
    		}
    	}
    	void del(int p,int ql,int qr){
    		if(ql<=l(p)&&r(p)<=qr){
    			mn(p)=INF;
    			mx(p)=-INF;
    			c(p)=1;
    			return;
    		}
    		psd(p);
    		int mid=l(p)+r(p)>>1;
    		if(ql<=mid)del(p<<1,ql,qr);
    		if(qr>mid)del(p<<1|1,ql,qr);
    		up(p);
    	}
    	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,lseg,rseg;
    struct BitPre{
    	int n,tr[N];
    	void init(int _n){
    		n=_n;
    		memset(tr,0,(n+1)*sizeof(*tr));
    	}
    	void add(int x,int v){
    		for(int i=x;i<=n;i+=i&-i)
    		tr[i]+=v;
    	}
    	int ask(int x){
    		if(x<0)return 0;
    		int ans=0; 
    		for(int i=x;i;i-=i&-i)
    		ans+=tr[i];
    		return ans;
    	}
    }tr;
    bool ok(int x){
    	return x!=INF && x!=-INF;
    }
    bool in(int x,int l,int r){
    	return l<=x && x<=r;
    }
    void cdq(int l,int r){
    	if(l==r)return;
    	int mid=(l+r)/2;
    	cdq(l,mid);cdq(mid+1,r);
    	for(int i=mid;i>=l;--i){
    		a[i]=-INF;b[i]=INF;
    		for(auto &v:L[i]){
    			if(v>r)continue;
    			if(v<=mid)a[i]=max(a[i],v);
    			else b[i]=min(b[i],v);//有无需本侧的情况
    			if(v>=mid)rseg.chg(1,v,i);
    		}
    		if(ok(a[i])){
    			a[i]=max(a[i],seg.amx(1,i,min(mid,a[i]+1)));
    			seg.chg(1,i,a[i]);
    		}
    	}
    	for(int i=mid+1;i<=r;++i){
    		a[i]=INF;b[i]=-INF;
    		for(auto &v:R[i]){
    			if(v<l)continue;
    			if(v>=mid+1)a[i]=min(a[i],v);
    			else b[i]=max(b[i],v);
    			if(v<=mid+1)lseg.chg(1,v,i);
    		}
    		if(ok(a[i])){
    			a[i]=min(a[i],seg.amn(1,max(mid+1,a[i]-1),i));
    			seg.chg(1,i,a[i]);
    		}
    	}
    	vector<array<int,3>>all;
    	for(int i=mid;i>=l;--i){
    		if(ok(a[i])){ // [i,a[i]+1]
    			int v=lseg.amn(1,i,a[i]+1);
    			if(in(v,mid+1,r)){
    				b[i]=min(b[i],v);
    			}
    		}
    		if(in(b[i],mid+1,r))all.push_back({i,0,b[i]});
    	}
    	for(int i=mid+1;i<=r;++i){
    		if(ok(a[i])){ // [a[i]-1,i]
    			int v=rseg.amx(1,a[i]-1,i);
    			if(in(v,l,mid)){
    				b[i]=max(b[i],v);
    			}
    		}
    		if(in(b[i],l,mid))all.push_back({b[i],1,i});
    	}
    	sort(all.begin(),all.end());
    	for(auto &w:all){
    		int op=w[1],ub=w[2];
    		if(op==0)tr.add(ub,1);
    		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]显然成立
    	}
    	seg.del(1,l,r);lseg.del(1,l,r);rseg.del(1,l,r);
    	for(auto &w:all){
    		int op=w[1],ub=w[2];
    		if(op==0)tr.add(ub,-1);
    	}
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	seg.init(n);lseg.init(n);rseg.init(n);tr.init(n);
    	for(int i=1;i<=m;++i){
    		scanf("%d%d",&l,&r);//重复无所谓
    		L[l].push_back(r);
    		R[r].push_back(l);
    	}
    	cdq(1,n);
    	printf("%lld\n",ans);
    	return 0;
    }

**运行结果：**

![856cacbb393742758e11b80dc2fbc08c.png][]

[CCF-CSP]: https://blog.csdn.net/weixin_53919192/article/details/124893395?spm=1001.2014.3001.5502
[Link 1]: http://118.190.20.162/view.page?gpid=T161
[CCF-CSP_ 202303 500]: https://blog.csdn.net/Code92007/article/details/129775241
[856cacbb393742758e11b80dc2fbc08c.png]: https://img-blog.csdnimg.cn/856cacbb393742758e11b80dc2fbc08c.png