模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板
模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板模板
attack
发布于 2018-04-12 10:33:20
发布于 2018-04-12 10:33:20
图论
最短路
SPFA
1 #include<cstdio>
2 #include<queue>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=1000001;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12
13 struct node
14 {
15 int u,v,w,nxt;
16 }edge[MAXN];
17 int head[MAXN];
18 int num=1;
19 inline void add_edge(int x,int y,int z)
20 {
21 edge[num].u=x; edge[num].v=y;
22 edge[num].w=z; edge[num].nxt=head[x];
23 head[x]=num++;
24 }
25 int N,M,S=1;;
26 int dis[MAXN],vis[MAXN];
27 inline void SPFA()
28 {
29 queue<int>q;q.push(S);
30 while(q.size()!=0)
31 {
32 int p=q.front();
33 q.pop();vis[p]=0;
34 for(int i=head[p];i!=-1;i=edge[i].nxt)
35 if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
36 {
37 dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
38 if(!vis[edge[i].v]) vis[edge[i].v]=1,q.push(edge[i].v);
39 }
40 }
41 }
42 int main()/*S到其他节点的最短路*/
43 {
44 memset(head,-1,sizeof(head));
45 read(N);read(M);read(S);
46 for(int i=1;i<=N;i++) dis[i]=2147483647; dis[S]=0;
47 for(int i=1;i<=M;i++)
48 {
49 int x,y,z;read(x);read(y);read(z);
50 add_edge(x,y,z);
51 }
52 SPFA();
53 for(int i=1;i<=N;i++) printf("%d ",dis[i]);
54 return 0;
55 } 1 #include<cstdio>
2 #include<deque>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=1000001;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12
13 struct node
14 {
15 int u,v,w,nxt;
16 }edge[MAXN];
17 int head[MAXN];
18 int num=1;
19 inline void add_edge(int x,int y,int z)
20 {
21 edge[num].u=x; edge[num].v=y;
22 edge[num].w=z; edge[num].nxt=head[x];
23 head[x]=num++;
24 }
25 int N,M,S=1;;
26 int dis[MAXN],vis[MAXN];
27 inline void SPFA()
28 {
29 deque<int>q;q.push_front(S);
30 while(q.size()!=0)
31 {
32 int p=q.front();
33 q.pop_front();vis[p]=0;
34 for(int i=head[p];i!=-1;i=edge[i].nxt)
35 if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
36 {
37 dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
38 if(!vis[edge[i].v]) vis[edge[i].v]=1,q.size()!=0&&dis[edge[i].v]<dis[q.front()]?q.push_front(edge[i].v):q.push_back(edge[i].v);
39 }
40 }
41 }
42 int main()/*S到其他节点的最短路*/
43 {
44 memset(head,-1,sizeof(head));
45 read(N);read(M);read(S);
46 for(int i=1;i<=N;i++) dis[i]=2147483647; dis[S]=0;
47 for(int i=1;i<=M;i++)
48 {
49 int x,y,z;read(x);read(y);read(z);
50 add_edge(x,y,z);
51 }
52 SPFA();
53 for(int i=1;i<=N;i++) printf("%d ",dis[i]);
54 return 0;
55 } 1 #include<cstdio>
2 #include<cstring>
3 #include<ext/pb_ds/priority_queue.hpp>
4 using namespace __gnu_pbds;
5 const int MAXN=1000001;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12
13 struct node
14 {
15 int u,v,w,nxt;
16 }edge[MAXN];
17 int head[MAXN];
18 int num=1;
19 inline void add_edge(int x,int y,int z)
20 {
21 edge[num].u=x; edge[num].v=y;
22 edge[num].w=z; edge[num].nxt=head[x];
23 head[x]=num++;
24 }
25 int N,M,S=1;;
26 int dis[MAXN],vis[MAXN];
27 struct Compare
28 {
29 __inline__ __attribute((always_inline)) bool operator()(int a,int b)//我以前的题解提到过的强制inline的方法
30 {
31 return dis[a]>dis[b];
32 }
33 };//自定义比较器
34 inline void SPFA()
35 {
36 priority_queue<int,Compare>q;
37 q.push(S);
38 while(q.size()!=0)
39 {
40 int p=q.top();
41 q.pop();vis[p]=0;
42 for(int i=head[p];i!=-1;i=edge[i].nxt)
43 if(dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
44 {
45 dis[edge[i].v]=dis[edge[i].u]+edge[i].w;
46 if(!vis[edge[i].v]) vis[edge[i].v]=1,q.push(edge[i].v);
47 }
48 }
49 }
50 int main()/*S到其他节点的最短路*/
51 {
52 memset(head,-1,sizeof(head));
53 read(N);read(M);read(S);
54 for(int i=1;i<=N;i++) dis[i]=2147483647; dis[S]=0;
55 for(int i=1;i<=M;i++)
56 {
57 int x,y,z;read(x);read(y);read(z);
58 add_edge(x,y,z);
59 }
60 SPFA();
61 for(int i=1;i<=N;i++) printf("%d ",dis[i]);
62 return 0;
63 }Floyd
1 #include<cstdio>
2 #include<queue>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=2501;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12 long long int map[MAXN][MAXN];
13 int main()/*S到T的最短路*/
14 {
15 int N,M,S,T;
16 read(N);read(M);read(S);read(T);
17 for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) map[i][j]=0x7fffff;
18 for(int i=1;i<=M;i++)
19 {
20 int x,y,z;read(x);read(y);read(z);
21 map[x][y]=z;map[y][x]=z;
22 }
23 for(int k=1;k<=N;k++)
24 for(int i=1;i<=N;i++)
25 for(int j=1;j<=N;j++)
26 map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
27 printf("%lld ",map[S][T]);
28 return 0;
29 } 1 #include<cstdio>
2 #include<queue>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=2501;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12 long long int map[MAXN][MAXN];
13 int main()/*S到T的最短路*/
14 {
15 int N,M,S,T;
16 read(N);read(M);read(S);read(T);
17 for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) map[i][j]=0x7fffff;
18 for(int i=1;i<=M;i++)
19 {
20 int x,y,z;read(x);read(y);read(z);
21 map[x][y]=z;map[y][x]=z;
22 }
23 for(int k=1;k<=N;k++)
24 for(int i=1;i<=N;i++)
25 for(int j=1;j<=i;j++)
26 map[j][i]=map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
27 printf("%lld ",map[S][T]);
28 return 0;
29 }堆优化dijkstra
1 #include<cstdio>
2 #include<queue>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=5000001;
6 inline void read(int &n)
7 {
8 char c=getchar();bool flag=0;n=0;
9 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
10 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
11 }
12 struct node
13 {
14 int u,v,w,nxt;
15 }edge[MAXN];
16 int head[MAXN];
17 int num=1;
18 inline void add_edge(int x,int y,int z)
19 {
20 edge[num].u=x; edge[num].v=y;
21 edge[num].w=z; edge[num].nxt=head[x];
22 head[x]=num++;
23 }
24 int N,M,S=1;;
25 int dis[MAXN],vis[MAXN];
26 struct pr
27 {
28 int p,v;
29 pr() {p=v=0;} pr(int a,int b) {p=a;v=b;}
30 bool operator<(const pr&a)const {return v>a.v;}
31 }inc;
32 inline void Dijkstra()
33 {
34 priority_queue<pr>q;
35 dis[S]=0; q.push(pr(S,0));
36 for(register int k=1;k<=N;k++)
37 {
38 while(vis[q.top().p]&&q.size()>=0) q.pop();
39 int pos=q.top().p;
40 vis[pos]=1;
41 for(register int i=head[pos];i!=-1;i=edge[i].nxt)
42 if(vis[edge[i].v]==0&&dis[edge[i].v]>dis[edge[i].u]+edge[i].w)
43 dis[edge[i].v]=dis[edge[i].u]+edge[i].w, q.push(pr(edge[i].v,dis[edge[i].v])) ;
44 }
45 }
46 int main()/*S到其他节点的最短路*/
47 {
48 memset(head,-1,sizeof(head));
49 read(N);read(M);read(S);
50 for(register int i=1;i<=N;i++) dis[i]=2147483647; dis[S]=0;
51 for(register int i=1;i<=M;i++)
52 {
53 int x,y,z;read(x);read(y);read(z);
54 add_edge(x,y,z);
55 }
56 Dijkstra();
57 for(register int i=1;i<=N;i++) printf("%d ",dis[i]);
58 return 0;
59 }最小生成树
Kruskal
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 using namespace std;
7 const int MAXN=400002;
8 inline void read(int &n)
9 {
10 char c=getchar();bool flag=0;n=0;
11 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
12 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 struct node
15 {
16 int u,v,w;
17 }edge[MAXN];
18 int num=1;
19 inline void add_edge(int x,int y,int z)
20 {
21 edge[num].u=x;
22 edge[num].v=y;
23 edge[num].w=z;
24 num++;
25 }
26 int comp(const node &a,const node &b)
27 {
28 return a.w<b.w;
29 }
30 int fa[MAXN];
31 int n,m;
32 int find(int x)
33 {
34 if(fa[x]==x) return fa[x];
35 else return fa[x]=find(fa[x]);
36 }
37 int unionn(int x,int y)
38 {
39 fa[find(x)]=find(y);
40 }
41 inline void Kruskal()
42 {
43 int ans=0,tot=0;
44 sort(edge+1,edge+num,comp);
45 for(int i=1;i<=num-1;i++)
46 {
47 if(find(edge[i].u)!=find(edge[i].v))
48 {
49 unionn(edge[i].u,edge[i].v);
50 tot++;
51 ans+=edge[i].w;
52 if(tot==n-1)
53 {
54 printf("%d",ans);
55 exit(0);
56 }
57 }
58 }
59 printf("orz");
60 }
61 int main()
62 {
63 read(n);read(m);
64 for(int i=1;i<=n;i++) fa[i]=i;
65 for(int i=1;i<=m;i++)
66 {
67 int x,y,z;
68 read(x);read(y);read(z);
69 add_edge(x,y,z);
70 }
71 Kruskal();
72 return 0;
73 }tarjan
void tarjan(int now)
{
dfn[now]=low[now]=++tot;
s.push(now);
vis[now]=1;
for(int i=headE[now];i!=-1;i=E[i].nxt)
{
if(!dfn[E[i].v])
tarjan(E[i].v),low[now]=min(low[now],low[E[i].v]);
else if(vis[E[i].v])
low[now]=min(low[now],dfn[E[i].v]);
}
if(low[now]==dfn[now])
{
int h;
colornum++;
do
{
h=s.top();
color[h]=colornum;
sum[colornum]+=money[h];
vis[h]=0;
s.pop();
}while(h!=now);
}
}void tarjan(int now,int fa)
{
dfn[now]=low[now]=++tot;
s.push(now);
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(!dfn[edge[i].v]&&edge[i].v!=fa)
{
tarjan(edge[i].v,now);
low[now]=min(low[now],low[edge[i].v]);
if(low[edge[i].v]>=dfn[now])
{
memset(in,0,sizeof(in));//哪些在双联通分量里
memset(color,0,sizeof(color));
int h=0,cnt=0;
do
{
h=s.top();s.pop();
in[h]=1;
point[++cnt]=h;
}while(h!=edge[i].v);//warning
if(cnt<=1) continue;//必须构成环
in[now]=1;point[++cnt]=now;
if(MakeColor(now,1)==0)
for(int j=1;j<=cnt;j++)
ans[point[j]]=1;
}
}
if(edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
}
}void tarjan(int now,int fa)
{
dfn[now]=low[now]=++tot;
s.push(now);
vis[now]=1;
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(!dfn[edge[i].v]&&edge[i].v!=fa)
tarjan(edge[i].v,now),low[now]=min(low[now],low[edge[i].v]);
if(vis[edge[i].v]&&edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
}
if(dfn[now]==low[now])
{
int h=0;
colornum++;
do
{
h=s.top();
color[h]=colornum;
s.pop();
}while(h!=now);
}
}int tarjan(int now,int fa)
{
int ch=0;
dfn[now]=low[now]=++tot;
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(!dfn[edge[i].v])
{
tarjan(edge[i].v,fa);
low[now]=min(low[now],low[edge[i].v]);
if(low[edge[i].v]>=dfn[now]&&now!=fa) cut[now]=1;
if(now==fa) ch++;
}
low[now]=min(low[now],dfn[edge[i].v]);
}
if(now==fa&&ch>=2) cut[now]=1;
}void tarjan(int now,int fa)
{
dfn[now]=low[now]=++tot;
for(int i=head[now];i!=-1;i=edge[i].nxt)
{
if(!dfn[edge[i].v])
{
deep[edge[i].v]=deep[now]+1;
f[edge[i].v]=now;
tarjan(edge[i].v,now);
low[now]=min(low[now],low[edge[i].v]);
if(low[edge[i].v]>dfn[now])
{
bridge[edge[i].v]=1;
ans++;
}
}
else if(edge[i].v!=fa) low[now]=min(low[now],dfn[edge[i].v]);
}
}数论
扩展欧几里得
https://www.luogu.org/problem/show?pid=1082
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 using namespace std;
8 const int MAXN=100001;
9 inline void read(int &n)
10 {
11 char c=getchar();bool flag=0;n=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 int a[6],b[6];
16 int exgcd(int a,int b,int &x,int &y)
17 {
18 if(b==0)
19 { x=1,y=0;return a; }
20 int r=exgcd(b,a%b,x,y);
21 int tmp=x;x=y;y=tmp-(a/b)*y;
22 return r;
23 }
24 int x,y;
25 int main()
26 {
27 int a,b;
28 read(a);read(b);
29 int r=exgcd(a,b,x,y);
30 while(x<0) x+=b;
31 printf("%d",x);
32 return 0;
33 }CRT
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 #define LL long long
8 using namespace std;
9 const LL MAXN=100001;
10 const LL n=4;
11 inline void read(LL &n)
12 {
13 char c=getchar();bool flag=0;n=0;
14 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
15 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
16 }
17 LL a[MAXN],b[MAXN];
18 LL exgcd(LL a,LL b,LL &x,LL &y)
19 {
20 if(b==0)
21 { x=1,y=0;return a; }
22 LL r=exgcd(b,a%b,x,y);
23 LL tmp=x;x=y;y=tmp-(a/b)*y;
24 return r;
25 }
26 LL x,y;
27 LL gcd(LL a,LL b)
28 {
29 return b==0?a:gcd(b,a%b);
30 }
31 LL CRT()
32 {
33 LL M=1,ans=0;
34 for(LL i=1;i<=n;i++) M*=a[i];
35 for(LL i=1;i<=n;i++)
36 {
37 LL r=exgcd(M/a[i],a[i],x,y);
38 ans=( ans+b[i]*(M/a[i])*x )%M;
39 }
40 while(ans<0) ans+=M;
41 return ans;
42 }
43 int main()
44 {
45
46 for(LL i=1;i<=n;i++)
47 read(a[i]),read(b[i]);
48 printf("%lld",CRT());
49 return 0;
50 }扩展CRT
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<queue>
7 using namespace std;
8 const int MAXN=100001;
9 const int n=4;
10 inline void read(int &n)
11 {
12 char c=getchar();bool flag=0;n=0;
13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 int a[MAXN],b[MAXN];
17 int exgcd(int a,int b,int &x,int &y)
18 {
19 if(b==0)
20 { x=1,y=0;return a; }
21 int r=exgcd(b,a%b,x,y);
22 int tmp=x;x=y;y=tmp-(a/b)*y;
23 return r;
24 }
25 int x,y;
26 int gcd(int a,int b)
27 {
28 return b==0?a:gcd(b,a%b);
29 }
30 inline int EX_CRT()
31 {
32 /*
33 x+a1*y1=b1 1
34 x+a2*y2=b2 2
35 x+a3*y3=b3 3
36 求这个方程的解x
37 */
38 int M=a[1],R=b[1],x,y;
39 // M=LCM(a1,a2)
40 // R=bi-b1
41 for(int i=2;i<=n;i++)
42 {
43
44 /*
45 a1*y1-a2*y2=b2-b1
46 a*x +b*y =gcd(a,b)
47 这样求出y1之后
48 带回得到对于1,2两个方程的解x0=b1-y1*a1
49 */
50 int r=exgcd(M,a[i],x,y);
51 if( (R-b[i])%r!=0) return -1;
52 /* R-b[i]相当于b2-b1
53 方程有解的条件(b2-b1)%gcd(a,b) ==0 */
54
55 x=(R-b[i])/r*x%a[i];//****
56
57
58 R=R-x*M;//x0=b1-y1*a1
59 M=M/r*a[i];// 新的模数
60 R=R%M;//R=X mod M
61 }
62 return (R%M+M)%M;
63 }
64 int main()
65 {
66
67 for(int i=1;i<=n;i++)
68 read(a[i]),read(b[i]);
69 printf("%d",EX_CRT());
70 return 0;
71 }快速幂
1 #include<cstdio>
2 #include<deque>
3 #include<cstring>
4 #define LL long long
5 using namespace std;
6 const LL MAXN=1000001;
7 inline void read(LL &n)
8 {
9 char c=getchar();bool flag=0;n=0;
10 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
11 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 LL a,p,mod,base;
14 LL fastpow(LL a,LL p)
15 {
16 for(base=1;p;p>>=1) p&1?base=(base*a)%mod,a=(a*a)%mod:a=(a*a)%mod;
17 return base;
18 }
19 int main()
20 {
21
22 read(a);read(p);read(mod);
23 printf("%lld^%lld mod %lld=%lld",a,p,mod,fastpow(a,p));
24 return 0;
25 }卡特兰数
https://www.luogu.org/problem/show?pid=1976
1 #include<cstdio>
2 const int MAXN=100001;
3 inline int read()
4 {
5 char c=getchar();int x=0,flag=1;
6 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
7 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
8 }
9 int n;
10 long long dp[MAXN];
11 int main()
12 {
13 n=read();
14 dp[0]=1;
15 int ans=0;
16 for(int i=1;i<=n;i++)
17 for(int j=0;j<i;j++)
18 dp[i]=(dp[i]+(dp[j]*dp[i-j-1])%100000007)%100000007;
19 printf("%lld",dp[n]%100000007);
20 return 0;
21 }字符串
KMP
1 #include<cstdio>
2 #include<deque>
3 #include<cstring>
4 using namespace std;
5 const int MAXN=1000001;
6 const int mod=1e7+7;
7 inline void read(int &n)
8 {
9 char c=getchar();bool flag=0;n=0;
10 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
11 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13
14
15 char a[MAXN];
16 char b[MAXN];
17 int nxt[MAXN];
18 int la,lb;
19 int MakeP()
20 {
21 int j=0;
22 for(int i=1;i<lb;i++)
23 {
24 while(b[i]!=b[j]&&j>0) j=nxt[j-1];
25 if(b[i]==b[j]) j++;
26 nxt[i]=j;
27 }
28 }
29 int KMP()
30 {
31 int j=0;
32 for(int i=0;i<la;i++)
33 {
34 while(a[i]!=b[j]&&j>0) j=nxt[j-1];
35 if(a[i]==b[j]) j++;
36 if(j==lb) printf("%d\n", i+1-lb+1);
37 }
38 }
39 int main()
40 {
41 scanf("%s%s",a,b);
42 la=strlen(a);lb=strlen(b);
43 MakeP();
44 KMP();
45 for(int i=0;i<lb;i++) printf("%d ",nxt[i]);
46 return 0;
47 }后缀数组
http://www.cnblogs.com/zwfymqz/p/8430014.html
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int MAXN=2*1e6+10;
int sa[MAXN],rak[MAXN],tp[MAXN],tax[MAXN],a[MAXN],N,M,height[MAXN];
char s[MAXN];
void Qsort()
{
for(int i=1;i<=M;i++) tax[i]=0;
for(int i=1;i<=N;i++) tax[rak[i]]++;
for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ] = tp[i];
}
void Ssort()
{
M=127;
for(int i=1;i<=N;i++) rak[i]=a[i],tp[i]=i;Qsort();
for(int w=1,p=1; p<N ; w<<=1,M=p)
{
p=0;
for(int i=N-w+1;i<=N;i++) tp[++p]=i;
for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
Qsort();
swap(tp,rak);
rak[sa[1]]=1;p=1;
for(int i=2;i<=N;i++) rak[sa[i]] = (tp[sa[i]]==tp[sa[i-1]]&&tp[sa[i]+w]==tp[sa[i-1]+w])?p:++p;
}
int j,k=0;
for(int i=1;i<=N;height[rak[i++]]=k)
for(k=k?k-1:k,j=sa[rak[i]-1];a[i+k]==a[j+k];++k );
for(int i=0;i<=N;i++)
{
for(int j=height[i]+1;;j++)
{
int tot=1;
for(int k=i+1;height[k]>=j;++k,++tot);
if(tot>1) printf("%d\n",tot);
else break;
}
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int Meiyong;
cin>>Meiyong;
scanf("%s",s);
N=strlen(s);
for(int i=1;i<=N;i++) a[i]=s[i-1];
Ssort();
return 0;
}数据结构
堆
1 struct S
2 {
3 int pos,val;
4 S(){ pos=0;val=0; }
5 S(int a,int b){ pos=a,val=b; }
6
7 };
8 bool operator <(const S &a,const S &b)
9 {
10 return a.pos>b.pos;
11 }//按照位置从小到大排序
12 priority_queue<S>q;单调队列
https://www.luogu.org/problem/show?pid=1886
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<deque>
6 using namespace std;
7 const int MAXN=1000010;
8 inline void read(int &n)
9 {
10 char c=getchar();n=0;bool flag=0;
11 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
12 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
13 }
14 struct node
15 {
16 int pos,val;
17 node(){pos=val=0;}
18 node(int a,int b) { pos=a;val=b; }
19 };
20 deque<node>q;
21 int a[MAXN];
22 int main()
23 {
24 int n,k;
25 read(n);read(k);
26 for(int i=1;i<=n;i++) read(a[i]);
27 for(int i=1;i<=n;i++)
28 {
29 while(q.size()>0&&q.front().pos<=(i-k)) q.pop_front();
30 while(q.size()>0&&a[i]<q.back().val) q.pop_back();
31 q.push_back(node(i,a[i]));
32 if(i>=k) printf("%d ",q.front().val);
33 }
34 printf("\n");
35 while(q.size()!=0) q.pop_front();
36 for(int i=1;i<=n;i++)
37 {
38 while(q.size()>0&&q.front().pos<=(i-k)) q.pop_front();
39 while(q.size()>0&&a[i]>q.back().val) q.pop_back();
40 q.push_back(node(i,a[i]));
41 if(i>=k) printf("%d ",q.front().val);
42 }
43 return 0;
44 }线段树
单点修改&&区间求和http://codevs.cn/problem/1080/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define ls k<<1
6 #define rs k<<1|1
7 using namespace std;
8 const int MAXN=400400;
9 inline void read(int &n)
10 {
11 char c=getchar();n=0;bool flag=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 struct node
16 {
17 int l,r,w,f;
18 }tree[MAXN];
19 int ans=0;
20 inline void update(int k)
21 { tree[k].w=tree[ls].w+tree[rs].w; }
22 inline void Build_Tree(int ll,int rr,int k)
23 {
24 tree[k].l=ll;tree[k].r=rr;
25 if(ll==rr)
26 { read(tree[k].w); return ; }
27 int mid=tree[k].l+tree[k].r>>1;
28 Build_Tree(ll,mid,ls); Build_Tree(mid+1,rr,rs);
29 update(k);
30 }
31 void Point_Add(int k,int pos,int val)
32 {
33 if(tree[k].l==tree[k].r)
34 { tree[k].w+=val; return ; }
35 int mid= tree[k].l+tree[k].r>>1;
36 if(pos<=mid) Point_Add(ls,pos,val);
37 else Point_Add(rs,pos,val);
38 update(k);
39 }
40 void Interval_Sum(int k,int ll,int rr)
41 {
42 if(ll<=tree[k].l&&tree[k].r<=rr)
43 { ans+=tree[k].w; return ; }
44 int mid=tree[k].l+tree[k].r>>1;
45 if(ll<=mid) Interval_Sum(ls,ll,rr);
46 if(rr>mid) Interval_Sum(rs,ll,rr);
47 }
48 int main()
49 {
50 int n,m;
51 read(n);
52 Build_Tree(1,n,1);
53 read(m);
54 for(int i=1;i<=m;i++)
55 {
56 int how;read(how);
57 if(how==1)
58 {
59 int pos,val; read(pos);read(val);
60 Point_Add(1,pos,val);
61 }
62 else
63 {
64 int a,b;read(a);read(b); ans=0;
65 Interval_Sum(1,a,b);
66 printf("%d\n",ans);
67 }
68 }
69 return 0;
70 }区间修改&&区间求和http://codevs.cn/problem/1082/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define ls k<<1
6 #define rs k<<1|1
7 #define LL long long
8 using namespace std;
9 const LL MAXN=800400;
10 inline void read(LL &n)
11 {
12 char c=getchar();n=0;bool flag=0;
13 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
14 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
15 }
16 struct node
17 {
18 LL l,r,w,f;
19 }tree[MAXN];
20 LL ans=0;
21 inline void update(LL k)
22 { tree[k].w=tree[ls].w+tree[rs].w; }
23 inline void Build_Tree(LL ll,LL rr,LL k)
24 {
25 tree[k].l=ll;tree[k].r=rr;
26 if(ll==rr)
27 { read(tree[k].w); return ; }
28 LL mid=tree[k].l+tree[k].r>>1;
29 Build_Tree(ll,mid,ls); Build_Tree(mid+1,rr,rs);
30 update(k);
31 }
32 inline void down(LL k)
33 {
34 tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].f;
35 tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].f;
36 tree[ls].f+=tree[k].f;
37 tree[rs].f+=tree[k].f;
38 tree[k].f=0;
39 }
40 inline void Interval_Add(LL k,LL ll,LL rr,LL val)
41 {
42 if(ll<=tree[k].l&&tree[k].r<=rr)
43 {
44 tree[k].w+=(tree[k].r-tree[k].l+1)*val;
45 tree[k].f+=val;
46 return ;
47 }
48 if(tree[k].f) down(k);
49 LL mid=tree[k].l+tree[k].r>>1;
50 if(ll<=mid) Interval_Add(ls,ll,rr,val);
51 if(rr>mid) Interval_Add(rs,ll,rr,val);
52 update(k);
53 }
54 inline void Interval_Sum(LL k,LL ll,LL rr)
55 {
56 if(ll<=tree[k].l&&tree[k].r<=rr)
57 {
58 ans+=tree[k].w;
59 return ;
60 }
61 if(tree[k].f) down(k);
62 LL mid=tree[k].l+tree[k].r>>1;
63 if(ll<=mid) Interval_Sum(ls,ll,rr);
64 if(rr>mid) Interval_Sum(rs,ll,rr);
65 }
66 int main()
67 {
68 LL n,m;
69 read(n);
70 Build_Tree(1,n,1);
71 read(m);
72 for(LL i=1;i<=m;i++)
73 {
74 LL how;read(how);
75 if(how==1)
76 {
77 LL x,y,val;read(x);read(y);read(val);
78 Interval_Add(1,x,y,val);
79 }
80 else
81 {
82 LL x,y;read(x);read(y);
83 ans=0;
84 Interval_Sum(1,x,y);
85 printf("%lld\n",ans);
86 }
87 }
88 return 0;
89 }区间修改&&单点修改http://codevs.cn/problem/1081/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define ls k<<1
6 #define rs k<<1|1
7 using namespace std;
8 const int MAXN=400400;
9 inline void read(int &n)
10 {
11 char c=getchar();n=0;bool flag=0;
12 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
13 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
14 }
15 struct node
16 {
17 int l,r,w,f;
18 }tree[MAXN];
19 int ans=0;
20 inline void update(int k)
21 { tree[k].w=tree[ls].w+tree[rs].w; }
22 inline void Build_Tree(int ll,int rr,int k)
23 {
24 tree[k].l=ll;tree[k].r=rr;
25 if(ll==rr)
26 { read(tree[k].w); return ; }
27 int mid=tree[k].l+tree[k].r>>1;
28 Build_Tree(ll,mid,ls); Build_Tree(mid+1,rr,rs);
29 update(k);
30 }
31 inline void down(int k)
32 {
33 tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].f;
34 tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].f;
35 tree[ls].f+=tree[k].f;
36 tree[rs].f+=tree[k].f;
37 tree[k].f=0;
38 update(k);
39 return ;
40 }
41 void Interval_Add(int k,int ll,int rr,int val)
42 {
43 if(ll<=tree[k].l&&tree[k].r<=rr)
44 {
45 tree[k].w=tree[k].w+(tree[k].r-tree[k].l+1)*val;
46 tree[k].f+=val;
47 return ;
48 }
49 if(tree[k].f) down(k);
50 int mid=tree[k].l+tree[k].r>>1;
51 if(ll<=mid) Interval_Add(ls,ll,rr,val);
52 if(rr>mid) Interval_Add(rs,ll,rr,val);
53 update(k);
54 }
55 void Point_Ask(int k,int pos)
56 {
57 if(tree[k].l==tree[k].r)
58 {
59 ans=tree[k].w;
60 return ;
61 }
62 if(tree[k].f) down(k);
63 int mid=tree[k].l+tree[k].r>>1;
64 if(pos<=mid) Point_Ask(ls,pos);
65 else Point_Ask(rs,pos);
66 }
67 int main()
68 {
69 int n,m;
70 read(n);
71 Build_Tree(1,n,1);
72 read(m);
73 for(int i=1;i<=m;i++)
74 {
75 int how;read(how);
76 if(how==1)
77 {
78 int x,y,val;read(x);read(y);read(val);
79 Interval_Add(1,x,y,val);
80 }
81 else
82 {
83 int pos;read(pos);
84 ans=0;
85 Point_Ask(1,pos);
86 printf("%d\n",ans);
87 }
88 }
89 return 0;
90 }区间修改&&区间覆盖&&区间求和&&最大值&&&最小值http://codevs.cn/problem/4927/
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define LL long long
6 #define ls k<<1
7 #define rs k<<1|1
8 using namespace std;
9 const LL MAXN=400400;
10 const LL INF =0x7fffff;
11 inline void read(LL &n)
12 {
13 char c=getchar();n=0;bool flag=0;
14 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
15 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
16 }
17 struct node
18 {
19 LL l,r,w,Max,Min,Set,Add;
20 bool V;
21 }tree[MAXN];
22 LL n,m;
23 LL ans=0;
24 inline void update(LL k)
25 {
26 tree[k].w=tree[ls].w+tree[rs].w;
27 tree[k].Max=max(tree[ls].Max,tree[rs].Max);
28 tree[k].Min=min(tree[ls].Min,tree[rs].Min);
29 }
30 void Build_Tree(LL ll,LL rr,LL k)
31 {
32 tree[k].l=ll;tree[k].r=rr;
33 if(tree[k].l==tree[k].r)
34 {
35 read(tree[k].w);
36 tree[k].Max=tree[k].w;
37 tree[k].Min=tree[k].w;
38 return ;
39 }
40 LL mid=tree[k].l+tree[k].r>>1;
41 Build_Tree(ll,mid,ls);
42 Build_Tree(mid+1,rr,rs);
43 update(k);
44 }
45 void down(LL k)
46 {
47 if(tree[k].V)
48 {
49 tree[ls].Add=0;
50 tree[ls].V=1;
51 tree[ls].w=(tree[ls].r-tree[ls].l+1)*tree[k].Set;
52 tree[ls].Max=tree[ls].Min=tree[ls].Set=tree[k].Set;
53
54 tree[rs].Add=0;
55 tree[rs].V=1;
56 tree[rs].w=(tree[rs].r-tree[rs].l+1)*tree[k].Set;
57 tree[rs].Max=tree[rs].Min=tree[rs].Set=tree[k].Set;
58
59 tree[k].Set=tree[k].V=0;
60 }
61 if(tree[k].Add)
62 {
63 tree[ls].w+=(tree[ls].r-tree[ls].l+1)*tree[k].Add;
64 tree[ls].Add+=tree[k].Add;
65 tree[ls].Max+=tree[k].Add;
66 tree[ls].Min+=tree[k].Add;
67
68 tree[rs].w+=(tree[rs].r-tree[rs].l+1)*tree[k].Add;
69 tree[rs].Add+=tree[k].Add;
70 tree[rs].Max+=tree[k].Add;
71 tree[rs].Min+=tree[k].Add;
72 tree[k].Add=0;
73 }
74
75 }
76 void Interval_Add(LL k,LL ll,LL rr,LL val)
77 {
78 if(ll<=tree[k].l&&tree[k].r<=rr)
79 {
80 tree[k].w+=(tree[k].r-tree[k].l+1)*val;
81 tree[k].Add+=val;
82 tree[k].Max+=val;
83 tree[k].Min+=val;
84 return ;
85 }
86 if(tree[k].Add||tree[k].V) down(k);
87 LL mid=tree[k].r+tree[k].l>>1;
88 if(ll<=mid) Interval_Add(ls,ll,rr,val);
89 if(rr>mid) Interval_Add(rs,ll,rr,val);
90 update(k);
91 }
92 void Interval_Change(LL k,LL ll,LL rr,LL val)
93 {
94 if(ll<=tree[k].l&&tree[k].r<=rr)
95 {
96 tree[k].Max=tree[k].Min=val;
97 tree[k].Set=val;tree[k].V=1;
98 tree[k].w=(tree[k].r-tree[k].l+1)*val;
99 tree[k].Add=0;
100 return ;
101 }
102 if(tree[k].Add||tree[k].V) down(k);
103 LL mid=tree[k].r+tree[k].l>>1;
104 if(ll<=mid) Interval_Change(ls,ll,rr,val);
105 if(rr>mid) Interval_Change(rs,ll,rr,val);
106 update(k);
107 }
108 void Interval_Sum(LL k,LL ll,LL rr)
109 {
110 if(ll<=tree[k].l&&tree[k].r<=rr)
111 {
112 ans+=tree[k].w;
113 return ;
114 }
115 if(tree[k].Add||tree[k].V) down(k);
116 LL mid=tree[k].r+tree[k].l>>1;
117 if(ll<=mid) Interval_Sum(ls,ll,rr);
118 if(rr>mid) Interval_Sum(rs,ll,rr);
119 }
120 void Interval_Max(LL k,LL ll,LL rr)
121 {
122 if(ll<=tree[k].l&&tree[k].r<=rr)
123 {
124 ans=max(ans,tree[k].Max);
125 return ;
126 }
127 if(tree[k].Add||tree[k].V) down(k);
128 LL mid=tree[k].r+tree[k].l>>1;
129 if(ll<=mid) Interval_Max(ls,ll,rr);
130 if(rr>mid) Interval_Max(rs,ll,rr);
131 }
132 void Interval_Min(LL k,LL ll,LL rr)
133 {
134 if(ll<=tree[k].l&&tree[k].r<=rr)
135 {
136 ans=min(ans,tree[k].Min);
137 return ;
138 }
139 if(tree[k].Add||tree[k].V) down(k);
140 LL mid=tree[k].r+tree[k].l>>1;
141 if(ll<=mid) Interval_Min(ls,ll,rr);
142 if(rr>mid) Interval_Min(rs,ll,rr);
143 }
144 int main()
145 {
146 read(n);read(m);
147 Build_Tree(1,n,1);
148 for(LL i=1;i<=m;i++)
149 {
150 char how[5];
151 scanf("%s",how);
152 if(how[0]=='a')//区间加
153 {
154 LL x,y,val;read(x);read(y);read(val);
155 Interval_Add(1,x,y,val);
156 }
157 else if(how[0]=='s'&&how[1]=='e')//区间赋值
158 {
159 LL x,y,val;read(x);read(y);read(val);
160 Interval_Change(1,x,y,val);
161 }
162 else if(how[0]=='s'&&how[1]=='u')//区间求和
163 {
164 LL x,y;read(x);read(y);ans=0;
165 Interval_Sum(1,x,y);
166 printf("%lld\n",ans);
167 }
168 else if(how[0]=='m'&&how[1]=='a')//区间最大值
169 {
170 LL x,y;read(x);read(y);ans=0;
171 Interval_Max(1,x,y);
172 printf("%lld\n",ans);
173 }
174 else if(how[0]=='m'&&how[1]=='i')// 区间最小值
175 {
176 LL x,y;read(x);read(y);ans=INF;
177 Interval_Min(1,x,y);
178 printf("%lld\n",ans);
179 }
180 }
181 return 0;
182 }树状数组
单点修改&&区间查询https://www.luogu.org/problem/show?pid=3374
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define lb(x) (x&(-x))
6 using namespace std;
7 const int MAXN=500001;
8 inline int read()
9 {
10 char c=getchar();int x=0;int f=1;
11 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
12 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
13 }
14 int tree[MAXN];
15 int n=read(),m=read();
16 inline void Point_Add(int pos,int val)
17 {
18 while(pos<=n) tree[pos]+=val,pos+=lb(pos);
19 }
20 inline int Interval_Sum(int pos)
21 {
22 int ans=0;
23 while(pos) ans+=tree[pos], pos-=lb(pos);
24 return ans;
25 }
26 int main()
27 {
28
29 for(int i=1;i<=n;i++)
30 {
31 int p=read();Point_Add(i,p);
32 }
33 for(int i=1;i<=m;i++)
34 {
35 int how=read(),x=read(),y=read();
36 if(how==1) Point_Add(x,y);
37 else printf("%d\n",Interval_Sum(y)-Interval_Sum(x-1));
38 }
39 return 0;
40 }区间修改&&单点查询https://www.luogu.org/problem/show?pid=3368
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #define lb(x) (x&(-x))
6 using namespace std;
7 const int MAXN=500001;
8 inline int read()
9 {
10 char c=getchar();int x=0;int f=1;
11 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
12 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
13 }
14 int tree[MAXN];
15 int n=read(),m=read();
16 inline void Point_Add(int pos,int val)
17 {
18 while(pos<=n) tree[pos]+=val,pos+=lb(pos);
19 }
20 inline int Interval_Sum(int pos)
21 {
22 int ans=0;
23 while(pos) ans+=tree[pos], pos-=lb(pos);
24 return ans;
25 }
26 int main()
27 {
28 int pre=0;
29 for(int i=1;i<=n;i++)
30 {
31 int p=read();Point_Add(i,p-pre);
32 pre=p;
33 }
34 for(int i=1;i<=m;i++)
35 {
36 int how=read(),x=read(),y,val;
37 if(how==1) y=read(),val=read(),Point_Add(x,val),Point_Add(y+1,-val);
38 else printf("%d\n",Interval_Sum(x));
39 }
40 return 0;
41 }平衡树
splay
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#define fa(x) T[x].fa
#define ls(x) T[x].ch[0]
#define rs(x) T[x].ch[1]
#define root T[0].ch[1]
using namespace std;
const int MAXN=1e6+10,INF=1e9+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
return x*f;
}
struct node
{
int fa,ch[2],val,rev,sum;
}T[MAXN];
int tot=0;
int ident(int x){return T[fa(x)].ch[0]==x?0:1;}
int connect(int x,int f,int how){T[f].ch[how]=x;T[x].fa=f;}
int update(int x){T[x].sum=T[ls(x)].sum+T[rs(x)].sum+T[x].rev;}
void rotate(int x)
{
int Y=T[x].fa,R=T[Y].fa;
int Yson=ident(x),Rson=ident(Y);
int B=T[x].ch[Yson^1];
connect(B,Y,Yson);
connect(Y,x,Yson^1);
connect(x,R,Rson);
update(Y);update(x);
}
void splay(int x,int to)
{
to=T[to].fa;
while(T[x].fa!=to)
{
if(T[fa(x)].fa==to) rotate(x);
else if(ident(x)==ident(fa(x))) rotate(fa(x)),rotate(x);
else rotate(x),rotate(x);
}
}
int newnode(int val,int fa)
{
T[++tot].val=val;
T[tot].fa=fa;
T[tot].rev=T[tot].sum=1;
return tot;
}
void Insert(int v)
{
if(root==0) {root=newnode(v,0);return ;}
int now=root;
while(1)
{
T[now].sum++;
if(T[now].val==v) {T[now].rev++;splay(now,root);return ;}
int nxt=v<T[now].val?0:1;
if(!T[now].ch[nxt]){T[now].ch[nxt]=newnode(v,now);splay(now,root);return ;}
now=T[now].ch[nxt];
}
}
int find(int v)
{
int now=root;
while(1)
{
if(T[now].val==v){splay(now,root);return now;}
int nxt=v<T[now].val?0:1;
now=T[now].ch[nxt];
}
}
void Delet(int v)
{
int now=find(v);
if(T[now].rev>1){T[now].rev--;T[now].sum--;return ;}
else if(!ls(now)&&!rs(now)){root=0;return ;}
else if(!ls(now)){root=rs(now);T[rs(now)].fa=0;return ;}
int left=ls(now);
while(rs(left)) left=rs(left);
splay(left,ls(now));
connect(rs(now),left,1);
connect(left,0,1);
update(left);//
}
int rak(int v)
{
int ans=0,now=root;
while(1)
{
if(T[now].val==v){return ans+T[ls(now)].sum+1;}
int nxt=v<T[now].val?0:1;
if(nxt==1) ans+=T[ls(now)].sum+T[now].rev;
now=T[now].ch[nxt];
}
}
int kth(int v)
{
int now=root;
while(1)
{
int used=T[now].sum-T[rs(now)].sum;
if(v>T[ls(now)].sum&&v<=used){splay(now,root);return T[now].val;}
if(v>used) v-=used,now=rs(now);
else now=ls(now);
}
}
int lower(int v)
{
int now=root,ans=-INF;
while(now)
{
if(T[now].val<v) ans=max(ans,T[now].val);
int nxt=v<=T[now].val?0:1;
now=T[now].ch[nxt];
}
return ans;
}
int upper(int v)
{
int now=root,ans=INF;
while(now)
{
if(T[now].val>v) ans=min(ans,T[now].val);
int nxt=v<T[now].val?0:1;
now=T[now].ch[nxt];
}
return ans;
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int N=read();
while(N--)
{
int opt=read(),x=read();
if(opt==1) Insert(x);
else if(opt==2) Delet(x);
else if(opt==3) printf("%d\n",rak(x));
else if(opt==4) printf("%d\n",kth(x));
else if(opt==5) printf("%d\n",lower(x));
else if(opt==6) printf("%d\n",upper(x));
}
return 0;
}Treap
#include<iostream>
#include<cstdio>
#include<cstdlib>
#define ls tree[k].l
#define rs tree[k].r
using namespace std;
const int MAXN=1e6+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin))?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
return x*f;
}
struct node
{
int l,r,tot,recy,val,rd;
}tree[MAXN];
int size,root,ans=0;
inline void update(int k)
{
tree[k].tot=tree[ls].tot+tree[rs].tot+tree[k].recy;
}
inline void insert(int &k,int x)
{
if(k==0)
{
++size;k=size;
tree[size].recy=tree[size].tot=1;
tree[size].val=x;tree[size].rd=rand();return ;
}
tree[k].tot++;
if(tree[k].val==x) tree[k].recy++;
else if(x < tree[k].val) insert( ls, x);
else insert( rs , x );
}
inline void LeftRotate(int &k)
{
int R=tree[k].r;
tree[k].r=tree[R].l;
tree[R].l=k;
tree[R].tot=tree[k].tot;
update(k);k=R;
}
inline void RightRotate(int &k)
{
int R=tree[k].l;
tree[k].l=tree[R].r;
tree[R].r=k;
tree[R].tot=tree[k].tot;
update(k);k=R;
}
inline void del(int &k,int x)
{
if(!k) return ;
if(tree[k].val==x)
{
if(tree[k].recy>1) {tree[k].recy-=1,tree[k].tot-=1;return; }
if(tree[k].l*tree[k].r==0) k=tree[k].l+tree[k].r;
else if(tree[ls].rd<tree[rs].rd) RightRotate(k),del(k,x);
else LeftRotate(k),del(k,x);
}
else if(x>tree[k].val) tree[k].tot--,del(rs,x);
else tree[k].tot--,del(ls,x);
}
int atrank(int &k,int x)
{
if(k==0) return 0;
if(tree[k].val==x) return tree[ls].tot+1;
if(tree[k].val<x) return atrank(rs,x)+tree[ls].tot+tree[k].recy;
else return atrank(ls,x);
}
int rerand(int k,int x)
{
if(k==0) return 0;
if(x<=tree[ls].tot) return rerand(ls,x);
else if(x>tree[ls].tot+tree[k].recy) return rerand(rs,x-tree[ls].tot-tree[k].recy);
else return tree[k].val;
}
void pred(int k,int x)
{
if(k==0) return ;
if(tree[k].val<x) ans=k,pred(rs,x);
else pred(ls,x);
}
void succ(int &k,int x)
{
if(k==0) return ;
if(tree[k].val>x) ans=k,succ(ls,x);
else succ(rs,x);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
int n=read();
while(n--)
{
int opt=read(),x=read();ans=0;
if(opt==1) insert(root,x);
if(opt==2) del(root,x);
if(opt==3) printf("%d\n",atrank(root,x));
if(opt==4) printf("%d\n",rerand(root,x));
if(opt==5) {pred(root,x);printf("%d\n",tree[ans].val);}
if(opt==6) {succ(root,x);printf("%d\n",tree[ans].val);}
}
}FHQ Treap
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
#define ls T[now].ch[0]
#define rs T[now].ch[1]
const int MAXN=1e6+10;
inline char nc()
{
static char buf[MAXN],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char c=nc();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
while(c>='0'&&c<='9'){x=x*10+c-'0',c=nc();}
return x*f;
}
struct node
{
int ch[2],val,siz,pri;
}T[MAXN];
int tot=0;
int x,y,z,root=0;
int newnode(int v)
{
T[++tot].siz=1;
T[tot].val=v;
T[tot].pri=rand();
return tot;
}
void update(int now)
{
T[now].siz=T[ls].siz+T[rs].siz+1;
}
void split(int now,int k,int &x,int &y)
{
if(!now) {x=y=0;return ;}
if(T[now].val<=k) x=now,split(rs,k,rs,y);
else y=now,split(ls,k,x,ls);
update(now);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
if(T[x].pri<T[y].pri)
{
T[x].ch[1]=merge(T[x].ch[1],y);
update(x);
return x;
}
else
{
T[y].ch[0]=merge(x,T[y].ch[0]);
update(y);
return y;
}
}
int kth(int now,int x)
{
while(1)
{
if(T[ls].siz>=x) now=ls;
else
if(T[ls].siz+1==x) return now;
else x-=T[ls].siz+1,now=rs;
}
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
srand((unsigned)time(NULL));
int n=read();
while(n--)
{
int opt=read(),val=read();
if(opt==1)
{
split(root,val,x,y);
root=merge( merge(x,newnode(val)),y );
}
else if(opt==2)
{
split(root,val,x,z);
split(x,val-1,x,y);
y=merge(T[y].ch[0],T[y].ch[1]);
root=merge( merge(x,y) ,z);
}
else if(opt==3)
{
split(root,val-1,x,y);
printf("%d\n",T[x].siz+1);
root=merge(x,y);
}
else if(opt==4)
{
printf("%d\n",T[kth(root,val)].val);
}
else if(opt==5)
{
split(root,val-1,x,y);
printf("%d\n",T[kth(x,T[x].siz)].val);
root=merge(x,y);
}
else if(opt==6)
{
split(root,val,x,y);
printf("%d\n",T[kth(y,1)].val);
root=merge(x,y);
}
}
return 0;
}
FHQ TreapTrie树
01 Trie
http://www.cnblogs.com/zwfymqz/p/8440398.html
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
#define debug(x) printf("%d",x);
struct node
{
int val,ch[2];
node(){val=ch[0]=ch[1]=0;}
void clear(){val=ch[0]=ch[1]=0;}
}T[MAXN];
int a[MAXN],root=0,tot=0;
void Insert(int v)
{
int now=root;
for(int i=31;i>=0;i--)
{
int opt=(v&(1<<i))?1:0;
if(!T[now].ch[opt])
T[now].ch[opt]=++tot;
now=T[now].ch[opt];
T[now].val++;
}
}
void Delet(int v)
{
int now=root;
for(int i=31;i>=0;i--)
{
int opt=(v&(1<<i))?1:0;
now=T[now].ch[opt];
T[now].val--;
}
}
int Query(int v)
{
int ans=0,now=root;
for(int i=31;i>=0;i--)
{
int opt=(v&(1<<i))?1:0;
if(T[T[now].ch[opt^1]].val)
ans+=1<<i,now=T[now].ch[opt^1];
else
now=T[now].ch[opt];
}
return ans;
}
int main()
{
freopen("a.in","r",stdin);
int Test=read();
while(Test--)
{
int N=read();
for(int i=1;i<=N;i++) a[i]=read();
for(int i=1;i<=4*N;i++)
T[i].clear();
for(int i=1;i<=N;i++)
Insert(a[i]);
int ans=0;
for(int i=1;i<=N;i++)
{
for(int j=1;j<i;j++)
{
Delet(a[i]);Delet(a[j]);
ans=max(ans,Query(a[i]+a[j]));
Insert(a[i]);Insert(a[j]);
}
}
printf("%d\n",ans);
}
return 0;
}杂类算法
树上倍增
https://www.luogu.org/problem/show?pid=3379
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=1000001;
7 inline void read(int &n)
8 {
9 char c=getchar();bool flag=0;n=0;
10 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
11 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 struct node
14 {
15 int u,v,nxt;
16 }edge[MAXN];
17 int head[MAXN];
18 int num=1;
19 inline void add_edge(int x,int y)
20 {
21 edge[num].u=x;
22 edge[num].v=y;
23 edge[num].nxt=head[x];
24 head[x]=num++;
25 }
26 int deep[MAXN];
27 int f[MAXN][21];
28 int n,m,root;
29 int dfs(int now)
30 {
31 for(int i=head[now];i!=-1;i=edge[i].nxt)
32 if(deep[edge[i].v]==0)
33 deep[edge[i].v]=deep[now]+1,f[edge[i].v][0]=now,dfs(edge[i].v);
34 }
35 int pre()
36 {
37 for(int i=1;i<=19;i++)
38 for(int j=1;j<=n;j++)
39 f[j][i]=f[f[j][i-1]][i-1];
40 }
41 int LCA(int x,int y)
42 {
43 if(deep[x]<deep[y]) swap(x,y);
44 for(int i=19;i>=0;i--)
45 if(deep[f[x][i]]>=deep[y])
46 x=f[x][i];
47 if(x==y) return x;
48 for(int i=19;i>=0;i--)
49 if(f[x][i]!=f[y][i])
50 x=f[x][i],y=f[y][i];
51 return f[x][0];
52 }
53 int main()
54 {
55 memset(head,-1,sizeof(head));
56 read(n);read(m);read(root);
57 for(int i=1;i<=n-1;i++)
58 {
59 int x,y;
60 read(x);read(y);add_edge(x,y);add_edge(y,x);
61 }
62 deep[root]=1;
63 dfs(root);
64 pre();
65 for(int i=1;i<=m;i++)
66 {
67 int x,y;
68 read(x);read(y);
69 printf("%d\n",LCA(x,y));
70 }
71 return 0;
72 }ST表
https://www.luogu.org/problem/show?pid=3865
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=100010;
7 inline void read(int &n)
8 {
9 char c=getchar();n=0;bool flag=0;
10 while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
11 while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 int f[MAXN][21];
14 int d[MAXN][21];
15
16 int a[MAXN];
17 int main()
18 {
19 int n,m;
20 read(n);read(m);
21 for(int i=1;i<=n;i++)
22 read(a[i]);
23 for(int i=1;i<=n;i++) f[i][0]=a[i];
24 for(int i=1;i<=19;i++)
25 for(int j=1;j+(1<<i)-1<=n;j++)
26 f[j][i]=max(f[j+( 1<<(i-1) )][i-1],f[j][i-1]);
27 for(int i=1;i<=m;i++)
28 {
29 int x,y;
30 read(x);read(y);if(x>y) swap(x,y);
31 int k=log2(y-x+1);
32 printf("%d\n",max(f[x][k],f[y-(1<<k)+1][k]));
33 }
34 return 0;
35 }排序
归并排序
1 #include<cstdio>
2 #include<iostream>
3 #include<cmath>
4 using namespace std;
5 const int MAXN=100001;
6 inline int read()
7 {
8 char c=getchar();int x=0,flag=1;
9 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();}
10 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag;
11 }
12 int n;
13 int a[MAXN];
14 int tmp[MAXN];
15 void Sort(int l,int r)
16 {
17 if(l==r) return ;
18 int mid=l+r>>1;
19 Sort(l,mid);Sort(mid+1,r);
20 int nowl=l,nowr=mid+1,nowpos=l;
21 while(nowl<=mid&&nowr<=r)
22 {
23 if(a[nowl]<=a[nowr]) tmp[nowpos++]=a[nowl],nowl++;
24 else tmp[nowpos++]=a[nowr],nowr++;
25 }
26 while(nowl<=mid) tmp[nowpos++]=a[nowl],nowl++;
27 while(nowr<=r) tmp[nowpos++]=a[nowr],nowr++;
28 for(int i=l;i<=r;i++) a[i]=tmp[i];
29 }
30 int main()
31 {
32 n=read();
33 for(int i=1;i<=n;i++) a[i]=read();
34 Sort(1,n);
35 for(int i=1;i<=n;i++) printf("%d ",a[i]);
36 return 0;
37 }高精度
高精加
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<stdlib.h>
6 #include<ctime>
7 using namespace std;
8 const int MAXN=100001;
9 inline int read()
10 {
11 char c=getchar();int f=1,x=0;
12 while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
13 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;
14 }
15 char a[MAXN],b[MAXN],c[MAXN];
16 int la,lb,x=0;
17 int main()
18 {
19 scanf("%s%s",a+1,b+1);
20 la=strlen(a+1);lb=strlen(b+1);
21 for(int i=1;i<=max(la,lb);i++)
22 c[i]+=(a[i]+b[i]+x)%10,x=(a[i]+b[i]+x)/10;
23 c[max(la,lb)+1]=x;
24 bool flag=0;
25 for(int i=max(la,lb)+1;i>=1;i--)
26 if(c[i]!=0)
27 {
28 for(int j=i;j>=1;j--) printf("%d",c[j]);
29 return 0;
30 }
31 printf("0");
32 return 0;
33 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-10-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录