ACM菜鸡选手自备的模板（不喜勿喷，纯属自备

------------------快速幂

------------------矩阵快速幂

------------------Dijstrla算法

------------------Spfa算法

------------------Floyd算法

------------------Tarjan算法

------------------Prim算法

------------------Kruskal算法

------------------EdmondsKarp算法

------------------Dinic算法

------------------拓扑排序

------------------树状数组

------------------线段树+离散化处理

------------------线段树+dfs序

------------------线段树+扫描线

------------------主席树

------------------树链剖分+线段树

------------------莫队+dfs序

------------------st表

------------------multiset的应用

------------------kmp算法

------------------字典树

------------------manacher算法

------------------并查集

------------------快速乘

------------------单调队列

------------------三分

快速幂

 1 typedef long long ll;
 2 ll mod;
 3 ll qpow(ll a, ll n)//计算a^n % mod
 4 {
 5     ll re = 1;
 6     while(n)
 7     {
 8         if(n & 1)//判断n的最后一位是否为1
 9             re = (re * a) % mod;
10         n >>= 1;//舍去n的最后一位
11         a = (a * a) % mod;//将a平方
12     }
13     return re % mod;
14 }

View Code

矩阵快速幂（19年牛客多校第五场B）

十进制版本，二进制同理

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 char s[1000005];
 8 ll mod;
 9 struct Matrix
10 {
11     ll a[2][2];
12     Matrix(int x)
13     {
14         a[0][0]=a[1][1]=x;
15         a[1][0]=a[0][1]=0;
16     }
17     Matrix operator *(Matrix s)
18     {
19         Matrix ans(0);
20         for(ll k=0; k<2; k++)
21         {
22             for(ll i=0; i<2; i++)
23             {
24                 ll sum=0;
25                 for(ll j=0; j<2; j++)
26                     sum=(sum+a[i][j]*s.a[j][k])%mod;
27                 ans.a[i][k]=sum;
28             }
29         }
30         return ans;
31     }
32 };
33 Matrix ten(Matrix s)
34 {
35     Matrix ans(1);
36     for(ll i=0; i<10; i++)
37         ans=ans*s;
38     return ans;
39 }
40 Matrix quick(Matrix s,char a[],ll len)
41 {
42     Matrix base(1),ans(1);
43     Matrix k(1);
44     base=s;
45     for(ll i=len-1; i>=0; i--)
46     {
47         if(a[i]!='0')
48         {
49             for(ll j=1; j<=a[i]-'0'; j++)
50                 ans=ans*base;
51         }
52         base=ten(base);
53     }
54     return ans;
55 }
56 int main()
57 {
58     ll x0,x1,a,b,i,j,len;
59     Matrix ss(0),ans(0);
60     while(scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b)!=EOF)
61     {
62         scanf("%s",s);
63         scanf("%lld",&mod);
64         ss.a[0][1]=1;
65         ss.a[0][0]=0;
66         ss.a[1][0]=b;
67         ss.a[1][1]=a;
68         if(strcmp(s,"1")==0)
69         {
70             printf("%lld
",x1);
71         }
72         else
73         {
74             char *p=s;
75             len=strlen(p);
76             if(p[len-1]!='0')
77             {
78                 p[len-1]--;
79             }
80             else
81             {
82                 p[len-1]='9';
83                 i=len-2;
84                 while(i>=0&&p[i]=='0')
85                     p[i]='9',i--;
86                 p[i]--;
87             }
88             if(p[0]=='0')
89                 ans=quick(ss,p+1,len-1);
90             else
91                 ans=quick(ss,p,len);
92             printf("%lld
",(ans.a[1][0]*x0+ans.a[1][1]*x1)%mod);
93         }
94     }
95     return 0;
96 }

View Code

Dijstrla算法（POJ2387）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 using namespace std;
 6 int head[1005];
 7 struct node
 8 {
 9     int k;
10     int step;
11     int next;
12 } a[4005];
13 int tol;
14 bool vis[1005];
15 inline void add(int x,int y,int z)
16 {
17     a[tol].next=head[x];
18     a[tol].k=y;
19     a[tol].step=z;
20     head[x]=tol++;
21     a[tol].next=head[y];
22     a[tol].k=x;
23     a[tol].step=z;
24     head[y]=tol++;
25 }
26 int n,t;
27 bool operator <(const node &x,const node &y)
28 {
29     return y.step<x.step;
30 }
31 int dij()
32 {
33     node r,p;
34     p.step=0;
35     p.k=1;
36     priority_queue<node>q;
37     q.push(p);
38     while(!q.empty())
39     {
40         p=q.top();
41         q.pop();
42         if(vis[p.k])
43             continue;
44         vis[p.k]=true;
45         if(p.k==t)
46             return p.step;
47         for(int i=head[p.k]; i!=-1; i=a[i].next)
48         {
49             if(!vis[a[i].k])
50             {
51                 r.k=a[i].k;
52                 r.step=p.step+a[i].step;
53                 q.push(r);
54             }
55         }
56     }
57     return 0;
58 }
59 int main()
60 {
61     int x,y,z,i;
62     while(scanf("%d%d",&n,&t)!=EOF)
63     {
64         tol=0;
65         memset(head,-1,sizeof(head));
66         memset(vis,false,sizeof(vis));
67         for(i=0; i<n; i++)
68             scanf("%d%d%d",&x,&y,&z),add(x,y,z);
69         printf("%d
",dij());
70     }
71     return 0;
72 }

View Code

Spfa算法

判负环（POJ1860）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<queue>
 6 using namespace std;
 7 int head[105];
 8 struct edge
 9 {
10     double a,b;
11     int k;
12     int next;
13 } aa[305];
14 int tol;
15 inline void add(int x,int y,double s1,double s2)
16 {
17     aa[tol].next=head[x];
18     aa[tol].k=y;
19     aa[tol].a=s1;
20     aa[tol].b=s2;
21     head[x]=tol++;
22 }
23 double dist[105];
24 bool vis[105];
25 int num[105];
26 int n,m;
27 int spfa(int x)
28 {
29     int i;
30     queue<edge>q;
31     edge p;
32     p.k=x;
33     q.push(p);
34     while(!q.empty())
35     {
36         p=q.front();
37         q.pop();
38         vis[p.k]=false;
39         for(i=head[p.k]; i!=-1; i=aa[i].next)
40         {
41             if(dist[aa[i].k]<(dist[p.k]-aa[i].b)*aa[i].a)
42             {
43                 dist[aa[i].k]=(dist[p.k]-aa[i].b)*aa[i].a;;
44                 if(!vis[aa[i].k])
45                 {
46                     vis[aa[i].k]=true;
47                     num[aa[i].k]++;
48                     q.push(aa[i]);
49                     if(num[aa[i].k]>=n)
50                         return 1;
51                 }
52             }
53         }
54     }
55     return 0;
56 }
57 int main()
58 {
59     int i,j,s,t;
60     int x,y;
61     double s1,s2,s3,s4,v;
62     while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF)
63     {
64         tol=0;
65         memset(vis,false,sizeof(vis));
66         memset(dist,0,sizeof(dist));
67         memset(head,-1,sizeof(head));
68         memset(num,0,sizeof(num));
69         for(i=0; i<m; i++)
70         {
71             scanf("%d%d%lf%lf%lf%lf",&x,&y,&s1,&s2,&s3,&s4);
72             add(x,y,s1,s2);
73             add(y,x,s3,s4);
74         }
75         dist[s]=v;
76         if(spfa(s))
77             printf("YES
");
78         else
79             printf("NO
");
80     }
81     return 0;
82 }

View Code

Floyd算法

 1 void floyd()
 2 {
 3        int i,j,k;
 4        for(k=1;k<=N;k++)
 5               for(i=1;i<=N;i++)
 6                      for(j=1;j<=N;j++)
 7                             if(map[i][j]>map[i][k]+map[k][j])
 8                             {
 9                                    map[i][j]=map[i][k]+map[k][j];
10                                    path[i][j]=path[i][k];
11                             }
12 }

View Code

Tarjan算法（19南昌邀请赛G）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<set>
  4 #include<string>
  5 #include<cstring>
  6 #include<map>
  7 #include<stack>
  8 #include<algorithm>
  9 using namespace std;
 10 #define INF 0x3f3f3f3f
 11 int dfn[100005];
 12 int low[100005];
 13 int id[100005];
 14 int due[100005];
 15 struct node
 16 {
 17     int k;
 18     int next;
 19 } e[300005];
 20 int head[100005],tol;
 21 inline void add(int x,int y)
 22 {
 23     e[tol].next=head[x];
 24     e[tol].k=y;
 25     head[x]=tol++;
 26 }
 27 bool vis[100005];
 28 stack<int>st;
 29 int tot,cnt;
 30 struct ss
 31 {
 32     int no;
 33     int num;
 34 }a[100005];
 35 void Tarjan(int x)
 36 {
 37     low[x]=cnt;
 38     dfn[x]=cnt++;
 39     vis[x]=true;
 40     st.push(x);
 41     for(int i=head[x]; i!=-1; i=e[i].next)
 42     {
 43         if(!dfn[e[i].k])
 44         {
 45             Tarjan(e[i].k);
 46             low[x]=min(low[e[i].k],low[x]);
 47         }
 48         else if(vis[e[i].k])
 49         {
 50             low[x]=min(low[x],dfn[e[i].k]);
 51         }
 52     }
 53     int t;
 54     if(dfn[x]==low[x])
 55     {
 56         int k;
 57         do
 58         {
 59             k=st.top();
 60             st.pop();
 61             id[k]=tot;
 62             vis[k]=false;
 63         }
 64         while(k!=x);
 65         tot++;
 66     }
 67 }
 68 bool cmp(ss s1,ss s2)
 69 {
 70     return s1.num>s2.num;
 71 }
 72 int main()
 73 {
 74     int n,m;
 75     int out,in,x,y,i,t,j,ans,q;
 76     bool flag;
 77     while(scanf("%d%d",&n,&q)!=EOF)
 78     {
 79         memset(vis,false,sizeof(vis));
 80         memset(dfn,0,sizeof(dfn));
 81         memset(id,0,sizeof(id));
 82         memset(head,-1,sizeof(head));
 83         tol=0;
 84         tot=1;
 85         cnt=1;
 86         flag=true;
 87         stack<int>ss;
 88         swap(ss,st);
 89         for(i=1;i<=3;i++)
 90         {
 91             for(j=1;j<=n;j++)
 92             {
 93               scanf("%d",&a[j].num),a[j].no=j;
 94             }
 95             sort(a+1,a+n+1,cmp);
 96             for(j=2;j<=n;j++)
 97                 if(a[j-1].num>a[j].num)
 98                 add(a[j-1].no,a[j].no);
 99         }
100         for(i=1; i<=n; i++)
101             if(!id[i])
102             {
103                 Tarjan(i);
104             }
105         for(i=1; i<=n; i++)
106         {
107             for(j=head[i]; j!=-1; j=e[j].next)
108             {
109                 if(id[i]!=id[e[j].k])
110                 {
111                     due[id[e[j].k]]++;
112                 }
113             }
114         }
115         in=0;
116         out=0;
117         for(i=1; i<tot; i++)
118         {
119            if(due[i]==0)
120            {
121             out++;
122             ans=i;
123            }
124         }
125       for(i=1;i<=q;i++)
126       {
127           scanf("%d",&in);
128           if(out>=2)
129             printf("NO
");
130           else if(due[id[in]]==0)
131           {
132               printf("YES
");
133           }
134           else
135             printf("NO
");
136       }
137 
138     }
139 
140 }

View Code

Prim算法(POJ1287)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cstdlib>
 6 using namespace std;
 7 int head[1005];
 8 #define INF 0x3f3f3f3f
 9 typedef long long ll;
10 struct node
11 {
12     int k;
13     int step;
14     int next;
15 } a[1000005];
16 int tol;
17 bool operator <(const node &x,const node &y)
18 {
19     return y.step<x.step;
20 }
21 int se=0;
22 bool vis[105];
23 int dist[1005];
24 inline void add(int x,int y,int z)
25 {
26     a[tol].next=head[x];
27     a[tol].k=y;
28     a[tol].step=z;
29     head[x]=tol++;
30     a[tol].next=head[y];
31     a[tol].k=x;
32     a[tol].step=z;
33     head[y]=tol++;
34 }
35 int n;
36 int prim()
37 {
38     // printf("sss
");
39     node r,p;
40     p.step=0;
41     int sum=0;
42     p.k=1;
43     priority_queue<node>q;
44     q.push(p);
45     dist[1]=0;
46     while(!q.empty())
47     {
48         p=q.top();
49         q.pop();
50         if(vis[p.k])
51             continue;
52         // printf("p.k=%d %d
",p.k,p.step);
53         vis[p.k]=true;
54         sum+=p.step;
55         for(int i=head[p.k]; i!=-1; i=a[i].next)
56         {
57             if(a[i].step<dist[a[i].k]&&!vis[a[i].k])
58             {
59                 dist[a[i].k]=a[i].step;
60                 node r;
61                 r.k=a[i].k;
62                 r.step=a[i].step;
63                 q.push(r);
64             }
65         }
66     }
67     return sum;
68 }
69 int main()
70 {
71     int x,y,z,i,t,j;
72     int m;
73     //  printf("%lld
",Fermat(1902382644,1e9+7));
74     // freopen("in.txt","r",stdin);
75     while(scanf("%d",&n)!=EOF&&n)
76     {
77         tol=0;
78         scanf("%d",&m);
79         memset(head,-1,sizeof(head));
80         memset(vis,false,sizeof(vis));
81         memset(dist,INF,sizeof(dist));
82         for(i=1; i<=m; i++)
83         {
84            scanf("%d %d %d",&x,&y,&z);
85            add(x,y,z);
86         }
87         //  printf("sss
");
88         printf("%d
",prim());
89     }
90     return 0;
91 }

View Code

Kruskal算法(POJ2421)

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<vector>
 4 #include<queue>
 5 #include<cstring>
 6 #include<algorithm>
 7 using namespace std;
 8 int parent[105];
 9 struct node
10 {
11     int x,y;
12     int step;
13 }a[100005];
14 int findroot(int x)
15 {
16     if(parent[x]!=x)
17         parent[x]=findroot(parent[x]);
18     return parent[x];
19 }
20 bool mergeroot(int x,int y)
21 {
22     int p1=findroot(x);
23     int p2=findroot(y);
24     if(p1==p2)
25         return false;
26    parent[p1]=p2;
27    return true;
28 }
29 bool cmp(node s1,node s2)
30 {
31     return s1.step<s2.step;
32 }
33 int main()
34 {
35     int n,x,y;
36     int m,i,j,ans,k;
37     while(scanf("%d",&n)!=EOF)
38     {
39         for(i=1;i<=n;i++)
40         {
41            parent[i]=i;
42         }
43         k=0;
44         for(i=1;i<=n;i++)
45             for(j=1;j<=n;j++)
46             scanf("%d",&a[k].step),a[k].x=i,a[k++].y=j;
47             sort(a,a+k,cmp);
48         ans=0;
49         scanf("%d",&m);
50         for(i=1;i<=m;i++)
51             scanf("%d %d",&x,&y),mergeroot(x,y);
52         for(i=0;i<k;i++)
53         {
54             if(mergeroot(a[i].x,a[i].y))
55                 ans+=a[i].step;
56         }
57         printf("%d
",ans);
58     }
59     return 0;
60 }

View Code

EdmondsKarp算法（HDU3549）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<string>
  5 #include<iostream>
  6 #include<queue>
  7 using namespace std;
  8 typedef long long ll;
  9 #define INF 0x3f3f3f3f
 10 struct edge
 11 {
 12     int w;
 13     int k;
 14     int next;
 15 } e[2005];
 16 struct pre
 17 {
 18     int id;
 19     int node;
 20 } pre[2005];
 21 int head[1005];
 22 bool vis[1005];
 23 int tol;
 24 int n,m;
 25 inline void add(int x,int y,int w)
 26 {
 27     e[tol].next=head[x];
 28     e[tol].w=w;
 29     e[tol].k=y;
 30     head[x]=tol++;
 31 }
 32 void init()
 33 {
 34     tol=0;
 35     for(int i=1; i<=n; i++)
 36         head[i]=-1;
 37 }
 38 bool bfs(int x,int y)
 39 {
 40     queue<edge>q;
 41     int i,j;
 42     for(i=1; i<=n; i++)
 43         vis[i]=false;
 44     vis[x]=true;
 45     edge p,r;
 46     p.k=x;
 47     q.push(p);
 48     while(!q.empty())
 49     {
 50         p=q.front();
 51         q.pop();
 52         if(p.k==y)
 53             return true;
 54         for(i=head[p.k]; i!=-1; i=e[i].next)
 55         {
 56             if(!vis[e[i].k]&&e[i].w)
 57             {
 58                 pre[e[i].k].node=p.k;
 59                 pre[e[i].k].id=i;
 60                 vis[e[i].k]=true;
 61                 q.push(e[i]);
 62             }
 63         }
 64     }
 65     return false;
 66 }
 67 int EK(int x,int y)
 68 {
 69     int ans=0;
 70     while(bfs(x,y))
 71     {
 72         int xx=y;
 73         int minv=INF;
 74         while(xx!=x)
 75         {
 76             minv=min(minv,e[pre[xx].id].w);
 77             xx=pre[xx].node;
 78         }
 79         for(int i=n; i!=1; i=pre[i].node)
 80         {
 81             e[pre[i].id].w-=minv;
 82             e[pre[i].id^1].w+=minv;
 83         }
 84         ans+=minv;
 85     }
 86     return ans;
 87 }
 88 int main()
 89 {
 90     int t;
 91     int i,j,x,y,w,k=1;
 92     scanf("%d",&t);
 93     while(t--)
 94     {
 95         scanf("%d %d",&n,&m);
 96         init();
 97         for(i=1; i<=m; i++)
 98             scanf("%d%d%d",&x,&y,&w),add(x,y,w),add(y,x,0);
 99         printf("Case %d: %d
",k++,EK(1,n));
100     }
101     return 0;
102 }

View Code

Dinic算法（HDU3549）

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #include<string>
  5 #include<iostream>
  6 #include<queue>
  7 using namespace std;
  8 typedef long long ll;
  9 #define INF 0x3f3f3f3f
 10 struct edge
 11 {
 12     int w;
 13     int k;
 14     int next;
 15     edge(int kk,int ww)
 16     {
 17         k=kk;
 18         w=ww;
 19     }
 20     edge() {}
 21 } e[2005];
 22 int head[1005];
 23 int dis[1005];
 24 bool vis[1005];
 25 int tol;
 26 int n,m;
 27 inline void add(int x,int y,int w)
 28 {
 29     e[tol].next=head[x];
 30     e[tol].w=w;
 31     e[tol].k=y;
 32     head[x]=tol++;
 33 }
 34 bool bfs(int s,int t)
 35 {
 36     int i,j;
 37     queue<int>q;
 38     for(i=1; i<=n; i++)
 39         dis[i]=0;
 40     q.push(s);
 41     dis[s]=1;
 42     while(!q.empty())
 43     {
 44         int x=q.front();
 45         q.pop();
 46         if(x==t)
 47             return true;
 48         for(i=head[x]; i!=-1; i=e[i].next)
 49         {
 50             if(e[i].w&&!dis[e[i].k])
 51             {
 52                 dis[e[i].k]=dis[x]+1;
 53                 q.push(e[i].k);
 54             }
 55         }
 56     }
 57     return false;
 58 }
 59 int dfs(int x,int t,int maxflow)
 60 {
 61     if(x==t)
 62         return maxflow;
 63     int ans=0;
 64     for(int i=head[x]; i!=-1; i=e[i].next)
 65     {
 66         if(dis[e[i].k]==dis[x]+1&&e[i].w&&maxflow>ans)
 67         {
 68             int tt=dfs(e[i].k,t,min(maxflow-ans,e[i].w));
 69             e[i].w-=tt;
 70             e[i^1].w+=tt;
 71             ans+=tt;
 72         }
 73     }
 74     return ans;
 75 }
 76 int Dinc(int s,int t)
 77 {
 78     int ans=0;
 79     while(bfs(s,t))
 80     {
 81         ans+=dfs(s,t,INF);
 82     }
 83     return ans;
 84 }
 85 int main()
 86 {
 87     int t;
 88     int i,j,x,y,w,k=1;
 89     scanf("%d",&t);
 90     while(t--)
 91     {
 92         scanf("%d %d",&n,&m);
 93         tol=0;
 94         for(i=1;i<=n;i++)head[i]=-1;
 95         for(i=1; i<=m; i++)
 96             scanf("%d%d%d",&x,&y,&w),add(x,y,w),add(y,x,0);
 97         printf("Case %d: %d
",k++,Dinc(1,n));
 98     }
 99     return 0;
100 }

View Code

拓扑排序

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<string>
 6 #include<queue>
 7 using namespace std;
 8 struct node
 9 {
10     int k;
11     int next;
12 } a[205];
13 int head[105];
14 int tol;
15 inline void add(int x,int y)
16 {
17     a[tol].next=head[x];
18     a[tol].k=y;
19     head[x]=tol++;
20 }
21 int due[105];
22 bool vis[105];
23 int main()
24 {
25     int n,m,x,y,i,j,cnt,t;
26     bool flag;
27     while(scanf("%d%d",&n,&m)!=EOF)
28     {
29         memset(due,0,sizeof(due));
30         memset(head,-1,sizeof(head));
31         memset(vis,false,sizeof(vis));
32         tol=0;
33         for(i=0; i<m; i++)
34             scanf("%d%d",&x,&y),due[y]++,add(x,y);
35        flag=true;
36        t=n;
37        queue<int>q;
38        for(i=1;i<=n;i++)
39        {
40            if(due[i]==0)
41            {
42                node p;
43                q.push(i);
44            }
45        }
46        while(!q.empty())
47        {
48            int p=q.front();
49            q.pop();
50            if(vis[p])
51             continue;
52             vis[p]=true;
53            t--;
54            for(i=head[p];i!=-1;i=a[i].next)
55            {
56                if(!vis[a[i].k])
57                {
58                    due[a[i].k]--;
59                    if(!due[a[i].k])
60                     q.push(a[i].k);
61                }
62            }
63        }
64      if(!t)
65         printf("YES
");
66      else
67         printf("NO
");
68     }
69     return 0;
70 }

View Code

树状数组

1.树状数组单点修改（HDU1166）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long ll;
 8 ll c[100005];
 9 ll m;
10 ll lowbit(ll x)  // 2^k
11 {
12     return x&(-x);
13 }
14 void update(ll i, ll x)//i点增cs量为x
15 {
16     while(i <= m)
17     {
18         c[i] += x;
19         i += lowbit(i);
20     }
21 }
22 ll sum(ll x)//区间求和 [1,x]
23 {
24     ll sum=0;
25     while(x>0)
26     {
27         sum+=c[x];
28         x-=lowbit(x);
29     }
30     return sum;
31 }
32 
33 ll Getsum(ll x1,ll x2) //求任意区间和
34 {
35     return sum(x2) - sum(x1-1);
36 }
37 int main()
38 {
39     ll i,j,t;
40     ll n;
41     ll op,a1,a2,r,sb;
42     scanf("%lld",&t);
43     string q;
44     ll p=0;
45     while(t--)
46     {
47         scanf("%lld",&m);
48   p++;
49   memset(c,0,sizeof(c));
50 
51 printf("Case %lld:
",p);
52         for(i=1;i<=m;i++)
53             {
54                 scanf("%lld",&r);
55                 update(i,r);
56             }
57              while(cin>>q&&q!="End")
58              {
59                  scanf("%lld %lld",&a1,&a2);
60                  if(q=="Query")
61                     printf("%lld
",Getsum(a1,a2));
62                  else if(q=="Add")
63                  {
64                      update(a1,a2);
65                  }
66                  else
67                     update(a1,-1*a2);
68              }
69 
70     }
71     return 0;
72 }

View Code

2.树状数组区间修改

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<queue>
 6 #include<vector>
 7 #include<set>
 8 #define ll long long
 9 using namespace std;
10 const int MAXN = 100100;
11 ll c1[MAXN],c2[MAXN],num[MAXN];
12 int n;
13 ll lowbit(ll x)
14 {
15     return x & -x;
16 }
17 
18 ll sigma(ll *a,ll pos)
19 {
20     ll ans = 0;
21     while(pos)
22     {
23         ans += a[pos];
24         pos -= lowbit(pos);
25     }
26     return ans;
27 }
28 
29 void add(ll a[],int pos, ll num)
30 {
31     while(pos < MAXN)
32     {
33         a[pos] += num;
34         pos += lowbit(pos);
35     }
36     return ;
37 }
38 
39 int main()
40 {
41     scanf("%d",&n);
42     for(int i = 1; i <= n; i++)
43     {
44         scanf("%I64d",num+i);
45         add(c1,i,num[i] - num[i-1]);
46         add(c2,i,(i-1)*(num[i]-num[i-1]));
47     }
48     //首先进行区间的更新操作
49     ll l,r,v;
50     scanf("%I64d%I64d%I64d",&l,&r,&v);
51     add(c1,l,v);
52     add(c1,r+1,-v);
53     add(c2,l,v*(l-1));
54     add(c2,r+1,-v*r);
55     //然后进行区间求和操作
56     scanf("%I64d%I64d",&l,&r);
57     ll sum1 = (l-1)*sigma(c1,l-1) - sigma(c2,l-1);
58     ll sum2 = r *sigma(c1,r) - sigma(c2,r);
59     printf("%I64d
",sum2 - sum1);
60 
61 }

View Code

线段树

1.线段树+离散化处理（POJ2528）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define il inline
  6 #define ull unsigned long long
  7 #define ll long long
  8 #define ls (u<<1)
  9 //等价于u*2
 10 #define rs (u<<1|1)
 11 //等价于u*2+1
 12 #define INF 0x3f3f3f3f
 13 using namespace std;
 14 const int maxn = 200000+7;
 15 int n,m;
 16 int hash1[10000005];
 17 int r[100005];
 18 int l[100005];
 19 int a[600005];
 20 struct node
 21 {
 22     int l,r;
 23     bool flag;
 24 } tree[1600005];
 25 void build(int u, int l, int r)
 26 {
 27     tree[u].l = l;
 28     tree[u].r = r;
 29   //  printf("u=%lld l=%lld r=%lld
")
 30     tree[u].flag=false;
 31     if(l==r)
 32     {
 33        //tree[u].flag=false;
 34         return ;
 35     }
 36     ll mid = (l+r) >> 1;
 37     build(ls,l,mid);
 38     build(rs,mid+1,r);
 39   //  pushup(u);
 40 }
 41 inline void pushup(int u)
 42 {
 43     tree[u].flag=tree[ls].flag&&tree[rs].flag;
 44 }
 45 inline void pushdown(int u)
 46 {
 47     tree[ls].flag=tree[rs].flag;
 48 }
 49 void update(int u, int l, int r)
 50 {
 51   // printf("u=%lld l=%lld r=%lld
",u,tree[u].l,tree[u].r);
 52     ll mid=(tree[u].l+tree[u].r)>>1;
 53     if(tree[u].flag)
 54         return;
 55     if(tree[u].l>=l&&tree[u].r<=r)
 56     {
 57        // printf("l=%lld r=%lld
",tree[u].l,tree[u].r);
 58         tree[u].flag=true;
 59         // tree[u].
 60         return ;
 61     }
 62     if(l<=mid)
 63         update(ls,l,r);
 64     if(r>mid)
 65         update(rs,l,r);
 66        pushup(u);
 67 }
 68 bool query(int u, int l, int r)
 69 {
 70     if(tree[u].flag)
 71         return true;
 72     if(l<=tree[u].l&&r>=tree[u].r)
 73     {
 74         return tree[u].flag;
 75     }
 76    // if(tree[u].lazy)
 77    // pushdown(u);
 78     ll mid=(tree[u].l+tree[u].r)>>1;
 79     bool flag=true;
 80     if(r>mid)
 81        flag=flag&&query(rs,l,r);
 82     if(l<=mid)
 83         flag=flag&&query(ls,l,r);
 84     return flag;
 85 }
 86 
 87 int main()
 88 {
 89     int i,t,k=0,cnt,s,ans;
 90     scanf("%d",&t);
 91     while(t--)
 92     {
 93     k=0;
 94     scanf("%d",&n);
 95     for(i=0;i<n;i++)
 96     {
 97         scanf("%d%d",&l[i],&r[i]);
 98         a[k++]=l[i]-1;
 99         a[k++]=l[i];
100         a[k++]=l[i]+1;
101         a[k++]=r[i]-1;
102         a[k++]=r[i];
103         a[k++]=r[i]+1;
104     }
105     ans=0;
106     sort(a,a+k);
107     k=unique(a,a+k)-a;
108     for(i=0;i<k;i++)
109         {
110             hash1[a[i]]=i;
111           //printf("hash=%lld i=%lld
",a[i],i);
112         }
113     build(1,0,k-1);
114     for(i=n-1;i>=0;i--)
115     {
116         if(!query(1,hash1[l[i]],hash1[r[i]]))
117             update(1,hash1[l[i]],hash1[r[i]]),ans++;
118          //   printf("ans=%lld
",ans);
119     }
120     printf("%d
",ans);
121     }
122 return 0;
123 }

View Code

2. 线段树+dfs序（HDU3974）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stack>
  6 #define ls (u<<1)
  7 #define rs (u<<1|1)
  8 #define INF 0x3f3f3f3f
  9 using namespace std;
 10 typedef int ll;
 11 struct node
 12 {
 13     ll l,r;
 14     ll lazy;
 15     ll data;
 16 } tree[400005];
 17 struct edge
 18 {
 19     ll k;
 20     ll next;
 21 } a[50005];
 22 inline void pushdown(ll u)
 23 {
 24     tree[ls].lazy=tree[rs].lazy=tree[u].lazy;
 25     tree[ls].data=tree[rs].data=tree[u].lazy;
 26     tree[u].lazy=0;
 27 }
 28 void build(ll u, ll l, ll r)
 29 {
 30     tree[u].l = l;
 31     tree[u].r = r;
 32     tree[u].lazy=0;
 33     tree[u].data=-1;
 34     if(l==r)
 35     {
 36         return ;
 37     }
 38     ll mid = (l+r) >> 1;
 39     build(ls,l,mid);
 40     build(rs,mid+1,r);
 41 }
 42 void update(ll u, ll l,ll r,ll c)
 43 {
 44 
 45     ll mid=(tree[u].l+tree[u].r)>>1;
 46     if(tree[u].l>=l&&tree[u].r<=r)
 47     {
 48         tree[u].data=c;
 49         tree[u].lazy=c;
 50         return ;
 51     }
 52     if(tree[u].lazy)
 53         pushdown(u);
 54     if(l<=mid)
 55         update(ls,l,r,c);
 56     if(r>mid)
 57         update(rs,l,r,c);
 58 }
 59 ll query(ll u, ll x)
 60 {
 61     if(tree[u].l==x&&tree[u].r==x)
 62     {
 63         return tree[u].data;
 64     }
 65     if(tree[u].lazy)
 66         pushdown(u);
 67     ll mid=(tree[u].l+tree[u].r)>>1;
 68     if(x<=mid)
 69         return query(ls,x);
 70     if(x>mid)
 71         return  query(rs,x);
 72 }
 73 ll p,tol;
 74 ll in[50005];
 75 ll out[50005];
 76 ll head[50005];
 77 inline void add(ll x,ll y)
 78 {
 79     a[tol].next=head[x];
 80     a[tol].k=y;
 81     head[x]=tol++;
 82 }
 83 void dfs(ll u)
 84 {
 85     in[u]=++p;
 86     for(ll i=head[u]; i!=-1; i=a[i].next)
 87         dfs(a[i].k);
 88     out[u]=p;
 89 }
 90 bool vis[50005];
 91 int main()
 92 {
 93     ll t=1,w;
 94     ll l,r,q,k,m,i;
 95     ll n;
 96     ll tol;
 97     char c;
 98     scanf("%d",&w);
 99     while(w--)
100     {
101         tol=0;
102         scanf("%d",&n);
103         memset(head,-1,sizeof(head));
104         memset(vis,false,sizeof(vis));
105         for(i=0; i<n-1; i++)
106         {
107             scanf("%d%d",&l,&r);
108             add(r,l);
109             vis[l]=true;
110         }
111         p=0;
112        for(i=1; i<=n; i++)
113             if(!vis[i])
114             {
115                 dfs(i);
116                 break;
117             }
118             build(1,1,n);
119         printf("Case #%d:
",t++);
120         scanf("%d",&m);
121         while(m--)
122         {
123             cin>>c;
124             scanf("%d",&k);
125             getchar();
126             if(c=='T')
127             {
128                 scanf("%d",&q);
129                 getchar();
130                 update(1,in[k],out[k],q);
131             }
132             else
133             {
134                 printf("%d
",query(1,in[k]));
135             }
136         }
137     }
138     return 0;
139 }

View Code

3.线段树+扫描线（HDU1255）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<stack>
  6 #define ls (u<<1)
  7 #define rs (u<<1|1)
  8 #define INF 0x3f3f3f3f
  9 using namespace std;
 10 struct node
 11 {
 12     int l,r;
 13     int cover;
 14 } tree[400005];
 15 struct edge
 16 {
 17     double l,r;
 18     double y;
 19     int t;
 20 } e[5005];
 21 bool cmp(edge x1,edge x2)
 22 {
 23     return x1.y<x2.y;
 24 }
 25 double s[2005];
 26 void build(int u, int l, int r)
 27 {
 28     tree[u].l = l;
 29     tree[u].r = r;
 30     tree[u].cover=0;
 31     if(l==r)
 32     {
 33         return ;
 34     }
 35     int mid = (l+r) >> 1;
 36     build(ls,l,mid);
 37     build(rs,mid+1,r);
 38 }
 39 inline void pushup(int u)
 40 {
 41     int k=min(tree[ls].cover,tree[rs].cover);
 42     tree[u].cover+=k;
 43     tree[ls].cover-=k;
 44     tree[rs].cover-=k;
 45 }
 46 inline pushdown(int u)
 47 {
 48     tree[ls].cover+=tree[u].cover;
 49     tree[rs].cover+=tree[u].cover;
 50     tree[u].cover=0;
 51 }
 52 void update(int u, int l,int r,int t)
 53 {
 54     int mid=(tree[u].l+tree[u].r)>>1;
 55     if(tree[u].l>=l&&tree[u].r<=r)
 56     {
 57         tree[u].cover+=t;
 58         return;
 59     }
 60  if(tree[u].cover&&tree[u].l!=tree[u].r)
 61       pushdown(u);
 62     if(l<=mid)
 63         update(ls,l,r,t);
 64     if(r>mid)
 65         update(rs,l,r,t);
 66     pushup(u);
 67 }
 68 double query(int u,int l,int r)
 69 {
 70     int mid=(tree[u].l+tree[u].r)>>1;
 71     if(tree[u].l>=l&&tree[u].r<=r&&tree[u].cover>=2)
 72     {
 73         return s[tree[u].r+1]-s[tree[u].l];
 74     }
 75     if(tree[u].l==tree[u].r)
 76         return 0;
 77     if(tree[u].cover&&tree[u].l!=tree[u].r)
 78         pushdown(u);
 79     double asb=0;
 80     if(l<=mid)
 81         asb+=query(ls,l,r);
 82     if(r>mid)
 83         asb+=query(rs,l,r);
 84     return asb;
 85 }
 86 int main()
 87 {
 88     int n;
 89     int t=0;
 90     int tol,i,k,j;
 91     int pos1,pos2;
 92     double x1,x2,y1,y2;
 93     double ans;
 94     scanf("%d",&t);
 95     while(t--)
 96     {
 97         scanf("%d",&n);
 98         tol=0;
 99         ans=0;
100         for(i=0; i<n; i++)
101         {
102             scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
103             s[tol]=x1;
104             s[tol+1]=x2;
105             e[tol].r=x2;
106             e[tol].l=x1;
107             e[tol].y=y1;
108             e[tol].t=1;
109             e[tol+1].r=x2;
110             e[tol+1].l=x1;
111             e[tol+1].y=y2;
112             e[tol+1].t=-1;
113             tol+=2;
114         }
115         sort(e,e+tol,cmp);
116         sort(s,s+tol);
117         k=unique(s,s+tol)-s;
118         build(1,0,k-1);
119         for(i=0; i<tol-1; i++)
120         {
121             pos1=lower_bound(s,s+k,e[i].l)-s;
122             pos2=lower_bound(s,s+k,e[i].r)-s-1;
123             update(1,pos1,pos2,e[i].t);
124             double sb=query(1,0,k-1);
125             ans+=sb*(e[i+1].y-e[i].y);
126         printf("%.2f
",ans);
127     }
128     return 0;
129 }

View Code

主席树（POJ2104）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef int ll;
 7 struct node
 8 {
 9     ll l,r;
10     ll ls,rs;
11     ll sum;
12 } tree[2000005];
13 ll rt[100005];
14 ll tol;
15 ll a[100005];
16 ll b[100005];
17 void build(ll &u,ll l,ll r)
18 {
19     u=tol++;
20     tree[u].l=l;
21     tree[u].r=r;
22     tree[u].sum=0;
23     ll mid=(tree[u].l+tree[u].r)>>1;
24     if(tree[u].r==tree[u].l)
25         return;
26     build(tree[u].ls,l,mid);
27     build(tree[u].rs,mid+1,r);
28 }
29 void update(ll p,ll &u,ll x)
30 {
31     u=tol++;
32     tree[u].l=tree[p].l;
33     tree[u].r=tree[p].r;
34     tree[u].ls=tree[p].ls;
35     tree[u].rs=tree[p].rs;
36     ll mid=(tree[u].l+tree[u].r)>>1;
37     tree[u].sum=tree[p].sum;
38     tree[u].sum++;
39     if(tree[u].l==tree[u].r)
40         return;
41     if(x>mid)
42         update(tree[p].rs,tree[u].rs,x);
43     else
44         update(tree[p].ls,tree[u].ls,x);
45 }
46 ll query(ll u,ll v,ll k)
47 {
48     ll mid=(tree[u].l+tree[u].r)>>1;
49     ll sum=tree[tree[v].ls].sum-tree[tree[u].ls].sum;
50     ll ans;
51     if(tree[u].l==tree[u].r)
52     {
53         return tree[u].l;
54     }
55     if(sum>=k)
56     {
57         ans=query(tree[u].ls,tree[v].ls,k);
58     }
59     else
60     {
61         ans=query(tree[u].rs,tree[v].rs,k-sum);
62     }
63     return ans;
64 }
65 int main()
66 {
67     tol=0;
68     ll n,m,s,i,j,l,r,k;
69     while(scanf("%d %d",&n,&m)!=EOF)
70     {
71         for(i=1; i<=n; i++)
72             scanf("%d",&a[i]),b[i]=a[i];
73         sort(b+1,b+n+1);
74         s=unique(b+1,b+n+1)-(b+1);
75         tol=0;
76         build(rt[0],1,s);
77         for(i=1; i<=n; i++)
78         {
79             ll pos=lower_bound(b+1,b+s+1,a[i])-(b);
80             update(rt[i-1],rt[i],pos);
81         }
82         for(i=1;i<=m;i++)
83         {
84             scanf("%d %d %d",&l,&r,&k);
85             s=query(rt[l-1],rt[r],k);
86            printf("%d
",b[s]);
87         }
88     }
89     return 0;
90 }

View Code

树链剖分+经典线段树（HDU2586）

  1 #include<iostream>
  2 #include<vector>
  3 #include<algorithm>
  4 #include<string>
  5 #include<map>
  6 #include<cstring>
  7 #include<cstdio>
  8 using namespace std;
  9 struct node
 10 {
 11     int k;
 12     int w;
 13     int next;
 14 } ed[80005];
 15 int head[40005];
 16 int tol,n;
 17 int maxi[40005<<2];
 18 inline void pushup(int u)
 19 {
 20     maxi[u]=maxi[u<<1]+maxi[u<<1|1];
 21 }
 22 void update(int u,int x,int l,int r,int num)
 23 {
 24     int mid=(l+r)>>1;
 25     if(l==r)
 26     {
 27         maxi[u]=num;
 28         return;
 29     }
 30     if(x<=mid)
 31         update(u<<1,x,l,mid,num);
 32     else
 33         update(u<<1|1,x,mid+1,r,num);
 34     pushup(u);
 35 }
 36 int query(int u,int l,int r,int L,int R)
 37 {
 38     if(L<=l&&r<=R)
 39     {
 40         return maxi[u];
 41     }
 42     int mid=(l+r)>>1;
 43     int ans=0;
 44     if(L<=mid)
 45     {
 46         ans+=query(u<<1,l,mid,L,R) ;
 47     }
 48     if(R>mid)
 49     {
 50         ans+=query(u<<1|1,mid+1,r,L,R) ;
 51     }
 52     return  ans;
 53 }
 54 inline void add(int x,int y,int w)
 55 {
 56     ed[tol].k=y;
 57     ed[tol].next=head[x];
 58     ed[tol].w=w;
 59     head[x]=tol++;
 60     ed[tol].k=x;
 61     ed[tol].next=head[y];
 62     ed[tol].w=w;
 63     head[y]=tol++;
 64 }
 65 int fa[40005];
 66 int son[40005];
 67 int size[40005];
 68 int depth[40005];
 69 int id[40005];
 70 int cnt;
 71 int top[40005];
 72 int pre[40005];
 73 void dfs1(int x,int d,int f)
 74 {
 75     depth[x]=d;
 76     fa[x]=f;
 77     son[x]=0;
 78     size[x]=1;
 79     int i;
 80     for(i=head[x]; i!=-1; i=ed[i].next)
 81     {
 82         if(ed[i].k!=f)
 83         {
 84             pre[ed[i].k]=ed[i].w;
 85             dfs1(ed[i].k,d+1,x);
 86             size[x]+=size[ed[i].k];
 87         }
 88         if(ed[i].k!=f&&(!son[x]||size[ed[i].k]>size[son[x]]))
 89             son[x]=ed[i].k;
 90     }
 91 }
 92 void dfs2(int x,int topf)
 93 {
 94     top[x]=topf;
 95     id[x]=++cnt;
 96     update(1,cnt,1,n,pre[x]);
 97     if(!son[x])
 98         return;
 99     int k;
100     dfs2(son[x],topf);
101     for(int i=head[x]; i!=-1; i=ed[i].next)
102     {
103         if(ed[i].k!=son[x]&&ed[i].k!=fa[x])
104         {
105             dfs2(ed[i].k,ed[i].k);
106         }
107         if(ed[i].k=son[x])
108             k=ed[i].w;
109     }
110 }
111 int main()
112 {
113     int m,x,y,w,i,s,f1,f2,t;
114     scanf("%d",&t);
115     while(t--)
116     {
117         tol=0;
118         scanf("%d %d",&n,&m);
119         memset(head,-1,sizeof(head));
120         memset(size,0,sizeof(size));
121         memset(maxi,0,sizeof(maxi));
122         for(i=0; i<n-1; i++)
123             scanf("%d%d%d",&x,&y,&w),add(x,y,w);
124         cnt=0;
125         pre[1]=0;
126         dfs1(1,1,1);
127         dfs2(1,1);
128         for(i=0; i<m; i++)
129         {
130             scanf("%d%d",&x,&y);
131             s=0;
132             while(top[x]!=top[y])
133             {
134                 if(depth[top[x]]>depth[top[y]])
135                 {
136                     s+=query(1,1,n,id[top[x]],id[x]);
137                     x=fa[top[x]];
138                 }
139                 else
140                 {
141                     s+=query(1,1,n,id[top[y]],id[y]);
142                     y=fa[top[y]];
143                 }
144             }
145             if(depth[x]>depth[y])
146             {
147                 s+=query(1,1,n,id[y]+1,id[x]);
148             }
149             else if(depth[x]<depth[y])
150             {
151                 s+=(query(1,1,n,id[x]+1,id[y]));
152             }
153             printf("%d
",s);
154         }
155     }
156     return 0;
157 }

View Code

莫队+dfs序（18年东北赛E HDU6504）

  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<cstdio>
  7 using namespace std;
  8 int head[100005];
  9 struct node
 10 {
 11     int k;
 12     int next;
 13 }a[200005];
 14 struct node1
 15 {
 16     int index;
 17     int l,r;
 18     int w;
 19 } ss[200005];
 20 int tol=0;
 21 inline void add(int x,int y)
 22 {
 23     a[tol].next=head[x];
 24     a[tol].k=y;
 25     head[x]=tol++;
 26     a[tol].next=head[y];
 27     a[tol].k=x;
 28     head[y]=tol++;
 29 }
 30 int in[200005];
 31 int out[200005];
 32 bool vis[100005];
 33 int aa[200005];
 34 int b[200005];
 35 int p;
 36 void dfs(int x)
 37 {
 38     in[x]=++p;
 39     b[p]=aa[x];
 40     for(int i=head[x]; i!=-1; i=a[i].next)
 41     {
 42         if(!vis[a[i].k])
 43         {
 44             vis[a[i].k]=true;
 45             dfs(a[i].k);
 46         }
 47     }
 48     out[x]=p;
 49 }
 50 int block;
 51 bool cmp(node1 s1,node1 s2)
 52 {
 53     if((s1.l/block)==(s2.l/block))
 54     {
 55         return s1.r<s2.r;
 56     }
 57     return s1.l<s2.l;
 58 }
 59 bool cmp1(node1 s1,node1 s2)
 60 {
 61     return s1.index<s2.index;
 62 }
 63 int cnt=0;
 64 int num[100005];
 65 inline void add(int x)
 66 {
 67     cnt+=num[x]==0;//if判断可能会tle
 68     num[x]++;
 69 }
 70 inline void del(int x)
 71 {
 72     cnt-=num[x]==1;//if判断可能会tle
 73     num[x]--;
 74 }
 75 int main()
 76 {
 77     int n,i,l,r,maxi;
 78     while(scanf("%d",&n)!=EOF)
 79     {
 80         tol=0;
 81         for(i=1; i<=n; i++)
 82             head[i]=-1,vis[i]=false;
 83             memset(num,0,sizeof(num));
 84         for(i=2; i<=n; i++)
 85             scanf("%d",&p),add(p,i);
 86         for(i=1; i<=n; i++)
 87             scanf("%d",&aa[i]);
 88         p=0;
 89         cnt=0;
 90         block=sqrt(n);
 91         vis[1]=true;
 92         dfs(1);
 93         for(i=1;i<=n;i++)
 94         {
 95             b[i+n]=b[i];
 96         }
 97         for(i=1; i<=n; i++)
 98             ss[i].l=in[i],ss[i].r=out[i],ss[i].index=i,ss[i+n].l=out[i]+1,ss[i+n].r=n+in[i]-1,ss[i+n].index=i+n;
 99             sort(ss+1,ss+2*n+1,cmp);
100             r=2*n;
101             for(i=1;i<=2*n;i++)
102                 add(b[i]);
103             l=1;
104             for(i=1;i<=2*n;i++)
105             {
106                 while(l<ss[i].l)
107                     del(b[l++]);
108                 while(r>ss[i].r)
109                     del(b[r--]);
110                 while(l>ss[i].l)
111                     add(b[--l]);
112                 while(r<ss[i].r)
113                     add(b[++r]);
114                 ss[i].w=cnt;
115             }
116             sort(ss+1,ss+2*n+1,cmp1);
117             maxi=0;
118             for(i=2;i<=n;i++)
119                 maxi=max(maxi,ss[i].w+ss[i+n].w);
120                 printf("%d
",maxi);
121     }
122     return 0;
123 }

View Code

st表

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 int a[1010];//原始输入数组
 5 int st[1010][20];//st表
 6 void init(int n)
 7 {
 8     for (int i = 0; i < n; i++)
 9         st[i][0] = a[i];
10 
11     for (int i = 1; (1 << i) <= n; i++)
12     {
13         for (int j = 0; j + (1 << i) - 1 < n; j++)
14             st[j][i] = min(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]);
15     }
16 }
17 int search(int l, int r)
18 {
19     int k = (int)(log((double)(r - l + 1)) / log(2.0));
20     return min(st[l][k],st[r - (1 << k) + 1][k]);
21 }
22 int main()
23 {
24     int n,m;
25     while (cin >> n >> m)
26     {
27         for (int i = 0; i < n; i++)
28             cin >> a[i];
29         init(n);
30         while (m--)
31         {
32             int l, r;
33             cin >> l >> r;
34             cout << search(l,r) << endl;;
35         }
36     }
37     return 0;
38 }

View Code

multiset的应用（19牛客多校第六场D）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<set>
 6 using namespace std;
 7 typedef long long ll;
 8 multiset<int>st;
 9 int a[1005];
10 int b[1005];
11 multiset<int> init(int n)
12 {
13     multiset<int>p;
14     for(int i=1; i<=n; i++)
15         p.insert(a[i]);
16     return p;
17 }
18 bool check(int x,int k)
19 {
20     multiset<int>p=st;
21     multiset<int>::iterator it;
22     for(int i=1; i<=k; i++)
23     {
24         int t=x;
25         it=p.upper_bound(t);
26         while(p.size()!=0&&(it!=(p.begin())))
27         {
28             it--;
29             t-=*it;
30             p.erase(it);
31             it=p.upper_bound(t);
32         }
33     }
34     if(p.size()==0)
35         return true;
36     else
37         return false;
38 }
39 int main()
40 {
41     int t;
42     int n,k,i,l,r,mid,kk=0,sum=0;
43     scanf("%d",&t);
44     while(t--)
45     {
46         scanf("%d%d",&n,&k);
47         st.clear();
48         mid=0;
49         sum=0;
50         for(i=1; i<=n; i++)
51             scanf("%d",&a[i]),mid=max(mid,a[i]),sum+=a[i];
52         st=init(n);
53         mid=max(mid,sum/k);
54             while(!check(mid,k))
55                 mid++;
56         printf("Case #%d: %d
",++kk,mid);
57     }
58     return 0;
59 }

View Code

kmp

注意这里是int平常应该是char（HDU1711）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 int s1[1000005];
 8 int s2[1000005];
 9 int next1[10005];
10 int kmp(int a[],int len1,int b[],int len2)
11 {
12    // int next[105];
13     next1[0]=-1;
14     next1[1]=0;
15     int i=2,j=0;
16     while(i<len2)
17     {
18         if(b[i-1]==b[j])
19         {
20             next1[i++]=++j;
21         }
22         else if(next1[j]==-1)
23         {
24             next1[i++]=0;
25         }
26         else
27             j=next1[j];
28     }
29     i=0;
30     j=0;
31     while(i<len1&&j<len2)
32     {
33         if(a[i]==b[j])
34             i++,j++;
35         else if(next1[j]==-1)
36         {
37             i++;
38         }
39         else
40             j=next1[j];
41     }
42     return j==len2?i-j+1:-1;
43 }
44 int main()
45 {
46     int n,m,i,t;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d%d",&n,&m);
51         for(i=0; i<n; i++)
52             scanf("%d",&s1[i]);
53         for(i=0; i<m; i++)
54             scanf("%d",&s2[i]);
55         printf("%d
",kmp(s1,n,s2,m));
56     }
57     return 0;
58 }

View Code

字典树（HDU1251）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<string.h>
 4 using namespace std;
 5 struct node
 6 {
 7     int next[27];
 8     int v;
 9     int init()
10     {
11         v=0;
12         memset(next,-1,sizeof(next));
13     }
14 }a[1000005];
15 int tol=0;
16 int ans=0;
17 void add(char s[],int len)
18 {
19     int now=0;
20     for(int i=0;i<len;i++)
21     {
22         int tmp=s[i]-'a';
23         if(a[now].next[tmp]==-1)
24         {
25             a[now].next[tmp]=++tol;
26             a[tol].init();
27         }
28         now=a[now].next[tmp];
29         a[now].v++;
30     };
31 }
32 int query(char s[],int len)
33 {
34     int now=0;
35 
36     for(int i=0;i<len;i++)
37     {
38         int tmp=s[i]-'a';
39         if(a[now].next[tmp]==-1)
40             return 0;
41             now=a[now].next[tmp];
42     }
43     return a[now].v;
44 }
45 char s[100];
46 int main()
47 {
48     int k;
49     a[0].init();
50     while(gets(s))
51     {
52         k=strlen(s);
53         if(k==0)
54             break;
55          add(s,k);
56     }
57     while(gets(s))
58     {
59         k=strlen(s);
60         printf("%d
",query(s,k));
61     }
62     return 0;
63 }

View Code

manacher算法（洛谷3805）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #define maxn 11000005
 7 using namespace std;
 8 int len[maxn<<1];
 9 char s[maxn],tmp[maxn<<1];
10 
11 inline int init(char *p){
12     int n=strlen(p);
13     tmp[0]='@';
14     for(int i=1;i<=2*n;i+=2){
15         tmp[i]='#',tmp[i+1]=p[i/2];
16     }
17     tmp[2*n+1]='#'; tmp[2*n+2]='$';
18     return 2*n+1;
19 }
20 
21 inline int Manacher(char *p,int n){
22     int mx=0,pos=0,ans=0;
23     for(int i=1;i<=n;i++){
24         if(mx>i) len[i]=min(mx-i,len[2*pos-i]);//i被mx覆盖了 
25         else len[i]=1;
26         while(p[i-len[i]]==p[i+len[i]]) len[i]++;//左右扩展 
27         if(len[i]+i>mx) mx=len[i]+i,pos=i;//更新 
28         ans=max(ans,len[i]-1);
29     }
30     return ans;
31 }
32 
33 int main(){
34     scanf("%s",s); int m=init(s);
35     printf("%d
",Manacher(tmp,m));
36     return 0;
37 }

View Code

并查集

 1 int findroot(int x)
 2 {
 3     if(x!=parent[x])
 4     {
 5         parent[x]=findroot(parent[x]);
 6     }
 7     return parent[x];
 8 }
 9 void mergeroot(int a,int b)
10 {
11     int p1=findroot(a);
12     int p2=findroot(b);
13     parent[p1]=p2;
14 }

View Code

快速乘

1 inline ll ksc(ll x,ll y,ll p){//计算x乘y的积
2     ll res=0;//加法初始化
3     while(y){
4         if(y&1)res=(res+x)%p;//模仿二进制
5         x=(x<<1)%p; y>>=1;//将x不断乘2达到二进制
6     }return res;
7 }
8 // ll 表示 long long

View Code

1 inline ll ksc(ll x,ll y,ll p){
2     ll z=(ld)x/p*y;
3     ll res=(ull)x*y-(ull)z*p;
4     return (res+p)%p;
5 }
6 // ll 表示 long long
7 // ld 表示 long double
8 // ull 表示 usigned long long
9 // 一种自动溢出的数据类型（存满了就会自动变为0）

View Code

单调队列（19牛客多校第三场F）

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 typedef long long ll;
 7 #define INF 100000000
 8 int mx[505],mi[505];
 9 int q1[505];
10 int q2[505];
11 int a[505][505];
12 int main()
13 {
14     int n,m,i,j,ans,q11,q21,q12,q22,k,last1,last2;
15     int t;
16     scanf("%d",&t);
17     while(t--)
18     {
19         scanf("%d%d",&n,&m);
20         ans=0;
21         for(i=1; i<=n; i++)
22         {
23             for(j=1; j<=n; j++)
24                 scanf("%d",&a[i][j]);
25         }
26         for(i=1; i<=n; i++)
27         {
28             for(j=1; j<=n; j++)
29                 mi[j]=mx[j]=a[i][j];
30             for(j=i; j<=n; j++)
31             {
32                 q11=q21=q12=q22=0;
33                 last1=1;
34                 last2=1;
35                 for(k=1; k<=n; k++)
36                 {
37                     mi[k]=min(mi[k],a[j][k]);
38                     mx[k]=max(mx[k],a[j][k]);
39                     while(q11!=q12&&mx[q1[q12]]<=mx[k])
40                         q12--;
41                     while(q21!=q22&&mi[q2[q22]]>=mi[k])
42                         q22--;
43                     q1[++q12]=k;
44                     q2[++q22]=k;
45                     while(q11!=q12&&q22!=q21&&mx[q1[q11+1]]-mi[q2[q21+1]]>m)
46                     {
47                         if(q1[q11+1]<q2[q21+1])
48                         {
49                             last1=q1[q11+1]+1;
50                             q11++;
51                         }
52                         else
53                         {
54                             last2=q2[q21+1]+1;
55                             q21++;
56                         }
57                     }
58                     if(q11!=q12&&q22!=q21)
59                     {
60                         ans=max((k-max(last1,last2)+1)*(j-i+1),ans);
61                     }
62                 }
63             }
64         }
65         printf("%d
",ans);
66     }
67     return 0;
68 }

View Code

三分

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 const double eps=1e-5;
 5 double a,b,c,xx,yy;
 6 double f(double x){
 7     return sqrt((x-xx)*(x-xx)+(a*x*x+b*x+c-yy)*(a*x*x+b*x+c-yy));
 8 }
 9 int main(){
10     scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&xx,&yy);
11     double l=-200,r=200;
12     while(r-l>eps){
13         double lm=l+(r-l)/3,rm=r-(r-l)/3;
14         if(f(lm)<f(rm)) r=rm;
15         else l=lm;
16     }
17     printf("%.3lf
",f(l));
18     return 0;
19 }

View Code