2023.3.25~2023.3.26 训练日志
（看眼博客列表）哦从 25 号开始。
模拟赛。
T1 之前写过了。
T2 是求区间直方图最大矩形要求 2log。猫树分治，分成全在左边，全在右边，和跨中线的。只在一边的需要支持撤销的李超树（其实就是主主树）维护一次函数最值（因为暴力写出来还需要把栈全遍历一次找贡献）。
维护两边的就是钦定最小值是哪一个，贡献拆开长成凸包的样子，还需要用树状数组维护一个 corner。
放个参考代码吧。
/*
ã‚ã‚“ã‚ん……ã‚ã‚“ã ã»ãƒ¼ã„ã£â˜†
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
LL read()
{
LL x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x;
}
void write(LL x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef pair<LL,LL> P;
typedef vector<LL> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
#define len(x) (LL(x.size()))
const LL inf=1e18;
struct Line{
LL k,b;
inline Line(LL K=0,LL B=0){k=K,b=B;}
inline LL operator () (LL x) {return k*x+b;}
};
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define Mm LL mid=(l+r)>>1
struct ConvexT{
vector<Line> tr[800005];
void build(LL l,LL r,LL u)
{
tr[u].clear();
if(l==r) return ;
Mm;
build(l,mid,lc(u)),build(mid+1,r,rc(u));
}
inline LL X(Line x){return x.k;}
inline LL Y(Line x){return -x.b;}
inline DB slope(Line x,Line y){return X(x)==X(y)?(Y(x)<Y(y)?-inf:inf):DB(Y(y)-Y(x))/DB(X(y)-X(x));}
void modify(LL l,LL r,LL u,LL p,Line w)
{
while(len(tr[u])>1)
{
if(slope(tr[u][len(tr[u])-2],tr[u][len(tr[u])-1])>=slope(tr[u][len(tr[u])-1],w)) tr[u].pop_back();
else break;
}
tr[u].push_back(w);
if(l==r) return ;
Mm;
p<=mid?modify(l,mid,lc(u),p,w):modify(mid+1,r,rc(u),p,w);
}
LL query(LL l,LL r,LL u,LL x,LL y,LL w)
{
if(y<l || x>r || x>y) return -inf;
if(x<=l && r<=y)
{
LL ret=-inf;
if(!tr[u].empty())
{
LL L=0,R=len(tr[u])-2,p=len(tr[u])-1;
ret=max(ret,tr[u][p](w));
while(L<=R)
{
LL mid=(L+R)>>1;
if(slope(tr[u][mid],tr[u][mid+1])>=w) p=mid,R=mid-1;
else L=mid+1;
}
ret=max(ret,tr[u][p](w));
}
return ret;
}
Mm,ret=-inf;
if(x<=mid) ret=max(ret,query(l,mid,lc(u),x,y,w));
if(mid<y) ret=max(ret,query(mid+1,r,rc(u),x,y,w));
return ret;
}
}ze;
inline LL lowbit(LL x){return x&(-x);}
LL n,q;
struct BinaryIndexedTree1{
LL tr[200005];
void modify(LL x,LL w){for(LL i=x;i<=n;i+=lowbit(i)) tr[i]=max(tr[i],w);}
void clear(LL x){for(LL i=x;i<=n;i+=lowbit(i)) tr[i]=0;}
LL query(LL x){LL ans=0;for(LL i=x;i;i^=lowbit(i)) ans=max(ans,tr[i]);return ans;}
}bit1;
struct BinaryIndexedTree2{
LL tr[200005];
void modify(LL x,LL w){for(LL i=x;i;i^=lowbit(i)) tr[i]=max(tr[i],w);}
void clear(LL x){for(LL i=x;i;i^=lowbit(i)) tr[i]=0;}
LL query(LL x){LL ans=0;for(LL i=x;i<=n;i+=lowbit(i)) ans=max(ans,tr[i]);return ans;}
}bit2;
LL a[200005],b[200005],h[200005];
Poly qry[800005];
LL ql[200005],qr[200005];
void insq(LL l,LL r,LL u,LL x,LL y,LL w)
{
if(l==r) return qry[u].push_back(w);
Mm;
if(x<=mid && mid<y) return qry[u].push_back(w);
x<=mid?insq(l,mid,lc(u),x,y,w):insq(mid+1,r,rc(u),x,y,w);
}
LL ans[200005];
PolyP fqry[200005];
LL rt[200005],cnt;
#undef lc
#undef rc
LL lc[8000005],rc[8000005];
Line tr[8000005];
inline void lctinit(){rt[0]=cnt=lc[0]=rc[0]=0,tr[0]=Line(0,-inf);}
inline LL newnode(){return ++cnt,lc[cnt]=rc[cnt]=0,tr[cnt]=Line(0,-inf),cnt;}
void insseg(LL l,LL r,LL &u,LL v,Line w)
{
u=newnode();
lc[u]=lc[v],rc[u]=rc[v],tr[u]=tr[v];
Mm;
if(w(mid)>tr[u](mid)) swap(tr[u],w);
if(w(l)>tr[u](l)) insseg(l,mid,lc[u],lc[v],w);
if(w(r)>tr[u](r)) insseg(mid+1,r,rc[u],rc[v],w);
}
LL query(LL l,LL r,LL u,LL p)
{
if(!u) return -inf;
Mm,ret=tr[u](p);
if(l==r) return ret;
return p<=mid?max(query(l,mid,lc[u],p),ret):max(query(mid+1,r,rc[u],p),ret);
}
LL stk[200005],top;
LL rem[200005],len;
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
void solve(LL l,LL r,LL u)
{
if(l==r)
{
for(LL id:qry[u]) ans[id]=a[l];
return ;
}
Mm;
if(qry[u].empty())
{
solve(l,mid,lc(u)),solve(mid+1,r,rc(u));
return ;
}
for(LL i=l;i<=r;++i) b[i]=a[i],fqry[i].clear(),rt[i]=0;
for(LL id:qry[u]) fqry[ql[id]].push_back(mp(qr[id],id)),fqry[qr[id]].push_back(mp(ql[id],id));
LL fans;
fans=top=0;
lctinit();
for(LL i=mid+1;i<=r;++i)
{
if(b[i]>b[stk[top]]) stk[++top]=i;
else
{
while(top && b[i]<=b[stk[top]]) fans=max(fans,(i-stk[top])*b[stk[top]]),--top;
b[stk[++top]]=b[i];
}
insseg(mid+1,r,rt[stk[top]],rt[stk[top-1]],Line(b[stk[top]],(-stk[top]+1)*b[stk[top]]));
fans=max(fans,query(mid+1,r,rt[stk[top]],i));
for(P st:fqry[i]) ans[st.second]=max(ans[st.second],fans);
}
fans=top=0;
lctinit();
for(LL i=mid;i>=l;--i)
{
if(b[i]>b[stk[top]]) stk[++top]=i;
else
{
while(top && b[i]<=b[stk[top]]) fans=max(fans,(i-stk[top])*b[stk[top]]),--top;
b[stk[++top]]=b[i];
}
insseg(l,mid,rt[stk[top]],rt[stk[top-1]],Line(-b[stk[top]],(stk[top]+1)*b[stk[top]]));
fans=max(fans,query(l,mid,rt[stk[top]],i));
for(P st:fqry[i]) ans[st.second]=max(ans[st.second],fans);
}
h[mid]=a[mid],h[mid+1]=a[mid+1];
for(LL i=mid-1;i>=l;--i) h[i]=min(a[i],h[i+1]);
for(LL i=mid+2;i<=r;++i) h[i]=min(a[i],h[i-1]);
ze.build(l,mid,1);
for(LL i=l;i<=mid;++i)
{
LL p=i;
while(p<mid && h[p+1]==h[i]) ++p;
ze.modify(l,mid,1,i,Line(h[i],-h[i]*(i-1)));
i=p;
}
len=0;
for(LL i=mid,p=mid;i>=l;--i)
{
while(p<r && h[p+1]>=h[i]) ++p;
if(p>=mid+1)
{
rem[++len]=p;
bit1.modify(p,h[i]*(p-i+1));
}
for(P st:fqry[i])
{
ans[st.second]=max(ans[st.second],bit1.query(st.first));
LL L=i,R=mid,f=i-1;
while(L<=R)
{
LL MID=(L+R)>>1;
if(h[MID]<=h[st.first]) f=MID,L=MID+1;
else R=MID-1;
}
if(i<=f) ans[st.second]=max({ans[st.second],h[i]*(st.first-i+1),ze.query(l,mid,1,i,f,st.first)});
}
}
for(LL i=1;i<=len;++i) bit1.clear(rem[i]);
ze.build(mid+1,r,1);
for(LL i=mid+1;i<=r;++i)
{
LL p=i;
while(p<r && h[p+1]==h[i]) ++p;
ze.modify(mid+1,r,1,p,Line(-h[p],h[p]*(p+1)));
i=p;
}
len=0;
for(LL i=mid+1,p=mid+1;i<=r;++i)
{
while(p>l && h[p-1]>=h[i]) --p;
if(p<=mid)
{
rem[++len]=p;
bit2.modify(p,h[i]*(i-p+1));
}
for(P st:fqry[i])
{
ans[st.second]=max(ans[st.second],bit2.query(st.first));
LL L=mid+1,R=i,f=i+1;
while(L<=R)
{
LL MID=(L+R)>>1;
if(h[MID]<=h[st.first]) R=MID-1,f=MID;
else L=MID+1;
}
if(f<=i) ans[st.second]=max({ans[st.second],h[i]*(i-st.first+1),ze.query(mid+1,r,1,f,i,st.first)});
}
}
for(LL i=1;i<=len;++i) bit2.clear(rem[i]);
solve(l,mid,lc(u)),solve(mid+1,r,rc(u));
}
int main(){
// freopen("8.in","r",stdin);
// freopen("ze.out","w",stdout);
n=read(),q=read();
for(LL i=1;i<=n;++i) a[i]=read();
for(LL i=1;i<=q;++i) ql[i]=read(),qr[i]=read(),insq(1,n,1,ql[i],qr[i],i);
solve(1,n,1);
for(LL i=1;i<=q;++i) write(ans[i]),etr;
return 0;
}T3 很屑，摆。
AGC024E Sequence Growing Hard
一眼鉴定为数最后一个序列。注意到一个最小值只能在后面的都删干净了删。那么枚举最小值第一次出现的位置就可以拆成两个值域有变的子问题。定义
/*
¤ï¤ó¤ï¤ó¡¡¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
int MOD=998244353;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
int ans=1,base=x;
while(p)
{
if(p&1) mul(ans,base);
mul(base,base);
p>>=1;
}
return ans;
}
int n,k;
int f[305][305];
int C[605][605];
int sum[605][605];
int main(){
n=read(),k=read(),MOD=read();
for(int i=0;i<=600;++i)
{
C[i][0]=1;
for(int j=1;j<=i;++j) C[i][j]=Add(C[i-1][j-1],C[i-1][j]);
}
for(int i=0;i<=600;++i) // i-p
{
sum[i][0]=C[0][i];
for(int j=1;j<=600;++j) sum[i][j]=Add(sum[i][j-1],C[j][i]);
}
for(int i=0;i<=k;++i) f[0][i]=1;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=k;++j)
{
for(int p=1;p<=i;++p)
{
add(f[i][j],Mul(Mul(f[p-1][j-1],f[i-p][j]),Sub(sum[i-p][i-1],i==p?0:sum[i-p][i-p-1])));
}
add(f[i][j],f[i][j-1]);
}
}
write(f[n][k]),etr;
return 0;
}UOJ449 喂鸽子
跟百鸽笼那个题差不了多少。一样的 minmax 容斥写上，转移跟百鸽笼一模一样。
瓶颈在背包转移。发现每次乘上的多项式
那么考虑递推，注意到
/*
¤ï¤ó¤ï¤ó¡¡¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
const int MOD=998244353;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
int ans=1,base=x;
while(p)
{
if(p&1) mul(ans,base);
mul(base,base);
p>>=1;
}
return ans;
}
int fac[100005],ifac[100005];
inline int C(int n,int m){return n<m || m<0?0:Mul(fac[n],Mul(ifac[m],ifac[n-m]));}
inline int inv(int x){return Mul(ifac[x],fac[x-1]);}
int n,K;
int g[55][50005],f[55];
int main(){
fac[0]=1;
for(int i=1;i<=100003;++i) fac[i]=Mul(fac[i-1],i);
ifac[100003]=QuickPow(fac[100003]);
for(int i=100002;~i;--i) ifac[i]=Mul(ifac[i+1],i+1);
n=read(),K=read();
g[0][0]=1;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=n*K;++j)
{
int w=g[i-1][j];
if(!w) continue;
for(int k=0;k<K && j+k<=n*K;++k) add(g[i][j+k],Mul(w,C(j+k,k)));
}
}
for(int i=1;i<=n;++i)
{
int c=0;
for(int j=K;j<=i*(K-1)+1;++j)
{
int coef=Mul(C(j-1,K-1),QuickPow(inv(i),j));
mul(coef,i);
mul(coef,g[i-1][j-K]);
add(c,Mul(coef,j));
}
f[i]=Mul(c,Mul(n,inv(i)));
}
int ans=0;
for(int i=1;i<=n;++i)
{
if(i&1) add(ans,Mul(C(n,i),f[i]));
else sub(ans,Mul(C(n,i),f[i]));
}
write(ans),etr;
return 0;
}CF757E Bash Plays with Functions
显然
/*
¤ï¤ó¤ï¤ó¡¡¤ï¤ó¤À¤Û©`¤¤¤Ã¡î
Wonderhoy!
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;
char buf[1<<21],*p1=buf,*p2=buf;
#define getchar() (p1==p2 && (p2=(p1=buf)+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0;
char c=getchar();
while(c<'0' || c>'9') c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0'),c=getchar();
return x;
}
void write(int x)
{
if(x>9) write(x/10);
putchar(x%10+'0');
}
typedef pair<int,int> P;
typedef vector<int> Poly;
typedef vector<P> PolyP;
#define mp make_pair
#define spc putchar(' ')
#define etr putchar('\n')
#define inlp(x,y) putchar(x==y?'\n':' ')
const int MOD=1e9+7;
inline int Add(int u,int v){return u+v>=MOD?u+v-MOD:u+v;}
inline int Sub(int u,int v){return u-v>=0?u-v:u-v+MOD;}
inline int Mul(int u,int v){return LL(u)*LL(v)%MOD;}
inline int add(int &u,int v){return u=Add(u,v);}
inline int sub(int &u,int v){return u=Sub(u,v);}
inline int mul(int &u,int v){return u=Mul(u,v);}
int QuickPow(int x,int p=MOD-2)
{
int ans=1,base=x;
while(p)
{
if(p&1) mul(ans,base);
mul(base,base);
p>>=1;
}
return ans;
}
void Solve();
Poly w[1000005];
bool vis[1000005];
int f[1000005][22];
int main(){
for(int i=2;i<=1000000;++i)
{
if(!vis[i])
{
for(int j=1;j*i<=1000000;++j)
{
vis[j*i]=true;
w[j*i].push_back(i);
}
}
}
for(int i=0;i<=1000000;++i) f[i][0]=1;
for(int j=1;j<=21;++j) f[0][j]=2;
for(int i=1;i<=1000000;++i) for(int j=1;j<=21;++j) f[i][j]=Add(f[i-1][j],f[i][j-1]);
int T=read();
while(T-->0) Solve();
return 0;
}
void Solve()
{
int r=read(),n=read();
int ans=1;
for(int d:w[n])
{
int c=0;
while(n%d==0) ++c,n/=d;
mul(ans,f[r][c]);
}
write(ans),etr;
}27 号没时间写l。