复习列表
lmrttx
2020-12-09 21:38:40
12.9.2020
负环模板，AC。
[负环](https://www.luogu.com.cn/problem/P3385)。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define inf 10000000
#define maxn 2001
#define maxm 3001
int n,m,cnt,h[maxn],T;
int dis[maxn],visnum[maxn];
bool vis[maxn];
queue<int> q;
struct edge{
int u,v,w,nxt;
edge(int u1=0,int v1=0,int w1=0,int n1=0):
u(u1),v(v1),w(w1),nxt(n1) {}
}e[maxm<<1];
inline void add(int u,int v,int w){
e[++cnt]=edge(u,v,w,h[u]);h[u]=cnt;
}
void in(){
scanf("%d%d",&n,&m);
cnt=-1;
memset(h,-1,sizeof(h));
for(register int i=1,u,v,w;i<=m;++i){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);if(w>=0)add(v,u,w);
}
}
void spfa(){
fill(dis+1,dis+n+1,inf);
memset(visnum,0,sizeof(visnum));
memset(vis,0,sizeof(vis));
while(!q.empty()){
q.pop();
}
int u,v,w;
dis[1]=0;vis[1]=1;q.push(1);
while(!q.empty()){
u=q.front();vis[u]=0;q.pop();
for(register int i=h[u];i!=-1;i=e[i].nxt){
v=e[i].v;w=e[i].w;
if(dis[u]+w<dis[v]){
dis[v]=dis[u]+w;
if(!vis[v]){
++visnum[v];
if(visnum[v]>=n){
printf("YES\n");
return;
}
q.push(v);
vis[v]=1;
}
}
}
}
printf("NO\n");
}
int main(){
scanf("%d",&T);
while(T--){
in();spfa();
}
return 0;
}
```
update 2020.12.13 **勿忘国耻**
笛卡尔树：二叉搜索树+小根堆 P5854
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 10000005
int n,a[maxn],b[maxn],s[maxn],top,ch[maxn][2],ls,rs;
#define gc() (p0==p1&&(p1=(p0=buf)+fread(buf,1,1048576,stdin),p0==p1)?EOF:*p0++)
char buf[1048576],*p0,*p1;
inline int read() {
int r=0; char c=gc(); while (c<48||c>57) c=gc();
while (c>47&&c<58) {r=(r<<3)+(r<<1)+(c^48); c=gc();} return r;
}
#undef gc
signed main(){
//scanf("%lld",&n);
n=read();
for(int i=1;i<=n;i++)//scanf("%lld",&a[i]);
a[i]=read();
s[++top]=0;
for(int i=1;i<=n;i++){
while(top&&a[s[top]]>a[i])ch[i][0]=s[top--];
if(s[top])ch[s[top]][1]=i;s[++top]=i;
}
for(int i=1;i<=n;i++){
ls^=(i*(ch[i][0]+1));rs^=(i*(ch[i][1]+1));
}
printf("%lld %lld",ls,rs);
return 0;
}
```
update 2021.1.3
[失配树模板](https://www.luogu.com.cn/problem/P5829#submit)
```cpp
#include<bits/stdc++.h>
using namespace std;
#define maxlog 25
#define maxn 1000005
int fail[maxn],fa[maxn][maxlog],dis[maxn],n,q,l1,r1;
char s[maxn];
int p=0;
int jump(int x,int h){
if(dis[x]<=h)return x;
for(register int i=21;i>=0;i--){if(dis[fa[x][i]]>h)x=fa[x][i];}
return fa[x][0];
}
int lca(int x,int y){
if(dis[x]<dis[y])swap(x,y);
x=jump(x,dis[y]);for(register int i=21;i>=0;i--){
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
}return fa[x][0];
}
int main(){
scanf("%s%d",&s[1],&q);n=strlen(s+1);
for(register int i=2;i<=n;i++){
while(p&&s[p+1]!=s[i])p=fail[p];
if(s[p+1]==s[i])++p;fail[i]=p;dis[i]=dis[p]+1;
fa[i][0]=p;
}
for(register int k=1;k<=21;k++)for(register int i=1;i<=n;i++)
fa[i][k]=fa[fa[i][k-1]][k-1];
while(q--){scanf("%d%d",&l1,&r1);printf("%d\n",lca(l1,r1));}
return 0;
}
```