洛谷-P2865 [USACO06NOV]Roadblocks G
求无向图中 \(1\to n\) 的严格次短路，有重边，一条边可以多次走。
首先一遍 \(\text{Dijkstra}\) 跑出来这个最短路，考虑这个可能的次短路从哪里转移出来。
倒序考虑，先从 \(n\) 开始，设最短路的最后一条边是 \(u\to n\)，那么可能从 \(u\) 的次短路加上 \(w(u,n)\) 转移，同时可能 \(w(u,n)\) 有多个，即可能是在保证严格次短的条件下由 \(u\) 的最短路加上 \(w'(u,v)\) 转移；对于其他的 \(v\to n\)，答案可能由 \(v\) 的最短路加上 \(w(v,n)\) 转移。
发现上面所说的 \(u\) 也是要求次短路的，而这个次短路又由最短路中的上一条边转移来，于是可以从 \(1\) 沿着最短路正推到 \(n\)，更新次短路即可。
注意到如果图是一条链，可以在走到 \(n\) 后将最后一条边重复走两边，于是可以把次短路的初始值赋成这个。
点击查看代码
int n,m;
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[5005];
struct node{
int u,d;
node()=default;
node(int u_,int d_):u(u_),d(d_){}
bool operator<(const node&rhs)const{
return d>rhs.d;
}
};
int dis[5005],fa[5005];
bool vis[5005];
priority_queue<node> q;
inline void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(node(1,0));
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge e:E[u]){
int v=e.v,w=e.w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w,fa[v]=u;
q.push(node(v,dis[v]));
}
}
}
}
int secdis[5005],nxt[5005];
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
E[u].push_back(edge(v,w));
E[v].push_back(edge(u,w));
}
Dijkstra();
int now=n,pre=-1;
while(1){
nxt[now]=pre;
if(now==1) break;
pre=now,now=fa[now];
}
memset(secdis,0x3f,sizeof(secdis));
for(int u=1;u!=-1;u=nxt[u]){
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==nxt[u]) secdis[v]=dis[v]+2*w;
}
}
for(int u=nxt[1];u!=-1;u=nxt[u]){
for(edge e:E[u]){
int v=e.v,w=e.w;
if(v==fa[u]&&secdis[v]+w>dis[u]) secdis[u]=min(secdis[u],secdis[v]+w);
if(dis[v]+w>dis[u]) secdis[u]=min(secdis[u],dis[v]+w);
}
}
printf("%d\n",secdis[n]);
return 0;
}
CodeForces-1076D Edge Deletion *1800
单源最短路径，一条最短路一定由另一条最短路转移而来，于是这样连边，可以得到一个树形结构，满足节点到根的距离即为最短路。
这告诉我们至少需要保留 \(n-1\) 条边才能使全部点的最短路都不变，于是分类讨论。
- 若\(k\ge n-1\)，只保留建出最短路树的树边即可。
- 若 \(k<n-1\)，考虑把叶子节点去掉的代价最小，可以使用魔幻拓扑排序，直到剩 \(k\) 条边为止。
点击查看代码
int n,m,k;
struct edge{
int v,w,id;
edge()=default;
edge(int v_,int w_,int id_):v(v_),w(w_),id(id_){}
};
vector<edge> E[maxn];
struct node{
int u;
ll d;
node()=default;
node(int u_,ll d_):u(u_),d(d_){}
bool operator<(const node&rhs)const{
return d>rhs.d;
}
};
priority_queue<node> p_q;
ll dis[maxn];
bool vis[maxn];
int fa[maxn],id[maxn];
inline void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
p_q.push(node(1,0));
while(!p_q.empty()){
int u=p_q.top().u;
p_q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge e:E[u]){
int v=e.v,w=e.w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w,fa[v]=u,id[v]=e.id;
p_q.push(node(v,dis[v]));
}
}
}
}
bool mark_edge[maxn];
int mark_node[maxn];
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
E[u].push_back(edge(v,w,i));
E[v].push_back(edge(u,w,i));
}
Dijkstra();
if(k>=n-1){
printf("%d\n",n-1);
for(int i=2;i<=n;++i) printf("%d ",id[i]);
printf("\n");
}
else{
printf("%d\n",k);
for(int i=1;i<=n;++i){
if(i>1) mark_edge[id[i]]=1;
++mark_node[fa[i]];
}
queue<int> q;
for(int i=1;i<=n;++i){
if(!mark_node[i]) q.push(i);
}
int cnt=0;
while(1){
int u=q.front();
q.pop();
mark_edge[id[u]]=0;
--mark_node[fa[u]];
if(!mark_node[fa[u]]) q.push(fa[u]);
++cnt;
if(cnt+k==n-1) break;
}
for(int i=1;i<=m;++i){
if(mark_edge[i]) printf("%d ",i);
}
printf("\n");
}
return 0;
}
洛谷-P2934 [USACO09JAN]Safe Travel G
依旧是建出最短路树，答案的来源一定是由一条非树边和其余树边组成的。
可以得到一个结论：答案的路径有且仅有一条非树边。
证明非常显然，考虑多于一条非树边的情况，只需要一条边规避掉当前考虑节点与其父亲的连边，另外一条的长度一定是劣于树边的，因此最多选择一条树边。
我们考虑这条非树边可以带来什么影响。
对于非树边 \((u,v)\)，可以发现其与 \(\operatorname{LCA}(u,v)\) 构成了一个环，而 \(u\) 与 \(v\) 的子树内节点是无法产生影响的，原因是转移仍然需要结果最后一条树边，同理，\(u\) 与 \(v\) 的一切公共祖先若要转移也需要结果最后一条树边。因此对这个环上除了 \(\operatorname{LCA}(u,v)\) 之外的节点 \(x\) 都能产生影响，这个答案是 \(dis(u)+dis(v)+w(u,v)-dis(x)\)，画图可以形象化的理解成走这个环的另一边。
考虑到批量处理，可以先不处理这个 \(dis(x)\)，树链剖分下来，线段树区间修改求最小值，到最后再减去 \(dis(x)\) 即可。
点击查看代码
int n,m;
struct edge{
int v,w,id;
edge()=default;
edge(int v_,int w_,int id_):v(v_),w(w_),id(id_){}
};
vector<edge> E[maxn];
struct node{
int u,d;
node()=default;
node(int u_,int d_):u(u_),d(d_){}
bool operator<(const node&rhs)const{
return d>rhs.d;
}
};
priority_queue<node> q;
int dis[maxn],fa[maxn],id[maxn];
bool vis[maxn];
inline void Dijkstra(){
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
q.push(node(1,0));
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(edge e:E[u]){
int v=e.v,w=e.w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w,fa[v]=u,id[v]=e.id;
q.push(node(v,dis[v]));
}
}
}
}
bool mark_edge[maxm];
vector<int> T[maxn];
int dep[maxn],siz[maxn],son[maxn];
int dfn[maxn],dfncnt,top[maxn],dfnid[maxn];
void dfs1(int u,int d){
dep[u]=d,siz[u]=1;
for(int v:T[u]){
if(v==fa[u]) continue;
dfs1(v,d+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int t){
dfn[u]=++dfncnt,top[u]=t,dfnid[dfncnt]=u;
if(!son[u]) return;
dfs2(son[u],t);
for(int v:T[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
int ans[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int mn[maxn<<2];
bool tag[maxn<<2];
void build(int rt,int l,int r){
mn[rt]=0x3f3f3f3f,tag[rt]=0;
if(l==r) return;
build(lson),build(rson);
}
inline void push_down(int rt){
if(tag[rt]){
if(mn[rt]<mn[rt<<1]) mn[rt<<1]=mn[rt],tag[rt<<1]=1;
if(mn[rt]<mn[rt<<1|1]) mn[rt<<1|1]=mn[rt],tag[rt<<1|1]=1;
tag[rt]=0;
}
}
void update(int rt,int l,int r,int pl,int pr,int k){
if(pl<=l&&r<=pr){
if(k<mn[rt]) mn[rt]=k,tag[rt]=1;
return;
}
push_down(rt);
if(pl<=mid) update(lson,pl,pr,k);
if(pr>mid) update(rson,pl,pr,k);
}
void query(int rt,int l,int r){
if(l==r){
ans[dfnid[l]]=mn[rt];
return;
}
push_down(rt);
query(lson),query(rson);
}
#undef mid
#undef lson
#undef rson
}S;
inline void update(int u,int v,int k){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
S.update(1,1,n,dfn[top[v]],dfn[v],k);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
if(u!=v) S.update(1,1,n,dfn[u]+1,dfn[v],k);
}
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
E[u].push_back(edge(v,w,i));
E[v].push_back(edge(u,w,i));
}
Dijkstra();
for(int i=2;i<=n;++i) mark_edge[id[i]]=1;
for(int u=2;u<=n;++u){
for(edge e:E[u]){
int v=e.v;
if(v==fa[u]){
T[v].push_back(u);
}
}
}
dfs1(1,0);
dfs2(1,1);
S.build(1,1,n);
for(int u=1;u<=n;++u){
for(edge e:E[u]){
if(mark_edge[e.id]) continue;
int v=e.v,w=e.w;
update(u,v,dis[u]+dis[v]+w);
mark_edge[e.id]=1;
}
}
S.query(1,1,n);
for(int i=2;i<=n;++i){
if(ans[i]==0x3f3f3f3f) printf("-1\n");
else printf("%d\n",ans[i]-dis[i]);
}
return 0;
}
洛谷-P1841 [JSOI2007] 重要的城市
\(n\) 才 \(200\)，考虑对每个点跑 \(\text{Dijkstra}\)，标记每个节点的转移点以及转移点是否唯一，得到一个树形结构。树的叶子节点对这个单源最短路径没有影响，非叶子节点考虑其子节点的转移点是否有唯一的，若没有则也可以去掉。这样找到在某个单源最短路径下不能去掉的点即可。
不带堆优化的 \(\text{Dijkstra}\) 复杂度 \(O(n^3)\)，带堆优化的复杂度 \(O(nm\log m)\)，实测二者跑得差不多。
点击查看代码
int n,m;
struct edge{
int v,w;
edge()=default;
edge(int v_,int w_):v(v_),w(w_){}
};
vector<edge> E[205];
int dis[205],fa[205];
bool vis[205],mark[205];
int cnt_son[205],cnt_mark[205];
int ans[205];
struct Graph{
inline void Dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(mark,0,sizeof(mark));
dis[s]=0;
for(int i=1;i<n;++i){
int now=0;
for(int u=1;u<=n;++u){
if(vis[u]) continue;
if(!now||dis[u]<dis[now]) now=u;
}
vis[now]=1;
for(edge e:E[now]){
int v=e.v,w=e.w;
if(vis[v]) continue;
if(dis[now]+w<dis[v]){
dis[v]=dis[now]+w,fa[v]=now,mark[v]=0;
}
else if(dis[now]+w==dis[v]) mark[v]=1;
}
}
}
inline void solve(int s){
Dijkstra(s);
memset(cnt_son,0,sizeof(cnt_son));
memset(cnt_mark,0,sizeof(cnt_mark));
for(int u=1;u<=n;++u){
if(u==s) continue;
++cnt_son[fa[u]];
cnt_mark[fa[u]]+=mark[u];
}
for(int u=1;u<=n;++u){
if(u==s) continue;
if(!cnt_son[u]) ++ans[u];
else if(cnt_son[u]==cnt_mark[u]) ++ans[u];
}
}
}G[205];
bool pd=0;
int main(){
n=read(),m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
E[u].push_back(edge(v,w));
E[v].push_back(edge(u,w));
}
for(int i=1;i<=n;++i){
G[i].solve(i);
}
for(int i=1;i<=n;++i){
if(ans[i]<n-1){
pd=1;
printf("%d ",i);
}
}
if(!pd) printf("No important cities.\n");
printf("\n");
return 0;
}
也可以使用 \(\text{Floyd}\)，记录下每个最短路的数目 \(cnt\)。
枚举点 \(k\)，若 \(dis(i,k)+dis(k,j)=dis(i,j)\) 且 \(cnt(i,k)\times cnt(k,j)=cnt(i,j)\)，说明点 \(k\) 在这个最短路上是唯一的。
点击查看代码
int n,m;
int dis[205][205];
ll cnt_edge[205][205];
int mark[205];
bool pd=0;
int main(){
n=read(),m=read();
memset(dis,0x3f,sizeof(dis));
for(int i=1;i<=m;++i){
int u=read(),v=read(),w=read();
dis[u][v]=dis[v][u]=w;
cnt_edge[u][v]=cnt_edge[v][u]=1;
}
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
if(i==k) continue;
for(int j=1;j<=n;++j){
if(i==j||j==k) continue;
if(dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
cnt_edge[i][j]=cnt_edge[i][k]*cnt_edge[k][j];
}
else if(dis[i][k]+dis[k][j]==dis[i][j]) cnt_edge[i][j]+=cnt_edge[i][k]*cnt_edge[k][j];
}
}
}
for(int k=1;k<=n;++k){
for(int i=1;i<=n;++i){
if(i==k) continue;
for(int j=1;j<=n;++j){
if(i==j||j==k) continue;
if(dis[i][k]+dis[k][j]==dis[i][j]){
if(cnt_edge[i][k]*cnt_edge[k][j]==cnt_edge[i][j]){
mark[k]=1;
break;
}
}
}
if(mark[k]) break;
}
}
for(int i=1;i<=n;++i){
if(mark[i]){
pd=1;
printf("%d ",i);
}
}
if(!pd) printf("No important cities.");
printf("\n");
return 0;
}
CodeForces-815B Karen and Test *2200
需要求出每一项的系数，手玩了一下，发现画出转移像是一个平行四边形，分向左和向右的边。但是没有直接规律可循，递推式与杨辉三角相似，考虑打表。
发现对于 \(n\bmod 4=0\) 的情况，只是将杨辉三角扩充成左边一位正右边一位负，而 \(n\bmod 4=2\) 的情况则是直接扩充成左右两位相同。
考虑打表的转移，发现对于 \(n\bmod 4=1\) 和 \(n\bmod 4=3\) 的情况，可以直接求出其下一行的系数，倒推出这一行的系数。
点击查看代码
int n;
inline int q_pow(int x,int p){
int res=1;
while(p){
if(p&1) res=1ll*res*x%mod;
x=1ll*x*x%mod;
p>>=1;
}
return res;
}
int fac[maxn],inv[maxn];
inline int C(int N,int M){
return 1ll*fac[N]*inv[M]%mod*inv[N-M]%mod;
}
int a[maxn];
int ans;
int main(){
n=read();
fac[0]=inv[0]=1;
for(int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
inv[n]=q_pow(fac[n],mod-2);
for(int i=n-1;i>=1;--i) inv[i]=1ll*inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;++i) a[i]=read();
if(n%4==0){
int m=n/2-1;
for(int i=0;i<=m;++i){
int c=C(m,i);
ans=(ans+1ll*a[i*2+1]*c%mod-1ll*a[i*2+2]*c%mod+mod)%mod;
}
printf("%d\n",ans);
}
else if(n%4==2){
int m=n/2-1;
for(int i=0;i<=m;++i){
int c=C(m,i);
ans=(ans+1ll*a[i*2+1]*c%mod+1ll*a[i*2+2]*c%mod)%mod;
}
printf("%d\n",ans);
}
else if(n%4==1){
int m=(n+1)/2-1;
for(int i=0;i<=m;++i){
int c=C(m,i);
ans=(ans+1ll*a[i*2+1]*c%mod)%mod;
}
printf("%d\n",ans);
}
else{
int m=(n+1)/2-1;
int now=1;
for(int i=2;i<=n+1;++i){
ans=(ans+1ll*now*a[i-1]%mod+mod)%mod;
if(i==n+1) break;
int c=C(m,(i-1)/2);
if(i%2==0){
c=(-c+mod)%mod;
now=(now-c+mod)%mod;
}
else{
now=(c-now+mod)%mod;
}
}
printf("%d\n",ans);
}
return 0;
}
CodeForces-359D Pair of Numbers *2000
\(\max\)，\(\min\)，\(\gcd\) 此类的操作都支持合并不支持撤销，而且满足单调性。对于每个点直接二分出合法的左端点和右端点，查询可以用 \(\text{ST}\) 表，复杂度是 \(O(n\log n\log a)\)，要存的是左端点，可能有重复情况，需要离散化去重。
点击查看代码
int n;
int a[maxn];
struct ST{
int gcd(int A,int B){
if(A<B) swap(A,B);
if(!B) return A;
return gcd(B,A%B);
}
int GCD[maxn][19];
inline void build(){
for(int i=1;i<=n;++i) GCD[i][0]=a[i];
for(int k=1;k<=18;++k){
for(int i=1;i+(1<<k)-1<=n;++i){
GCD[i][k]=gcd(GCD[i][k-1],GCD[i+(1<<(k-1))][k-1]);
}
}
}
inline int query(int l,int r){
int k=log2(r-l+1);
return gcd(GCD[l][k],GCD[r-(1<<k)+1][k]);
}
}S;
int len;
vector<int> V;
int main(){
n=read();
for(int i=1;i<=n;++i) a[i]=read();
S.build();
for(int i=1;i<=n;++i){
int l=1,r=i,lpos=i,rpos=i;
while(l<=r){
int mid=(l+r)>>1;
if(S.query(mid,i)==a[i]) lpos=mid,r=mid-1;
else l=mid+1;
}
l=i,r=n;
while(l<=r){
int mid=(l+r)>>1;
if(S.query(i,mid)==a[i]) rpos=mid,l=mid+1;
else r=mid-1;
}
if(rpos-lpos>len){
len=rpos-lpos;
V.clear();
V.push_back(lpos);
}
else if(rpos-lpos==len){
V.push_back(lpos);
}
}
sort(V.begin(),V.end());
V.erase(unique(V.begin(),V.end()),V.end());
printf("%d %d\n",(int)V.size(),len);
for(int i:V) printf("%d ",i);
printf("\n");
return 0;
}
CodeForces-1585F Non-equal Neighbours *2400/CodeForces-1591F Non-equal Neighbours *2400/AtCoder-ARC115E LEQ and NEQ
闲话：我以为是数学题，实际上是 \(\text{dp}\) 题；我以为是 \(\text{dp}\) 题，实际上是线段树懒标记练习题。
设 \(f_{i,j}\) 表示第 \(i\) 个位置上数字为 \(j\) 的方案数得到转移方程：
发现第二个式子其实是 \(\sum_{k=1}^{a_{i-1}}f_{i-1,k}-f_{i-1,j}\)。
考虑线段树优化，支持区间乘、区间加以及区间求和。
点击查看代码
int a[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
int sum[maxm],ch[maxm][2],tag1[maxm],tag2[maxm],tot;
inline void push_up(int rt){
sum[rt]=(sum[ch[rt][0]]+sum[ch[rt][1]])%mod;
}
inline void push_down(int rt,int l,int r){
if(!ch[rt][0]) ch[rt][0]=++tot,tag1[ch[rt][0]]=1;
if(!ch[rt][1]) ch[rt][1]=++tot,tag1[ch[rt][1]]=1;
if(tag1[rt]!=1){
sum[ch[rt][0]]=(sum[ch[rt][0]]*tag1[rt]+mod)%mod,sum[ch[rt][1]]=(sum[ch[rt][1]]*tag1[rt]+mod)%mod;
tag1[ch[rt][0]]*=tag1[rt],tag1[ch[rt][1]]*=tag1[rt];
tag2[ch[rt][0]]=(tag2[ch[rt][0]]*tag1[rt]+mod)%mod,tag2[ch[rt][1]]=(tag2[ch[rt][1]]*tag1[rt]+mod)%mod;
tag1[rt]=1;
}
if(tag2[rt]){
sum[ch[rt][0]]=(sum[ch[rt][0]]+1ll*tag2[rt]*(mid-l+1)%mod)%mod,sum[ch[rt][1]]=(sum[ch[rt][1]]+1ll*tag2[rt]*(r-mid)%mod)%mod;
tag2[ch[rt][0]]=(tag2[ch[rt][0]]+tag2[rt])%mod,tag2[ch[rt][1]]=(tag2[ch[rt][1]]+tag2[rt])%mod;
tag2[rt]=0;
}
}
inline void update1(int &rt,int l,int r,int pl,int pr,int k){
if(!rt) rt=++tot,tag1[rt]=1;
if(pl<=l&&r<=pr){
sum[rt]=(sum[rt]*k+mod)%mod,tag1[rt]=tag1[rt]*k,tag2[rt]=(tag2[rt]*k+mod)%mod;
return;
}
push_down(rt,l,r);
if(pl<=mid) update1(ch[rt][0],l,mid,pl,pr,k);
if(pr>mid) update1(ch[rt][1],mid+1,r,pl,pr,k);
push_up(rt);
}
inline void update2(int &rt,int l,int r,int pl,int pr,int k){
if(!rt) rt=++tot,tag1[rt]=1;
if(pl<=l&&r<=pr){
sum[rt]=(sum[rt]+1ll*k*(r-l+1)%mod)%mod,tag2[rt]=(tag2[rt]+k)%mod;
return;
}
push_down(rt,l,r);
if(pl<=mid) update2(ch[rt][0],l,mid,pl,pr,k);
if(pr>mid) update2(ch[rt][1],mid+1,r,pl,pr,k);
push_up(rt);
}
}S;
int rt;
int main(){
n=read();
for(int i=1;i<=n;++i){
a[i]=read();
m=max(m,a[i]);
}
S.update2(rt,1,m,1,a[1],1);
for(int i=2;i<=n;++i){
int sum=S.sum[1];
if(a[i]<m) S.update1(rt,1,m,a[i]+1,m,0);
S.update1(rt,1,m,1,a[i],-1);
S.update2(rt,1,m,1,a[i],sum);
}
printf("%d\n",S.sum[1]);
return 0;
}
CodeForces-446C DZY Loves Fibonacci Numbers *2400
考虑两个斐波那契数列 \(f\) 和 \(g\) 合并后，依旧有：\(f_i+g_i=f_{i-1}+g_{i-1}+f_{i-2}+g_{i-2}\)，也就是说，懒标记是可以合并的，那么可以用线段树维护。
预处理出符合斐波那契数列性质的数列第 \(i\) 项是由多少第 \(1\) 项和多少第 \(2\) 项相加得到的，以及前 \(i\) 项之和是由多少第 \(1\) 项和多少第 \(2\) 项相加得到的。这样就可以快速算出这样一个数列的单点值以及前缀和。
线段树懒标记维护这个区间标记的序列的前两项，发现在计算单点值以及前缀和时，要求知道准确的序列长度，因此区间修改操作时，查询区间在下传时应当是当前区间的一个子集。
点击查看代码
int n,m;
int a[maxn],sum[maxn];
int Fib[maxn][2],sumFib[maxn][2];
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
int val[maxn<<2],tag[maxn<<2][2];
inline void push_up(int rt){
val[rt]=(val[rt<<1]+val[rt<<1|1])%mod;
}
void build(int rt,int l,int r){
val[rt]=0,tag[rt][0]=0,tag[rt][1]=0;
if(l==r) return;
build(lson),build(rson);
push_up(rt);
}
inline int get_val(int l,int r,int K0,int K1){
return (1ll*K0*Fib[r-l+1][0]%mod+1ll*K1*Fib[r-l+1][1]%mod)%mod;
}
inline int get_sum(int l,int r,int K0,int K1){
return (1ll*K0*sumFib[r-l+1][0]%mod+1ll*K1*sumFib[r-l+1][1]%mod)%mod;
}
inline void push_down(int rt,int l,int r){
if(tag[rt][0]){
val[rt<<1]=(val[rt<<1]+get_sum(l,mid,tag[rt][0],tag[rt][1]))%mod;
val[rt<<1|1]=(val[rt<<1|1]+get_sum(mid+1,r,get_val(l,mid+1,tag[rt][0],tag[rt][1]),get_val(l,mid+2,tag[rt][0],tag[rt][1])))%mod;
tag[rt<<1][0]=(tag[rt<<1][0]+tag[rt][0])%mod,tag[rt<<1][1]=(tag[rt<<1][1]+tag[rt][1])%mod;
tag[rt<<1|1][0]=(tag[rt<<1|1][0]+get_val(l,mid+1,tag[rt][0],tag[rt][1]))%mod,tag[rt<<1|1][1]=(tag[rt<<1|1][1]+get_val(l,mid+2,tag[rt][0],tag[rt][1]))%mod;
tag[rt][0]=0,tag[rt][1]=0;
}
}
void update(int rt,int l,int r,int pl,int pr,int K0,int K1){
if(pl<=l&&r<=pr){
val[rt]=(val[rt]+get_sum(l,r,K0,K1))%mod;
tag[rt][0]=(tag[rt][0]+K0)%mod,tag[rt][1]=(tag[rt][1]+K1)%mod;
return;
}
push_down(rt,l,r);
if(pr<=mid) update(lson,pl,pr,K0,K1);
else if(pl>mid) update(rson,pl,pr,K0,K1);
else{
update(lson,pl,mid,K0,K1);
update(rson,mid+1,pr,get_val(pl,mid+1,K0,K1),get_val(pl,mid+2,K0,K1));
}
push_up(rt);
}
int query(int rt,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return val[rt];
push_down(rt,l,r);
int res=0;
if(pl<=mid) res=(res+query(lson,pl,pr))%mod;
if(pr>mid) res=(res+query(rson,pl,pr))%mod;
return res;
}
#undef mid
#undef lson
#undef rson
}S;
int main(){
n=read(),m=read();
for(int i=1;i<=n;++i) a[i]=read(),sum[i]=(sum[i-1]+a[i])%mod;
Fib[1][0]=1,Fib[1][1]=0,Fib[2][0]=0,Fib[2][1]=1;
sumFib[1][0]=1,sumFib[1][1]=0,sumFib[2][0]=1,sumFib[2][1]=1;
for(int i=3;i<=n;++i){
Fib[i][0]=(Fib[i-1][0]+Fib[i-2][0])%mod,Fib[i][1]=(Fib[i-1][1]+Fib[i-2][1])%mod;
sumFib[i][0]=(sumFib[i-1][0]+Fib[i][0])%mod,sumFib[i][1]=(sumFib[i-1][1]+Fib[i][1])%mod;
}
S.build(1,1,n);
while(m--){
int opt=read(),l=read(),r=read();
if(opt==1) S.update(1,1,n,l,r,1,1);
else{
int res=(sum[r]-sum[l-1]+mod)%mod;
res=(res+S.query(1,1,n,l,r))%mod;
printf("%d\n",res);
}
}
return 0;
}
洛谷-P2260 [清华集训2012]模积和
发现两个求和号是假的，\(i\ne j\) 的限制也是假的，把一个因式提出就变成朴素的余数求和，对于\(i\ne j\) 的限制可以最后去掉 \(i=j\) 的贡献。
把 \(a\bmod b\) 写成 \(a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b\) 应该是常规操作。
模数不是质数，求逆元用扩欧。
点击查看代码
int n,m;
int exgcd(int a,int b,int &x,int &y){
if(!b){
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,x,y);
int t=x;
x=y,y=t-a/b*y;
return d;
}
int inv2,inv6;
inline void init(){
int y;
exgcd(2,mod,inv2,y);
inv2=(inv2%mod+mod)%mod;
exgcd(6,mod,inv6,y);
inv6=(inv6%mod+mod)%mod;
}
int ans1,ans2,ans3;
inline int get_sum(int x){
return 1ll*x*(x+1)%mod*(2*x%mod+1)%mod*inv6%mod;
}
ll ans;
int main(){
init();
n=read(),m=read();
ans1=1ll*n*n%mod,ans2=1ll*m*m%mod;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans1=(ans1-1ll*(n/l)*(l+r)%mod*(r-l+1)%mod*inv2%mod+mod)%mod;
}
for(int l=1,r;l<=m;l=r+1){
r=m/(m/l);
ans2=(ans2-1ll*(m/l)*(l+r)%mod*(r-l+1)%mod*inv2%mod+mod)%mod;
}
if(n>m) swap(n,m);
ans3=1ll*n*n%mod*m%mod;
for(int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
int k1=n/l,k2=m/l;
int s1=1ll*(l+r)*(r-l+1)%mod*inv2%mod,s2=(get_sum(r)-get_sum(l-1)+mod)%mod;
ans3=(ans3+1ll*k1*k2%mod*s2%mod)%mod;
ans3=(ans3-(1ll*k1*m%mod*s1%mod+1ll*k2*n%mod*s1%mod)%mod+mod)%mod;
}
ans=(1ll*ans1*ans2%mod-ans3+mod)%mod;
printf("%lld\n",ans);
return 0;
}