这套题全是SHOI2015的题，题目描述真是绝了，都是“发明家SHTSC公开了他的新发明”。
这道题最关键的地方就是，要理解题目的单调性，就是对于每个 n ，能切的题数是单调递减的。我们只要二分找到题数等于k的 n 就行了，然后再二分找到最大的题数大于等于k的 n 就是n的最大值了，二分找到最小的题数小于等于 k 的n就是 n 的最小值。注意一点：可能没有满足条件的n，那么输出-1，之所以提这一点，是因为机房里的小伙伴们有的忘了输出-1，有的输出了两个-1，这就很尴尬了。
int n,m; int A[M]; int calc(ll x){ int cnt=0; ll sum=0; for(int i=1;i<=n;i++){ sum+=A[i]; if(sum<0)sum=0; if(sum>=x){ cnt++; sum=0; } } return cnt; } ll sum,mx; int main(){ Rd(n);Rd(m); for(int i=1;i<=n;i++){ Rd(A[i]); sum+=A[i]; mx=max(mx,sum); if(sum<0)sum=0; } sum=0; ll L=1,R=mx,res=-1; while(L<=R){ ll mid=(L+R)>>1; int tmp=calc(mid); if(tmp==m){res=mid;break;} if(tmp>m)L=mid+1; else R=mid-1; } if(~res){ L=1,R=res-1; ll resL=res; while(L<=R){ ll mid=(L+R)>>1; if(calc(mid)<=m){ resL=mid; R=mid-1; }else L=mid+1; } L=res+1,R=mx; ll resR=res; while(L<=R){ ll mid=(L+R)>>1; if(calc(mid)>=m){ resR=mid; L=mid+1; }else R=mid-1; } Pt(resL); putchar(' '); Pt(resR); }else Pt(-1); putchar('\n'); return 0; }这题就是个简单的数据结构题，套个线段树模拟一下就好了，但是我敲炸了。赛后找原因，原本一直以为是不是线段树敲错了，最后发现是1操作的 find 敲错了，就是找到要覆盖的区间位置。一开始是二分找位置，复杂度是 log2n 的，显然会超时，之后改成了直接用线段树查询区间第 k 值得方法，简单很多，而且快很多。
struct Segment_Tree{ struct node{ int L,R,l,r,mx,sum,add; }tree[M<<2]; void up(int p){ int L=tree[p].L,R=tree[p].R,mid=(L R)>>1,add=tree[p].add; int sumL=mid-L 1,sumR=R-mid; int LL=p<<1,RR=p<<1|1; int l=(sumL==tree[LL].l?tree[LL].l tree[RR].l:tree[LL].l); int r=(sumR==tree[RR].r?tree[RR].r tree[LL].r:tree[RR].r); int mx=max(tree[LL].r tree[RR].l,max(tree[LL].mx,tree[RR].mx)); int sum=tree[LL].sum tree[RR].sum; tree[p]=(node){L,R,l,r,mx,sum,add}; } void down(int p){ if(tree[p].add==-1)return; int L=tree[p].L,R=tree[p].R,mid=(L R)>>1,a=tree[p].add; int l=a*(mid-L 1),r=a*(R-mid); tree[p<<1]=(node){L,mid,l,l,l,l,a}; tree[p<<1|1]=(node){mid 1,R,r,r,r,r,a}; tree[p].add=-1; } void build(int L,int R,int p){ tree[p]=(node){L,R,0,0,0,0,-1}; if(L==R)return; int mid=(L R)>>1; build(L,mid,p<<1); build(mid 1,R,p<<1|1); } void update(int L,int R,int a,int p){ if(L<tree[p].L||R>tree[p].R||L>R)return; if(tree[p].L==L&&tree[p].R==R){ int t=a*(R-L 1); tree[p]=(node){L,R,t,t,t,t,a}; return; } down(p); int mid=(tree[p].L tree[p].R)>>1; if(R<=mid)update(L,R,a,p<<1); else if(L>mid)update(L,R,a,p<<1|1); else{update(L,mid,a,p<<1);update(mid 1,R,a,p<<1|1);} up(p); } int query(int L,int R,int p){ if(tree[p].L==L&&tree[p].R==R)return tree[p].mx; down(p); int mid=(tree[p].L tree[p].R)>>1; if(R<=mid)return query(L,R,p<<1); if(L>mid)return query(L,R,p<<1|1); return max(max(query(L,mid,p<<1),query(mid 1,R,p<<1|1)),min(tree[p<<1].r,mid-L 1) min(tree[p<<1|1].l,R-mid)); } int sum(int L,int R,int p){ if(L<tree[p].L||R>tree[p].R||L>R)return 0; if(tree[p].L==L&&tree[p].R==R)return tree[p].sum; down(p); int mid=(tree[p].L tree[p].R)>>1; if(R<=mid)return sum(L,R,p<<1); if(L>mid)return sum(L,R,p<<1|1); return sum(L,mid,p<<1) sum(mid 1,R,p<<1|1); } int find(int k,int p){ if(tree[p].L==tree[p].R)return tree[p].L; down(p); if(tree[p<<1].sum>=k)return find(k,p<<1); return find(k-tree[p<<1].sum,p<<1|1); } }T; int n,m; int tot,res[M]; int main(){ int opr,l0,r0,l1,r1; Rd(n);Rd(m); T.build(1,n,1); for(int i=1;i<=m;i ){ Rd(opr); if(!opr){ Rd(l0);Rd(r0); T.update(l0,r0,1,1); }else if(opr==1){ Rd(l0);Rd(r0);Rd(l1);Rd(r1); int k=r0-l0 1-T.sum(l0,r0,1); T.update(l0,r0,1,1); k =T.sum(1,l1-1,1); r1=min(r1,T.find(k,1)); T.update(l1,r1,0,1); }else{ Rd(l0);Rd(r0); res[ tot]=T.query(l0,r0,1); } } for(int i=1;i<=tot;i )Pt(res[i]),putchar('\n'); return 0; }这题要用到一个很高级的定理，就是传说中的Lucas定理，可以去看看网上的题解，反正都是直接用的。
int C[P][P],sum[P][P]; int c(ll n,ll m){ if(n<P&&m<P)return C[n][m]; return c(n/P,m/P)*C[n%P][m%P]%P; } int calc(ll n,ll k){ if(k<0)return 0; if(n<P&&k<P)return sum[n][k]; return (calc(n/P,k/P-1)*sum[n%P][P-1]+c(n/P,k/P)*sum[n%P][k%P])%P; } void Init(){ for(int i=0;i<P;i++)C[i][0]=sum[i][0]=sum[0][i]=1; for(int i=1;i<P;i++) for(int j=1;j<P;j++){ C[i][j]=(C[i-1][j-1]+C[i-1][j])%P; sum[i][j]=(sum[i][j-1]+C[i][j])%P; } } ll n,k; int T; int main(){ Init(); Rd(T); while(T--){ Rd(n);Rd(k); Pt(calc(n,k)),putchar('\n'); } return 0; }就是T2感觉很亏，这么大一个线段树就毁在了 find 上，好气啊。
