一、图论
1.单源最短路
洛谷P3371
(1)spfa
已加SLF优化 419ms
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=1e4+5,M=5e5+5,INF=2147483647; 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x*f;12 }13 int n,m,s,u,v,w;14 struct edge{15 int v,ne,w;16 }e[M<<1];17 int h[N],cnt=0;18 inline void ins(int u,int v,int w){19 cnt++;20 e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;21 }22 inline void lop(int &x){if(x==N) x=1;else if(x==0) x=N-1;}23 int d[N],q[N],head,tail,inq[N];24 void spfa(int s){25 for(int i=1;i<=n;i++) d[i]=INF;26 head=tail=1;27 q[tail++]=s;inq[s]=1;d[s]=0;28 while(head!=tail){29 int u=q[head++];inq[u]=0;lop(head);30 for(int i=h[u];i;i=e[i].ne){31 int v=e[i].v,w=e[i].w;32 if(d[v]>d[u]+w){33 d[v]=d[u]+w;34 if(!inq[v]){35 if(d[v]<d[q[head]]) head--,lop(head),q[head]=v;36 else q[tail++]=v,lop(tail);37 inq[v]=1;38 }39 }40 }41 }42 }43 int main(){44 n=read();m=read();s=read();45 for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}46 spfa(s);47 for(int i=1;i<=n;i++) printf("%d ",d[i]);48 }
(2)dijkstra 503ms
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N=1e4+5,M=5e5+5,INF=2147483647; 8 inline int read(){ 9 char c=getchar();int x=0,f=1;10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}11 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}12 return x;13 }14 int n,m,s,u,v,w;15 struct edge{16 int v,ne,w;17 }e[M];18 int h[N],cnt=0;19 inline void ins(int u,int v,int w){20 cnt++;21 e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;22 }23 struct hn{24 int u,d;25 hn(int a=0,int b=0):u(a),d(b){}26 bool operator <(const hn &r)const{return d>r.d;}27 };28 priority_queue q;29 int d[N],done[N];30 void dij(int s){31 for(int i=1;i<=n;i++) d[i]=INF;32 d[s]=0;33 q.push(hn(s,0));34 while(!q.empty()){35 hn x=q.top();q.pop();36 int u=x.u;if(done[u]) continue;37 done[u]=1;38 for(int i=h[u];i;i=e[i].ne){39 int v=e[i].v,w=e[i].w;40 if(d[v]>d[u]+w){41 d[v]=d[u]+w;42 if(!done[v]) q.push(hn(v,d[v]));//xiao you hua43 }44 }45 }46 }47 int main(){48 n=read();m=read();s=read();49 for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}50 dij(s);51 for(int i=1;i<=n;i++) printf("%d ",d[i]);52 }
(3)dijkstra+配对堆 380ms 吊打用SLF优化的spfa啊啊啊啊啊
1 #include 2 #include 3 #include 4 #include 5 #include 6 #define pa pair 7 #define mp make_pair 8 using namespace std; 9 using namespace __gnu_pbds;10 typedef __gnu_pbds::priority_queue<pa,greater,thin > heap;11 const int N=1e4+5,M=5e5+5,INF=2147483647;12 inline int read(){13 char c=getchar();int x=0,f=1;14 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}15 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}16 return x*f;17 }18 int n,m,s,u,v,w;19 struct edge{20 int v,ne,w;21 }e[M];22 int h[N],cnt=0;23 inline void ins(int u,int v,int w){24 cnt++;25 e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;26 }27 28 heap q;29 heap::point_iterator it[N];30 int d[N];31 void dij(int s){32 for(int i=1;i<=n;i++) d[i]=INF;33 d[s]=0;34 it[s]=q.push(mp(0,s));35 while(!q.empty()){36 int u=q.top().second;q.pop();37 for(int i=h[u];i;i=e[i].ne){38 int v=e[i].v,w=e[i].w;39 if(d[v]>d[u]+w){40 d[v]=d[u]+w;41 if(it[v]!=0) q.modify(it[v],mp(d[v],v));42 else it[v]=q.push(mp(d[v],v));43 }44 }45 }46 }47 int main(){48 n=read();m=read();s=read();49 for(int i=1;i<=m;i++){u=read();v=read();w=read();ins(u,v,w);}50 dij(s);51 for(int i=1;i<=n;i++) printf("%d ",d[i]);52 }
2.判负环
Vijos P1053Easy sssp
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=1e3+5,M=1e5+5,INF=1e9+5; 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x*f;12 }13 int n,m,s,u,v,w;14 struct edge{15 int v,ne,w;16 }e[M+N];17 int h[N],cnt=0;18 inline void ins(int u,int v,int w){19 cnt++;20 e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;21 }22 inline void lop(int &x){x++;if(x==N) x=1;}23 int q[N],head=1,tail=1,inq[N];24 int d[N],nc[N];25 bool spfa(int s){26 head=tail=1;27 for(int i=1;i<=n;i++) d[i]=INF,inq[i]=nc[i]=0;28 q[tail]=s;inq[s]=nc[s]=1; lop(tail);29 d[s]=0;30 while(head!=tail){31 int u=q[head];inq[u]=0; lop(head);32 for(int i=h[u];i;i=e[i].ne){33 int v=e[i].v,w=e[i].w;34 if(d[v]>d[u]+w){35 d[v]=d[u]+w;36 if(!inq[v]){37 inq[v]=1;q[tail]=v; lop(tail);38 if(++nc[v]>n) return false;39 }40 }41 }42 }43 return true;44 }45 int main(){46 n=read();m=read();s=read();47 for(int i=1;i<=m;i++){48 u=read();v=read();w=read();49 if(u==v&&w<0) {printf("-1");return 0;}50 if(u!=v)ins(u,v,w);51 }52 53 int ss=n+1;//超级源54 for(int i=1;i<=n;i++) ins(ss,i,0);55 int flag=spfa(ss);56 if(!flag){printf("-1");return 0;}57 spfa(s);58 for(int i=1;i<=n;i++){59 if(d[i]>=INF) printf("NoPath\n");60 else printf("%d\n",d[i]);61 }62 }
3.最小生成树
洛谷P3366
kruskal
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=5005,M=2e5+5,INF=1e9+5; 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x*f;12 }13 int n,m,u,v,w;14 int cnt=0;15 struct edge{16 int u,v,w;17 bool operator <(const edge &r)const{return w<r.w;}18 }e[M];19 int fa[N];20 inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}21 int kruskal(){22 int ans=0,cnt=0;23 for(int i=1;i<=n;i++) fa[i]=i;24 sort(e+1,e+1+m);25 for(int i=1;i<=m;i++){26 int u=e[i].u,v=e[i].v,w=e[i].w;27 int f1=find(u),f2=find(v);28 if(f1!=f2){29 ans+=w;30 fa[f1]=f2;31 cnt++;32 if(cnt==n-1) break;33 }34 }35 return ans;36 }37 int main(){38 n=read();m=read();39 for(int i=1;i<=m;i++){40 e[i].u=read();e[i].v=read();e[i].w=read();41 }42 int ans=kruskal();43 printf("%d",ans);44 }
4.floyd
(1)传递闭包
d[i][j]=d[i][j]||(d[i][k]&&d[k][j])
(2)最小环
Vijos P1046观光旅行
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=105,M=1e4+5,INF=1e8+5;//1E9+1E9+1E9溢出 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x*f;12 }13 int n,m,u,v,w,g[N][N];14 int d[N][N],ans=INF;15 void floyd(){16 ans=INF;17 for(int k=1;k<=n;k++){18 for(int i=1;i<=k-1;i++)19 for(int j=i+1;j<=k-1;j++)20 ans=min(ans,g[i][k]+g[k][j]+d[i][j]);21 for(int i=1;i<=n;i++)22 for(int j=1;j<=n;j++)23 d[i][j]=min(d[i][j],d[i][k]+d[k][j]);24 }25 26 }27 int main(){28 while(scanf("%d%d",&n,&m)!=EOF){29 for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) d[i][j]=d[j][i]=g[i][j]=g[j][i]=INF;30 for(int i=1;i<=m;i++){31 u=read();v=read();w=read();32 d[u][v]=d[v][u]=g[u][v]=g[v][u]=w;33 }34 floyd();35 if(ans==INF) puts("No solution.");36 else printf("%d\n",ans);37 }38 }
5.割点
洛谷P3388
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=1e5+5,M=1e5+5,INF=1e9+5; 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x;12 }13 int n=0,m,u,v;14 struct edge{15 int v,ne;16 }e[M<<1];17 int h[N],cnt=0;18 inline void ins(int u,int v){19 cnt++;20 e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;21 cnt++;22 e[cnt].v=u;e[cnt].ne=h[v];h[v]=cnt;23 }24 int dfn[N],low[N],dfc=0,iscut[N];25 void dfs(int u,int fa){26 dfn[u]=low[u]=++dfc;27 int child=0;28 for(int i=h[u];i;i=e[i].ne){29 int v=e[i].v;30 if(!dfn[v]){31 child++;32 dfs(v,u);33 low[u]=min(low[u],low[v]);34 if(low[v]>=dfn[u]) iscut[u]=1;35 }else if(v!=fa) low[u]=min(low[u],dfn[v]);36 }37 if(fa==0&&child==1) iscut[u]=0;38 }39 int main(){40 n=read();m=read();41 for(int i=1;i<=m;i++){u=read();v=read();ins(u,v);}42 for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,0);43 44 int ans=0;45 for(int i=1;i<=n;i++) if(iscut[i]) ans++;46 printf("%d\n",ans);47 for(int i=1;i<=n;i++) if(iscut[i]) printf("%d ",i);48 }
6.tarjan 强连通分量
POJ2186
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int N=1e4+5,M=5e4+5; 8 typedef long long ll; 9 inline int read(){10 char c=getchar();int x=0,f=1;11 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}12 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}13 return x*f;14 }15 int n,m,u,v;16 struct edge{17 int v,ne;18 }e[M];19 int h[N],cnt=0;20 inline void ins(int u,int v){21 cnt++;22 e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;23 }24 int dfn[N],belong[N],low[N],dfc,scc,st[N],top;25 int size[N];26 void dfs(int u){27 dfn[u]=low[u]=++dfc;28 st[++top]=u;29 for(int i=h[u];i;i=e[i].ne){30 int v=e[i].v;31 if(!dfn[v]){32 dfs(v);33 low[u]=min(low[u],low[v]);34 }else if(!belong[v])35 low[u]=min(low[u],dfn[v]);36 }37 if(low[u]==dfn[u]){38 scc++;39 while(true){40 int x=st[top--];41 belong[x]=scc;42 size[scc]++;43 if(x==u) break;44 }45 }46 }47 int outd[N],ind[N],ans;48 void point(){49 for(int u=1;u<=n;u++)50 for(int i=h[u];i;i=e[i].ne){51 int v=e[i].v;52 if(belong[u]!=belong[v]) outd[belong[u]]++,ind[belong[v]]++;53 }54 }55 int main(){56 n=read();m=read();57 for(int i=1;i<=m;i++){u=read();v=read();ins(u,v);}58 for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i);59 point();
60 for(int i=1;i<=scc;i++){61 if(outd[i]==0){62 if(ans){ans=0;break;}63 else ans=size[i];
64 }65 }66 printf("%d",ans);67 }
7.二分图染色
1 bool color(int u,int c){2 col[u]=c;
3 for(int i=h[u];i;i=e[i].ne){4 int v=e[i].v;5 if(col[u]==col[v]) return false;6 if(!col[v]&&!color(v,3-c)) return false;7 }8 return true;9 }
8.二分图最大匹配
洛谷P3386
1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 const int N=1005; 7 inline int read(){ 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}11 return x*f;12 }13 int n,m,s,u,v;14 struct edge{15 int v,ne;16 }e[N*N<<1];17 int h[N],cnt=0;18 inline void ins(int u,int v){19 cnt++;20 e[cnt].v=v;e[cnt].ne=h[u];h[u]=cnt;21 }22 int vis[N],le[N];23 bool find(int u){24 for(int i=h[u];i;i=e[i].ne){25 int v=e[i].v;26 if(!vis[v]){27 vis[v]=1;28 if(!le[v]||find(le[v])){29 le[v]=u;30 return true;31 }32 }33 }34 return false;35 }36 int ans=0;37 void hungary(){38 for(int i=1;i<=n;i++){39 memset(vis,0,sizeof(vis));40 if(find(i)) ans++;
41 }42 }43 int main(){44 n=read();m=read();int t=read();45 for(int i=1;i<=t;i++){u=read();v=read();if(v>m)continue;ins(u,v);}46 ans=0;47 hungary();48 printf("%d\n",ans);49 }
9、tarjan缩点
洛谷p3387
1 #include 2 #include 3 #include 4 #define N 10005 5 #define M 100005 6 #define INF 1e9 7 using namespace std; 8 int tot,nxt[M],point[N],v[M],low[N],Dfn[N],nn,cnt,a[N],c[N],x[M],y[M]; 9 int tot1,nxt1[M],point1[N],v1[M],f[N],out[N],stack[N],num,belong[N],ans;10 bool vis[N];11 void addline(int x,int y){++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}12 void addline1(int x,int y){++tot1; nxt1[tot1]=point1[x]; point1[x]=tot1; v1[tot1]=y;}
13 void tarjan(int x)14 {15 Dfn[x]=low[x]=++nn; vis[x]=1; stack[++cnt]=x;16 for (int i=point[x];i;i=nxt[i])
17 if (!Dfn[v[i]])18 {19 tarjan(v[i]);20 low[x]=min(low[x],low[v[i]]);21 }22 else if (vis[v[i]]) low[x]=min(low[x],Dfn[v[i]]);23 24 if (low[x]==Dfn[x])25 {26 num++;27 while (stack[cnt]!=x)28 {29 c[num]+=a[stack[cnt]];30 belong[stack[cnt]]=num;31 vis[stack[cnt]]=0;32 cnt--;33 }34 c[num]+=a[stack[cnt]];35 belong[stack[cnt]]=num;36 vis[stack[cnt]]=0;37 cnt--;38 }39 }40 void dp(int x,int fa)41 {42 if (vis[x]) return;43 f[x]=c[x];vis[x]=1;int maxx=0;44 for (int i=point1[x];i;i=nxt1[i])45 if (v1[i]!=fa)46 {47 dp(v1[i],x);48 maxx=max(maxx,f[v1[i]]);49 }50 f[x]+=maxx;51 }52 int main()53 {54 int n,m,i;55 scanf("%d%d",&n,&m);56 for (i=1;i<=n;i++) scanf("%d",&a[i]);57 for (i=1;i<=m;i++)58 {59 scanf("%d%d",&x[i],&y[i]);60 addline(x[i],y[i]);61 }62 for(i=1;i<=n;i++)63 if(!Dfn[i])tarjan(i);64 for(i=1;i<=m;i++)65 if(belong[x[i]]!=belong[y[i]])66 addline1(belong[x[i]],belong[y[i]]);67 ans=-INF;68 memset(vis,0,sizeof(vis));69 for(i=1;i<=num;i++)70 if(!vis[i])dp(i,0),ans=max(ans,f[i]);71 printf("%d",ans);72 }
数据结构
1.st表
1 int a[N],f[N][21]; 2 3 void init(int n){ 4 for(int i=1;i<=n;i++) f[i][0]=a[i]; 5 6 for(int j=1;j<=20;j++) 7 for(int i=1;i+(1<<j)-1<=n;i++) 8 f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]); 9 }10 11 int RMQ(int l,int r){12 int k=log(r-l+1)/log(2); //2^k<=l~r13 return min(f[l][k],f[r-(1<<k)+1][k]);14 }
2.trie树
1 int ch[N*L][27],size=0,val[N*L]; 2 void insert(char s[],int n,int id){ 3 int u=0; 4 for(int i=1;i<=n;i++){ 5 int v=s[i]-'a'; 6 if(!ch[u][v]) ch[u][v]=++size; 7 u=ch[u][v]; 8 } 9 val[u]=id;//printf("ins %d %d\n",u,id);10 }
3.单调栈
求最大全flag子矩阵
1 void sol(int flag){ 2 memset(tot,0,sizeof(tot)); 3 for(int i=1;i<=n;i++){ 4 top=0; 5 for(int j=1;j<=m;j++){ 6 if(a[i][j]==flag) tot[j]++; 7 else tot[j]=0; 8 data t; 9 t.h=tot[j];t.l=1;t.pos=j;10 while(top&&st[top].h>=t.h){11 int l=st[top].l+j-1-st[top].pos,h=st[top].h;12 ans1=max(ans1,min(l,h)*min(l,h));13 ans2=max(ans2,l*h);14 t.l+=st[top].l;15 top--;16 }17 st[++top]=t;18 }19 while(top){20 int l=st[top].l+m-st[top].pos,h=st[top].h;21 ans1=max(ans1,min(l,h)*min(l,h));22 ans2=max(ans2,l*h);23 top--;24 }25 }26 }
4.单调队列
q[]保存的是下标
//删除 while(head<=tail&&q[head]<=i-k) head++; //也可能<//插入while(heada[i]) tail--;//单增q[++tail]=i;
5.并查集
带权
1 for(int i=1;i<=n;i++) fa[i]=i,d[i]=0,s[i]=1;2 3 int fa[N],d[N],s[N];4 inline int find(int x){5 if(x==fa[x]) return x;6 int root=find(fa[x]);7 d[x]+=d[fa[x]];8 return fa[x]=root;9 }
6.树状数组
1 模板 2 3 int lowbit(int x) 4 { 5 return x & (-x); 6 } 7 void modify(int x,int add)//一维 8 {
9 while(x<=MAXN)
10 {
11 a[x]+=add;
12 x+=lowbit(x);
13 }14 }15 int get_sum(int x)16 {
17 int ret=0;
18 while(x!=0)
19 {
20 ret+=a[x];
21 x-=lowbit(x);
22 }
23 return ret;24 }25 void modify(int x,int y,int data)//二维26 {27 for(int i=x;i<MAXN;i+=lowbit(i))28 for(int j=y;j<MAXN;j+=lowbit(j))29 a[i][j]+=data;30 }31 int get_sum(int x,int y)32 {33 int res=0;34 for(int i=x;i>0;i-=lowbit(i))35 for(int j=y;j>0;j-=lowbit(j))36 res+=a[i][j];37 return res;38 }
7.线段树
1 //下面是某线段树模板题的代码： 2 #include 3 #include 4 using namespace std; 5 6 typedef long long LL; 7 static const int maxm=1e6+10; 8 LL tree[maxm],lazy[maxm],A[maxm],left[maxm],right[maxm]; 9 int n,m;10 11 void build(int num,int l,int r){12 left[num]=l;right[num]=r;13 int mid=(l+r)>>1;14 if(l==r){ tree[num]=A[l]; return; }15 build(num<<1,l,mid);16 build(num<<1|1,mid+1,r);17 tree[num]=tree[num<<1]+tree[num<<1|1];18 }19 20 void pushdown(int num){21 if(lazy[num]){22 int mid=(left[num]+right[num])>>1;23 tree[num<<1]+=(mid-left[num]+1)*lazy[num];24 tree[num<<1|1]+=(right[num]-mid)*lazy[num];25 lazy[num<<1]+=lazy[num];26 lazy[num<<1|1]+=lazy[num];27 lazy[num]=0;28 }29 }30 31 void update(int num,int l,int r,LL add){32 if(left[num]>=l&&right[num]<=r){33 tree[num]+=(right[num]-left[num]+1)*add;34 lazy[num]+=add;35 return;36 }37 if(left[num]>r||right[num]<l)return;38 pushdown(num);39 update(num<<1,l,r,add);40 update(num<<1|1,l,r,add);41 tree[num]=tree[num<<1]+tree[num<<1|1];42 }43 44 LL Query(int num,int l,int r){45 if(left[num]>=l&&right[num]<=r)return tree[num];46 if(left[num]>r||right[num]<l) return 0;47 LL ret=0;48 pushdown(num);49 ret+=Query(num<<1,l,r);50 ret+=Query(num<<1|1,l,r);51 return ret;52 }53 54 int main(){55 scanf("%d%d",&n,&m);56 for(int i=1;i<=n;i++)scanf("%lld",&A[i]);57 build(1,1,n);58 for(int i=1;i<=m;i++){59 int f,x,y;LL add;60 scanf("%d",&f);61 switch(f){62 case 1:scanf("%d%d%lld",&x,&y,&add);update(1,x,y,add);break;63 case 2:scanf("%d%d",&x,&y);printf("%lld\n",Query(1,x,y));break;64 default:printf("Orz %%%");break;65 }66 }67 68 return 0;69 }
//以下是维护序列的代码：(支持乘法运算)#includetypedef long long LL;static const int maxm=100005;
LL A[maxm],pls[maxm<<2],mul[maxm<<2],tr[maxm<<2];int left[maxm<<2],right[maxm<<2];int n,m;
LL MOD;int build(int id,int l,int r){
left[id]=l;right[id]=r;mul[id]=1; if(l==r)return tr[id]=A[l]%MOD,0; int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
tr[id]=(tr[id<<1]+tr[id<<1|1])%MOD;
}void pushdown(int id){ int l=left[id];int r=right[id];int mid=(l+r)>>1;
pls[id<<1]=(pls[id<<1]*mul[id]%MOD+pls[id])%MOD;
pls[id<<1|1]=(pls[id<<1|1]*mul[id]%MOD+pls[id])%MOD;
mul[id<<1]=(mul[id]*mul[id<<1])%MOD;
mul[id<<1|1]=(mul[id]*mul[id<<1|1])%MOD;
tr[id<<1]=(tr[id<<1]*mul[id]%MOD+pls[id]*(mid-l+1)%MOD)%MOD;
tr[id<<1|1]=(tr[id<<1|1]*mul[id]%MOD+pls[id]*(r-mid)%MOD)%MOD;
mul[id]=1;pls[id]=0;
}void modify(int id,int l,int r,int c,int opt){ if(left[id]>=l&&right[id]<=r){ if(opt==1){
mul[id]=(mul[id]*c)%MOD;
pls[id]=(pls[id]*c)%MOD;
tr[id]=(tr[id]*c)%MOD;
}else if(opt==2){
pls[id]=(pls[id]+c)%MOD;
tr[id]=(tr[id]+(LL)c*(right[id]-left[id]+1)%MOD)%MOD;
} return ;
} if(right[id]r)return ;
pushdown(id);
modify(id<<1,l,r,c,opt);
modify(id<<1|1,l,r,c,opt);
tr[id]=(tr[id<<1]+tr[id<<1|1])%MOD;
}
LL Query(int id,int l,int r){ if(left[id]>=l&&right[id]<=r)return tr[id]%MOD; if(left[id]>r||right[id]<l)return 0;
pushdown(id); return (Query(id<<1,l,r)%MOD+Query(id<<1|1,l,r)%MOD)%MOD;
}int main(){ int opt,l,r,c;
scanf("%d%lld",&n,&MOD); for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
scanf("%d",&m);
build(1,1,n);
while(m--){
scanf("%d",&opt); if(opt!=3){
scanf("%d%d%d",&l,&r,&c);
modify(1,l,r,c,opt);
} else scanf("%d%d",&l,&r),printf("%lld\n",Query(1,l,r)%MOD);
} return 0;
}
8、网络最大流
#includeusing namespace std;#define inf 233333333#define il inlineil int gi()
{ int a=0;char x=getchar();bool f=0; while((x<'0'||x>'9')&&x!='-')x=getchar(); if(x=='-')x=getchar(),f=1; while(x>='0'&&x<='9')a=a*10+x-48,x=getchar(); return f?-a:a;
}const int N=100005,M=10005;struct edge{int to,net,w;
}e[N*2];int h[M],cnt=1,n,m,s,t,ans,flow,dis[M];
queue<int>q;
il void add(int u,int v,int w)
{
e[++cnt].to=v,e[cnt].w=w,e[cnt].net=h[u],h[u]=cnt;
}
il int bfs()
{
memset(dis,-1,sizeof(dis));
dis[s]=0;
q.push(s); while(!q.empty())
{ int u=q.front();
q.pop(); for(int i=h[u];i;i=e[i].net)
{ int v=e[i].to; if(dis[v]==-1&&e[i].w>0){dis[v]=dis[u]+1;q.push(v);}
}
} return dis[t]!=-1;
}
il int dfs(int u,int op)
{ if(u==t)return op; int flow=0,tmp=0; for(int i=h[u];i;i=e[i].net)
{ int v=e[i].to; if(dis[v]==dis[u]+1&&e[i].w>0){
tmp=dfs(v,min(op,e[i].w)); if(!tmp)continue;
op-=tmp;flow+=tmp;
e[i].w-=tmp;e[i^1].w+=tmp; if(!op)break; // return tmp; }
} return flow;
}int main()
{
n=gi(),m=gi(),s=gi(),t=gi(); int u,v,w; for(int i=1;i<=m;i++)
{
u=gi(),v=gi(),w=gi();
add(u,v,w),add(v,u,0);
} while(bfs())ans+=dfs(s,inf);
printf("%d\n",ans); return 0;
}
