目录
------------------快速幂
------------------矩阵快速幂
------------------dijstrla算法
------------------spfa算法
------------------floyd算法
------------------tarjan算法
------------------拓扑排序
------------------树状数组
------------------线段树+离散化处理
------------------线段树+dfs序
------------------线段树+扫描线
------------------主席树
------------------树链剖分+线段树
------------------莫队+dfs序
------------------st表
------------------multiset的应用
------------------kmp算法
------------------字典树
------------------manacher算法
------------------并查集
------------------快速乘
------------------单调队列
------------------三分
快速幂
typedef long long ll;
ll mod;
ll qpow(ll a, ll n)//计算a^n % mod
{
ll re = 1;
while(n)
{
if(n & 1)//判断n的最后一位是否为1
re = (re * a) % mod;
n >>= 1;//舍去n的最后一位
a = (a * a) % mod;//将a平方
}
return re % mod;
}
矩阵快速幂（19年牛客多校第五场B）
十进制版本，二进制同理
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
char s[1000005];
ll mod;
struct Matrix
{
ll a[2][2];
Matrix(int x)
{
a[0][0]=a[1][1]=x;
a[1][0]=a[0][1]=0;
}
Matrix operator *(Matrix s)
{
Matrix ans(0);
for(ll k=0; k<2; k++)
{
for(ll i=0; i<2; i++)
{
ll sum=0;
for(ll j=0; j<2; j++)
sum=(sum+a[i][j]*s.a[j][k])%mod;
ans.a[i][k]=sum;
}
}
return ans;
}
};
Matrix ten(Matrix s)
{
Matrix ans(1);
for(ll i=0; i<10; i++)
ans=ans*s;
return ans;
}
Matrix quick(Matrix s,char a[],ll len)
{
Matrix base(1),ans(1);
Matrix k(1);
base=s;
for(ll i=len-1; i>=0; i--)
{
if(a[i]!='0')
{
for(ll j=1; j<=a[i]-'0'; j++)
ans=ans*base;
}
base=ten(base);
}
return ans;
}
int main()
{
ll x0,x1,a,b,i,j,len;
Matrix ss(0),ans(0);
while(scanf("%lld %lld %lld %lld",&x0,&x1,&a,&b)!=EOF)
{
scanf("%s",s);
scanf("%lld",&mod);
ss.a[0][1]=1;
ss.a[0][0]=0;
ss.a[1][0]=b;
ss.a[1][1]=a;
if(strcmp(s,"1")==0)
{
printf("%lld\n",x1);
}
else
{
char *p=s;
len=strlen(p);
if(p[len-1]!='0')
{
p[len-1]--;
}
else
{
p[len-1]='9';
i=len-2;
while(i>=0&&p[i]=='0')
p[i]='9',i--;
p[i]--;
}
if(p[0]=='0')
ans=quick(ss,p+1,len-1);
else
ans=quick(ss,p,len);
printf("%lld\n",(ans.a[1][0]*x0+ans.a[1][1]*x1)%mod);
}
}
return 0;
}
dijstrla算法（POJ2387）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int head[1005];
struct node
{
int k;
int step;
int next;
} a[4005];
int tol;
bool vis[1005];
inline void add(int x,int y,int z)
{
a[tol].next=head[x];
a[tol].k=y;
a[tol].step=z;
head[x]=tol++;
a[tol].next=head[y];
a[tol].k=x;
a[tol].step=z;
head[y]=tol++;
}
int n,t;
bool operator <(const node &x,const node &y)
{
return y.step<x.step;
}
int dij()
{
node r,p;
p.step=0;
p.k=1;
priority_queue<node>q;
q.push(p);
while(!q.empty())
{
p=q.top();
q.pop();
if(vis[p.k])
continue;
vis[p.k]=true;
if(p.k==t)
return p.step;
for(int i=head[p.k]; i!=-1; i=a[i].next)
{
if(!vis[a[i].k])
{
r.k=a[i].k;
r.step=p.step+a[i].step;
q.push(r);
}
}
}
return 0;
}
int main()
{
int x,y,z,i;
while(scanf("%d%d",&n,&t)!=EOF)
{
tol=0;
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
for(i=0; i<n; i++)
scanf("%d%d%d",&x,&y,&z),add(x,y,z);
printf("%d\n",dij());
}
return 0;
}
spfa算法
判负环（POJ1860）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
int head[105];
struct edge
{
double a,b;
int k;
int next;
} aa[305];
int tol;
inline void add(int x,int y,double s1,double s2)
{
aa[tol].next=head[x];
aa[tol].k=y;
aa[tol].a=s1;
aa[tol].b=s2;
head[x]=tol++;
}
double dist[105];
bool vis[105];
int num[105];
int n,m;
int spfa(int x)
{
int i;
queue<edge>q;
edge p;
p.k=x;
q.push(p);
while(!q.empty())
{
p=q.front();
q.pop();
vis[p.k]=false;
for(i=head[p.k]; i!=-1; i=aa[i].next)
{
if(dist[aa[i].k]<(dist[p.k]-aa[i].b)*aa[i].a)
{
dist[aa[i].k]=(dist[p.k]-aa[i].b)*aa[i].a;;
if(!vis[aa[i].k])
{
vis[aa[i].k]=true;
num[aa[i].k]++;
q.push(aa[i]);
if(num[aa[i].k]>=n)
return 1;
}
}
}
}
return 0;
}
int main()
{
int i,j,s,t;
int x,y;
double s1,s2,s3,s4,v;
while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF)
{
tol=0;
memset(vis,false,sizeof(vis));
memset(dist,0,sizeof(dist));
memset(head,-1,sizeof(head));
memset(num,0,sizeof(num));
for(i=0; i<m; i++)
{
scanf("%d%d%lf%lf%lf%lf",&x,&y,&s1,&s2,&s3,&s4);
add(x,y,s1,s2);
add(y,x,s3,s4);
}
dist[s]=v;
if(spfa(s))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
floyd算法
void floyd()
{
int i,j,k;
for(k=1;k<=N;k++)
for(i=1;i<=N;i++)
for(j=1;j<=N;j++)
if(map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
path[i][j]=path[i][k];
}
}
tarjan算法（19南昌邀请赛F）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100005];
int sum[50005][2],n;
inline int lowbit(int x)
{
return x&(-x);
}
void update(int x,int y,int w)
{
while(x<=n/2+1)
{
sum[x][y]^=w;
x+=lowbit(x);
}
}
int sum1(int x,int y)
{
int ans=0;
while(x>0)
{
ans^=sum[x][y];
x-=lowbit(x);
}
return ans;
}
int getsum(int l,int r,int y)
{
return sum1(l/2,y)^sum1(r/2+1,y);
}
int main()
{
int t,m,i,j,x,l,r;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
printf("Case #%d:\n",i);
scanf("%d%d",&n,&m);
memset(sum,0,sizeof(sum));
for(j=1;j<=n;j++)
scanf("%d",&a[j]),update(j/2+1,j%2,a[j]);
for(j=1;j<=m;j++)
{
scanf("%d %d %d",&x,&l,&r);
if(x==0)
{
update(l/2+1,(l)%2,r^a[l]);
a[l]=r;
continue;
}
if((r-l+1)%2==0)
printf("0\n");
else
{
printf("%d\n",getsum(l,r,(l)%2));
}
}
}
return 0;
}
拓扑排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
struct node
{
int k;
int next;
} a[205];
int head[105];
int tol;
inline void add(int x,int y)
{
a[tol].next=head[x];
a[tol].k=y;
head[x]=tol++;
}
int due[105];
bool vis[105];
int main()
{
int n,m,x,y,i,j,cnt,t;
bool flag;
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(due,0,sizeof(due));
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
tol=0;
for(i=0; i<m; i++)
scanf("%d%d",&x,&y),due[y]++,add(x,y);
flag=true;
t=n;
queue<int>q;
for(i=1;i<=n;i++)
{
if(due[i]==0)
{
node p;
q.push(i);
}
}
while(!q.empty())
{
int p=q.front();
q.pop();
if(vis[p])
continue;
vis[p]=true;
t--;
for(i=head[p];i!=-1;i=a[i].next)
{
if(!vis[a[i].k])
{
due[a[i].k]--;
if(!due[a[i].k])
q.push(a[i].k);
}
}
}
if(!t)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
树状数组
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;
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:\n",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\n",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 }
2.树状数组区间修改
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#define ll long long
using namespace std;
const int MAXN = 100100;
ll c1[MAXN],c2[MAXN],num[MAXN];
int n;
ll lowbit(ll x)
{
return x & -x;
}
ll sigma(ll *a,ll pos)
{
ll ans = 0;
while(pos)
{
ans += a[pos];
pos -= lowbit(pos);
}
return ans;
}
void add(ll a[],int pos, ll num)
{
while(pos < MAXN)
{
a[pos] += num;
pos += lowbit(pos);
}
return ;
}
int main()
{
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%I64d",num+i);
add(c1,i,num[i] - num[i-1]);
add(c2,i,(i-1)*(num[i]-num[i-1]));
}
//首先进行区间的更新操作
ll l,r,v;
scanf("%I64d%I64d%I64d",&l,&r,&v);
add(c1,l,v);
add(c1,r+1,-v);
add(c2,l,v*(l-1));
add(c2,r+1,-v*r);
//然后进行区间求和操作
scanf("%I64d%I64d",&l,&r);
ll sum1 = (l-1)*sigma(c1,l-1) - sigma(c2,l-1);
ll sum2 = r *sigma(c1,r) - sigma(c2,r);
printf("%I64d\n",sum2 - sum1);
}
线段树
1.线段树+离散化处理（POJ2528）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define il inline
#define ull unsigned long long
#define ll long long
#define ls (u<<1)
//等价于u*2
#define rs (u<<1|1)
//等价于u*2+1
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 200000+7;
int n,m;
int hash1[10000005];
int r[100005];
int l[100005];
int a[600005];
struct node
{
int l,r;
bool flag;
} tree[1600005];
void build(int u, int l, int r)
{
tree[u].l = l;
tree[u].r = r;
// printf("u=%lld l=%lld r=%lld\n")
tree[u].flag=false;
if(l==r)
{
//tree[u].flag=false;
return ;
}
ll mid = (l+r) >> 1;
build(ls,l,mid);
build(rs,mid+1,r);
// pushup(u);
}
inline void pushup(int u)
{
tree[u].flag=tree[ls].flag&&tree[rs].flag;
}
inline void pushdown(int u)
{
tree[ls].flag=tree[rs].flag;
}
void update(int u, int l, int r)
{
// printf("u=%lld l=%lld r=%lld\n",u,tree[u].l,tree[u].r);
ll mid=(tree[u].l+tree[u].r)>>1;
if(tree[u].flag)
return;
if(tree[u].l>=l&&tree[u].r<=r)
{
// printf("l=%lld r=%lld\n",tree[u].l,tree[u].r);
tree[u].flag=true;
// tree[u].
return ;
}
if(l<=mid)
update(ls,l,r);
if(r>mid)
update(rs,l,r);
pushup(u);
}
bool query(int u, int l, int r)
{
if(tree[u].flag)
return true;
if(l<=tree[u].l&&r>=tree[u].r)
{
return tree[u].flag;
}
// if(tree[u].lazy)
// pushdown(u);
ll mid=(tree[u].l+tree[u].r)>>1;
bool flag=true;
if(r>mid)
flag=flag&&query(rs,l,r);
if(l<=mid)
flag=flag&&query(ls,l,r);
return flag;
}
int main()
{
int i,t,k=0,cnt,s,ans;
scanf("%d",&t);
while(t--)
{
k=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&l[i],&r[i]);
a[k++]=l[i]-1;
a[k++]=l[i];
a[k++]=l[i]+1;
a[k++]=r[i]-1;
a[k++]=r[i];
a[k++]=r[i]+1;
}
ans=0;
sort(a,a+k);
k=unique(a,a+k)-a;
for(i=0;i<k;i++)
{
hash1[a[i]]=i;
//printf("hash=%lld i=%lld\n",a[i],i);
}
build(1,0,k-1);
for(i=n-1;i>=0;i--)
{
if(!query(1,hash1[l[i]],hash1[r[i]]))
update(1,hash1[l[i]],hash1[r[i]]),ans++;
// printf("ans=%lld\n",ans);
}
printf("%d\n",ans);
}
return 0;
}
2. 线段树+dfs序（HDU3974）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define ls (u<<1)
#define rs (u<<1|1)
#define INF 0x3f3f3f3f
using namespace std;
typedef int ll;
struct node
{
ll l,r;
ll lazy;
ll data;
} tree[400005];
struct edge
{
ll k;
ll next;
} a[50005];
inline void pushdown(ll u)
{
tree[ls].lazy=tree[rs].lazy=tree[u].lazy;
tree[ls].data=tree[rs].data=tree[u].lazy;
tree[u].lazy=0;
}
void build(ll u, ll l, ll r)
{
tree[u].l = l;
tree[u].r = r;
tree[u].lazy=0;
tree[u].data=-1;
if(l==r)
{
return ;
}
ll mid = (l+r) >> 1;
build(ls,l,mid);
build(rs,mid+1,r);
}
void update(ll u, ll l,ll r,ll c)
{
ll mid=(tree[u].l+tree[u].r)>>1;
if(tree[u].l>=l&&tree[u].r<=r)
{
tree[u].data=c;
tree[u].lazy=c;
return ;
}
if(tree[u].lazy)
pushdown(u);
if(l<=mid)
update(ls,l,r,c);
if(r>mid)
update(rs,l,r,c);
}
ll query(ll u, ll x)
{
if(tree[u].l==x&&tree[u].r==x)
{
return tree[u].data;
}
if(tree[u].lazy)
pushdown(u);
ll mid=(tree[u].l+tree[u].r)>>1;
if(x<=mid)
return query(ls,x);
if(x>mid)
return query(rs,x);
}
ll p,tol;
ll in[50005];
ll out[50005];
ll head[50005];
inline void add(ll x,ll y)
{
a[tol].next=head[x];
a[tol].k=y;
head[x]=tol++;
}
void dfs(ll u)
{
in[u]=++p;
for(ll i=head[u]; i!=-1; i=a[i].next)
dfs(a[i].k);
out[u]=p;
}
bool vis[50005];
int main()
{
ll t=1,w;
ll l,r,q,k,m,i;
ll n;
ll tol;
char c;
scanf("%d",&w);
while(w--)
{
tol=0;
scanf("%d",&n);
memset(head,-1,sizeof(head));
memset(vis,false,sizeof(vis));
for(i=0; i<n-1; i++)
{
scanf("%d%d",&l,&r);
add(r,l);
vis[l]=true;
}
p=0;
for(i=1; i<=n; i++)
if(!vis[i])
{
dfs(i);
break;
}
build(1,1,n);
printf("Case #%d:\n",t++);
scanf("%d",&m);
while(m--)
{
cin>>c;
scanf("%d",&k);
getchar();
if(c=='T')
{
scanf("%d",&q);
getchar();
update(1,in[k],out[k],q);
}
else
{
printf("%d\n",query(1,in[k]));
}
}
}
return 0;
}
3.线段树+扫描线（HDU1255）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#define ls (u<<1)
#define rs (u<<1|1)
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
int l,r;
int cover;
} tree[400005];
struct edge
{
double l,r;
double y;
int t;
} e[5005];
bool cmp(edge x1,edge x2)
{
return x1.y<x2.y;
}
double s[2005];
void build(int u, int l, int r)
{
tree[u].l = l;
tree[u].r = r;
tree[u].cover=0;
if(l==r)
{
return ;
}
int mid = (l+r) >> 1;
build(ls,l,mid);
build(rs,mid+1,r);
}
inline void pushup(int u)
{
int k=min(tree[ls].cover,tree[rs].cover);
tree[u].cover+=k;
tree[ls].cover-=k;
tree[rs].cover-=k;
}
inline pushdown(int u)
{
tree[ls].cover+=tree[u].cover;
tree[rs].cover+=tree[u].cover;
tree[u].cover=0;
}
void update(int u, int l,int r,int t)
{
int mid=(tree[u].l+tree[u].r)>>1;
if(tree[u].l>=l&&tree[u].r<=r)
{
tree[u].cover+=t;
return;
}
if(tree[u].cover&&tree[u].l!=tree[u].r)
pushdown(u);
if(l<=mid)
update(ls,l,r,t);
if(r>mid)
update(rs,l,r,t);
pushup(u);
}
double query(int u,int l,int r)
{
int mid=(tree[u].l+tree[u].r)>>1;
if(tree[u].l>=l&&tree[u].r<=r&&tree[u].cover>=2)
{
return s[tree[u].r+1]-s[tree[u].l];
}
if(tree[u].l==tree[u].r)
return 0;
if(tree[u].cover&&tree[u].l!=tree[u].r)
pushdown(u);
double asb=0;
if(l<=mid)
asb+=query(ls,l,r);
if(r>mid)
asb+=query(rs,l,r);
return asb;
}
int main()
{
int n;
int t=0;
int tol,i,k,j;
int pos1,pos2;
double x1,x2,y1,y2;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
tol=0;
ans=0;
for(i=0; i<n; i++)
{
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
s[tol]=x1;
s[tol+1]=x2;
e[tol].r=x2;
e[tol].l=x1;
e[tol].y=y1;
e[tol].t=1;
e[tol+1].r=x2;
e[tol+1].l=x1;
e[tol+1].y=y2;
e[tol+1].t=-1;
tol+=2;
}
sort(e,e+tol,cmp);
sort(s,s+tol);
k=unique(s,s+tol)-s;
build(1,0,k-1);
for(i=0; i<tol-1; i++)
{
pos1=lower_bound(s,s+k,e[i].l)-s;
pos2=lower_bound(s,s+k,e[i].r)-s-1;
update(1,pos1,pos2,e[i].t);
double sb=query(1,0,k-1);
ans+=sb*(e[i+1].y-e[i].y);
printf("%.2f\n",ans);
}
return 0;
}
主席树（POJ2104）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef int ll;
struct node
{
ll l,r;
ll ls,rs;
ll sum;
} tree[2000005];
ll rt[100005];
ll tol;
ll a[100005];
ll b[100005];
void build(ll &u,ll l,ll r)
{
u=tol++;
tree[u].l=l;
tree[u].r=r;
tree[u].sum=0;
ll mid=(tree[u].l+tree[u].r)>>1;
if(tree[u].r==tree[u].l)
return;
build(tree[u].ls,l,mid);
build(tree[u].rs,mid+1,r);
}
void update(ll p,ll &u,ll x)
{
u=tol++;
tree[u].l=tree[p].l;
tree[u].r=tree[p].r;
tree[u].ls=tree[p].ls;
tree[u].rs=tree[p].rs;
ll mid=(tree[u].l+tree[u].r)>>1;
tree[u].sum=tree[p].sum;
tree[u].sum++;
if(tree[u].l==tree[u].r)
return;
if(x>mid)
update(tree[p].rs,tree[u].rs,x);
else
update(tree[p].ls,tree[u].ls,x);
}
ll query(ll u,ll v,ll k)
{
ll mid=(tree[u].l+tree[u].r)>>1;
ll sum=tree[tree[v].ls].sum-tree[tree[u].ls].sum;
ll ans;
if(tree[u].l==tree[u].r)
{
return tree[u].l;
}
if(sum>=k)
{
ans=query(tree[u].ls,tree[v].ls,k);
}
else
{
ans=query(tree[u].rs,tree[v].rs,k-sum);
}
return ans;
}
int main()
{
tol=0;
ll n,m,s,i,j,l,r,k;
while(scanf("%d %d",&n,&m)!=EOF)
{
for(i=1; i<=n; i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+n+1);
s=unique(b+1,b+n+1)-(b+1);
tol=0;
build(rt[0],1,s);
for(i=1; i<=n; i++)
{
ll pos=lower_bound(b+1,b+s+1,a[i])-(b);
update(rt[i-1],rt[i],pos);
}
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&l,&r,&k);
s=query(rt[l-1],rt[r],k);
printf("%d\n",b[s]);
}
}
return 0;
}
树链剖分+经典线段树（HDU2586）
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<cstring>
#include<cstdio>
using namespace std;
struct node
{
int k;
int w;
int next;
} ed[80005];
int head[40005];
int tol,n;
int maxi[40005<<2];
inline void pushup(int u)
{
maxi[u]=maxi[u<<1]+maxi[u<<1|1];
}
void update(int u,int x,int l,int r,int num)
{
int mid=(l+r)>>1;
if(l==r)
{
maxi[u]=num;
return;
}
if(x<=mid)
update(u<<1,x,l,mid,num);
else
update(u<<1|1,x,mid+1,r,num);
pushup(u);
}
int query(int u,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return maxi[u];
}
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)
{
ans+=query(u<<1,l,mid,L,R) ;
}
if(R>mid)
{
ans+=query(u<<1|1,mid+1,r,L,R) ;
}
return ans;
}
inline void add(int x,int y,int w)
{
ed[tol].k=y;
ed[tol].next=head[x];
ed[tol].w=w;
head[x]=tol++;
ed[tol].k=x;
ed[tol].next=head[y];
ed[tol].w=w;
head[y]=tol++;
}
int fa[40005];
int son[40005];
int size[40005];
int depth[40005];
int id[40005];
int cnt;
int top[40005];
int pre[40005];
void dfs1(int x,int d,int f)
{
depth[x]=d;
fa[x]=f;
son[x]=0;
size[x]=1;
int i;
for(i=head[x]; i!=-1; i=ed[i].next)
{
if(ed[i].k!=f)
{
pre[ed[i].k]=ed[i].w;
dfs1(ed[i].k,d+1,x);
size[x]+=size[ed[i].k];
}
if(ed[i].k!=f&&(!son[x]||size[ed[i].k]>size[son[x]]))
son[x]=ed[i].k;
}
}
void dfs2(int x,int topf)
{
top[x]=topf;
id[x]=++cnt;
update(1,cnt,1,n,pre[x]);
if(!son[x])
return;
int k;
dfs2(son[x],topf);
for(int i=head[x]; i!=-1; i=ed[i].next)
{
if(ed[i].k!=son[x]&&ed[i].k!=fa[x])
{
dfs2(ed[i].k,ed[i].k);
}
if(ed[i].k=son[x])
k=ed[i].w;
}
}
int main()
{
int m,x,y,w,i,s,f1,f2,t;
scanf("%d",&t);
while(t--)
{
tol=0;
scanf("%d %d",&n,&m);
memset(head,-1,sizeof(head));
memset(size,0,sizeof(size));
memset(maxi,0,sizeof(maxi));
for(i=0; i<n-1; i++)
scanf("%d%d%d",&x,&y,&w),add(x,y,w);
cnt=0;
pre[1]=0;
dfs1(1,1,1);
dfs2(1,1);
for(i=0; i<m; i++)
{
scanf("%d%d",&x,&y);
s=0;
while(top[x]!=top[y])
{
if(depth[top[x]]>depth[top[y]])
{
s+=query(1,1,n,id[top[x]],id[x]);
x=fa[top[x]];
}
else
{
s+=query(1,1,n,id[top[y]],id[y]);
y=fa[top[y]];
}
}
if(depth[x]>depth[y])
{
s+=query(1,1,n,id[y]+1,id[x]);
}
else if(depth[x]<depth[y])
{
s+=(query(1,1,n,id[x]+1,id[y]));
}
printf("%d\n",s);
}
}
return 0;
}
莫队+dfs序
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
int head[100005];
struct node
{
int k;
int next;
}a[200005];
struct node1
{
int index;
int l,r;
int w;
} ss[200005];
int tol=0;
inline void add(int x,int y)
{
a[tol].next=head[x];
a[tol].k=y;
head[x]=tol++;
a[tol].next=head[y];
a[tol].k=x;
head[y]=tol++;
}
int in[200005];
int out[200005];
bool vis[100005];
int aa[200005];
int b[200005];
int p;
void dfs(int x)
{
in[x]=++p;
b[p]=aa[x];
for(int i=head[x]; i!=-1; i=a[i].next)
{
if(!vis[a[i].k])
{
vis[a[i].k]=true;
dfs(a[i].k);
}
}
out[x]=p;
}
int block;
bool cmp(node1 s1,node1 s2)
{
if((s1.l/block)==(s2.l/block))
{
return s1.r<s2.r;
}
return s1.l<s2.l;
}
bool cmp1(node1 s1,node1 s2)
{
return s1.index<s2.index;
}
int cnt=0;
int num[100005];
inline void add(int x)
{
cnt+=num[x]==0;//if判断可能会tle
num[x]++;
}
inline void del(int x)
{
cnt-=num[x]==1;//if判断可能会tle
num[x]--;
}
int main()
{
int n,i,l,r,maxi;
while(scanf("%d",&n)!=EOF)
{
tol=0;
for(i=1; i<=n; i++)
head[i]=-1,vis[i]=false;
memset(num,0,sizeof(num));
for(i=2; i<=n; i++)
scanf("%d",&p),add(p,i);
for(i=1; i<=n; i++)
scanf("%d",&aa[i]);
p=0;
cnt=0;
block=sqrt(n);
vis[1]=true;
dfs(1);
for(i=1;i<=n;i++)
{
b[i+n]=b[i];
}
for(i=1; i<=n; i++)
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;
sort(ss+1,ss+2*n+1,cmp);
r=2*n;
for(i=1;i<=2*n;i++)
add(b[i]);
l=1;
for(i=1;i<=2*n;i++)
{
while(l<ss[i].l)
del(b[l++]);
while(r>ss[i].r)
del(b[r--]);
while(l>ss[i].l)
add(b[--l]);
while(r<ss[i].r)
add(b[++r]);
ss[i].w=cnt;
}
sort(ss+1,ss+2*n+1,cmp1);
maxi=0;
for(i=2;i<=n;i++)
maxi=max(maxi,ss[i].w+ss[i+n].w);
printf("%d\n",maxi);
}
return 0;
}
st表
#include <iostream>
#include <algorithm>
using namespace std;
int a[1010];//原始输入数组
int st[1010][20];//st表
void init(int n)
{
for (int i = 0; i < n; i++)
st[i][0] = a[i];
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 0; j + (1 << i) - 1 < n; j++)
st[j][i] = min(st[j][i - 1],st[j + (1 << (i - 1))][i - 1]);
}
}
int search(int l, int r)
{
int k = (int)(log((double)(r - l + 1)) / log(2.0));
return min(st[l][k],st[r - (1 << k) + 1][k]);
}
int main()
{
int n,m;
while (cin >> n >> m)
{
for (int i = 0; i < n; i++)
cin >> a[i];
init(n);
while (m--)
{
int l, r;
cin >> l >> r;
cout << search(l,r) << endl;;
}
}
return 0;
}
multiset的应用（19牛客多校第六场D）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll;
multiset<int>st;
int a[1005];
int b[1005];
multiset<int> init(int n)
{
multiset<int>p;
for(int i=1; i<=n; i++)
p.insert(a[i]);
return p;
}
bool check(int x,int k)
{
multiset<int>p=st;
multiset<int>::iterator it;
for(int i=1; i<=k; i++)
{
int t=x;
it=p.upper_bound(t);
while(p.size()!=0&&(it!=(p.begin())))
{
it--;
t-=*it;
p.erase(it);
it=p.upper_bound(t);
}
}
if(p.size()==0)
return true;
else
return false;
}
int main()
{
int t;
int n,k,i,l,r,mid,kk=0,sum=0;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
st.clear();
mid=0;
sum=0;
for(i=1; i<=n; i++)
scanf("%d",&a[i]),mid=max(mid,a[i]),sum+=a[i];
st=init(n);
mid=max(mid,sum/k);
while(!check(mid,k))
mid++;
printf("Case #%d: %d\n",++kk,mid);
}
return 0;
}
kmp
注意这里是int平常应该是char（HDU1711）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int s1[1000005];
int s2[1000005];
int next1[10005];
int kmp(int a[],int len1,int b[],int len2)
{
// int next[105];
next1[0]=-1;
next1[1]=0;
int i=2,j=0;
while(i<len2)
{
if(b[i-1]==b[j])
{
next1[i++]=++j;
}
else if(next1[j]==-1)
{
next1[i++]=0;
}
else
j=next1[j];
}
i=0;
j=0;
while(i<len1&&j<len2)
{
if(a[i]==b[j])
i++,j++;
else if(next1[j]==-1)
{
i++;
}
else
j=next1[j];
}
return j==len2?i-j+1:-1;
}
int main()
{
int n,m,i,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=0; i<n; i++)
scanf("%d",&s1[i]);
for(i=0; i<m; i++)
scanf("%d",&s2[i]);
printf("%d\n",kmp(s1,n,s2,m));
}
return 0;
}
字典树（HDU1251）
#include<cstdio>
#include<iostream>
#include<string.h>
using namespace std;
struct node
{
int next[27];
int v;
int init()
{
v=0;
memset(next,-1,sizeof(next));
}
}a[1000005];
int tol=0;
int ans=0;
void add(char s[],int len)
{
int now=0;
for(int i=0;i<len;i++)
{
int tmp=s[i]-'a';
if(a[now].next[tmp]==-1)
{
a[now].next[tmp]=++tol;
a[tol].init();
}
now=a[now].next[tmp];
a[now].v++;
};
}
int query(char s[],int len)
{
int now=0;
for(int i=0;i<len;i++)
{
int tmp=s[i]-'a';
if(a[now].next[tmp]==-1)
return 0;
now=a[now].next[tmp];
}
return a[now].v;
}
char s[100];
int main()
{
int k;
a[0].init();
while(gets(s))
{
k=strlen(s);
if(k==0)
break;
add(s,k);
}
while(gets(s))
{
k=strlen(s);
printf("%d\n",query(s,k));
}
return 0;
}
manacher算法（洛谷3805）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define maxn 11000005
using namespace std;
int len[maxn<<1];
char s[maxn],tmp[maxn<<1];
inline int init(char *p){
int n=strlen(p);
tmp[0]='@';
for(int i=1;i<=2*n;i+=2){
tmp[i]='#',tmp[i+1]=p[i/2];
}
tmp[2*n+1]='#'; tmp[2*n+2]='$';
return 2*n+1;
}
inline int Manacher(char *p,int n){
int mx=0,pos=0,ans=0;
for(int i=1;i<=n;i++){
if(mx>i) len[i]=min(mx-i,len[2*pos-i]);//i被mx覆盖了
else len[i]=1;
while(p[i-len[i]]==p[i+len[i]]) len[i]++;//左右扩展
if(len[i]+i>mx) mx=len[i]+i,pos=i;//更新
ans=max(ans,len[i]-1);
}
return ans;
}
int main(){
scanf("%s",s); int m=init(s);
printf("%d\n",Manacher(tmp,m));
return 0;
}
并查集
int findroot(int x)
{
if(x!=parent[x])
{
parent[x]=findroot(parent[x]);
}
return parent[x];
}
void mergeroot(int a,int b)
{
int p1=findroot(a);
int p2=findroot(b);
parent[p1]=p2;
}
快速乘
inline ll ksc(ll x,ll y,ll p){//计算x乘y的积
ll res=0;//加法初始化
while(y){
if(y&1)res=(res+x)%p;//模仿二进制
x=(x<<1)%p; y>>=1;//将x不断乘2达到二进制
}return res;
}
// ll 表示 long long
inline ll ksc(ll x,ll y,ll p){
ll z=(ld)x/p*y;
ll res=(ull)x*y-(ull)z*p;
return (res+p)%p;
}
// ll 表示 long long
// ld 表示 long double
// ull 表示 usigned long long
// 一种自动溢出的数据类型（存满了就会自动变为0）
单调队列（19牛客多校第三场F）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define INF 100000000
int mx[505],mi[505];
int q1[505];
int q2[505];
int a[505][505];
int main()
{
int n,m,i,j,ans,q11,q21,q12,q22,k,last1,last2;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
ans=0;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
}
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
mi[j]=mx[j]=a[i][j];
for(j=i; j<=n; j++)
{
q11=q21=q12=q22=0;
last1=1;
last2=1;
for(k=1; k<=n; k++)
{
mi[k]=min(mi[k],a[j][k]);
mx[k]=max(mx[k],a[j][k]);
while(q11!=q12&&mx[q1[q12]]<=mx[k])
q12--;
while(q21!=q22&&mi[q2[q22]]>=mi[k])
q22--;
q1[++q12]=k;
q2[++q22]=k;
while(q11!=q12&&q22!=q21&&mx[q1[q11+1]]-mi[q2[q21+1]]>m)
{
if(q1[q11+1]<q2[q21+1])
{
last1=q1[q11+1]+1;
q11++;
}
else
{
last2=q2[q21+1]+1;
q21++;
}
}
if(q11!=q12&&q22!=q21)
{
ans=max((k-max(last1,last2)+1)*(j-i+1),ans);
}
}
}
}
printf("%d\n",ans);
}
return 0;
}
三分
#include<cstdio>
#include<cmath>
using namespace std;
const double eps=1e-5;
double a,b,c,xx,yy;
double f(double x){
return sqrt((x-xx)*(x-xx)+(a*x*x+b*x+c-yy)*(a*x*x+b*x+c-yy));
}
int main(){
scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&xx,&yy);
double l=-200,r=200;
while(r-l>eps){
double lm=l+(r-l)/3,rm=r-(r-l)/3;
if(f(lm)<f(rm)) r=rm;
else l=lm;
}
printf("%.3lf\n",f(l));
return 0;
}