本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-07 21:33:56
前言
T1 数据造水了。谢罪。
T3 数据造水且造错了，最后修了三次才对。谢罪谢罪谢罪。
题目难度可能偏高，这是赛前没有预料到的，比较抱歉。
U606783 缥缈愿
出处：SDSC2025 D1T1 By yixiuge777.
该题在原赛时作为 T1 通过率为 $\frac {15}{48}$。
Sol.5,6 是两种不同的 std。
题意
给出长为 $n$ 的序列 $a_i$，可进行一次区间加 $k$ 操作，求全局 GCD 的最大值。多测，$T\le 3,n\le6\times10^5,a_i,k\le 10^{18}$。
Sol.1
暴力枚举 $[l,r]$ 后暴力计算 GCD。时间复杂度 $O(n^3\log V)$，期望得分 $10$。
Sol.2
预处理前后缀 GCD，然后先枚举 $l$，在枚举 $r$ 的过程中维护中间部分 $a_i+k$ 的 GCD。时间复杂度 $O(n^2\log V)$，期望得分 $30$。
Sol.3
答案较小时可枚举答案 $res$，若存在 $res\nmid a_i$ 且 $res\nmid a_i+k$，则该答案一定不合法。之后每个 $a_i$ 可能必须加 $k$，可能必须不加，也可能两者皆可。找到必须加的第一个和最后一个位置 $[l,r]$，当且仅当该区间内部都能加时答案合法。时间复杂度 $O(nV_r)$，其中 $V_r$ 为答案值域。期望得分 $20$。
Sol.4
当 $a_1=1$ 时，若 $l>1$ 则 GCD 必为 $1$，因此 $l=1$。类似 Sol.2 中的方式枚举 $r$ 即可，$a_n=1$ 的情况是类似的。时间复杂度 $O(n\log V)$，加上 Sol.2 期望得分 $40$，拼上 Sol.3 期望得分 $60$。
Sol.5,6
观察一下答案结构，是前后缀各一段再拼上中间加 $k$ 的形式。又由于前缀 GCD 只有 $O(\log V)$ 段不同取值，猜想每段有用的 $l$ 很少。事实的确如此，若结尾在 $[L,R]$ 内的前缀 GCD 均为 $g$，则 $l=R+1$ 在 $l\in [L+1,R+1]$ 中一定最优。证明考虑最终答案是 $g_L,g_M,g_R$ 三者的 GCD，而这段 $l$ 对应的 $g_L$ 均为 $g$，此时把尽可能少的数划到中间一定更优。同理也只有 $O(\log V)$ 个有用的 $r$。
Sol.5
可以直接类似 Sol.2 枚举所有有用的 $l$，同时只在有用的 $r$ 处统计答案。这里由于 GCD 不变时函数只会运行 $O(1)$ 次，直接维护中间部分 GCD 就是 $O(n+\log V)$ 的。由于统计答案时还要算一次 GCD，总复杂度为 $O(n\log V+\log ^3V)$，期望得分 $100$。
Sol.6
直接暴力枚举所有合法对 $[l,r]$，$g_L$ 和 $g_R$ 容易前后缀预处理。考虑使用 ST 表维护区间 GCD，复杂度 $O(n\log^2V+\log^3 V)$，期望得分 $65$，拼上 Sol.4 期望得分 $75$。但 chb 说这个是均摊 $O(n\log V)$ 的，不懂，反正过不了。
事实上注意到关键点只有 $O(\log V)$ 个，考虑只对这些点建 ST 表，即 $w_i$ 表示两个关键点之间的 GCD。预处理 $w_i$ 只需 $O(n\log V)$ 的复杂度，对 $w$ 建出 ST 表后枚举区间即可，总复杂度 $O(n\log V+\log^3V)$，期望得分 $100$。
U606784 虚构义
出处：SDSC2025 D4T2 By Mikefeng.
该题在原赛时作为 T2 通过率为 $\frac 7{48}$。
Sol.6,7,8 是三种不同的 std，均使用 Prim 求解最小生成树，事实上也并没有卡 $O(qh^2\log h)$ 的 Kruskal。
Sol.9 是 chb 提出的做法，作为补充 std。
题意
$h$ 个点 $n$ 条边，$q$ 次询问 $[l,r]$ 内的边形成的最小生成树。$h\le 10,n,q\le 5\times 10^5$。
Sol.1
暴力对 $O(n)$ 条边跑 Kruskal，时间复杂度 $O(qn\log n)$，期望得分 $15$。
Sol.2
$h=2$ 时求 $w$ 的区间最小值，用 ST 表维护即可，时间复杂度 $O(n\log n+q)$，期望得分 $10$。
Sol.3
由于点数很少，考虑将 Sol.1 中的 Kruskal 改为 Prim。发现一共只有 $\frac{h(h-1)}2\le 45$ 种边，每种边只会用到 $w$ 最小的一条，因此对每种边求出 $w$ 最小值后跑 Prim 即可，下面 Sol.6,7,8, 的最后一步也是如此。时间复杂度 $O(qn+qh^2)$，期望得分 $30$。
Sol.4
对于 $w\le 3$ 的情况，可对每种边再按 $w$ 分类，记录每种 $w$ 的每种边在 $n$ 条边中的位置。之后从小到大枚举 $w$，并试图用这种权值的边更新连通情况，该过程类似 Sol.1。当然也可以用这种方式快速求出每种边的最小值，再跑 Sol.3 中的 Prim。时间复杂度 $O(Vh^2q\log n)$，期望得分 $10$。
Sol.5
直接暴力上线段树，每个节点上记录该区间内最小生成森林的所有边，至多 $h$ 条，合并时用 $2h$ 条边跑最小生成树即可。时间复杂度 $O(n\log nh\lpha(h))$，期望得分不知道，由于常数较大，只能过 $65$。
Sol.6
对 Sol.3 中的取最小值部分用 ST 表进行优化。然而直接维护 $h^2$ 个 ST 表需要 $O(h^2n\log n)$ 的空间，大概只能接受 $n\le 10^5$。因此改为对每个询问维护 $h^2$ 种边的最大值，然后枚举每种边，建出 ST 表后对所有询问更新，空间复杂度优化到 $O(qh^2+n\log n)$。这两种的时间复杂度均为 $O(h^2n\log n+qh^2)$，前者空间爆了，后者期望得分 $100$。
Sol.7
Sol.5 中的 $h^2$ 个 ST 表内其实总共只有 $n$ 个元素，因此可以只建大小为 $cnt$ 的 ST 表，查询前映射过去。由于总元素个数有保证，建 ST 表的总时空复杂度为 $O(n\log n)$。比较暴力的映射方式是记录出现的位置，从而二分出左右端点，时间复杂度 $O(qh^2\log n)$，期望得分 $[65,85]$。
考虑去掉二分，直接对每种边开两个长为 $n$ 的数组，记录每个位置左边第一条和右边第一条该种边的编号即可，空间复杂度 $O(h^2n+n\log n)$，时间复杂度 $O(n\log n+h^2n+qh^2)$，期望得分 $100$。
Sol.8
是另一种优化 Sol.3 的方式。考虑直接对边的编号 $[1,n]$ 分治，每次处理所有跨过中点 $mid$ 的所有询问，再把其余询问递归下去处理。具体地，每种边在 $[l,mid]$ 内处理一个后缀最小值，$[mid+1,r]$ 内处理一个前缀最小值，询问时把前后缀拼起来即可得到每种边的最小权值。空间复杂度 $O(h^2n)$，时间复杂度 $O(h^2n\log n+qh^2)$，期望得分 $100$。由于数据比较水常数小，该做法跑得最快。
Sol.9
是 chb 的做法。将 Sol.8 的分治与 Sol.5 的维护方式结合起来，每次预处理前后缀最小生成树内的边。这时每次只会加一条边，因此不需要重跑 Kruskal，只需要在原树中 DFS 求路径最大值，并试图用新边替代最大边即可，复杂度 $O(h)$。询问时将前后缀 Kruskal 拼起来得到答案。时间复杂度 $O(hn\log n+qh\lpha(h))$，期望得分 $100$。值得一提的是本题的 $\log n>h$，因此本做法算复杂度可能没有 Sol.7 优。
事实上 Sol.8,9 的分治均可以在线，即猫树分治，先把整个分治结构的信息全存下来，再依次处理每个询问。然而空间复杂度会因此变大不少，可能要乘个 $O(\log n)$，这样 Sol.8 空间就炸了。
U606785 短恨歌
出处：可能是原创 By KSCD_.
是从 【数据删除】 的唐氏做法拓展出来的，感觉可能有更优美的做法，欢迎爆标。
【数据删除】
U606786 花草野
出处：SDSC2025 D4T4 By Anonyme.
该题在原赛时作为 T4 通过率为 $\frac 1{48}$，非 AC 最高分为 $20$。
这题在原比赛和本比赛应该都是防 AK 题，但在难写的同时兼具一定的学习价值，感觉会了本题就足够精通单侧递归线段树了，故将其搬来作为 T4。另外建议在学习本题之前做做 P4198，并将代码优化得简洁一些，写本题会好写点。
题意
维护一个环，每个点的贡献为经过的 $a$ 最大值乘 $a_i$，需要支持区间覆盖，区间修改，查询给出 $i,z$，询问从 $i$ 开始走到第一个贡献大于 $z$ 的点。$n,q\le 2\times 10^5$。
Sol.1
考虑所有 $a_i$ 相等的情况，此时每个区域贡献均为 $a_i^2$，因此答案为 $(i+\lfloor\frac x{a_i^2}\rfloor)\bmod n$，期望得分 $10$。
Sol.2
在 $n,q$ 较小时可暴力修改和判断。具体地，先暴力算第一圈能走到哪，若能走完再计算一下 $(\max a_i)(\sum a_i)$，并将剩余的 $x$ 对其取模，即先走完整的若干圈。最后再暴力找最后一圈能走到哪，时间复杂度为 $O(nq)$，拼上 Sol.1 期望得分 $30$。
Sol.3
下文中所有 $p$ 均与题面中相同，表示前面走过的最大值。
考虑使用数据结构维护每个区域的贡献，再在该数据结构上二分。由于某个区域的贡献会受到前面最大值的影响，考虑使用单侧递归线段树。在每个节点上维护区间长度 $l$，$a_i$ 的最大值 $x$ 以及只经过该区间的总贡献 $w=\sum a_ip_i$，区间修改为 $k$ 时有 $x=k,w=lk^2$。
然而区间加只维护这些是不够的，区间加 $k$ 时对 $w$ 拆开 $\sum(p_i+k)(a_i+k)$ 得到 $\sum p_ia_i+kp_i+ka_i+k^2$，因此需要维护 $s=\sum a_i,d=\sum p_i$，即有 $w'=w+kd+ks+lk^2$。$s,d$ 修改为 $k$ 时均会变成 $lk$，区间加时均会增加 $lk$，就实现了所有的区间修改。
因此可以类似普通线段树用两个懒标记维护，注意覆盖标记会清空加标记，区间加时若有覆盖标记则加给覆盖标记，懒标记的下传也是容易的。现在需要实现的是 pushup 合并两个区间的操作，这种贡献与前面值有关的合并需要单侧递归。
具体地，设 $lc,rc$ 为线段树上左右儿子，现需合并 $L=lc_u,R=rc_u$ 的信息到 $u$。显然 $L$ 的信息均不变，而 $R$ 的信息可能会受到 $x_L$ 的影响。考虑再将 $R$ 分成 $lc_R$ 和 $rc_{R}$ 两部分，若 $x_{L}\ge x_{lc_R}$，则 $lc_{R}$ 内均以 $x_{L}$ 为 $p$，容易计算，因此记录 $x_L$ 并递归到 $rc_{R}$ 计算贡献；否则 $x_L<x_{lc_R}$，$x_L$ 一定无法越过 $lc_R$，$rc_R$ 的贡献为其在 $R$ 节点内的贡献，可用 $w_R-w_{lc_R}$ 计算，因此记录 $x_L$ 并递归到 $lc_R$ 计算贡献。
每次只会向左右子树中的一个递归，因此单次 pushup 的复杂度是 $O(\log n)$ 的。实现上只需要写成函数，对某节点传入一个前面经过的最大值 $p$，返回其内部考虑上前面的 $p$ 时的信息。上面其实就是调用 $(R,x_L)$ 的过程，具体可能要对 $d,w$ 分别写函数。
这样就以单次修改 $O(\log^2n)$ 的复杂度维护出了任意区间的信息。询问时考虑在线段树上二分，先求出能走到第一圈的哪个位置，过程中还是要带着前面的最大值，需要将该值传到函数里 $O(\log n)$ 确定当前节点的贡献。后面部分需求出最后一圈走到哪个位置，这里只对 $s$ 二分即可。实现起来细节比较多，还要考虑跨过环的情况，具体看代码。时间复杂度 $O(q\log ^2n)$，期望得分 $100$。事实上有一份把二分写在外面的 $O(q\log ^3n)$ 代码也是可以通过的。
后记
MOCKER44. 好听。SSP 是其外号 烧诗P 的缩写，并非费用流算法。
题解修改了三次，谢罪。
下面是各 std 代码：
U606783 缥缈愿
Sol.5
#include<iostream>
#define ll long long
using namespace std;
const int N=6e5+10;
ll read()
{
ll s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch==-1) w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void print(ll x)
{
if(x<0) putchar('-');
if(x>=10) print(x\/10);
putchar(x%10+'0');
}
int n,m; ll res,X,a[N],b[N],c[N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
void sol()
{
n=read(),X=read(),m=b[0]=c[n+1]=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=gcd(b[i-1],a[i]);
for(int i=n;i>=1;i--) c[i]=gcd(c[i+1],a[i]);
res=b[n];
for(int l=1;l<=n;l++) if(b[l]!=b[l-1])
{
ll tr=b[l-1];
for(int r=l;r<=n;r++)
{
tr=gcd(tr,a[r]+X);
if(c[r]!=c[r+1]) res=max(res,gcd(tr,c[r+1]));
}
}
print(res),putchar('\n');
}
int main()
{
int TT=read();
while(TT--) sol();
return 0;
}
Sol.6
#include<iostream>
#define ll long long
using namespace std;
const int N=6e5+10;
const int P=6e5;
const int K=19+6;
ll read()
{
ll s=0,w=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch==-1) w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void print(ll x)
{
if(x<0) putchar('-');
if(x>=10) print(x\/10);
putchar(x%10+'0');
}
int n,m,p[N],lg[N],po[K]; ll res,X,a[N],b[N],c[N],f[K][N];
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll gcdlr(int l,int r)
{
if(l>r) return 0;
int k=lg[r-l+1];
return gcd(f[k][l],f[k][r-po[k]+1]);
}
void sol()
{
n=read(),X=read(),m=b[0]=c[n+1]=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=gcd(b[i-1],a[i]);
for(int i=n;i>=1;i--) c[i]=gcd(c[i+1],a[i]);
res=b[n];
for(int i=1;i<=n;i++) if(b[i]!=b[i-1]||c[i]!=c[i-1]) p[++m]=i;
p[++m]=n+1;
for(int i=1;i<m;i++)
{
f[0][i]=0;
for(int j=p[i];j<p[i+1];j++) f[0][i]=gcd(f[0][i],a[j]+X);
}
for(int k=1;k<=20;k++) for(int i=1;i+po[k]-1<=m;i++)
f[k][i]=gcd(f[k-1][i],f[k-1][i+po[k-1]]);
for(int i=1;i<=m;i++) for(int j=i+1;j<=m;j++) res=max(res,gcd(gcdlr(i,j-1),gcd(b[p[i]-1],c[p[j]])));
print(res),putchar('\n');
}
int main()
{
int TT=read(); lg[0]=-1,po[0]=1;
for(int i=1;i<=P;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
while(TT--) sol();
return 0;
}
U606784 虚构义
Sol.6
#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],ti[N],tw[N],w[N][M],td[M],po[M],lg[N],tl[N],tr[N];
bool vis[N];
struct STtable
{
int s[M][N];
void build()
{
for(int k=1;po[k]<=n;k++) for(int i=1;i+po[k]-1<=n;i++)
s[k][i]=min(s[k-1][i],s[k-1][i+po[k-1]]);
}
int query(int l,int r)
{
int k=lg[r-l+1];
return min(s[k][l],s[k][r-po[k]+1]);
}
}T;
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>h>>n>>q,po[0]=1,lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
for(int i=1;i<=n;i++)
{
int u,v; cin>>u>>v>>tw[i];
ti[i]=id[min(u,v)][max(u,v)];
}
for(int i=1;i<=q;i++) cin>>tl[i]>>tr[i];
for(int x=1;x<=ct;x++)
{
for(int i=1;i<=n;i++) T.s[0][i]=(ti[i]==x?tw[i]:inf);
T.build();
for(int i=1;i<=q;i++) w[i][x]=T.query(tl[i],tr[i]);
}
for(int i=1;i<=q;i++)
{
ll res=0;
for(int u=1;u<=h;u++) for(int v=u+1;v<=h;v++) d[u][v]=d[v][u]=w[i][id[u][v]];
for(int i=0;i<=h;i++) td[i]=inf,vis[i]=0;
td[1]=0;
for(int _=1;_<=h;_++)
{
int x=0;
for(int i=1;i<=h;i++) if(!vis[i]&&td[i]<td[x]) x=i;
if(!x) {res=-1; break;}
res+=td[x],vis[x]=1;
for(int i=1;i<=h;i++) if(!vis[i]) td[i]=min(td[i],d[x][i]);
}
cout<<res<<'\n';
}
return 0;
}
Sol.7
#include<iostream>
#include<vector>
#define pb push_back
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],td[M];
int po[M],lg[N],tl[M][N],tr[M][N];
bool vis[M];
vector <int> a[M];
struct STtable
{
vector <int> st[M];
void build(int id,int n)
{
for(int i=0;po[i]<=n;i++) st[i].resize(n+2-po[i]);
for(int i=1;i<=n;i++) st[0][i]=a[id][i-1];
for(int k=1;po[k]<=n;k++) for(int i=1;i+po[k]-1<=n;i++)
st[k][i]=min(st[k-1][i],st[k-1][i+po[k-1]]);
}
int query(int l,int r)
{
int k=lg[r-l+1];
return min(st[k][l],st[k][r-po[k]+1]);
}
}T[M];
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>h>>n>>q,po[0]=1,lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
for(int i=1;i<=20;i++) po[i]=(po[i-1]<<1);
for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
for(int i=1;i<=ct;i++) tl[i][n+1]=N,tr[i][0]=-1;
for(int i=1;i<=n;i++)
{
int u,v,w; cin>>u>>v>>w;
if(u>v) swap(u,v);
a[id[u][v]].pb(w),tl[id[u][v]][i]=tr[id[u][v]][i]=a[id[u][v]].size();
}
for(int i=1;i<=ct;i++)
{
for(int j=1;j<=n;j++) if(!tr[i][j]) tr[i][j]=tr[i][j-1];
for(int j=n;j>=1;j--) if(!tl[i][j]) tl[i][j]=tl[i][j+1];
}
for(int i=1;i<=ct;i++) if(a[i].size()) T[i].build(i,a[i].size());
while(q--)
{
int l,r; ll res=0; cin>>l>>r;
for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++)
{
d[i][j]=d[j][i]=inf; int ti=id[i][j];
if(tl[ti][l]<=tr[ti][r]) d[i][j]=d[j][i]=T[ti].query(tl[ti][l],tr[ti][r]);
}
for(int i=0;i<=h;i++) td[i]=inf,vis[i]=0;
td[1]=0;
for(int _=1;_<=h;_++)
{
int x=0;
for(int i=1;i<=h;i++) if(!vis[i]&&td[i]<td[x]) x=i;
if(!x) {res=-1; break;}
res+=td[x],vis[x]=1;
for(int i=1;i<=h;i++) if(!vis[i]) td[i]=min(td[i],d[x][i]);
}
cout<<res<<'\n';
}
return 0;
}
Sol.8
#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int M=45+5;
const int inf=1e9+1e7;
int h,n,q,ct,id[M][M],d[M][M],td[M],ti[N],tw[N],w[N][M]; ll res[N];
bool vis[N];
struct nod{int l,r,id;}a[N],b[N];
void solve(int l,int r,int ql,int qr)
{
if(l>r||ql>qr) return;
if(r-l+1<h-1) {for(int i=ql;i<=qr;i++) res[a[i].id]=-1; return;}
if(l==r) {for(int i=ql;i<=qr;i++) res[a[i].id]=tw[l]; return;}
int mid=((l+r)>>1),pl=ql,pr=qr;
for(int i=mid;i>=l;i--)
{
if(i<mid) for(int j=1;j<=ct;j++) w[i][j]=w[i+1][j];
else for(int j=1;j<=ct;j++) w[i][j]=inf;
w[i][ti[i]]=min(w[i][ti[i]],tw[i]);
}
for(int i=mid+1;i<=r;i++)
{
if(i>mid+1) for(int j=1;j<=ct;j++) w[i][j]=w[i-1][j];
else for(int j=1;j<=ct;j++) w[i][j]=inf;
w[i][ti[i]]=min(w[i][ti[i]],tw[i]);
}
for(int i=ql;i<=qr;i++)
{
if(a[i].l<=mid&&a[i].r>mid)
{
for(int u=1;u<=h;u++) for(int v=u+1;v<=h;v++)
d[u][v]=d[v][u]=min(w[a[i].l][id[u][v]],w[a[i].r][id[u][v]]);
for(int u=0;u<=h;u++) td[u]=inf,vis[u]=0;
td[1]=0;
for(int _=1;_<=h;_++)
{
int x=0;
for(int u=1;u<=h;u++) if(!vis[u]&&td[u]<td[x]) x=u;
if(!x) {res[a[i].id]=-1; break;}
res[a[i].id]+=td[x],vis[x]=1;
for(int v=1;v<=h;v++) if(!vis[v]) td[v]=min(td[v],d[x][v]);
}
}
else if(a[i].r<=mid) b[pl++]=a[i];
else b[pr--]=a[i];
}
for(int i=ql;i<pl;i++) a[i]=b[i];
for(int i=pr+1;i<=qr;i++) a[i]=b[i];
solve(l,mid,ql,pl-1),solve(mid+1,r,pr+1,qr);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>h>>n>>q;
for(int i=1;i<=h;i++) for(int j=i+1;j<=h;j++) id[i][j]=++ct;
for(int i=1;i<=n;i++)
{
int u,v; cin>>u>>v>>tw[i];
ti[i]=id[min(u,v)][max(u,v)];
}
for(int i=1;i<=q;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
solve(1,n,1,q);
for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
return 0;
}
Sol.9
#include<iostream>
#define ll long long
using namespace std;
const int N=5e5+10;
const int H=10+3;
int h,n,q,ce,tu[N],tv[N],tw[N],f[H],s[H],head[H],t[H],fa[H],fi[H]; ll res[N];
int finds(int x) {return f[x]==x?x:f[x]=finds(f[x]);}
bool mg(int x,int y)
{
x=finds(x),y=finds(y);
if(x==y) return false;
if(s[x]>s[y]) swap(x,y);
s[y]+=s[x],f[x]=y; return true;
}
struct ask{int l,r,id;}a[N],b[N];
struct edg{int v,id,nxt;}e[H<<1];
void add(int u,int v,int id) {e[++ce]={v,id,head[u]},head[u]=ce;}
void dfs(int u,int fat)
{
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v,id=e[i].id;
if(v!=fat) fa[v]=u,fi[v]=id,dfs(v,u);
}
}
struct nod
{
int ei[H],c; ll s;
void ins(int id)
{
ce=0;
for(int i=1;i<=h;i++) head[i]=0,fa[i]=0;
for(int i=0;i<c;i++)
{
int ti=ei[i],u=tu[ti],v=tv[ti];
add(u,v,ti),add(v,u,ti),t[i]=ti;
}
int u=tu[id],v=tv[id],w=tw[id],ti=0;
dfs(u,0);
if(fa[v]) while(v!=u)
{
if(tw[fi[v]]>tw[ti]) ti=fi[v];
v=fa[v];
}
if(!ti||w<tw[ti])
{
int tc=c; bool tf=false; c=0;
for(int i=0;i<tc;i++)
{
if(tw[t[i]]>w&&!tf) tf=true,ei[c++]=id;
if(t[i]==ti) continue;
ei[c++]=t[i];
}
if(!tf) ei[c++]=id;
}
}
}c[N];
nod merg(nod a,nod b)
{
nod r; r.s=r.c=0; int ta=0,tb=0;
for(int i=1;i<=h;i++) f[i]=i,s[i]=1;
while(ta<a.c&&tb<b.c)
{
if(r.c==n-1) break;
int x=a.ei[ta];
if(tw[b.ei[tb]]<tw[x]) x=b.ei[tb],tb++;
else ta++;
if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
}
while(r.c<h-1&&ta<a.c)
{
int x=a.ei[ta]; ta++;
if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
}
while(r.c<h-1&&tb<b.c)
{
int x=b.ei[tb]; tb++;
if(mg(tu[x],tv[x])) r.ei[r.c++]=x,r.s+=tw[x];
}
return r;
}
void solve(int l,int r,int ql,int qr)
{
if(l>r||ql>qr) return;
if(r-l+1<h-1) {for(int i=ql;i<=qr;i++) res[a[i].id]=-1; return;}
if(l==r) {for(int i=ql;i<=qr;i++) res[a[i].id]=tw[l]; return;}
int mid=((l+r)>>1),pl=ql,pr=qr;
for(int i=mid;i>=l;i--)
{
if(i<mid) c[i]=c[i+1];
else c[i].s=c[i].c=0;
c[i].ins(i);
}
for(int i=mid+1;i<=r;i++)
{
if(i>mid+1) c[i]=c[i-1];
else c[i].s=c[i].c=0;
c[i].ins(i);
}
for(int i=ql;i<=qr;i++)
{
int l=a[i].l,r=a[i].r,ti=a[i].id;
if(l<=mid&&mid<r)
{
nod tr=merg(c[l],c[r]);
res[ti]=(tr.c==h-1?tr.s:-1);
}
else if(r<=mid) b[pl++]=a[i];
else b[pr--]=a[i];
}
for(int i=ql;i<pl;i++) a[i]=b[i];
for(int i=pr+1;i<=qr;i++) a[i]=b[i];
solve(l,mid,ql,pl-1),solve(mid+1,r,pr+1,qr);
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>h>>n>>q;
for(int i=1;i<=n;i++) cin>>tu[i]>>tv[i]>>tw[i];
for(int i=1;i<=q;i++) cin>>a[i].l>>a[i].r,a[i].id=i;
solve(1,n,1,q);
for(int i=1;i<=q;i++) cout<<res[i]<<'\n';
return 0;
}
U606785 短恨歌
【数据删除】
U606786 花草野
Sol.3
#include<iostream>
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
#define lc (u<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define Lc lc,l,mid
#define Rc rc,mid+1,r
#define U 1,0,n-1
using namespace std;
const int N=2e5+10;
int n,q;
struct nod{ll x,s,d,w;};
struct sgmtt
{
nod w[N<<2]; int t[N<<2],c[N<<2],s[N<<2];
void pt(int u,ll x,bool f)
{
if(f) t[u]=0,c[u]=x,w[u]={x,s[u]*x,s[u]*x,s[u]*x*x};
else
{
t[u]+=x,w[u].w+=(w[u].d+w[u].s+s[u]*x)*x;
w[u].x+=x,w[u].s+=s[u]*x,w[u].d+=s[u]*x;
}
}
void Pd(int u)
{
if(c[u]) pt(lc,c[u],1),pt(rc,c[u],1),c[u]=0;
if(t[u]) pt(lc,t[u],0),pt(rc,t[u],0),t[u]=0;
}
ll Ua(ll pre,int u)
{
if(pre>=w[u].x) return pre*w[u].s;
if(s[u]==1) return w[u].w;
Pd(u);
return w[lc].x<=pre?w[lc].s*pre+Ua(pre,rc):Ua(pre,lc)+w[u].w-w[lc].w;
}
ll Ub(ll pre,int u)
{
if(pre>=w[u].x) return pre*s[u];
if(s[u]==1) return w[u].x;
Pd(u);
return w[lc].x<=pre?s[lc]*pre+Ub(pre,rc):Ub(pre,lc)+w[u].d-w[lc].d;
}
void Pu(int u)
{
w[u].s=w[lc].s+w[rc].s,w[u].x=max(w[lc].x,w[rc].x);
w[u].w=w[lc].w+Ua(w[lc].x,rc),w[u].d=w[lc].d+Ub(w[lc].x,rc);
}
void B(int u,int l,int r)
{
s[u]=r-l+1;
if(l==r) {ll x; cin>>x; w[u]={x,x,x,x*x}; return;}
B(Lc),B(Rc),Pu(u);
}
void C(int u,int l,int r,int L,int R,int x,bool f)
{
if(l>=L&&r<=R) {pt(u,x,f); return;}
Pd(u);
if(L<=mid) C(Lc,L,R,x,f);
if(R>mid) C(Rc,L,R,x,f);
Pu(u);
}
nod Q(int u,int l,int r,int L,int R,ll pre)
{
if(l>=L&&r<=R) {nod tr=w[u]; tr.w=Ua(pre,u); return tr;}
Pd(u); nod tl={0,0,0,0},tr=tl;
if(L<=mid) tl=Q(Lc,L,R,pre);
if(R>mid) tr=Q(Rc,L,R,max(pre,tl.x));
return {max(tl.x,tr.x),tl.s+tr.s,tl.d+tr.d,tl.w+tr.w};
}
nod Pa(int u,int l,int r,int st,ll x,ll pre)
{
if(r<st) return {0,-1,0,0};
if(l==r) return {w[u].x,x<=w[u].x*max(pre,w[u].x)?l:-1,0,w[u].x*max(pre,w[u].x)};
Pd(u);
if(l>=st)
{
ll uw=Ua(pre,u),lw=Ua(pre,lc);
if(x>uw) return {w[u].x,-1,0,uw};
return x<=lw?Pa(Lc,st,x,pre):Pa(Rc,st,x-lw,max(pre,w[lc].x));
}
nod rl=Pa(Lc,st,x,pre),rr;
if(rl.s!=-1) return rl;
rr=Pa(Rc,st,x-rl.w,max(pre,rl.x));
if(rr.s!=-1) return rr;
rr.x=max(rr.x,rl.x),rr.w+=rl.w; return rr;
}
pll Pb(int u,int l,int r,int st,ll x)
{
if(r<st) return {-1,0};
if(l==r) return {x<=w[u].s?l:-1,w[u].s};
Pd(u);
if(l>=st)
{
if(x>w[u].s) return {-1,w[u].s};
return x<=w[lc].s?Pb(Lc,st,x):Pb(Rc,st,x-w[lc].s);
}
pll rl=Pb(Lc,st,x),rr;
if(rl.fi!=-1) return rl;
rr=Pb(Rc,st,x-rl.se);
if(rr.fi!=-1) return rr;
rr.se+=rl.se; return rr;
}
}T;
int S()
{
ll s,x,d=T.w[1].w; cin>>s>>x,x++;
if(s)
{
nod A=T.Q(U,s,n-1,0),B=T.Q(U,0,s-1,A.x);
d=A.w+B.w;
}
if(x<=d)
{
nod A=T.Pa(U,s,x,0);
return A.s==-1?T.Pa(U,0,x-A.w,A.x).s:A.s;
}
else
{
int B=T.w[1].x; x=(x-d)%(T.w[1].s*B);
ll m=1ll*T.Q(U,s,n-1,0).s*B;
if(x<=m) return T.Pb(U,s,(x+B-1)\/B).fi;
else return T.Pb(U,0,(x-m+B-1)\/B).fi;
}
}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>q,T.B(U);
while(q--)
{
char c; cin>>c;
if(c=='Q') cout<<S()<<'\n';
else
{
int l,r,x; cin>>l>>r>>x;
if(l<=r) T.C(U,l,r,x,c=='R');
else T.C(U,0,r,x,c=='R'),T.C(U,l,n-1,x,c=='R');
}
}
return 0;
}
鲁ICP备2025150228号