[ARC117E] Zero-Sum Ranges 2
考虑分层对前缀和的折线 \(dp\)，发现每个“峰”会往下两边延伸形成一段，然后与另一个峰的相同结构撞上并终止，那么类似于 [ZJOI2012] 波浪 地设计状态 \(dp_{i,j,k}\) 表示已经加入了 \(i\) 个点，当前有 \(j\) 段，匹配个数为 \(k\) 的方案数。转移时枚举下一层新加入 \(p\) 个点，那么这 \(p\) 个点中有 \(p-j\) 个段（每个段应当产生两个点，那么一些段合并起来会比段数 \(+1\)），新增 \(\frac{p\times(p-1)}{2}\) 个匹配，需要带上 \(\binom{p-1}{j}\) 的插板系数（\(j\) 个段有 \(j+1\) 个空，\(j\) 块板子），由于有首位为 \(0\) 的限制，还要拼一下 \(\ge 0\) 和 \(<0\) 的部分
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 65
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,ans,C[N][N],dp[N][N][N*N];
signed main(){
n=read();m=read();
for(int i=0;i<=n+n+1;i++)
for(int j=C[i][0]=1;j<=i;j++)
C[i][j]=C[i-1][j]+C[i-1][j-1];
for(int i=1;i<=n+1;i++)dp[i][i][i*(i-1)/2]=1;
for(int i=1;i<=n+n+1;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<=m;k++)
if(dp[i][j][k])
for(int p=j+1;i+p<=n+n+1;p++)
if(k+p*(p-1)/2<=m)dp[i+p][p-j][k+p*(p-1)/2]+=dp[i][j][k]*C[p-1][j];
for(int i=1;i<=n+n+1;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=m;k++)
ans+=dp[i][j+1][k]*dp[n+n+1-i][j][m-k];
printf("%lld\n",ans+dp[n+n+1][1][m]);
return 0;
}
[ARC121F] Logical Operations on Tree
这种憨题还蠢了一下。考虑先操作 \(\text{AND}\) 会比较优，因为先操作了 \(\text{OR}\) 在之后的 \(\text{AND}\) 会丢失更多的 \(1\)，那么合法当且仅当将全树按 \(\text{OR}\) 断开后，至少存在一个连通块全为 \(1\)，容斥一下变成不存在就很容易 \(dp\) 了：
\[\begin{aligned} dp_{u,0}&=2\times dp_{u,0}\times dp_{v,0}+dp_{u,0}\times dp_{v,1}+dp_{u,1}\times dp_{v,0}\\ dp_{u,1}&=dp_{u,1}\times(dp_{v,0}+dp_{v,1}) \end{aligned} \]答案即 \(2^{2n-1}-dp_{1,0}\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
const int mod=998244353;
struct Edge{int next,to;}edge[N<<1];
int n,dp[N][2];
int head[N],num;
void add(int u,int v){edge[++num]=(Edge){head[u],v};head[u]=num;}
void dfs(int u,int fa){
dp[u][0]=dp[u][1]=1;
for(int i=head[u],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa){
dfs(v,u);
int f[2]={dp[u][0],dp[u][1]};
dp[u][0]=(2ll*f[0]*dp[v][0]%mod+f[0]*dp[v][1]%mod+f[1]*dp[v][0]%mod)%mod;
dp[u][1]=(f[1]*dp[v][0]%mod+f[1]*dp[v][1]%mod)%mod;
}
}
signed main(){
n=read();int pw=1;
for(int i=1;i<=n+n-1;i++)pw=2ll*pw%mod;
for(int i=2,u,v;i<=n;i++)u=read(),v=read(),add(u,v),add(v,u);
dfs(1,0);printf("%lld\n",(pw+mod-dp[1][0])%mod);
return 0;
}
[POI2021-2022R1] Druk
考虑什么样的模板串 \(|S|\) 可能是合法的，首先其必须满足 \([S|n]\vee[S|m]\)，证明可以考虑对网格 \((i+j)\mod |S|\) 染色，每次覆盖必须包含 \(1\sim |S|\)，其次这个串一定是左上角横着或竖着的一条，证明显然
考虑如何判定，发现可以从上到下从左往右贪心地横着覆盖，如果无法横着再竖着覆盖，原因是如果有一个横着覆盖的区间不选择横着覆盖，那么必须用这个串的开头依次填充这个区间，那么模板串必须全相同，这种情况可以简单判断
复杂度为 \(O(d(n)nm)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 1005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
const int mod=1e9+7,base=29;
int n,m,pw[N],F[N][N],G[N][N];
char S[N][N];bool cov[N][N],vis[N][N];
int Substr(int p,int l,int r){return(F[p][r]+mod-F[p][l-1]*pw[r-l+1]%mod)%mod;}
int Strsub(int p,int l,int r){return(G[p][r]+mod-G[p][l-1]*pw[r-l+1]%mod)%mod;}
bool Check(int len,int str){
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)cov[i][j]=vis[i][j]=false;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(cov[i][j])continue;
if(!vis[i][j]&&j+len-1<=m&&Substr(i,j,j+len-1)==str){
bool flg=false;
for(int k=1;k<=len;k++)
if(cov[i][j+k-1])flg=true;
if(flg)
for(int k=1;k<=len;k++){
if(cov[i][j+k-1])break;
vis[i][j+k-1]=true;
}
else{
for(int k=1;k<=len;k++)
cov[i][j+k-1]=true;
continue;
}
}
if(i+len-1<=n&&Strsub(j,i,i+len-1)==str){
for(int k=1;k<=len;k++)cov[i+k-1][j]=true;
continue;
}
return false;
}
return true;
}
bool check(int len){return Check(len,Substr(1,1,len))||Check(len,Strsub(1,1,len));}
signed main(){
n=read();m=read();bool flg=true;
for(int i=1;i<=n;i++)scanf("%s",S[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)flg&=(S[i][j]==S[1][1]);
for(int i=pw[0]=1;i<=max(n,m);i++)pw[i]=pw[i-1]*base%mod;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)F[i][j]=(F[i][j-1]*base%mod+S[i][j]-'0')%mod;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)G[i][j]=(G[i][j-1]*base%mod+S[j][i]-'0')%mod;
static int stk[N<<1],top=0;
for(int i=1;i<=max(n,m);i++)
if((n%i==0||m%i==0)&&(flg||check(i)))stk[++top]=i;
printf("%lld\n",top);
for(int i=1;i<=top;i++)printf("%lld ",stk[i]);
return 0;
}
[POI 2019] Przedszkole
没意思的题，第一个包考虑状压哪些小盆友的颜色相同，枚举子集转移，第二个包考虑对边容斥计算连通块数量，有意思一点的第三个包，首先 \(dp\) 是显然的，考虑枚举环上某相邻的两个点是否同色，不同色即 \(f_n\)，同色可以把这两个点合并，即 \(f_{n-1}\)，而不考虑是否同色即对链染色，方案数 \(m(m-1)^{n-1}\)，于是有 \(f_n=m(m-1)^{n-1}-f_{n-1}\)，把这个显眼的 \(m\) 换一下，变成 \(f_n=(m-1)^n+(m-1)^{n-1}-f_{n-1}\)，移项得到 \((m-1)^n-f_n+(m-1)^{n-1}-f_{n-1}=0\)，那么就可以递推得到通项 \((m-1)^n+(-1)^n(m-1)\)，合并大小相同的环就可以做到单次 \(O(\sqrt n\log n)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
const int mod=1e9+7;
int n,m,q,U[N],V[N];
vector<int>G[N];
inline void add(int&x,int y){(x+=y)>mod?x-=mod:x;}
namespace Math{
int Fac[N],IFac[N];
int qpow(int b,int k){int s=1;while(k){if(k&1)s=s*b%mod;b=b*b%mod;k>>=1;}return s;}
void Init(int n){
for(int i=Fac[0]=1;i<=n;i++)Fac[i]=Fac[i-1]*i%mod;
IFac[n]=qpow(Fac[n],mod-2);
for(int i=n-1;~i;i--)IFac[i]=IFac[i+1]*(i+1)%mod;
}
}
using namespace Math;
namespace DSU{
int fa[N],siz[N];
int Find(int x){return x==fa[x]?x:fa[x]=Find(fa[x]);}
bool Union(int x,int y){
if((x=Find(x))==(y=Find(y)))return false;
if(siz[x]>siz[y])swap(x,y);
siz[fa[x]=y]+=siz[x];
return true;
}
}
using namespace DSU;
namespace SmallN{
int dp[1<<15][16],cnt[1<<15];
int C(int n,int m){
int c=IFac[m];if(n<m)return 0;
for(int i=n;i>=n-m+1;i--)c=c*i%mod;
return c;
}
int main(){
for(int s=1;s<1<<n;s++){
bool flg=true;
cnt[s]=__builtin_popcount(s);
for(int u=0;u<n;u++)
if(((s>>u)&1))
for(auto v:G[u])
if((s>>v)&1)flg=false;
dp[s][1]=flg;
}
for(int s=1;s<1<<n;s++)
for(int t=s;t;t=(t-1)&s)
for(int p=1;p<=cnt[t];p++)add(dp[s][p+1],dp[t][p]*dp[s^t][1]%mod);
while(q--){
int c=read(),ans=0;
for(int i=1;i<=n;i++)
add(ans,C(c,i)*dp[(1<<n)-1][i]%mod);
printf("%lld\n",ans);
}
return 0;
}
}
namespace SmallM{
int dp[1<<24];
int Find(int x){return x==fa[x]?x:Find(fa[x]);}
void dfs(int u,int cnt,int t){
if(u==m)return add(dp[cnt],(t&1)?mod-1:1);
int x=Find(U[u]),y=Find(V[u]);
if(siz[x]>siz[y])swap(x,y);
siz[fa[x]=y]+=siz[x];
dfs(u+1,cnt-(x!=y),t+1);
siz[y]-=siz[fa[x]=x];
dfs(u+1,cnt,t);
}
int main(){
for(int i=0;i<n;i++)siz[fa[i]=i]=1;
dfs(0,n,0);
while(q--){
int c=read(),ans=0;
for(int i=max(0ll,n-(m<<1));i<=n;i++)add(ans,dp[i]*qpow(c,i)%mod);
printf("%lld\n",ans);
}
return 0;
}
}
namespace Circle{
int cnt[N],stk[N],f[N],top;
int main(){
for(int i=0;i<n;i++)siz[fa[i]=i]=1;
for(int i=0;i<m;i++)Union(U[i],V[i]);
for(int i=0;i<n;i++)if(Find(i)==i)cnt[siz[i]]++;
for(int i=1;i<=n;i++)if(cnt[i])stk[++top]=i;
while(q--){
int c=read(),ans=1;
auto F=[&](int x){return(qpow(c-1,x)+mod+((x&1)?-1:1)*(c-1))%mod;};
for(int i=1;i<=top;i++)ans=ans*qpow(F(stk[i]),cnt[stk[i]])%mod;
printf("%lld\n",ans);
}
return 0;
}
}
signed main(){
Init(n=read());m=read();q=read();
for(int i=0;i<m;i++){
U[i]=read()-1;V[i]=read()-1;
G[U[i]].emplace_back(V[i]);
G[V[i]].emplace_back(U[i]);
}
if(n<=15)return SmallN::main();
if(m<=24)return SmallM::main();
return Circle::main();
}
「JOI Open 2019」三级跳
考虑枚举其中两个求最大的第三个，发现左边两个的性质是比较好的，因为左边两个距离越近贡献的范围就越大，那么显然有一个单调性，就是左端只会向后面的前缀 \(\max\) 连边，中间只会让前面的后缀 \(\max\) 连边，于是用一个单调栈就可以解决，然后从右往左扫描线 \(+\) 线段树即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 500005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,q,a[N],ans[N],stk[N],top;
vector<int>line[N];
vector<pair<int,int>>vec[N];
inline void chkmax(int&x,int y){x<y?x=y:x;}
namespace SGT{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
int Max[N<<2],Lis[N<<2],Tag[N<<2];
void Pushup(int k){Max[k]=max(Max[ls],Max[rs]);}
void Update(int k,int v){chkmax(Max[k],Lis[k]+v);chkmax(Tag[k],v);}
void Pushdown(int k){Update(ls,Tag[k]);Update(rs,Tag[k]);Tag[k]=0;}
void Build(int k,int l,int r){
if(l==r)return void(Lis[k]=a[l]);
Build(ls,l,mid);Build(rs,mid+1,r);
Lis[k]=max(Lis[ls],Lis[rs]);
}
void Modify(int k,int l,int r,int x,int y,int z){
if(l>y||r<x||x>y)return;
if(l>=x&&r<=y)return Update(k,z);
if(Tag[k])Pushdown(k);
if(x<=mid)Modify(ls,l,mid,x,y,z);
if(mid<y)Modify(rs,mid+1,r,x,y,z);
Pushup(k);
}
int Query(int k,int l,int r,int x,int y){
if(l>=x&&r<=y)return Max[k];
if(Tag[k])Pushdown(k);
if(y<=mid)return Query(ls,l,mid,x,y);
if(mid<x)return Query(rs,mid+1,r,x,y);
return max(Query(ls,l,mid,x,y),Query(rs,mid+1,r,x,y));
}
}
using namespace SGT;
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
Build(1,1,n);q=read();
for(int i=1,l,r;i<=q;i++)l=read(),r=read(),vec[l].emplace_back(r,i);
for(int i=1;i<=n;i++){
while(top&&a[stk[top]]<=a[i])
line[stk[top--]].emplace_back(i);
if(top)line[stk[top]].emplace_back(i);
stk[++top]=i;
}
for(int i=n;i>=1;i--){
for(auto u:line[i])Modify(1,1,n,(u<<1)-i,n,a[i]+a[u]);
for(auto[u,id]:vec[i])ans[id]=Query(1,1,n,i,u);
}
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
Magic Breeding
发现 \(k\) 非常小，考虑类似于二分转 \(01\) 的套路，对于每种特征，将离散化后 \([1,x]\) 中的生物赋为 \(1\)，\((x,k]\) 中的生物赋为 \(0\)，这样就只有 \(2^k\) 种不同的取值状态，然后对每个生物用 \(\text{bitset}\) 存下哪些取值状态中该生物的特征为 \(1\)，询问时直接扫即可
点击查看代码
#include<bits/stdc++.h>
#define N 100005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,q,tot,a[13][N],b[N][13],sta[N*13];
bitset<1<<12>bi[N<<1];
signed main(){
n=read();m=read();q=read();tot=m;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)a[i][j]=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)b[i][j]=a[j][i];
sort(b[i]+1,b[i]+m+1);
for(int j=1;j<=m;j++){
a[j][i]=lower_bound(b[i]+1,b[i]+m+1,a[j][i])-b[i];
for(int k=1;k<a[j][i];k++)sta[(i-1)*m+k]|=(1<<(j-1));
}
}
for(int s=0;s<1<<m;s++)
for(int i=1;i<=m;i++)bi[i][s]=(s>>(i-1))&1;
while(q--){
int opt=read(),x=read(),y=read();
if(opt==1)bi[++tot]=bi[x]|bi[y];
if(opt==2)bi[++tot]=bi[x]&bi[y];
if(opt==3){
for(int i=(y-1)*m+1;i<=y*m;i++)
if(!bi[x][sta[i]]){
printf("%d\n",b[y][i-(y-1)*m]);
break;
}
}
}
return 0;
}
[PA2021] Wystawa
首先二分答案，考虑 \(dp\)，设 \(dp_{i,j}\) 表示前 \(i\) 个数，用了 \(j\) 次，且当前所有最大子段和均满足条件下最小的最大后缀和，转移：
\[\begin{aligned} dp_{i,j}+a_i&\to dp_{i+1,j+1}\\ dp_{i,j}+b_i&\to dp_{i+1,j} \end{aligned} \]假如我们默认强制 \(a_i\le b_i\)，即 \(a\) 不优的地方不考虑，这个方程显然对 \(j\) 具有凸性，考虑 \(\text{slope trick}\)
发现这个转移相当于先整体向上平移 \(b_i\)，然后与图像移动 \((1,a_i)\) 取 \(\min\)，那么也就是找到第一个斜率 \(>a_i-b_i\) 的位置对后缀移动，然后删掉前缀中不合法的位置，并对后缀取 \(\max\)，这些操作都可以用 set 来维护
点击查看题解
#include<bits/stdc++.h>
#define int long long
#define inf 1e15
#define N 200005
#define mid ((l+r)>>1)
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,a[N],b[N],vis[N];
set<pair<int,int>>s;vector<int>ans;
bool check(int lim){
int sum=0,Max=0;s.clear();ans.clear();
auto ins=[&](pair<int,int>par){s.insert(par);sum+=par.first;};
auto del=[&](pair<int,int>par){s.erase(par);sum-=par.first;};
for(int i=1;i<=n;i++){
Max+=a[i];
if(!vis[i])ins({b[i]-a[i],i});
while(sum+Max>lim)
if(s.empty())return false;
else del(*s.rbegin());
while(Max<0){
if(s.empty()){Max=0;break;}
auto par=*s.begin();del(par);
if(Max+par.first<0)Max+=par.first,ans.emplace_back(par.second);
else par.first+=Max,Max=0,ins(par);
}
}
for(auto u:s)ans.emplace_back(u.second);
return ans.size()>=m;
}
signed main(){
n=read();m=n-read();int cnt=0,rvs=0;
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++)b[i]=read();
for(int i=1;i<=n;i++)cnt+=(a[i]>b[i]);
if(cnt>m){m=n-m;rvs=true;for(int i=1;i<=n;i++)swap(a[i],b[i]);}
for(int i=1;i<=n;i++)if(a[i]>b[i])m--,swap(a[i],b[i]),vis[i]=true;
int l=0,r=inf,res=inf;
while(l<=r)check(mid)?res=mid,r=mid-1:l=mid+1;
check(res);cnt=0;
printf("%lld\n",res);
for(auto u:ans)if(++cnt<=m)vis[u]=true;
for(int i=1;i<=n;i++)putchar((vis[i]^rvs)?'B':'A');
return 0;
}
[AGC023E] Inversions
评价是比较套路了
考虑对每个逆序对算贡献，固定一个位置 \(i\)，为避免算重只计算所有 \(a_j<a_i\) 的贡献
发现未钦定逆序对时的方案数为 \(f(\pi)=\prod\limits_{i=1}^n(x_i-i+1)\)，其中 \(x\) 是 \(a\) 排序后的数组，令排序后第 \(i\) 个数是原数组中下标为 \(b_i\) 的数，即 \(a_{b_i}\)，原数组中第 \(i\) 个数排序后的排名为 \(c_i\)
对 \(j\) 与 \(i\) 的位置关系进行分类讨论：
- 当 \(j<i\) 时，\(a_i\) 比 \(a_j\) 大的部分是无效的，钦定 \(p_i,p_j\) 的方案数为 \(\frac{f(\pi)\times\frac{a_j-c_j}{a_i-c_i+1}\prod\limits_{k\in(c_j,c_i)}\frac{a_{b_k}-k}{a_{b_k}-k+1}}{2}\)，式子表示从原来的方案数中更改 \(i\) 的贡献，\((c_j,c_i)\) 中由于 \(i\) 往前挪贡献要 \(-1\)，而 \(p_j>p_i\) 的方案数占 \(\frac{1}{2}\)
- 当 \(j>i\) 时，考虑计算顺序对数，然后从总方案中减掉，即 \(f(\pi)-\) 上式
先不考虑位置，把贡献系数改写一下，得到 \(\sum\limits_{j\not=i}\frac{f(\pi)}{2\times(a_i-c_i+1)}\times(a_j-c_j)\times \prod\limits_{k\in(c_j,c_i)}\frac{a_{b_k}-k}{a_{b_k}-k+1}\)
考虑扫描线，按排名 \(i\) 从小到大加入每一个数，每次相当于先进行一个全局乘 \(\frac{a_{b_k}-k}{a_{b_k}-k+1}\)，然后把位置 \(b_i\) 赋为 \((a_{b_i}-i)\)，位置关系是容易讨论的，用线段树维护即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
const int mod=1e9+7;
int n,ans,inv[N],a[N],b[N];
inline void add(int&x,int y){(x+=y)>=mod?x-=mod:x;}
inline int Add(int x,int y){return(x+y)>=mod?(x+y-mod):(x+y);}
namespace Fenwick{
int c[N],s;
inline void add(int x,int y){for(;x<=n;x+=x&(-x))c[x]+=y;}
inline int ask(int x){for(s=0;x;x-=x&(-x))s+=c[x];return s;}
inline int ask(int l,int r){return l<=r?ask(r)-ask(l-1):0;}
}
namespace SGT{
#define ls k<<1
#define rs k<<1|1
#define mid ((l+r)>>1)
int Sum[N<<2],Tag[N<<2];
inline void Pushup(int k){Sum[k]=Add(Sum[ls],Sum[rs]);}
inline void Update(int k,int v){(Sum[k]*=v)%=mod;(Tag[k]*=v)%=mod;}
inline void Pushdown(int k){Update(ls,Tag[k]);Update(rs,Tag[k]);Tag[k]=1;}
void Build(int k,int l,int r){
Tag[k]=1;if(l==r)return;
Build(ls,l,mid);Build(rs,mid+1,r);
}
void Modify(int k,int l,int r,int x,int y,int z){
if(l>=x&&r<=y)return Update(k,z);
if(Tag[k]!=1)Pushdown(k);
if(x<=mid)Modify(ls,l,mid,x,y,z);
if(mid<y)Modify(rs,mid+1,r,x,y,z);
Pushup(k);
}
void Insert(int k,int l,int r,int x,int y){
if(l==r)return void(Sum[k]=y);
if(Tag[k]!=1)Pushdown(k);
x<=mid?Insert(ls,l,mid,x,y):Insert(rs,mid+1,r,x,y);
Pushup(k);
}
int Query(int k,int l,int r,int x,int y){
if(l>y||r<x||x>y)return 0;
if(l>=x&&r<=y)return Sum[k];
if(Tag[k]!=1)Pushdown(k);
if(y<=mid)return Query(ls,l,mid,x,y);
if(mid<x)return Query(rs,mid+1,r,x,y);
return Add(Query(ls,l,mid,x,y),Query(rs,mid+1,r,x,y));
}
}
using namespace SGT;
signed main(){
n=read();int coef=inv[1]=1;
for(int i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=1;i<=n;i++)a[b[i]=i]=read();
sort(b+1,b+n+1,[](int x,int y){return a[x]<a[y];});
for(int i=1;i<=n;i++)(coef*=(a[b[i]]-i+1))%=mod;
for(int i=1;i<=n;i++){
int u=b[i],cur=a[u];
int sum=Add(Query(1,1,n,1,u),mod-Query(1,1,n,u+1,n));
(sum*=coef*inv[cur-i+1]%mod*inv[2]%mod)%=mod;
add(sum,coef*Fenwick::ask(u+1,n)%mod);add(ans,sum);
Modify(1,1,n,1,n,(cur-i)*inv[cur-i+1]%mod);
Insert(1,1,n,u,cur-i);Fenwick::add(u,1);
}
printf("%lld\n",ans);
return 0;
}
[ARC125E] Snack
有显然的二分图网络流模型，考虑转化为最小割，发现中间的边与零食是无关的，因此代价是 \(\sum\limits_{i\in cut(s,i)}a_i+|U/cut(s,i)|\sum\limits_{i\notin cut(i,t)}b_i+\sum\limits_{i\in cut(i,t)}c_i\)
第一部分的代价显然只取最小的，考虑对于固定的 \(|U/cut(s,i)|\)，\(b_i,c_i\) 中也会取较小的，因此按 \(\frac{c_i}{b_i}\) 排序扫描线即可得到所有三类贡献
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define inf (int)1e18
#define N 200005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,m,a[N],b[N],c[N],id[N];
signed main(){
n=read();m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=m;i++)b[i]=read();
for(int i=1;i<=m;i++)c[i]=read();
sort(a+1,a+n+1);iota(id+1,id+m+1,1);
sort(id+1,id+m+1,[](int x,int y){return c[x]*b[y]>c[y]*b[x];});
int A=0,B=0,C=0,ans=inf;
for(int i=1;i<=m;i++)C+=c[i];
for(int i=n,j=1;i>=0;i--){
while(j<=m&&b[id[j]]*i<=c[id[j]])B+=b[id[j]],C-=c[id[j]],j++;
A+=a[n-i];ans=min(ans,A+B*i+C);
}
printf("%lld\n",ans);
return 0;
}
「JOI Open 2022」放学路
可以发现 \(\text{K4}\) 一定会导出有解，结合 \(\text{Subtask}\) 中的 \(m-n\le 13\)，容易想到广义串并联图相关结论，缩点的时候将新边的边权赋为两条边之和，叠合重边的时候如果两条边边权不同则导出有解，注意要把 \(1,n\) 之间的点双抠出来跑，严谨证明不会
点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
#define inf (int)1e18
#define N 100005
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
struct Edge{int next,to,val;}edge[N<<2];
int n,m,Path;
int head[N],num;
inline void chkmax(int&x,int y){x<y?x=y:x;}
void add(int u,int v,int w){edge[++num]=(Edge){head[u],v,w};head[u]=num;}
namespace Dijkstra{
int dist[N];bool vis[N];
priority_queue<pair<int,int>>q;
void dijkstra(){
for(int i=1;i<=n;i++)dist[i]=inf;
q.emplace(dist[1]=0,1);
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u])continue;vis[u]=true;
for(int i=head[u],v;i;i=edge[i].next)
if(dist[u]+edge[i].val<dist[v=edge[i].to])
q.emplace(-(dist[v]=dist[u]+edge[i].val),v);
}
Path=dist[n];
}
}
using namespace Dijkstra;
namespace Tarjan{
int dfn[N],low[N],tim,stk[N],top;
vector<int>DCC[N];int tot;
void tarjan(int u){
dfn[u]=low[u]=++tim;stk[++top]=u;
for(int i=head[u],v;i;i=edge[i].next)
if(!dfn[v=edge[i].to]){
tarjan(v);low[u]=min(low[u],low[v]);
if(dfn[u]==low[v]){
DCC[++tot].emplace_back(u);
while(stk[top+1]!=v)
DCC[tot].emplace_back(stk[top--]);
}
}
else low[u]=min(low[u],dfn[v]);
}
}
using namespace Tarjan;
namespace Graph{
__gnu_pbds::gp_hash_table<int,int>G[N];queue<int>q;
int solve(vector<int>vec){
for(auto u:vec)vis[u]=true;
for(int u=1;u<=n;u++)
for(int i=head[u],v;i;i=edge[i].next)
if(vis[u]&&vis[v=edge[i].to]){
if(G[u].find(v)!=G[u].end()){
if(edge[i].val!=G[u][v])G[u][v]=-inf;
else G[u][v]=edge[i].val;
}
else G[u][v]=edge[i].val;
}
for(int i=1;i<=n;i++)
if(G[i].size()<=2)q.emplace(i);
while(!q.empty()){
int u=q.front();q.pop();
if(u==1||u==n)continue;
if(G[u].size()==1){
int v=(*G[u].begin()).first;
G[u].erase(v);G[v].erase(u);
//cout<<"erase "<<u<<" to "<<v<<endl;
if(G[v].size()<=2)q.emplace(v);
}
if(G[u].size()==2){
int x=(*G[u].begin()).first,wx=G[u][x];
int y=(*++G[u].begin()).first,wy=G[u][y];
G[u].erase(x);G[x].erase(u);
G[u].erase(y);G[y].erase(u);
//cout<<"merge "<<u<<" to "<<x<<' '<<y<<endl;
if(G[x].find(y)!=G[x].end()||G[y].find(x)!=G[y].end()){
if(wx+wy!=G[x][y]||wx+wy!=G[y][x])G[x][y]=G[y][x]=-inf;
else G[x][y]=G[y][x]=wx+wy;
}
else G[x][y]=G[y][x]=wx+wy;
if(G[x].size()<=2)q.emplace(x);
if(G[y].size()<=2)q.emplace(y);
}
}
for(int i=2;i<n;i++)if(G[i].size())return puts("1"),0;
if(G[1].find(n)!=G[1].end()||G[n].find(1)!=G[n].end())
return puts(G[1][n]>=0?"0":"1"),0;
return puts("1"),0;
}
}
using namespace Graph;
signed main(){
n=read();m=read();
for(int i=1,u,v,w;i<=m;i++)
u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
dijkstra();add(1,n,Path);add(n,1,Path);
for(int i=1;i<=n;i++)vis[i]=false;
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=tot;i++){
bool flg1=false,flgn=false;
for(auto u:DCC[i]){
if(u==1)flg1=true;
if(u==n)flgn=true;
}
if(flg1&&flgn)return solve(DCC[i]);
}
return 0;
}
[ARC159F] Good Division
感觉 \(\log^2\) 其实好想的，但场上脑子宕机了没发现绝对众数 \(\log\) 的性质
显然一个区间合法当且仅当不存在绝对众数，然后就有一个 \(O(n^2)\) 的 \(dp\)，可以发现这个 \(dp\) 非常地勾引我们去 \(cdq\) 分治，考虑固定左端点，往右扫的过程中至多会有 \(\log n\) 种不同的绝对众数，因为要变出一个新的就必须倍增区间
那么考虑绝对众数和中位数这一类题目的经典套路，将绝对众数设为 \(1\)，其余为 \(-1\)，一个区间合法当且仅当区间和 \(\le 0\)，因此可以扫一遍开个桶用前缀和统计
点击查看代码
#include<bits/stdc++.h>
#define N 1000005
#define mid ((l+r)>>1)
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
const int mod=998244353;
int n,a[N],dp[N],pre[N],suf[N],cnt[N];bool vis[N];
inline void add(int&x,int y){(x+=y)>=mod?x-=mod:x;}
inline int Add(int x,int y){return(x+y)>=mod?x+y-mod:(x+y);}
void divide(int l,int r){
if(l==r)return;
divide(l,mid);
static int stk[64];int top=0,sum=0;
auto ins=[&](int x){if(!vis[x])vis[stk[++top]=x]=true;};
for(int i=mid;i>l;i--)
if((++cnt[a[i]])<<1>mid-i+1)ins(a[i]);
for(int i=mid;i>l;i--)cnt[a[i]]=0;
for(int i=mid+1;i<=r;i++)
if((++cnt[a[i]])<<1>i-mid)ins(a[i]);
for(int i=mid+1;i<=r;i++)cnt[a[i]]=0;
for(int i=l;i<=mid;i++)if(!(i&1))add(sum,dp[i]);
for(int i=mid+1;i<=r;i++)if(!(i&1))add(dp[i],sum);
for(int p=1;p<=top;p++){
pre[mid]=suf[mid+1]=0;
int val=stk[p],dlt=r-l+1;
vector<int>tmp((dlt<<1)+5,0);
for(int i=mid;i>l;i--)suf[i]=suf[i+1]+(a[i]==val?1:-1);
for(int i=mid+1;i<=r;i++)pre[i]=pre[i-1]+(a[i]==val?1:-1);
for(int i=l;i<=mid;i++)
if(!(i&1))add(tmp[suf[i+1]+dlt],dp[i]);
for(int i=dlt<<1;i>=0;i--)add(tmp[i],tmp[i+1]);
for(int i=mid+1;i<=r;i++)
if(!(i&1))add(dp[i],mod-tmp[dlt-pre[i]+1]);
}
for(int i=l;i<=r;i++)vis[a[i]]=false;
divide(mid+1,r);
}
signed main(){
n=read()<<1;dp[0]=1;
for(int i=1;i<=n;i++)a[i]=read();
divide(0,n);printf("%d\n",dp[n]);
return 0;
}
[BalticOI 2016 Day2] 交换
由于有这个顺序限制，一个点操作完之后左右儿子就独立了，手玩一下可以得到四种相对顺序：abc，bac，cab，cba，前两种平凡，只要考虑当根填 c 时左右儿子分别填什么即可
题目给出了优美的二叉树形态，于是所有子树大小的和是 \(O(n\log n)\) 的，总状态数也是 \(O(n\log n)\) 的，加上离散化 \(O(n\log^2 n)\)，下面是一份复杂度可能写的比较假但跑得很快的代码
点击查看代码
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define N 200005
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
int n,a[N];unordered_map<int,int>G[N];
int Find(int u,int val){
if(G[u].find(val)!=G[u].end())return G[u][val];
int ls=u<<1,rs=u<<1|1,pos=u;
if(ls<=n&&rs<=n){
int x=val,y=a[ls],z=a[rs];
if(x<y&&x<z)return G[u][val]=pos;
if(y<x&&y<z)return G[u][val]=Find(ls,x);
if(x<y)return G[u][val]=min(Find(ls,x),Find(rs,x));
return G[u][val]=(Find(ls,y)<Find(rs,y)?Find(rs,x):Find(ls,x));
}
if(ls<=n)return G[u][val]=(val<a[ls]?u:ls);
return G[u][val]=u;
}
void dfs(int u){
int ls=u<<1,rs=u<<1|1;
if(ls<=n&&rs<=n){
int x=a[u],y=a[ls],z=a[rs];
if(x<y&&x<z)return dfs(ls),dfs(rs);
if(y<x&&y<z)return swap(a[u],a[ls]),dfs(ls),dfs(rs);
a[u]=z;
if(x>y)swap(x,y);
int lpos=Find(ls,x),rpos=Find(rs,x);
a[ls]=(lpos<rpos?x:y);dfs(ls);
a[rs]=(lpos<rpos?y:x);dfs(rs);
return;
}
if(ls<=n&&a[u]>a[ls])swap(a[u],a[ls]);
}
signed main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
dfs(1);
for(int i=1;i<=n;i++)printf("%d ",a[i]);
return 0;
}
Ж-function
这里是核仁的奇妙做法，建出反串后缀 \(\text{link}\) 树后答案是 \(\sum\limits_{i=l}^r\min(r-i+1,len_{\text{LCA}(l,i)})\)，考虑点分治，对上子树和下子树进行讨论，当 \(i\) 在下子树的时候，\(\text{LCA}\) 是分治中心或者 \(l\)（\(l\) 在上子树），这一类贡献只需要讨论 \(\min\) 的取值，开个桶二分 \(+\) 前缀和可以实现，然后是上子树对下子树的贡献，这个限制形如 \([l\le i\le r]\vee[r-i+1<len_i]\)，直接二维数点即可，代码很长，但细节非常少
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define N 400005
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
int read(){
int w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-h;ch=getchar();}
while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
return w*h;
}
struct Edge{int next,to;}edge[N<<1];
int n,q,L[N],R[N];char S[N];ll ans[N];
int head[N],num;vector<int>que[N];
void addedge(int u,int v){edge[++num]=(Edge){head[u],v};head[u]=num;}
namespace SAM{
struct Data{int ch[26],len,link;}t[N];int cur,tot;
inline void Extend(char c,int id){
int p=c-'a',u=id;
t[u].len=t[cur].len+1;swap(u,cur);
while(~u&&!t[u].ch[p])t[u].ch[p]=cur,u=t[u].link;
if(u==-1)return;
int v=t[u].ch[p];
if(t[v].len==t[u].len+1)
return void(t[cur].link=v),void();
int w=++tot;
t[w].len=t[u].len+1;
t[w].link=t[v].link;
t[v].link=t[cur].link=w;
for(int i=0;i<26;i++)t[w].ch[i]=t[v].ch[i];
while(~u&&t[u].ch[p]==v)t[u].ch[p]=w,u=t[u].link;
}
}
using namespace SAM;
struct Fenwick{
ll c[N],s;
inline void add(int x,ll y){if(x)for(;x<=n;x+=x&(-x))c[x]+=y;}
inline ll ask(int x){for(s=0;x;x-=x&(-x))s+=c[x];return s;}
inline ll ask(int l,int r){return l<=r?ask(r)-ask(l-1):0;}
}tr[3];
namespace Divide{
#define fir first
#define sec second
int Siz[N],Max[N],core;bool vis[N];
vector<pair<int,int>>Up,Dn,line[N];
void Center(int u,int fa,int cnt,int&core){
Siz[u]=1;Max[u]=0;
for(int i=head[u],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa&&!vis[v])
Center(v,u,cnt,core),Siz[u]+=Siz[v],Max[u]=max(Max[u],Siz[v]);
if((Max[u]=max(Max[u],cnt-Siz[u]))<Max[core])core=u;
}
void dfs(int u,int fa,int len,vector<pair<int,int>>&vec){
vec.emplace_back(u,len=min(len,t[u].len));
for(int i=head[u],v;i;i=edge[i].next)
if((v=edge[i].to)!=fa&&!vis[v])dfs(v,u,len,vec);
}
void Calc(int u){
Up.clear();Dn.clear();
for(int i=head[u],v;i;i=edge[i].next)
if(!vis[v=edge[i].to]){
vector<pair<int,int>>tmp;
dfs(v,u,t[u].len,tmp);
if(tmp[0].second<t[u].len)Up=tmp;
else for(auto u:tmp)Dn.emplace_back(u);
}
Up.emplace_back(0,0);
Dn.emplace_back(0,0);
Dn.emplace_back(u,t[u].len);
sort(Up.begin(),Up.end());
sort(Dn.begin(),Dn.end());
vector<ll>sum(Dn.size(),0);
for(int i=1;i<sum.size();i++)sum[i]=sum[i-1]+Dn[i].fir;
auto UP=[&](pair<int,int>par){
return(int)(lower_bound(Up.begin()+1,Up.end(),par)-Up.begin());
};
auto DN=[&](pair<int,int>par){
return(int)(lower_bound(Dn.begin()+1,Dn.end(),par)-Dn.begin());
};
auto Solve=[&](vector<pair<int,int>>vec,ll t){
for(auto[v,len]:vec){
if(v==tot)continue;
for(auto id:que[v]){
ans[id]+=t*max(0,DN({R[id]-len+1,0})-DN({L[id],0}))*len;
int l=DN({max(L[id],R[id]-len+1),0}),r=DN({R[id]+1,0});
if(l<r)ans[id]+=t*(r-l)*(R[id]+1)-t*(sum[r-1]-sum[l-1]);
}
}
};
Solve(Up,1);Solve(Dn,1);
for(auto[v,len]:Dn)
for(auto id:que[v]){
line[Up[UP({L[id],0})-1].fir].emplace_back(id,-1);
line[Up[UP({R[id]+1,0})-1].fir].emplace_back(id,1);
}
auto ins=[&](int u,int len,int t){
tr[0].add(u+len-1,t*len);tr[1].add(u+len-1,t);tr[2].add(u+len-1,t*u);
};
for(auto[v,len]:Up){
if(v>=1&&v<=n)ins(v,len,1);
for(auto[id,t]:line[v]){
ans[id]+=t*tr[0].ask(R[id]);
ans[id]+=t*(tr[1].ask(R[id]+1,n)*(R[id]+1)-tr[2].ask(R[id]+1,n));
}
line[v].clear();
}
for(auto[v,len]:Up)
if(v>=1&&v<=n)ins(v,len,-1);
for(int i=head[u],v;i;i=edge[i].next)
if(!vis[v=edge[i].to]){
vector<pair<int,int>>tmp;
dfs(v,u,t[u].len,tmp);
if(tmp[0].second>=t[u].len){
Dn=tmp;Dn.emplace_back(0,0);
sort(Dn.begin(),Dn.end());
sum.resize(Dn.size(),0);
for(int i=1;i<sum.size();i++)sum[i]=sum[i-1]+Dn[i].fir;
Solve(Dn,-1);
}
}
}
void divide(int u,int cnt){
Center(u,0,cnt,core=0);vis[u=core]=true;Calc(u);
for(int i=head[u],v;i;i=edge[i].next)
if(!vis[v=edge[i].to])divide(v,Siz[v]>Siz[u]?cnt-Siz[u]:Siz[v]);
}
#undef fir
#undef sec
}
using namespace Divide;
signed main(){
scanf("%s",S+1);t[0].link=-1;
n=strlen(S+1);tot=n;q=read();
for(int i=n;i>=1;i--)Extend(S[i],i);
for(int i=1;i<=tot;i++){
int fa=(t[i].link?t[i].link:(tot+1));
addedge(fa,i);addedge(i,fa);
}
for(int i=1;i<=q;i++)L[i]=read(),R[i]=read(),que[L[i]].emplace_back(i);
Max[0]=(++tot)+1;divide(1,tot);
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}