对拍程序
while true; do
./makedata > test.in
./A < test.in > A.out
./B < test.in > B.out
if diff A.out B.out; then
printf AC
else
echo WA
exit 0
fi
done
Vim简要配置
set tabstop=4
set softtabstop=4
set shiftwidth=4
syntax on
set nu
set ruler
set autoindent
set smartindent
set scrolloff=5
noremap <F9> :call R()<CR>
noremap <F8> :call G()<CR>
func! R()
exe "w"
exe "!g++ % -std=c++14 -g -Wall -o %<"
exe "!./%<"
endfunc
func! G()
exe "!g++ % -std=c++14 -g -Wall -o %<"
exe "!gdb %<"
endfunc
func! s:ADB() abort
call append(line("'>"),'}')
call append(line("'<")-1,'{')
endfunc
inoremap {<CR> {<CR>}<ESC>O
vnoremap { :<C-u>call <sid>ADB()<CR>gvokoj=k$cmap w!! w !sudo tee > /dev/null %
树链剖分：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
const LL MAX=~0ULL;
const int maxn=1e5+10;
struct HLD // Heavy_Light_Decomposition
{
struct Segment_Tree
{
LL sum[maxn<<2];
LL tag_inc[maxn<<2];
LL tag_mul[maxn<<2];
int n;
#define ls (o<<1)
#define rs ((o<<1)|1)
#define mid ((l+r)>>1)
void Mark_Inc(int o,int l,int r,LL t_inc)
{
sum[o]+=(LL)(r-l+1)*t_inc;
tag_inc[o]+=t_inc;
}
void Mark_Mul(int o,int l,int r,LL t_mul)
{
sum[o]*=t_mul;
tag_mul[o]*=t_mul;
tag_inc[o]*=t_mul;
}
void Push_Down(int o,int l,int r)
{
if (tag_mul[o]!=1ULL)
{
Mark_Mul(ls,l,mid,tag_mul[o]);
Mark_Mul(rs,mid+1,r,tag_mul[o]);
tag_mul[o]=1ULL;
}
if (tag_inc[o])
{
Mark_Inc(ls,l,mid,tag_inc[o]);
Mark_Inc(rs,mid+1,r,tag_inc[o]);
tag_inc[o]=0ULL;
}
}
void Update(int o)
{
sum[o]=sum[ls]+sum[rs];
}
void Change(int o,int l,int r,int a,int b,LL t_inc,LL t_mul)
{
if (a<=l && r<=b)
{
Mark_Mul(o,l,r,t_mul);
Mark_Inc(o,l,r,t_inc);
return;
}
Push_Down(o,l,r);
if (a<=mid) Change(ls,l,mid,a,b,t_inc,t_mul);
if (b> mid) Change(rs,mid+1,r,a,b,t_inc,t_mul);
Update(o);
}
LL Query(int o,int l,int r,int a,int b)
{
if (a<=l && r<=b)
return sum[o];
Push_Down(o,l,r);
LL res=0ULL;
if (a<=mid) res+=Query(ls,l,mid,a,b);
if (b> mid) res+=Query(rs,mid+1,r,a,b);
Update(o);
return res;
}
void Build_Tree(int o,int l,int r)
{
tag_inc[o]=0ULL;
tag_mul[o]=1ULL;
sum[o]=0ULL;
if (l==r) return;
Build_Tree(ls,l,mid);
Build_Tree(rs,mid+1,r);
}
#undef ls
#undef rs
#undef mid
void Init(int _n) {n=_n;Build_Tree(1,1,n);}
void Change(int x,int y,LL t_inc,LL t_mul) {Change(1,1,n,x,y,t_inc,t_mul);}
LL Query(int x,int y) {return Query(1,1,n,x,y);}
}ST;
int wson[maxn];
int sons[maxn];
int top[maxn];
int dep[maxn];
int fa[maxn];
int dfq[maxn],order[maxn],Index;
int *head,*nxt,*E;
int n;
void DFS(int x,int father,int depth)
{
dep[x]=depth;
fa[x]=father;
sons[x]=1;
for (int i=head[x];i;i=nxt[i]) if (E[i]!=father)
{
DFS(E[i],x,depth+1),sons[x]+=sons[E[i]];
if (sons[wson[x]]<sons[E[i]]) wson[x]=E[i];
}
}
void DFS2(int x,int father,int is_wson)
{
top[x]=(is_wson)?top[father]:x;
dfq[++Index]=x;
order[x]=Index;
if (wson[x]) DFS2(wson[x],x,1);
for (int i=head[x];i;i=nxt[i]) if (E[i]!=father && E[i]!=wson[x])
DFS2(E[i],x,0);
}
void Build_HLD(int _n,int *_head,int *_nxt,int *_E)
{
n=_n,head=_head,nxt=_nxt,E=_E;
Index=0;
memset(wson,0,(n+1)*sizeof(int));
DFS(1,0,1);
DFS2(1,0,0);
ST.Init(n);
}
LL Query(int x,int y)
{
LL res=0ULL;
while (top[x]!=top[y])
(dep[top[x]]>dep[top[y]]) ? (res+=ST.Query(order[top[x]],order[x]),x=fa[top[x]])
: (res+=ST.Query(order[top[y]],order[y]),y=fa[top[y]]);
if (order[x]>order[y]) swap(x,y);
res+=ST.Query(order[x],order[y]);
return res;
}
void Change(int x,int y,LL t_inc,LL t_mul)
{
while (top[x]!=top[y])
(dep[top[x]]>dep[top[y]]) ? (ST.Change(order[top[x]],order[x],t_inc,t_mul),x=fa[top[x]])
: (ST.Change(order[top[y]],order[y],t_inc,t_mul),y=fa[top[y]]);
if (order[x]>order[y]) swap(x,y);
ST.Change(order[x],order[y],t_inc,t_mul);
}
void Change_Inc(int x,int y,LL t_inc) {Change(x,y,t_inc,1ULL);}
void Change_Mul(int x,int y,LL t_mul) {Change(x,y,0ULL,t_mul);}
void Change_Not(int x,int y) {Change(x,y,MAX,MAX);}
}T;
int head[maxn],nxt[maxn],E[maxn],Ecnt;
int n,m;
void Add_Edge(int x,int y) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(head,0,sizeof(head));
Ecnt=0;
for(int i=2,x;i<=n;i++)
scanf("%d",&x),Add_Edge(x,i);
T.Build_HLD(n,head,nxt,E);
scanf("%d",&m);
while(m--)
{
int op,u,v;
LL x;
scanf("%d",&op);
if(op==1)
scanf("%d%d%llu",&u,&v,&x),
T.Change_Mul(u,v,x);
if(op==2)
{
scanf("%d%d%llu",&u,&v,&x);
T.Change_Inc(u,v,x);
}
if(op==3)
scanf("%d%d",&u,&v),
T.Change_Not(u,v);
if(op==4)
scanf("%d%d",&u,&v),
printf("%llu\n",T.Query(u,v));
}
}
return 0;
}
网络流ISAP
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1e5+10,maxm=2e5+10,inf=~0U>>1;
int head[maxn],nxt[maxm<<1],E[maxm<<1],F[maxm<<1],Ecnt;
int h[maxn],cur[maxn],gap[maxn];
int n,m,S,T;
void Add_Edge(int x,int y,int c)
{
nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;F[Ecnt]=0;
nxt[++Ecnt]=head[y];head[y]=Ecnt;E[Ecnt]=x;F[Ecnt]=c;
}
int DFS(int v,int flow)
{
if (v==T) return flow;
int rest=flow;
for (int &i=cur[v];i;i=nxt[i]) if (h[v]==h[E[i]]+1 && F[i^1])
{
int ret=DFS(E[i],min(rest,F[i^1]));
F[i]+=ret,F[i^1]-=ret,rest-=ret;
if (rest==0) return flow;
}
if (--gap[h[v]] == 0) h[S]=n;
gap[++h[v]]++;
cur[v]=head[v];
return flow-rest;
}
int ISAP()
{
int ans=0;
for (int i=1;i<=n;i++) h[i]=0,gap[i]=0,cur[i]=head[i];
gap[0]=n;
while (h[S]<n)
ans+=DFS(S,inf);
return ans;
}
int main()
{
while (scanf("%d%d",&m,&n)!=EOF)
{
Ecnt=1;
for (int i=1;i<=n;i++) head[i]=0;
for (int i=1,x,y,c;i<=m;i++) scanf("%d%d%d",&x,&y,&c),Add_Edge(x,y,c);
S=1,T=n;
printf("%d\n",ISAP());
}
}
有向图最小生成树
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10,maxm=3e5+10,inf=~0U>>1;
struct Edge
{
int v,c;
Edge(int _v=0,int _c=0):v(_v),c(_c){};
bool operator< (const Edge &b) const {if (c==b.c) return v<b.v;return c<b.c;}
};
set<Edge> ME[maxn],*E[maxn];
stack<int> Q;
int gv[maxn];
int Instack[maxn];
int fa[maxn];
long long ans;
int n,m;
int F(int x) {return (fa[x]==x)?x:fa[x]=F(fa[x]);}
void Union(int x,int y)
{
x=F(x),y=F(y);
if (E[x]->size()<E[y]->size()) swap(E[x],E[y]),swap(gv[x],gv[y]);
for (auto e=E[y]->begin();e!=E[y]->end();++e) if (F(e->v)!=x && F(e->v)!=y)
E[x]->insert(Edge(F(e->v),e->c-gv[y]+gv[x]));
E[y]->clear();
fa[y]=x;
}
int main()
{
//freopen("test.in","r",stdin);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) E[i]=&ME[i];
for (int i=1,x,y,c;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&c);
ME[y].insert(Edge(x,c));
}
for (int i=1;i<=n;i++) fa[i]=i,gv[i]=0;
for (int i=2;i<=n;i++) if (F(i)!=F(1))
{
Q.push(F(i));
Instack[F(i)]=1;
while (true)
{
int x=F(Q.top());
while (!E[x]->empty() && F(E[x]->begin()->v)==F(x)) E[x]->erase(E[x]->begin());
if (E[x]->empty()) {while (!Q.empty()) Instack[Q.top()]=0,Q.pop();break;}
int mincost=E[x]->begin()->c,nextNode=F(E[x]->begin()->v);
ans+=mincost-gv[x];
gv[x]=mincost;
if (F(nextNode)==F(1))
{
while (!Q.empty())
{
Instack[F(Q.top())]=0;
E[F(Q.top())]->clear();
Union(1,Q.top());
Q.pop();
}
break;
}
else if (Instack[F(nextNode)])
{
while (F(Q.top())!=F(nextNode))
{
Instack[F(Q.top())]=0;
Union(nextNode,Q.top());
Q.pop();
}
}
else
{
Q.push(nextNode);
Instack[nextNode]=1;
}
}
}
for (int i=1;i<=n;i++) if (F(i)!=F(1))
return printf("NO\n"),0;
printf("YES\n%lld\n",ans);
return 0;
}
FWT（临时）
void FWT(int a[],int n)
{
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++)
{
int x=a[i+j],y=a[i+j+d];
a[i+j]=(x+y)%mod,a[i+j+d]=(x-y+mod)%mod;
//xor:a[i+j]=x+y,a[i+j+d]=(x-y+mod)%mod;
//and:a[i+j]=x+y;
//or:a[i+j+d]=x+y;
}
}
void UFWT(int a[],int n)
{
for(int d=1;d<n;d<<=1)
for(int m=d<<1,i=0;i<n;i+=m)
for(int j=0;j<d;j++)
{
int x=a[i+j],y=a[i+j+d];
a[i+j]=1LL*(x+y)*rev%mod,a[i+j+d]=(1LL*(x-y)*rev%mod+mod)%mod;
//rev表示2在模mod下的逆元
//xor:a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;
//and:a[i+j]=x-y;
//or:a[i+j+d]=y-x;
}
}
void solve(int a[],int b[],int n)
{
FWT(a,n);
FWT(b,n);
for(int i=0;i<n;i++) a[i]=1LL*a[i]*b[i]%mod;
UFWT(a,n);
}
FWT（Xor)
void trans(int *a,int n) {
for (int i = 1; i < n; i << = 1)
for (int j = 0; j < n; j += (i << 1) )
for (int k = 0; k < i; ++k)
{
long long x = a[j + k], y = a[j + k + i];
a[j + k] = (x + y) % P;
a[j + k + i] = (x - y + P) % P;
}
}
void trans(int *a,int n) {
for (int i = 1; i < n; i *= 3)
for (int j = 0; j < n; j += i * 3)
for (int k = 0; k < i; ++k)
{
long long x = a[j + k], y = a[j + k + i], z = a[j + k + i + i];
a[j + k] = (x + y + z) % P;
a[j + k + i] = (x + W1 * y + W2 * z) % P;
a[j + k + i + i] = (x + W2 * y + W1 * z) % P;
}
}
// W1 = g^((P - 1) / 3), W2 = g^((P -1) / 3 * 2)
任意模数FFT
const int maxn = 262144 + 10, M = 32767, mo = 1e9 + 7;
const double pi = acos(-1.0);
typedef long long LL;
struct Complex {
double r, i;
Complex (double _r = 0, double _i = 0) : r(_r), i(_i) {}
Complex operator * (const Complex &a) const {return Complex(r * a.r - i * a.i, r * a.i + i * a.r);}
Complex operator + (const Complex &a) const {return Complex(r + a.r, i + a.i);}
Complex operator - (const Complex &a) const {return Complex(r - a.r, i - a.i);}
void operator += (const Complex &a) {r += a.r; i += a.i;}
void operator -= (const Complex &a) {r -= a.r; i -= a.i;}
Complex conj() const {return Complex(r, -i);}
};
void FFT(Complex *arr, int N, int *rev, Complex *w) {
for (int i = 0; i < N; ++i) if (i < rev[i]) swap(arr[i], arr[rev[i]]);
for (int i = 1, wn = N >> 1; i < N; i <<= 1, wn >>= 1)
for (int j = 0; j < N; j += (i<<1))
for (int k = 0, wp = 0; k < i; ++k, wp += wn)
{
Complex tmp = w[wp] * arr[i + j + k];
arr[i + j + k] = arr[j + k] - tmp; arr[j + k] += tmp;
}
}
void Mul(int *A, int *B, int *C, int n, int m)
{
static Complex a[maxn], b[maxn], Da[maxn], Db[maxn], Dc[maxn], Dd[maxn], w[maxn];
static int N, rev[maxn];
if (n <= 50 || m <= 50)
{
for (int i = 0; i < n + m - 1; ++i) C[i]=0;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
(C[i + j] += (LL)A[i] * B[j] % mo) %= mo;
return;
}
N = 1; while (N <= n + m - 1) N <<= 1;
for (int i = 0; i < N; ++i) w[i] = Complex(cos(2 * pi / N * i), sin(2 * pi / N * i));
for (int i = 1; i < N; ++i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N >> 1));
for (int i = 0; i < n; ++i) a[i] = Complex(A[i] & M, A[i] >> 15);
for (int i = n; i < N; ++i) a[i] = Complex(0, 0);
for (int i = 0; i < m; ++i) b[i] = Complex(B[i] & M, B[i] >> 15);
for (int i = m; i < N; ++i) b[i] = Complex(0, 0);
FFT(a, N, rev, w); FFT(b, N, rev, w);
for (int i = 0; i < N; ++i)
{
int j = (i==0) ? 0 : (N - i);
Complex da, db, dc, dd;
da = (a[i] + a[j].conj()) * Complex(0.5, 0);
db = (a[i] - a[j].conj()) * Complex(0, -0.5);
dc = (b[i] + b[j].conj()) * Complex(0.5, 0);
dd = (b[i] - b[j].conj()) * Complex(0, -0.5);
Da[j] = da * dc; Db[j] = da * dd; Dc[j] = db * dc; Dd[j] = db * dd;
}
for (int i = 0; i < N; ++i) a[i] = Da[i] + Db[i] * Complex(0, 1);
for (int i = 0; i < N; ++i) b[i] = Dc[i] + Dd[i] * Complex(0, 1);
FFT(a, N, rev, w); FFT(b, N, rev, w);
for (int i = 0; i < N; ++i) {
int da = (LL) (a[i].r / N + 0.5) % mo;
int db = (LL) (a[i].i / N + 0.5) % mo;
int dc = (LL) (b[i].r / N + 0.5) % mo;
int dd = (LL) (b[i].i / N + 0.5) % mo;
C[i] = (da + ((LL)(db + dc) << 15) + ((LL)dd << 30)) % mo;
}
}
多项式乘法、除法、取模、多点求值
typedef long long LL;
const int maxn = 262144 + 10, mo = 998244353, g = 3;
long long Pow(long long x,int p)
{
long long res = 1;
while (p)
{
if (p & 1) (res *= x) %= mo;
(x *= x) %= mo;
p >>= 1;
}
return res;
}
long long inv(long long x)
{
return Pow(x, mo - 2);
}
inline void FFT(int *arr, int N)
{
static int N0 = 0, rev[maxn];
if (N != N0)
{
for (int i = 1; i < N; ++i)
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (N >> 1));
N0 = N;
}
for (int i = 0; i < N; ++i) if (i < rev[i]) swap(arr[i], arr[rev[i]]);
for (int i = 1; i < N; i <<= 1)
{
int wn = Pow(g, ((mo - 1) / i) >> 1);
for (int j = 0; j < N; j += i << 1)
{
int w = 1;
for (int k = 0; k < i; ++k, w = (long long)w * wn % mo)
{
int x = arr[j + k], y = (long long)w * arr[i + j + k] % mo;
arr[j + k] = (x + y) % mo, arr[j + k + i] = ( x - y + mo) % mo;
}
}
}
}
inline void IDFT(int *arr, int N)
{
reverse(arr + 1, arr + N);
FFT(arr, N);
int invN = inv(N);
for (int i = 0; i < N; ++i) arr[i] = (long long)arr[i] * invN % mo;
}
inline void Polynomial_Multiply(int *A, int *B, int n, int m, int *C) // n = degree bound of A, m = degree bound of B
{
static int tempA[maxn],tempB[maxn];
int N = 1;
if (n <= 5 || m <= 5)
{
N = n + m - 1;
memset(tempA, 0, sizeof(int) * N);
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
(tempA[i + j] += (long long) A[i] * B[j] % mo) %= mo;
copy(tempA, tempA + N, C);
return;
}
while (N < n + m - 1) N <<= 1;
memcpy(tempA, A, sizeof(int) * n);
memcpy(tempB, B, sizeof(int) * m);
memset(tempA + n, 0, sizeof(int) * (N - n));
memset(tempB + m, 0, sizeof(int) * (N - m));
FFT(tempA, N);
FFT(tempB, N);
for (int i = 0; i < N; ++i) C[i] = (long long)tempA[i] * tempB[i] % mo;
IDFT(C, N);
}
void Polynomial_Inverse(int *A, int *invA, int n) // mod x^n
{
if (n == 1)
{
invA[0] = inv(A[0]);
return;
}
int mid = (n + 1) >> 1, N = 1;
static int tempA[maxn], tempB[maxn];
Polynomial_Inverse(A, invA, mid);
while (N < (n << 1) - 1) N <<= 1;
copy(A, A + n, tempA);
memset(tempA + n, 0, sizeof(int) * (N - n));
copy(invA, invA + mid, tempB);
memset(tempB + mid, 0, sizeof(int) * (N - mid));
FFT(tempA, N);
FFT(tempB, N);
for (int i = 0; i < N; ++i) invA[i] = (2 - (long long)tempA[i] * tempB[i] % mo + mo) * tempB[i] % mo;
IDFT(invA, N);
}
void Polynomial_Division(int *A, int *B, int n, int m, int *Q, int *R) // n = degree bound of A, m = degree bound of B, A = B * Q + R
{
if (n < m)
{
memcpy(R, A, sizeof(int) * n);
return;
}
static int tempA[maxn], tempB[maxn];
int N = 1, M = n - m + 1;
while (N < (M << 1) - 1) N <<= 1;
//tempB = B^R^-1
memset(tempA, 0, sizeof(int) * N);
reverse_copy(B, B + m, tempA);
Polynomial_Inverse(tempA, tempB, M);
reverse_copy(A, A + n, tempA);
Polynomial_Multiply(tempA, tempB, M, M, Q);
reverse(Q, Q + M);
Polynomial_Multiply(Q, B, M, m, R);
for (int i = 0; i < m - 1; ++i) if ((R[i] = A[i] - R[i]) < 0) R[i] += mo;
}
void Polynomial_Binary_Coefficient(int *X, int *res, int n, int **ptr, int &tot, int id)
{
if (n == 1)
{
if ((res[tot] = -X[0]) < 0) res[tot] += mo;
res[tot + 1] = 1;
ptr[id] = res + tot;
tot += 2;
return;
}
int mid = n >> 1, N = 1;
Polynomial_Binary_Coefficient(X, res, mid, ptr, tot, id << 1);
Polynomial_Binary_Coefficient(X + mid, res, n - mid, ptr, tot, id << 1 | 1);
if (id == 1) return;
ptr[id] = res + tot;
Polynomial_Multiply(ptr[id << 1], ptr[id << 1 | 1], mid + 1, n - mid + 1, ptr[id]);
tot += n + 1;
}
void Polynomial_Calculator(int *A, int n, int *Y, int m, int **BCoef_ptr, int *X, int id)
{
if (n <= 300 || m <= 300)
{
for (int i = 0; i < m; ++i)
{
long long p = 1, res = 0;
for (int j = 0; j < n; ++j)
res = (res + p * A[j]) % mo,
p = p * X[i] % mo;
Y[i] = res;
}
return;
}
if (n == 1)
{
Y[0] = A[0];
return;
}
int mid = m >> 1, Rn = 0;
static int Q[maxn];
Polynomial_Division(A, BCoef_ptr[id << 1], n, mid + 1, Q, A + n); //R won't be cleared during division
Rn = mid; while (Rn > 1 && A[n + Rn - 1] == 0) Rn--;
Polynomial_Calculator(A + n, Rn, Y, mid, BCoef_ptr, X, id << 1);
Polynomial_Division(A, BCoef_ptr[id << 1 | 1], n, m - mid + 1, Q, A + n);
Rn = m - mid; while (Rn > 1 && A[n + Rn - 1] == 0) Rn--;
Polynomial_Calculator(A + n, Rn, Y + mid, m - mid, BCoef_ptr, X + mid, id << 1 | 1);
}
void Polynomial_Calculator(int *Coef, int *X, int *Y, int n, int m)
{
static int BCoef[maxn * 20], *BCoef_ptr[maxn << 2], temp[maxn << 2]; //BCoef : Coefficients of \prod(x - xi)
int tot = 0;
Polynomial_Binary_Coefficient(X, BCoef, m, BCoef_ptr, tot, 1);
memcpy(temp, Coef, sizeof(int) * n);
Polynomial_Calculator(temp, n, Y, m, BCoef_ptr, X, 1);
}
Pollard_Rho
inline LL add(LL x, LL y, LL mod) {
return (x += y) < mod ? x : x - mod;
}
inline LL mul(LL x, LL y, LL mod) {
const int BLEN = __builtin_clzll(mod) - 1;
const LL BMSK = (1LL << BLEN) - 1;
LL ret = 0;
if(x < y)
swap(x, y);
while(y > 0) {
ret += x * (y & BMSK);
ret = ret < mod ? ret : ret % mod;
y >>= BLEN;
x <<= BLEN;
x = x < mod ? x : x % mod;
}
return ret;
}
inline LL Pow(LL x, LL k, LL mod) {
LL ret = mod > 1 ? 1 : 0;
for( ; k > 0; k >>= 1, x = mul(x, x, mod))
if(k & 1)
ret = mul(ret, x, mod);
return ret;
}
inline bool miller_rabin(LL n) {
if(n == 2)
return 1;
if(n < 2 || !(n & 1))
return 0;
LL s, r;
for(s = 0, r = n - 1; !(r & 1); r >>= 1, ++s);
static const int ptot = 12, pr[ptot] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for(int p : pr) {
if(p >= n)
break;
LL cur = 1, nxt = p;
for(LL k = r; k > 0; k >>= 1, nxt = mul(nxt, nxt, n))
if(k & 1)
cur = mul(cur, nxt, n);
for(int i = 0; i < s; ++i) {
nxt = mul(cur, cur, n);
if(nxt == 1 && cur != 1 && cur != n - 1)
return 0;
cur = nxt;
}
if(cur != 1)
return 0;
}
return 1;
}
inline LL pollard_rho(LL n) {
static mt19937_64 rnd(996);
while(1) {
LL x = rnd() % (n - 3) + 2, y = x, c = rnd() % n, tim = 0, prd = 1;
for(LL i = 1, stp = 2; ; ++i) {
if(i == stp) {
y = x;
stp <<= 1;
}
if((x = add(mul(x, x, n), c, n)) == y)
break;
LL tmp = prd;
if((prd = mul(prd, abs(y - x), n)) == 0)
return __gcd(tmp, n);
static const int maxt = 100;
if((++tim) < maxt)
continue;
if((prd = __gcd(prd, n)) > 1)
return prd;
tim = 0;
}
if(tim > 0 && (prd = __gcd(prd, n)) > 1)
return prd;
}
assert(0);
}
inline void factorize(LL n, vector<pair<LL, int> > &ret) {
vector<LL> vec;
queue<LL> que;
que.push(n);
while(!que.empty()) {
LL x = que.front();
que.pop();
for(LL y : vec)
for( ; x % y == 0; x /= y, vec.push_back(y));
if(x == 1)
continue;
if(miller_rabin(x)) {
vec.push_back(x);
} else {
LL y = pollard_rho(x);
que.push(y);
que.push(x / y);
}
}
sort(vec.begin(), vec.end());
ret.clear();
for(auto x : vec)
if(!ret.empty() && ret.back().first == x) {
++ret.back().second;
} else {
ret.push_back(make_pair(x, 1LL));
}
}
long long get_primitive_root(long long m, long long phim, vector<pair<long long, int> > &fac)
{
if (m == 2) return 1;
for (int x = 2;; x++)
{
int flg=1;
if (Pow(x, phim, m) != 1) continue;
for (auto p : fac)
if (Pow(x, phim / p.first, m) == 1)
{flg = 0; break;}
if (flg) return x;
}
}
后缀自动机
struct SAM
{
struct State
{
int next[26];
int link;
int len;
}st[maxn<<1];
int last,cnt,n;
int ccnt[maxn];
int T[maxn<<1];
int temp[maxn<<1],minl[maxn<<1];
SAM() {last=cnt=1;}
void Extend(int c)
{
int x=++cnt,p;n++;
st[x].len=st[last].len+1;
for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
if (!p) st[x].link=1;
else {
int q=st[p].next[c];
if (st[q].len==st[p].len+1) st[x].link=q;
else {
int v=++cnt;
st[v]=st[q];
st[v].len=st[p].len+1;
for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
st[x].link=st[q].link=v;
}
}
last=x;
}
void Topo()
{
for (int i=1;i<=cnt;i++) ccnt[st[i].len]++;
for (int i=1;i<=n;i++) ccnt[i]+=ccnt[i-1];
for (int i=1;i<=cnt;i++) T[ccnt[st[i].len]--]=i;
for (int i=1;i<=cnt;i++) minl[i]=st[i].len;
}
}
后缀数组
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int sa[maxn],Rank[maxn],h[maxn];
char s[maxn];
int n;
void Radix_Sort(int *x,int *y,int m)
{
static int c[maxn];
for (int i=0;i<=m;i++) c[i]=0;
for (int i=1;i<=n;i++) c[x[y[i]]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i;i--) sa[c[x[y[i]]]--]=y[i];
}
void Build_SA()
{
static int tmp1[maxn],tmp2[maxn];
int i,m=128,*x=tmp1,*y=tmp2;
for (i=1;i<=n;i++) x[i]=s[i],y[i]=i;
Radix_Sort(x,y,m);
for (int k=1;k<=n;k<<=1)
{
int p=0;
for (i=n-k+1;i<=n;i++) y[++p]=i;
for (i=1;i<=n;i++) if (sa[i]>k) y[++p]=sa[i]-k;
Radix_Sort(x,y,m);
swap(x,y);p=1;x[sa[1]]=1;
for (i=2;i<=n;i++) x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
if (p>=n) break;
m=p;
}
for (i=1;i<=n;i++) Rank[sa[i]]=i;
}
void Get_Height()
{
for (int i=1,hn=0;i<=n;i++)
{
if (hn) hn--;
int j=sa[Rank[i]-1];
while (i+hn<=n && j+hn<=n && s[i+hn]==s[j+hn]) hn++;
h[Rank[i]]=hn;
}
}
LCT维护后缀自动机Link树
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=600010;
struct SAM
{
struct LCT
{
struct Node
{
Node *c[2],*p,*lcp;
int v;
int tag;
int w() {return p->c[1]==this;}
}MEM[maxn<<1],*ID[maxn<<1],*Null;
int cnt;
#define ls (x->c[0])
#define rs (x->c[1])
Node* NewNode(int _v=0)
{
++cnt;
MEM[cnt].c[0]=MEM[cnt].c[1]=MEM[cnt].p=MEM[cnt].lcp=Null;
MEM[cnt].v=_v;
MEM[cnt].tag=0;
return &MEM[cnt];
}
LCT()
{
Null=&MEM[0];
Null->c[0]=Null->c[1]=Null->p=Null->lcp=Null;
Null->v=Null->tag=0;
}
void Mark_Add(Node *x,int v) {if (x==Null) return;x->v+=v;x->tag+=v;}
void Push_Down(Node *x)
{
if (x->tag)
{
Mark_Add(ls,x->tag);
Mark_Add(rs,x->tag);
x->tag=0;
}
}
void Rotate(Node *x)
{
Node *p=x->p;
int w=x->w();
x->lcp=p->lcp;p->lcp=Null;
Push_Down(p);Push_Down(x);
x->p=p->p;p->p->c[p->w()]=x;
x->c[!w]->p=p;p->c[w]=x->c[!w];
x->c[!w]=p;p->p=x;
}
void Splay(Node *x)
{
Push_Down(x);
while (x->p!=Null)
{
if (x->p->p==Null) {Rotate(x);break;}
if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
else Rotate(x),Rotate(x);
}
}
void Access(Node *x)
{
Node *v=Null,*pre=x;
while (x!=Null)
{
Splay(x);
rs->p=v->lcp=Null;
rs->lcp=v->p=x;
rs=v;
v=x;x=x->lcp;
}
Splay(pre);
}
void Add_Node(int x,int c)
{
ID[x]=NewNode(c);
}
void Link(int x,int y)
{
ID[x]->lcp=ID[y];
Access(ID[y]);
Mark_Add(ID[y],ID[x]->v);
}
void Cut(int x)
{
Access(ID[x]);
ID[x]->c[0]->p=Null;
Mark_Add(ID[x]->c[0],-ID[x]->v);
ID[x]->c[0]=Null;
}
int Query(int x)
{
Access(ID[x]);
return ID[x]->v;
}
}T;
struct State
{
int next[26];
int link;
int len;
}st[maxn<<1];
int cnt,last;
SAM() {cnt=last=1;T.ID[1]=T.NewNode();}
void Extend(int c)
{
int x=++cnt,p;
T.Add_Node(x,1);
st[x].len=st[last].len+1;
for (p=last;p && !st[p].next[c];p=st[p].link) st[p].next[c]=x;
if (!p) st[x].link=1,T.Link(x,1);
else {
int q=st[p].next[c];
if (st[p].len+1==st[q].len) st[x].link=q,T.Link(x,q);
else {
int v=++cnt;
T.Add_Node(v,0);
st[v]=st[q];
st[v].len=st[p].len+1;
T.Cut(q);T.Link(v,st[v].link);
for (;p && st[p].next[c]==q;p=st[p].link) st[p].next[c]=v;
st[x].link=st[q].link=v;
T.Link(x,v);T.Link(q,v);
}
}
last=x;
}
void Insert(char *ch)
{
int n=strlen(ch);
for (int i=0;i<n;i++) Extend(ch[i]-'A');
}
int Query(char *ch)
{
int n=strlen(ch),x=1;
for (int i=0;i<n;i++)
{
int c=ch[i]-'A';
if (!st[x].next[c]) return 0;
x=st[x].next[c];
}
return T.Query(x);
}
}M;
void decodeWithMask(char *ch,int mask)
{
int n=strlen(ch);
for (int j=0;j<n;j++)
swap(ch[j],ch[mask=((mask*131)+j)%n]);
}
char ch[maxn],type[10];
int q,mask,ans;
int main()
{
scanf("%d",&q);
scanf("%s",ch);
M.Insert(ch);
for (int i=1;i<=q;i++)
{
scanf("%s%s",type,ch);
decodeWithMask(ch,mask);
if (type[0]=='A') M.Insert(ch);
else printf("%d\n",ans=M.Query(ch)),mask^=ans;
}
return 0;
}
网络流Dinic
int head[maxv],nxt[maxm],E[maxm],F[maxm],Ecnt;
int cur[maxv],h[maxv];
int S,T;
bool BFS()
{
static int q[maxn];
int top=1,tail=1;
for (int i=1;i<=T;i++) cur[i]=head[i],h[i]=inf;
h[S]=1;
q[1]=S;
while (top<=tail)
{
int u=q[top++];
for (int i=head[u];i;i=nxt[i]) if (F[i^1] && h[E[i]]==inf)
{
h[E[i]]=h[u]+1;
q[++tail]=E[i];
}
}
return h[T]!=inf;
}
int DFS(int x,int flow)
{
if (x==T) return flow;
int rest=flow;
for (int &i=cur[x];i;i=nxt[i]) if (F[i^1] && h[E[i]]==h[x]+1)
{
int ret=DFS(E[i],min(rest,F[i^1]));
rest-=ret;
F[i]+=ret;F[i^1]-=ret;
if (rest==0) return flow;
}
return flow-rest;
}
int Dinic()
{
int res=0;
while (BFS()) res+=DFS(S,inf);
return res;
}
//Init: Ecnt=1;memset(head,0,sizeof(head));
高斯消元
double coef[maxequa][maxn+1];
double ans[maxn];
int freevar[maxn],freevar_num;
int Gauss(int equa_cnt,int num) //equa_cnt : number of equations; n : number of variables;
{
int leadvar_num=0;
for (int i=1,lead_var=1;i<=equa_cnt && lead_var<=num;i++,lead_var++)
{
int valid_equa=-1;
while (valid_equa==-1)
{
for (int j=i;j<=equa_cnt;j++) if (coef[j][lead_var]!=0) {valid_equa=j;break;}
if (valid_equa==-1)
freevar[++freevar_num]=lead_var++;
if (lead_var>num) break;
}
if (valid_equa==-1) continue;
leadvar_num++;
if (valid_equa!=i)
for (int j=lead_var;j<=num+1;j++) swap(coef[i][j],coef[valid_equa][j]);
for (int j=lead_var+1;j<=num+1;j++) coef[i][j]=coef[i][j]/coef[i][lead_var];
coef[i][lead_var]=1;
for (int j=i+1;j<=equa_cnt;j++) if (coef[j][lead_var]!=0)
{
double g=coef[j][lead_var]/coef[i][lead_var];
for (int k=lead_var;k<=num+1;k++)
coef[j][k]=coef[j][k]-g*coef[i][k];
}
}
while (lead_var<=num)
freevar[++freevar_num]=lead_var++;
for (int i=leadvar_num+1;i<=equa_cnt;i++) if (coef[i][num+1]!=0) return -1; // no solution
for (int i=leadvar_num;i>=1;i--)
{
int lead_var=-1;
for (int j=i;j<=num;j++) if (coef[i][j]!=0) {lead_var=j;break;}
for (int j=1;j<i;j++) if (coef[j][lead_var]!=0)
{
double g=coef[j][lead_var]/coef[i][lead_var];
for (int k=lead_var;k<=num+1;k++)
coef[j][k]=coef[j][k]-g*coef[i][k];
}
}
return leadvar_num;
}
void MultiSolution(int num)
{
for (int i=1;i<=freevar_num;i++) ans[freevar[i]]=1; //free variable
for (int i=num-freevar_num;i>=1;i--)
{
int lead_var=-1;
for (int j=i;j<=num;j++) if (coef[i][j]!=0) {lead_var=j;break;}
ans[lead_var]=coef[i][num+1];
for (int j=lead_var+1;j<=num;j++) if (coef[i][j]!=0)
ans[lead_var]=ans[lead_var]-coef[i][j]*ans[j];
}
for (int i=1;i<=num;i++)
ans[i].print();
}
前向星存图
struct Edge
{
int x,y;
};
struct Graph
{
Edge E[maxm],*begin[maxn],*end[maxn];
int n,m;
void init(int _n=0) {n=_n,m=0;}
void add_edge(int x,int y) {E[m++]={x,y};}
void resort()
{
static Edge tmp[maxm];
static int cnt[maxn];
memcpy(tmp,E,sizeof(Edge)*m);
memset(cnt,0,sizeof(int)*(n+1));
for (int i=0;i<m;i++) cnt[tmp[i].y]++;
for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for (int i=0;i<m;i++) E[--cnt[tmp[i].y]]=tmp[i];
memcpy(tmp,E,sizeof(Edge)*m);
memset(cnt,0,sizeof(int)*(n+1));
for (int i=0;i<m;i++) cnt[tmp[i].x]++;
for (int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
for (int i=0;i<m;i++) E[--cnt[tmp[i].x]]=tmp[i];
int m0=m;m=m0?1:0;
for (int i=1;i<m0;i++) if (!(E[i].x==E[m-1].x && E[i].y==E[m-1].y)) E[m++]=E[i];
for (int i=1,j=0;i<=n;i++)
{
begin[i]=&E[j];
while (j<m && E[j].x==i) j++;
end[i]=&E[j];
}
}
int order[maxn];
void topo()
{
static int deg[maxn];
memset(deg,0,sizeof(int)*(n+1));
for (int i=0;i<m;i++) deg[E[i].y]++;
int tail=0;
for (int i=1;i<=n;i++) if (deg[i]==0) order[++tail]=i;
for (int p=1;p<=tail;p++)
{
int u=order[p];
for (auto it=begin[u];it!=end[u];++it)
if ((--deg[it->y])==0)
order[++tail]=it->y;
}
}
}G;
斜率优化（简易版）
struct Info
{
long double k,b;
Info(long double _k=0,long double _b=0):k(_k),b(_b){}
};
struct Deque
{
Info I[maxn];
long double k[maxn],b[maxn];
int top,tail;
Deque() {top=1;tail=0;}
void autopop(long double x)
{
while (top<tail && I[top].k*x+I[top].b>=k[top+1]*x+b[top+1]) top++;
}
void push(long double k0,long double b0)
{
while (top<tail && (b0-b[tail-1])/(k0-k[tail-1])>=(b[tail]-b[tail-1])/(k[tail]-k[tail-1])) tail--;
++tail;
k[tail]=k0;
b[tail]=b0;
}
Info front() {return Info(k[top],b[top]);}
}Q;
费用流
struct Queue
{
int q[maxn];
int Instack[maxn];
int top,tail;
bool empty() {return top==(tail+1)%maxn;}
void Init() {top=1;tail=0;}
void push(int x)
{
tail=(tail+1)%maxn;
q[tail]=x;
Instack[x]=1;
}
void pop()
{
Instack[q[top]]=0;
top=(top+1)%maxn;
}
int front()
{
return q[top];
}
}Q;
int pred[maxn];
int dis[maxn];
bool SPFA()
{
Q.Init();
for (int i=1;i<=T;i++) dis[i]=inf;
dis[S]=0;
Q.push(S);
while (!Q.empty())
{
int x=Q.front();
Q.pop();
if (x==T) continue;
for (int i=head[x];i;i=nxt[i]) if (F[i^1] && dis[E[i]]>dis[x]+D[i])
{
dis[E[i]]=dis[x]+D[i];
pred[E[i]]=i;
if (!Q.Instack[E[i]])
Q.push(E[i]);
}
}
return dis[T]!=inf;
}
int MinCostFlow()
{
int res=0;
while (SPFA())
{
int flow=inf;
for (int i=T;i!=S;i=E[pred[i]^1])
flow=min(flow,F[pred[i]^1]);
res+=flow;
for (int i=T;i!=S;i=E[pred[i]^1])
F[pred[i]]+=flow,
F[pred[i]^1]-=flow;
}
return res;
}
Splay
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int maxn=500010,inf=~0U>>1;
using namespace std;
struct Node
{
Node *c[2],*p;
int size;
int v,sum;
int lmax,rmax,vmax;
bool tag_same,tag_rev;
int samev;
bool w() {return p->c[1]==this;}
}*root,*Null;
namespace Memory
{
Node Mem[maxn];
Node *Stack[maxn];
int top;
void Memory_Init() {for (int i=0;i<maxn;i++) Stack[i]=&Mem[i];top=maxn-1;}
void Delete_Node(Node *t) {Stack[++top]=t;}
Node* New_Node() {return Stack[top--];}
};
struct Splay_Tree
{
#define ls x->c[0]
#define rs x->c[1]
void Update(Node *x)
{
if (x==Null) return;
x->sum=ls->sum+rs->sum+x->v;
x->size=ls->size+rs->size+1;
int L_rmax=max(ls->rmax,0),R_lmax=max(rs->lmax,0);
x->lmax=max(ls->lmax,ls->sum+x->v+R_lmax);
x->rmax=max(rs->rmax,rs->sum+x->v+L_rmax);
x->vmax=max(ls->vmax,rs->vmax);
x->vmax=max(x->vmax,L_rmax+x->v+R_lmax);
}
void Update_Same(Node *x,int samev)
{
if (x==Null) return;
x->v=samev;
x->sum=x->size*samev;
x->lmax=x->rmax=x->vmax=max(x->sum,samev);
x->samev=samev;
x->tag_same=1;
}
void Update_Rev(Node *x)
{
if (x==Null) return;
swap(ls,rs);
swap(x->lmax,x->rmax);
x->tag_rev^=1;
}
void Push_Down(Node *x)
{
if (x->tag_same)
{
Update_Same(ls,x->samev);
Update_Same(rs,x->samev);
x->tag_same=0;
x->samev=0;
}
if (x->tag_rev)
{
Update_Rev(ls);
Update_Rev(rs);
x->tag_rev=0;
}
}
void Rotate(Node *x)
{
Node *p=x->p;
Push_Down(p);Push_Down(x);
bool w=x->w();
p->p->c[p->w()]=x;
x->p=p->p;p->c[w]=x->c[!w];
x->c[!w]->p=p;
x->c[!w]=p;p->p=x;
Update(p);
if (p==root) root=x;
}
void Splay(Node *x,Node *head)
{
if (x==Null) return;
Push_Down(x);
while (x->p!=head)
if (x->p->p==head) Rotate(x);
else if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
else Rotate(x),Rotate(x);
Update(x);
}
Node* Select(int kth)
{
Node *x=root;
while (kth)
{
Push_Down(x);
int lsize=ls->size;
if (lsize+1==kth) return x;
if (kth>lsize) kth-=lsize+1,x=rs;
else x=ls;
}
return x;
}
Node* Get_Seq(int l,int r)
{
if (l==1 && r==root->size) return root;
if (l==1 && r< root->size) {Splay(Select(r+1),Null);return root->c[0];}
if (l> 1 && r==root->size) {Splay(Select(l-1),Null);return root->c[1];}
Splay(Select(l-1),Null);
Splay(Select(r+1),root);
return root->c[1]->c[0];
}
void Mark_Same(Node *x,int samev)
{
Update_Same(x,samev);
Splay(x,Null);
}
void Mark_Rev(Node *x)
{
Update_Rev(x);
Splay(x,Null);
}
Node* New_Node(int v)
{
Node *x=Memory::New_Node();
x->v=v;
x->samev=x->tag_same=x->tag_rev=0;
return x;
}
Node* Make_Tree(int *a,int l,int r)
{
if (l>r) return Null;
int mid=(l+r)>>1;
Node *x=New_Node(a[mid]);
ls=Make_Tree(a,l,mid-1);
rs=Make_Tree(a,mid+1,r);
if (ls!=Null) ls->p=x;
if (rs!=Null) rs->p=x;
Update(x);
return x;
}
Splay_Tree()
{
Memory::Memory_Init();
Null=Memory::New_Node();
Null->v=Null->sum=Null->size=Null->samev=0;
Null->tag_same=Null->tag_rev=0;
Null->lmax=Null->rmax=Null->vmax=-inf;
Null->p=Null->c[0]=Null->c[1]=NULL;
root=Null;
}
void Insert(int *a,int posi,int tot)
{
Node *x=Make_Tree(a,1,tot);
if (root==Null) root=x,root->p=Null,Null->c[0]=root;
else if (posi==root->size) {
Splay(Select(root->size),Null);
root->c[1]=x;
x->p=root;
Update(root);
} else if (posi==0) {
Splay(Select(1),Null);
root->c[0]=x;
x->p=root;
Update(root);
} else {
Splay(Select(posi),Null);
Splay(Select(posi+1),root);
root->c[1]->c[0]=x;
x->p=root->c[1];
Splay(x,Null);
}
}
void Delete_DFS(Node *x)
{
if (ls!=Null) Delete_DFS(ls);
if (rs!=Null) Delete_DFS(rs);
Memory::Delete_Node(x);
}
void Delete(int posi,int tot)
{
Node *x=Get_Seq(posi,posi+tot-1);
if (x==root) root=Null;
else x->p->c[x->w()]=Null,Splay(x->p,Null);
Delete_DFS(x);
}
void Make_Same(int posi,int tot,int c)
{
Node *x=Get_Seq(posi,posi+tot-1);
Mark_Same(x,c);
Splay(x,Null);
}
void Make_Rev(int posi,int tot)
{
Node *x=Get_Seq(posi,posi+tot-1);
Mark_Rev(x);
Splay(x,Null);
}
void Get_Sum(int posi,int tot)
{
Node *x=Get_Seq(posi,posi+tot-1);
printf("%d\n",x->sum);
Splay(x,Null);
}
void Max_Sum()
{
printf("%d\n",(root==Null)?0:root->vmax);
}
void Print(Node *x)
{
if (x==Null) {if (x==root) printf("\n");return;}
Push_Down(x);
Print(ls);
printf("%d ",x->v);
Print(rs);
if (x==root) printf("\n");
}
}T;
int a[maxn];
char ctr[20];
int n,m;
inline void read(int &x)
{
char ch;
int flag=0;
while (((ch=getchar())<'0' || ch>'9') && ch!='-');
if (ch=='-') flag=-1,x=0;
else flag=1,x=ch-'0';
while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';
x=x*flag;
}
int main()
{
read(n),read(m);
for (int i=1;i<=n;i++) read(a[i]);
T.Insert(a,0,n);
for (int i=1;i<=m;i++)
{
scanf("%s",ctr+1);
int tot,posi,c;
if (ctr[1]=='I') {read(posi),read(tot);for (int i=1;i<=tot;i++) read(a[i]);T.Insert(a,posi,tot);}
else if (ctr[1]=='D') {read(posi),read(tot);T.Delete(posi,tot);}
else if (ctr[1]=='R') {read(posi),read(tot);T.Make_Rev(posi,tot);}
else if (ctr[1]=='G') {read(posi),read(tot);T.Get_Sum(posi,tot);}
else if (ctr[3]=='K') {read(posi),read(tot),read(c);T.Make_Same(posi,tot,c);}
else T.Max_Sum();
//T.Print(root);
}
return 0;
}
LCT
struct LCT
{
struct Node
{
Node *c[2],*p,*lcp,*maxv;
int v;
int tag_rev;
int w() {return p->c[1]==this;}
}*Null,*ND[maxn],*ED[maxm];
#define ls x->c[0]
#define rs x->c[1]
void Update(Node *x)
{
if (x==Null) return;
x->maxv=x;
if (ls->maxv->v>x->maxv->v) x->maxv=ls->maxv;
if (rs->maxv->v>x->maxv->v) x->maxv=rs->maxv;
}
void Mark_Rev(Node *x)
{
swap(ls,rs);
x->tag_rev^=1;
}
void Push_Down(Node *x)
{
if (!x->tag_rev) return;
Mark_Rev(ls);
Mark_Rev(rs);
x->tag_rev=0;
}
void Rotate(Node *x)
{
Node *p=x->p;
int w=x->w();
Push_Down(p);Push_Down(x);
x->lcp=p->lcp;p->lcp=Null;
p->p->c[p->w()]=x;x->c[!w]->p=p;
x->p=p->p;p->c[w]=x->c[!w];
x->c[!w]=p;p->p=x;
Update(p);
}
void Splay(Node *x)
{
if (x==Null) return;
Push_Down(x);
while (x->p!=Null)
{
if (x->p->p==Null) {Rotate(x);break;}
if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
else Rotate(x),Rotate(x);
}
Update(x);
}
void Access(Node *x)
{
Node *v=Null,*pre=x;
while (x!=Null)
{
Splay(x);
rs->lcp=x;
rs->p=Null;
rs=v;
v->p=x;
v->lcp=Null;
Update(x);
v=x;x=x->lcp;
}
Splay(pre);
}
Node* Find_Root(Node *x)
{
Access(x);
while (ls!=Null) Push_Down(x),x=ls;
Splay(x);
return x;
}
void Set_Root(Node *x)
{
Access(x);
Mark_Rev(x);
}
Node* Prev(Node *x)
{
Splay(x);
if (rs==Null) return Null;
Push_Down(x);x=rs;
while (ls!=Null) Push_Down(x),x=ls;
Splay(x);
return x;
}
void Link(Node *x,Node *v)
{
Set_Root(x);
x->lcp=v;
Access(x);
}
void Cut(Node *x)
{
Access(x);
ls->p=Null;
ls=Null;
Update(x);
}
void Init(int n,int m)
{
for (int i=0;i<=n;i++) ND[i]=new Node;
for (int i=1;i<=m;i++) ED[i]=new Node;
Null=ND[0];
for (int i=0;i<=n;i++) ND[i]->c[0]=ND[i]->c[1]=ND[i]->p=ND[i]->lcp=ND[i]->maxv=Null,ND[i]->v=ND[i]->tag_rev=0;
for (int i=1;i<=m;i++) ED[i]->c[0]=ED[i]->c[1]=ED[i]->p=ED[i]->lcp=Null,ED[i]->maxv=ED[i],ED[i]->v=ED[i]->tag_rev=0;
}
void Link(int x,int y,int e)
{
Link(ND[x],ED[e]);
Link(ED[e],ND[y]);
}
bool Connected(int x,int y) {return Find_Root(ND[x])==Find_Root(ND[y]);}
Node* Max_Edge(Node *x,Node *y)
{
Set_Root(x);
Access(y);
return y->maxv;
}
void Cut_MaxEdge(int x,int y)
{
Node *e=Max_Edge(ND[x],ND[y]);
Cut(Prev(e)),Cut(e);
}
int Max_Edge_V(int x,int y) {return Max_Edge(ND[x],ND[y])->v;}
#undef ls
#undef rs
}T;