RMQ问题：区间最值查询
ST表：
- 经过一次预处理后o(1)的离线查询任意区间最值（可重复贡献）
- 利用区间dp的思想
- f[i][j]=从i开始的2的j次方的最值
- f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1];
模板
void ST()
{
for(int i=1;i<=n;i++)
f[i][0]=a[i];
for(int j=1;j<25;j++)//1e6
for(int i=1;i+(1<<j)-1<=n;i++)
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
int k=log(r-l+1)/log(2);
return min(f[l][k],f[r-(1<<k)+1][k]);
}
p2629 好消息，坏消息
题意：给定一段长为n的序列，求存在多少个k使得k~n+1~k-1构成的序列任意前缀和大于等于0
SOl:
用ST表维护最小前缀和
f[i][0]=sum[i];if(query(1,n)>=0) ans++; for(int i=2;i<=n;i++) if(query(i,n)-sum[i-1]>=0&&sum[n]-sum[i-1]+query(1,i-1)>=0) //i到n是否有负数 //再次加上1~i是否有负数 ans++;
***query(i,n)-sum[i-1]//序列中的段前缀和
p7244 章节划分
题意：将长为n的序列分为k段，每段取最大值，最大化所有最大值的最大公因数
SOL:
枚举最大数的约数
int tot=0; for(int i=1;i<=sqrt(extre);i++) if(extre%i==0) { p[++tot]=i; if(i!=extre/i) p[++tot]=extre/i; } sort(p+1,p+tot+1,cmp);
尽可能多分段，若合法的段数大于等于k,则该约数为答案（多余的任意合并不会对答案造成影响）
计算段数：利用递归，每次找到区间最大值，若该数能整除约数则将其单独分段
否则将其归在左右较大的那一边int cal(int l,int r,int mod) { if(l>r||l<1||r>n) return 0; int b=query(l,r); int ll=0,rr=0; if(a[b]%mod==0) return cal(l,b-1,mod)+1+cal(b+1,r,mod); else { if(l>1) ll=cal(b+1,r,mod); if(r<n) rr=cal(l,b-1,mod); return max(ll,rr); } }
ll lca(ll a,ll b) { while(a!=b) { if(a<b) swap(a,b); int x=lower_bound(f,f+61,a)-f; a-=f[x-1]; } return a; }
在begin到end-1位置中进行二分 lower_bound(begin,end,num) 在从小到大的排序中 lower_bound(数组名称，数组大小，x)-数组 第一个大于或等于x的数 upper_bound 第一个大于x的数在从大到小的排序中 lower_bound 第一个小于等于x的数 upper_bound 第一个小于x的数
scanf("%d",&a[i]); a[i+n]=a[i];F[i][i+n-1]//截取环的长度