noip的一些模板(参考了神牛的博客)

一、图论

1.单源最短路

(1)spfa

已加SLF优化 419ms

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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 <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <queue>
 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<hn> 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 hua
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 }

(3)dijkstra+配对堆 380ms 吊打用SLF优化的spfa啊啊啊啊啊

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <ext/pb_ds/priority_queue.hpp>
 6 #define pa pair<int,int>
 7 #define mp make_pair
 8 using namespace std;
 9 using namespace __gnu_pbds;
10 typedef __gnu_pbds::priority_queue<pa,greater<pa>,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 <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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
");
60         else printf("%d
",d[i]);
61     }
62 }

3.最小生成树

洛谷P3366

kruskal

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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 <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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
",ans);
37     }
38 }

5.割点

洛谷P3388

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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
",ans);
47     for(int i=1;i<=n;i++) if(iscut[i]) printf("%d ",i);
48 }

6.tarjan 强连通分量

POJ2186

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cmath>
 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 <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 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
",ans);
49 }

9、tarjan缩点

洛谷p3387

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 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~r
13     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
",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(head<=tail&&a[q[tail]]>a[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 <cstdio>
 3 #include <algorithm>
 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
",Query(1,x,y));break;
64             default:printf("Orz %%%");break;
65         }
66     }
67 
68     return 0;
69 }

//以下是维护序列的代码：(支持乘法运算)
#include <cstdio>

typedef 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]<l||left[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
",Query(1,l,r)%MOD);
    }

    return 0;
}

8、网络最大流

#include<bits/stdc++.h>
using namespace std;
#define inf 233333333
#define il inline
il 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
",ans);
    return 0;
}

PS：～蒟蒻写博客不易，转载请注明出处，万分感谢！～