Test - 7
A 蓝玫瑰
按照题意直接枚举每一种情况，如果满足条件则 \(cnt+1\)，时间复杂度为 \(O(abc)\)，会 \(\text{TLE}\)
scanf("%d%d%d",&a,&b,&c);
for(int i=0;i<=a/2;i++)
{for(int j=0;j<=b;j++){for(int k=c/2;k<=c;k++){if(i==0&&j==0&&k==0) continue; if(i>j||k>j) continue;if(j!=0&&k!=0&&i*j>k*k) continue;if(i>10) continue;cnt++;}}
}
printf("%d\n",cnt);
注意到有一个条件为 \(a'\leq 10\)，第一重循环可以只枚举到 \(\min\{10,\frac a 2\}\)，这样时间复杂度降为 \(O(10bc)\)
scanf("%d%d%d",&a,&b,&c);
for(int i=0;i<=min(a/2,10);i++)
{for(int j=0;j<=b;j++){for(int k=c/2;k<=c;k++){if(i==0&&j==0&&k==0) continue; if(i>j||k>j) continue;if(j!=0&&k!=0&&i*j>k*k) continue;cnt++;}}
}
printf("%d\n",cnt);
B [CSP-J 2021] 分糖果
题意简单，对于 \(L\leq k\leq R\)，求 \(\max k\%n\)
直观想法，直接枚举每一个 \(k\)，记录最大值即可。但是 \(R-L\leq 10^9\) 直接枚举会 \(\text{TLE}\)。
scanf("%d%d%d",&n,&l,&r);
for(int i=l;i<=r;i++)ans=max(ans,i%n);
printf("%d\n",ans);
容易想到，随着 \(k\) 的增加，\(k\%n\) 的值是在 \(0\to n-1\) 循环变化的
那么我们可以先求出 \(L\%n\) 的值，然后可以 \(O(1)\) 判断出从 \(L\) 到 \(R\) 内，\(k\%n\) 的值是否出现过 \(n-1\)
详见代码
scanf("%d%d%d",&n,&l,&r);
int temp=l%n+r-l;
if(temp>=n-1) printf("%d\n",n-1);
else printf("%d\n",temp);
C [CSP-J 2022] 逻辑表达式
一道大模拟，类似于 [NOIP 2013 普及组] 表达式求值，只是计算的规则变多了
但是有一个很巧妙的做法，代码量很小，详见 题解。
D Dynamic Rankings
整体二分（二分的进阶版）一篇讲解博客
基本原理就是：每次询问都需要进行一次完整二分，这中间一定会有很多不变的区间被重复判断，整体二分就是优化掉重复判断的情况
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,M=1e6+10,Mod=998244353,INF=0x3f3f3f3f;inline int lowbit(int x)
{return x&-x;
}struct node
{int op,x,y,z;
}q[3*N],lq[3*N],rq[3*N];bool mycmp(node x,node y)
{return x.op<y.op;
}vector<int> vec;
int n,m,t,a[N],c[3*N],ans[3*N];inline void add(int x,int val)
{while(x<=n){c[x]+=val;x+=lowbit(x);}
}inline int ask(int x)
{int res=0;while(x){res+=c[x];x-=lowbit(x);}return res;
}void solve(int lval,int rval,int st,int ed)
{if(st>ed) return;if(lval==rval){for(int i=st;i<=ed;i++)if(q[i].op>0) ans[q[i].op]=vec[lval-1];return; }int lt=0,rt=0,mid=(lval+rval)>>1;for(int i=st;i<=ed;i++){if(q[i].op==0) {if(q[i].y<=mid) add(q[i].x,1),lq[++lt]=q[i];else rq[++rt]=q[i];}else if(q[i].op==-1){if(q[i].y<=mid) add(q[i].x,-1),lq[++lt]=q[i];else rq[++rt]=q[i]; }else{int temp=ask(q[i].y)-ask(q[i].x-1);if(temp>=q[i].z) lq[++lt]=q[i];else q[i].z-=temp, rq[++rt]=q[i];}}for(int i=st;i<=ed;i++){if(q[i].op==0&&q[i].y<=mid) add(q[i].x,-1);if(q[i].op==-1&&q[i].y<=mid) add(q[i].x,1);}for(int i=1;i<=lt;i++) q[st+i-1]=lq[i];for(int i=1;i<=rt;i++) q[st+lt+i-1]=rq[i];solve(lval,mid,st,st+lt-1);solve(mid+1,rval,st+lt,ed);
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&a[i]);q[++t]={0,i,a[i],0};vec.push_back(a[i]);} for(int i=1;i<=m;i++){char ch;scanf("\n%c",&ch);if(ch=='Q'){int l,r,k;scanf("%d%d%d",&l,&r,&k);q[++t]={i,l,r,k};}else{int x,y;scanf("%d%d",&x,&y);q[++t]={-1,x,a[x],0};q[++t]={0,x,y,0};vec.push_back(y);a[x]=y;}}sort(vec.begin(),vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end());for(int i=1;i<=t;i++)if(q[i].op==0||q[i].op==-1) q[i].y=lower_bound(vec.begin(),vec.end(),q[i].y)-vec.begin()+1;solve(1,vec.size(),1,t);sort(q+1,q+1+t,mycmp); for(int i=1;i<=t;i++)if(q[i].op>0) printf("%d\n",ans[q[i].op]);return 0;
}
E [HEOI2016/TJOI2016] 序列
CDQ分治，一篇讲解博客
这道题是 三维偏序 CDQ 优化 DP
\[pos[i]\leq pos[j] \\
maxval[i] \leq val[j] \\
val[i] \leq minval[j]
\]
第一维 \(pos\) 用 \(sort\) 解决
第二维分治时，用 \(maxval[i]\) 比较，用 \(val[i]\) 存储到 BIT 中
第三维 BIT
详见代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10,M=2e5+10,Mod=998244353,INF=0x3f3f3f3f;inline int lowbit(int x)
{return x&-x;
}struct node
{int pos,minn,maxn,val;
}a[N],b[N],tmp[N];bool mycmp(node x,node y)
{return x.val<y.val;
}int n,m,sze,c[N],f[N],ans;inline void add(int x,int y,bool flag)
{while(x<=sze){if(flag) c[x]=max(c[x],y);else c[x]=0;x+=lowbit(x);}
}inline int ask(int x)
{int res=0;while(x){res=max(res,c[x]);x-=lowbit(x);}return res;
}void cdq(int l,int r)
{if(l==r){f[a[l].pos]=max(f[a[l].pos],1);return;}int mid=(l+r)>>1;cdq(l,mid);for(int i=l;i<=r;i++)b[i]=a[i];sort(b+mid+1,b+r+1,mycmp);int p=l,q=mid+1,k=l;while(p<=mid||q<=r){if(q>r||(p<=mid&&b[p].maxn<=b[q].val))add(b[p].val,f[b[p].pos],1),p++;else f[b[q].pos]=max(f[b[q].pos],ask(b[q].minn)+1),q++;} for(int i=l;i<=mid;i++)add(b[i].val,0,0);cdq(mid+1,r);p=l,q=mid+1,k=l;while(p<=mid||q<=r){if(q>r||(p<=mid&&a[p].maxn<=a[q].maxn)) tmp[k++]=a[p++];else tmp[k++]=a[q++];}for(int i=l;i<=r;i++)a[i]=tmp[i];}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);a[i]={i,x,x,x};sze=max(sze,x);} for(int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);sze=max(sze,y);a[x].minn=min(a[x].minn,y);a[x].maxn=max(a[x].maxn,y);}cdq(1,n);for(int i=1;i<=n;i++)ans=max(ans,f[i]);printf("%d\n",ans);return 0;
}