想查看其他题的真题及题解的同学可以前往查看：CCF-CSP真题附题解大全
| 试题编号： | 202303-5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 试题名称： | 施肥 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 时间限制： | 2.0s | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 内存限制： | 1.0GB | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 问题描述： | 问题描述春天到了，西西艾弗岛上的 n 块田地需要施肥了。n 块田地编号为 1,2,⋯,n，按照编号从小到大的顺序排成一列。 为了给田地施肥，顿顿准备了 m 辆施肥车。但是由于土地的松软程度不同，施肥车的质量不一，不一定每一辆施肥车都能给每一块田地施肥。其中，第 i 辆施肥车只能恰好从第 li 块田地开到第 ri 块田地，并给编号在 li 与 ri 之间的田地（包含 li 和 ri）都施一遍肥。其中 1≤li 顿顿希望制定一个施肥的计划。首先，他将选定二元组 (L,R)(1≤L 现在，他想知道，他能够选择多少种不同的二元组 (L,R) 作为施肥范围，使得可以选出一部分（或全部）施肥车，完成他的目标。 从标准输入读入数据。 第一行输入两个正整数 n,m，表示田地的块数和 施肥车的辆数。数据保证 2≤n≤2⋅105,1≤m≤2⋅105。 接下来 m 行，第 i 行输入两个正整数 li,ri，表示第 i 辆施肥车的施肥范围从第 li 块田地到第 ri 块田地。数据保证 1≤li 输出到标准输出。 输出一个正整数，表示顿顿能够选择多少种不同的二元组 (L,R) 作为施肥范围，使得他可以选出一部分（或全部）施肥车，完成他的目标。 4 3 6 在这组样例中，顿顿可以选择 6 种不同的二元组 (L,R)。 第一种：选择 (L,R)=(1,2)，并只选取第 1 个施肥车施肥。 第二种：选择 (L,R)=(3,4)，并只选取第 2 个施肥车施肥。 第三种：选择 (L,R)=(2,3)，并只选取第 3 个施肥车施肥。 第四种：选择 (L,R)=(1,4)，并选取第 1 个和第 2 个施肥车施肥。 第五种：选择 (L,R)=(1,3)，并选取第 1 个和第 3 个施肥车施肥。 第六种：选择 (L,R)=(2,4)，并选取第 2 个和第 3 个施肥车施肥。 见题目目录下的 这个样例满足 n,m≤18。 见题目目录下的 这个样例满足 n,m≤50。 见题目目录下的 这个样例满足 n,m≤400。 见题目目录下的 这个样例满足 n,m≤3000。 见题目目录下的 这个样例满足特殊性质 A。 见题目目录下的 这个样例满足 n,m≤200000。 特殊性质 A：保证任意两个施肥车的施肥范围不存在相互包含的关系，也就是说，对任意 1≤i |
真题来源：施肥
感兴趣的同学可以如此编码进去进行练习提交
c++满分题解：
#includeusing namespace std;typedef long long ll;#define SZ(x) (int)x.size()#define fi first#define se secondconst int N=2e5+10,INF=0x3f3f3f3f;int n,m,l,r,a[N],b[N];vectorL[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].mxvoid 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=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>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 运行结果：
来源地址：https://blog.csdn.net/weixin_53919192/article/details/131566317
