1. The violence

1. The binary

In the case where the graph of the function is monotonous. Dichotomous answer, when the problem is monotone in the interval can be directly dichotomous.

bool pd(a){}
/ / integer domain
ll l,r,ans;
while(l<=r){
    ll mid=l+r>>1
    if(pd(mid)) ans=mid,l=mid+1;
    else r=mid- 1;
}
/ / real number domain
long double l,r,ans;
while(r-l>eps){
    long double mid=(l+r)/2;
    if(pd(mid)) r=mid;
    else l=mid;
}
Copy the code

2. The three points

In the case of an inflection point on the graph of the function. Three points of answer, when in the interval of the increase and then decrease or decrease and then increase.

bool pd(a){}
/ / integer domain
ll l,r,ans;
while(l+10<r){
    ll lm=l+(r-l)/3,rm=r-(r-l)/3;
    if(pd(lm)>=pd(rm)) r=rm;
    else l=lm;
}
for(inti=l; i<=r; i++) ans=max(ans,pd(i))/ / real number domain
long double l,r,ans;
while(r-l>eps){
    long double lm=l+(r-l)/3,rm=r-(r-l)/3;
    if(pd(lm)>=pd(rm)) r=rm;
    else l=lm;
}
ans=l;
Copy the code

3. The block

With the square root of complexity, all data is divided into square root blocks, and operations on the same block can be condensed into one.

Block nine chapters

void init(a){
    blo=sqrt(n);
    for(int i=1; i<=n; i++) block[i]=(i- 1)/blo+1;
}
void update(ll l,ll r,ll w){
    for(inti=l; i<=min(block[l]*blo,r); i++) f[i]+=w;if(block[l]! =block[r])for(int i=(block[r]- 1)*blo+1; i<=r; i++) f[i]+=w;for(int i=bolck[l]+1; i<=block[r]- 1; i++) F[i]+=w; }Copy the code

4. Team

Offline interval inquiry, after the optimization of the left and right Pointers to achieve O(nn)O(n\ SQRT {n})O(nn). Notice that when you add, you add, and when you subtract, you subtract.

ll n,m,block,res,k;
ll a[manx],b[manx],c[manx],L[manx],R[manx],ans[manx];
struct query{
    ll l,r,id;
    bool operator < (const query & b){
        if(l/block==b.l/block) return r/block<b.r/block;
        return l/block<b.l/block;
    }
}q[manx];
void add(ll x,ll w){
    while(x<=n) c[x]+=w, x+=(x&(-x));
}
ll query(ll x){
    ll cnt=0;
    while(x) cnt+=c[x],x-=(x&(-x));
    return cnt;
}
void add(ll x){
    ll cnt=query(R[x])-query(L[x]);
    res+=cnt;
    add(a[x], 1);
  // cout<<"add:"<
}
void del(ll x){
    add(a[x], - 1);
    ll cnt=query(R[x])-query(L[x]);
    res-=cnt;
  // cout<<"del:"<
}
void mo(a){
    ll l=1,r=0;
    for(int i=1; i<=m; i++){ ll ql=q[i].l,qr=q[i].r;while(l<ql) del(l++);
        while(l>ql) add(--l);
        while(r<qr) add(++r);
        while(r>qr) del(r--); ans[q[i].id]=res; }}int main(a){
    n=read(),m=read(),k=read(); block=sqrt(n);
    for(int i=1; i<=n; i++){ a[i]=read(); b[i]=a[i]; } sort(b+1,b+1+n);
    ll sz=unique(b+1,b+1+n)-b- 1;
    for(int i=1; i<=n; i++){ L[i]=lower_bound(b+1,b+1+sz,a[i]-k)-b- 1;
        R[i]=upper_bound(b+1,b+1+sz,a[i]+k)-b- 1;
        a[i]=lower_bound(b+1,b+1+sz,a[i])-b;
    }
    for(int i=1; i<=m; i++){ q[i].l=read(),q[i].r=read(),q[i].id=i; } sort(q+1,q+1+m);
    mo();
    for(int i=1; i<=m; i++){cout<<ans[i]<<endl;
    }
    return 0;
}
Copy the code

5. SG function

The nature of winning points and losing points:

  • All endpoints are fail-safe
  • There is at least one way to enter a losing point from any winning point
  • No matter how to operate, from the losing point can only enter the winning point.
//f[N]: a method that can change the current state. N is the type of the method. F [N] should be preprocessed before getSG
//SG[]: indicates the SG function value from 0 to n
//S[]: is the set of x subsequent states
ll f[N],SG[MAXN],S[MAXN];
void  getSG(int n){
    int i,j;
    memset(SG,0.sizeof(SG));
    // Since SG[0] is always equal to 0, I starts at 1
    for(i = 1; i <= n; i++){
        // The subsequent set of the previous state is reset each time
        memset(S,0.sizeof(S));
        for(j = 0; f[j] <= i && j <= N; j++)
            S[SG[i-f[j]]] = 1;  // Mark the SG function value of the subsequent state
        for(j = 0;; j++) if(! S[j]){// Query the minimum non-zero SG value in the current successor state
            SG[i] = j;
            break; }}}Copy the code

2. Data structure

1. The monotonous stack

Monotone stack is used to find the first element on the left (right) side that is larger (smaller) than itself. The elements in the stack are monotone. And, of course, you can use this idea to figure out the first one on the left that’s not a multiple of itself or something like that. The essence of an algorithm is the idea.

for(int i=1; i<=n; i++){ l[i]=i- 1;
	while(l[i]&&a[l[i]]%a[i]==0) l[i]=l[l[i]];
}
Copy the code

1. Find that the first person on the left is greater than you

for(int i=1; i<=n; i++){while(top&&a[s[top]]<=a[i]) --top;
	if(! top) lma[i]=0;
    else lma[i]=s[top];
    s[++top]=i;
}
Copy the code

2. Find that the first one on the right is greater than you

for(inti=n; i>=1; i--){while(top&&a[s[top]]<=a[i]) --top;
	if(! top) rma[i]=n+1;
    else rma[i]=s[top];
    s[++top]=i;
}
Copy the code

2. Monotonous queues

The maximum (minimum) value or difference of the maintenance interval. How is the difference implemented? The elements maintained by the queue are monotonous, so two queues are used to maintain the maximum and minimum values, and the element difference between the two queue heads is the difference between the maximum and minimum values.

// The window length is k
vector<ll>ans
ll q[N],a[N];
ll h=1,t=0,k; 
for(int i=1; i<=n; i++){while(h<=t&&q[h]<(i-k+1)) ++h;
    while(h<=t&&a[q[t]]<=a[i]) --t;  A [q[t]]>=a[I
    q[++t]=i; 
    if(i>=k) ans.push_back(q[h]);
}
Copy the code

Table 3. ST

F [I][j] maintenance of the ith element beginning of the interval length of 2j f[I][j] maintenance of the ith element beginning of the interval length of 2j f[I][j] maintenance of the ith element beginning of the interval length of 2j f[I][j] maintenance of the ith element beginning of the interval length of 2j is obvious, f[I][0] is the current element obvious, F [I][0] = f[I][0] = f[I][0] = f[I][0] = f F [I] [j] = Max (f [I] [j – 1], [I + 2 j – 1] f [j] – 1) f [I] [j] = Max (f [1], [I] f [I + 2 ^ {1} j] [1]) f [I] [j] = Max (f [j – 1], [I] f [I + 2 j – 1] [j] – 1) For the processing of a query, we can find a multiple k of 2 that is not greater than the interval length: x+2k−1=r We can find x: x+2 ^{k} -1 =r We can find x: X + 2 k – 1 = r and x second f [l] [k] and [r] + 1-2 k f [k] can cover the second f/l, r interval [l] [k] and [f r + 1 2 ^ {k}] [k] can cover second f/l, r interval [l] [k] and [r] + 1-2 k f [k] can cover [l, r] interval

//f[I][0] is itself.
// The relaxation interval
ll f[manx][25];
void init(a){
    for(int j=1; j<=21; j++)for(int i=1; i+(1<<j)- 1<=n; i++) f[i][j]=max(f[i][j- 1],f[i+(1<<(j- 1))][j- 1]);    
}
// query interval
ll query(ll l,ll r){
    ll k=log2(r-l+1);
    return max(f[l][k],f[r+1- (1<<k)][k]);
}        
Copy the code

4. Check and set

Connect two nodes.

ll f[manx];
void init(ll n){
    for(int i=1; i<=n; i++) f[i]=i; }ll find(ll x){
    returnf[x]==x? x:f[x]=find(f[x]);
}

// select * from set
ll find(ll x)
{
	if(x ! = f[x]) { ll t = f[x]; f[x] =find(f[x]);
		w[x] += w[t];
	}
	return f[x];
}
Copy the code

5. Tree arrays

The core is the idea of binary and prefix sum, to maintain the prefix sum of 1 ~ I, too complex operations can be converted to line tree operation.

Refer to team Mo in the violence sectionCopy the code

6. Segment tree

He is the only one who knows.

ll s[manx],laz[manx],a[manx];
inline void up(ll k){
    s[k]=s[k<<1]+s[k<<1|1];
}
inline void down(ll k,ll len){
    laz[k<<1]+=laz[k],laz[k<<1|1]+=laz[k];
    s[k<<l]+=laz[k]*(len-len>>1),s[k<<1|1]+=laz[k]*(len>>1);
    laz[k]=0;
}
/ / build (1, 1, n);
inline void build(ll k,ll l,ll r){
    if(l==r){
        s[l]=a[l],laz[l]=0; return;
    }
    ll mid=l+r>>1;
    build(k<<1,l,mid); build(k<<1|1,mid+1,r);
    up(k);
}
// interval query
inline ll query(ll k,ll l,ll r,ll ql,ll qr){
    if(l>=ql&&r<=qr) return s[k];
    if(laz[k]) down(k,r-l+1);
    ll mid=l+r>>1,ans=0;
    if(mid>=ql) ans+=query(k<<1,l,mid,ql,qr);
    if(mid<qr) ans+=query(k<<1|1,mid+1,r,ql,qr);
}
// Interval update
inline void update(ll k,ll l,ll r,ll ql,ll qr,ll w){
    if(l>=ql&&r<=qr){
        laz[k]+=w; s[k]+=(r-l+1)*w; return;
    }
    if(laz[k]) down(k,r-l+1);
    ll mid=l+r>>1,ans=0;
    if(mid>=ql) update(k<<1,l,mid,ql,qr,w);
    if(mid<qr) update(k<<1|1,mid+1,r,ql,qr,w);
    up(k);
}

Copy the code

7. Tree chain splitting

(diameter of line segment tree maintenance tree) dfS1 traverses once: 1. Parent node F of each node; 2. The depth d; 3. Subtree size sz; 1. The parent node of each node f; 2. The depth d; 3. Subtree size sz; 1. The parent node of each node f; 2. The depth d; 3. Subtree size sz; 1. The top of the chain where each node is located; 2. 2. DFS sequence ID of each node; 3. Each DFS sequence represents the node RK; 1. The top of the chain where each node is located; 2. DFS sequence ID of each node; 3. Each DFS sequence represents the node RK; 1. The top of the chain where each node is located; 2. DFS sequence ID of each node; 3. Each DFS sequence represents the node RK; Pay attention to enter the heavy son first to ensure the continuity of the interval where the heavy chain is located, and the rest is the core of other chains. The core is to use TOP acceleration and DFS sequence to convert the nodes of the same chain into the continuous interval for line segment tree operation. Point weights can be operated directly. For edge weights, since each node has only one parent node, this operation converts the weights of U −> VU -> VU −> V into the weights of VVV. Then the sum of the path weights of u to V is the sum of the weights of the second point to V on the path from u to V.

vector<pair<ll,ll> >g[manx];
ll n,m,cnt;
ll d[manx],f[manx],sz[manx],son[manx],dp[manx];
ll top[manx];//,id[manx],rk[manx];
struct node{
    ll l,r,w;
}a[manx<<2];
inline void dfs1(ll u,ll pre){
    d[u]=d[pre]+1,f[u]=pre,sz[u]=1;
    for(auto pi: g[u]){
        ll v=pi.fi,w=pi.se;
        if(v==pre) continue;
        dp[v]=dp[u]+w;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[son[u]]<sz[v]) son[u]=v; }}inline void dfs2(ll u,ll tp){
    top[u]=tp;//,id[u]=++cnt,rk[cnt]=u;
    if(! son[u])return;
    dfs2(son[u],tp);
    for(auto pi: g[u]){
        ll v=pi.fi;
        if(v! =son[u]&&v! =f[u])dfs2(v,v); }}inline ll lca(ll x,ll y){
    while(top[x]! =top[y]){if(d[top[x]]<d[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    returnd[x]<d[y]? x:y; }inline ll dis(ll x,ll y){
    return dp[x]+dp[y]2 -*dp[lca(x,y)];
}
inline node compare(node a,node b){
    return dis(a.l,a.r)>dis(b.l,b.r)? a:b; }inline node up(node a,node b){
    node ans1=compare((node){a.l,b.l,0},(node){a.r,b.l,0});
    node ans2=compare((node){a.l,b.r,0},(node){a.r,b.r,0});
    node ans =compare(ans1,ans2);
    ans.w=dis(ans.l,ans.r);
    if(a.w>ans.w) ans=a;
    if(b.w>ans.w) ans=b;
    return ans;
}
inline void build(ll k,ll l,ll r){
    if(l==r){
        a[k].l=a[k].r=l; a[k].w=0; return;
    }
    ll mid=l+r>>1;
    build(k<<1,l,mid); build(k<<1|1,mid+1,r);
    a[k]=up(a[k<<1],a[k<<1|1]);
}
inline node query(ll k,ll l,ll r,ll L,ll R){
    if(l>=L&&r<=R) return a[k];
    ll mid=l+r>>1;
    ll ql=0,qr=0; node ans1,ans2;
    if(mid>=L) ans1=query(k<<1,l,mid,L,R),++ql;
    if(R>mid) ans2=query(k<<1|1,mid+1,r,L,R),++qr;
    return (ql&qr)?up(ans1,ans2):(ql? ans1:ans2); }Copy the code

8. Block lists

Its algorithm complexity n*(n^0.5), can be achieved in a very short time to quickly insert, delete and find the string.

#inlcude< ext / rope >
using namespace __gnu_cxx;
rope test;

test.push_back(x);// Add x at the end

test.insert(pos,x);// Insert x at pos

test.erase(pos,x);// Delete x from pos

test.copy(pos,len,x);// replace with x from pos to pos+len

test.replace(pos,x);// change from pos to x

test.substr(pos,x);// Start with x pos

test.at(x)/[x];// Access element x
Copy the code

3. The number theory

He is the only one who knows.

1. Euclid

int gcd(int a,int b){
	return b==0? a:gcd(b,a%b); }int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
Copy the code

2. Extend Euclid

Bezou’s theorem:

That is, if a and b are integers, there must be integers x and y such that Ax +by= GCD (a,b).

In particular: x = y1, y = x1 – a/b *y1

The inverse element is limited to finding the linear congruence a * x mod b = 1 can be converted to Ax + by = 1

ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){ x=1,y=0; returna; } ll gcd=exgcd(b,a%b,y,x); y-=a/b*x;return gcd;
}
ll inv(ll a,ll b,ll &x,ll &y){
    ll gcd=exgcd(a,b,x,y);
    if(gcd! =1) return - 1;
    else return (x+b)%b;
}
Copy the code

3. Special numbers

1. Cattelan number


f [ n ] = C 2 n n n + 1 = C 2 n n – C 2 n n – 1 f[n]=\frac{C^{n}_{2n}}{n+1}={C^{n}_{2n}}-{C^{n-1}_{2n}}

1, 1, 2, 5, 14, 42, 132…… Cases are:

  1. NNN Number of triangulation schemes of a side shape
  2. Number of stack in and out sequences/number of legal schemes for left and right parentheses/number of 010101 numbers filled
  3. NNN number of binary tree structures of nodes
  4. From (1, 1) to (n, n) (1, 1) to (n, n) (1, 1) to (n, n), can be right or go up at a time, for no more than y = y = y = x number of the line solution.
  5. NNN The multiplication order of the continued product of numbers
dp[0] =0,dp[1] =1;
for(int i=2; i<=n; i++) dp[i]=dp[i- 1] * (4*i2 -)/(i+1)
Copy the code

2. Super Cattelan number/Large Schroeder number

(n + 1) fn + 1 = fn (6 n – 3) – (n – 2) fn – 1 f_ (n + 1) + 1} {n = 6 n – (3) f_n – f_ (n – 2) {}, n – 1 (n + 1) fn + 1 = fn (6 n – 3) – (n – 2) fn – 1 the number of big schroeder, before a few is 1, 2, 6, 22, 90, 394 1806 8558 41586 206098…. The first items of the super Cattelan sequence are 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049…. You can see that the large Schroeder number is twice as large as the super Cattelan number except for the first term.

Cases are:

  1. NNN Number of arbitrary subdivision schemes of a boundary shape.
  2. Number of valid schemes for open parentheses + numbers
  3. From (1, 1) to (n, n) (1, 1) to (n, n) (1, 1) to (n, n), each time to the right, up, walking on the right, for no more than y = y = y = x number of the line solution.
inv[0]=inv[1]=f[0]=f[1] = 1;
for(int i=2; i<=n; ++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(int i=2; i<=n2 -; ++i) f[i]=((6ll*i- 3)*f[i- 1]-(i-2ll)*f[i2 -])%mod*inv[i+1]%mod
Copy the code

4. Matrix multiplication

struct node{
    ll x[N][N];
    node(){ memset(x,0.sizeof(x)); }inline void init(a){ for(int i=0; i<=n; i++) x[i][i]=1; }}; nodeoperator* (const node &a, const node &b){
    node res;
    for(int k=0; k<=n; k++)for(int i=0; i<=n; i++)for(int j=0; j<=n; j++) res.x[i][j]=(res.x[i][j]+a.x[i][k]*b.x[k][j])%mod;return res;
}
node fast(node a, ll b){
    node ans; ans.init();
    while(b){
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
Copy the code

5. Lucas theorem


L u c a s ( n . m . p ) = C m % p n % p x L u c a s ( n / p . m / p . p ) Lucas (n, m, p) = C ^ {n \ % p} _ {m \ % p} by Lucas (n/p, m/p, p) %, p

L u c a s ( n . 0 . p ) = 1 Lucas(n,0,p)=1

Deal with the modular problem of combination number.

ll Inv(ll x,ll p){return qp(x,p2 -,p); }ll Cal(ll n,ll m,ll p){
    if(m>n) return 0;
    ll ans=1;
    for(int i=1; i<=m; ++i)ans=ans*Inv(i,p)%p*(n-i+1)%p;
    return ans%p;
}
ll Lucas(ll n,ll m,ll p){
    if(! m)return 1;
    return Cal(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}
Copy the code

6. Multiplicative inverse


Suppose you have p = k i + r : In the sense of taking a mold: k i + r m o d p = = 0 on i – 1 As well as r – 1 : i – 1 = – k ∗ r – 1 Substitution: i – 1 = ( – ( p / i ) ∗ ( p % i ) – 1 ) % p There are: i – 1 = ( p – ( p / i ) ∗ ( p % i ) – 1 ) % p Among them i n v [ 1 ] = 1 Suppose there is p = ki + r: \ \ modulus sense: ki mod p + r = = 0 \ \ on the I ^ {1} and r ^ {1} : I ^ {1} = – k * r ^ {1} \ \ substitution: I ^ {1} = (- (p/I) * (I) p \ % ^ {1}) \ % p \ \ : I ^ {1} = (p – (p/I) * (I) p \ % ^ {1}) \ % p \ \ the inv [1] = 1 \ \ 
inv[1] =1;
for(int i=2; i<=n; i++) inv[i]=((p-p/i)*inv[p%i])%p;Copy the code

7. Divide evenly

void gets(ll n){
    ll ans=0;
    for(ll l=1,r; l<=n; l=r+1){
        r=n/(n/l);
        ans+=(r-l+1)*(n/l);
    }
    return ans;
}
Copy the code

8. Euler functions

// Find the Euler function of a number directly
ll euler(ll n){
    ll ans=n;
    for(ll i=2; i*i<=n; i++){if(n%i==0){
            ans-=ans/i;
            while(n%i==0) n/=i; }}if(n>1) ans-=ans/n;
    return ans;
}
/ / erichsen screen
ll phi[manx];
void euler(ll n){
    for(int i=1; i<=n; i++) phi[i]=i;for(int i=2; i<=n; i++){if(phi[i]==i){
            for(int j=i;j<=n;j+=i)
                phi[j]-=phi[j]/i;
        }
    }
}
/ / euler's screen
ll vis[manx],phi[manx],prime[manx];
ll cnt;
void euler(ll n){
    phi[1] =1;
    for(int i=2; i<=n; i++){if(! vis[i]) prime[++cnt]=i,phi[i]=i- 1;
        for(int j=1; j<=cnt&&i*prime[j]<=n; j++){ vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];  //
                break; 
            }
            elsephi[i*prime[j]]=phi[i]*phi[prime[j]]; }}}Copy the code

9. Linear sieve

/ / euler's screen
ll vis[manx],prime[manx];
ll cnt;
void euler(ll n){
    for(int i=2; i<=n; i++){if(! vis[i]) prime[++cnt]=i;for(int j=1; j<=cnt&&i*prime[j]<=n; j++){ vis[i*prime[j]]=1;
            if(i%prime[j]==0) break; }}}Copy the code

4. The string

1.Hash

  1. String length. Hash: Records the hash value from 1 to I. Pw: records base^ I
  2. Query: indicates the hash value of the string [L,r], whose type is the hash number
  3. Same: Checks whether the string in [lu,ru] of string u is the same as the string in [lv,rv] of string V
struct Hash{
    int base[4],mod[4];
    int tot,hash[4][manx],pw[4][manx]; 
    Hash() {
        tot=0;
        for(int i=1; i<=3; i++) pw[i][0] =1;
        base[1] =233; base[2] =19260817; base[3] =20030714;
        mod[1] =1e9+7; mod[2] =1e9+9; mod[3] =998244353;
    }
    void init(a) { tot=0; }void insert(int c) {
        tot++;
        for(int i=1; i<=3; i++) hash[i][tot]=(1LL*hash[i][tot- 1]*base[i]+c)%mod[i];
        for(int i=1; i<=3; i++) pw[i][tot]=(1LL*pw[i][tot- 1]*base[i])%mod[i];
    }
    int query(int l,int r,int type) { 
        return (hash[type][r]-(1LL*hash[type][l- 1]*pw[type][r-l+1]%mod[type])+mod[type])%mod[type];
    }
    friend bool same(Hash &u,int lu,int ru,Hash &v,int lv,int rv) { 
        if(ru-lu! =rv-lv)return false;
        for(int i=1; i<=3; i++)if(u.query(lu,ru,i)! =v.query(lv,rv,i))return false;
        return true;
    }
}hash;
Copy the code

2.KMP

1. The next array

  1. next[0]= -1 / 0
  2. Next [I] represents the length of the longest common suffix for the first I characters of the pattern string
  3. When a mismatch occurs, the pattern string moves j-next[j] units to the right, as j=next[j], because the first j characters have the longest common prefix and suffix next[j].
  4. Set len to n-next[n]
  5. If next[n] is not 0 and n is a multiple of len, then the minimum loop section of the string is n-next[n] with n/len;
  6. Otherwise, the string must add len – n%len characters to form a loop string. (n%len where the suffix is part of the loop string)
// This template moves the string one bit to the right as a whole
// next[I] indicates the length of the longest common suffix for the first I characters of the pattern string
void getnexts(string s){
    ll i=0,j=- 1,m=s.size();
    nexts[i]=j;
    while(i<m){
        if(j==- 1||s[i]==s[j]) nexts[++i]=++j;
        elsej=nexts[j]; }}Copy the code

2. KMP matching process

ll kmp(string s,string p){
    getsnexts();
    ll i=0,j=0,n=s.size(),m=p.size();
    while(i<n&&j<m){
        if(j==- 1||s[i]==p[j]) ++i,++j;
        else j=nexts[j];
    }
    if(j==m) return i-j;
    return - 1;
}

Copy the code

3.Manacher

Mx is the rightmost palindrome reached, id is the midpoint of mx, maxpoint is the midpoint of the longest palindrome, maxlen is the length of the longest palindrome, and the P array maintains the length of the palindrome at I.

In particular, p[I]== I indicates that the beginning of the palindrome string is the beginning of the string, and I +p[I]==len(the length of the string) indicates that the end of the palindrome string is the end of the string.

string Manacher(string s1){
    string s="$#";
    for(int i=0; i<s1.size(); i++) s+=s1[i],s+="#";
    vector<int>p(s.size(),0); 
    int id=0,mx=0,maxpoint=0,maxlen=0; 
    for(int i=1; i<s.size(); i++){ p[i]=mx>i+p[i]? min(mx-i,p[2*id-i]):1;  
        while(s[i+p[i]]==s[i-p[i]]) ++p[i];  
        if(i+p[i]>mx) id=i,mx=i+p[i]; 
        if(p[i]>maxlen) maxlen=p[i],maxpoint=i; 
    }
    return s1.substr( (maxpoint-maxlen)/2 , maxlen- 1 );  
}
Copy the code

4. Sequential automata

void gets(a){
    int n=s.size();
    for(int i=0; i<26; i++) dp[n][i]=- 1;
    for(int foi=n- 1; i>=0; i--){for(int j=0; j<26; j++) dp[i][j]=dp[i+1][j];
        dp[i][s[i]-'a']=i; }}bool pd(string t){
    int pos=- 1;
    for(int i=0; i<t.size(); i++){ pos=dp[pos+1][t[i]-'a'];
        if(pos==- 1) return false;
    }
    return true;
}
Copy the code

Palindromic automata

/* nexts stores the son node, Num Records the number of substrings ending in the ith character. Len Records the maximum length of substrings ending in the ith character. S is the added string. N is the size of the string
struct PAM{
    ll nexts[manx][26],fail[manx],cnt[manx],num[manx],len[manx],s[manx];
    ll last,n,p;
    int newnode(ll x){ // Create a node
        for(int i=1; i<26; i++) nexts[p][i]=0;
        cnt[p]=0,num[p]=0,len[p]=x;
        return p++;
    }
    void init(a){ / / initialization
        p=0; newnode(0); newnode(- 1);
        last=n=0; fail[0] =1; s[n]=- 1;// Start with a character that is not in the set to reduce the special judgment
    }
    int get_fail(ll x){
        while(s[n-len[x]- 1]! =s[n]) x=fail[x];return  x;
    }
    void add(ll c){
        c-='a'; s[++n]=c;
        int cur=get_fail(last);
        if(! nexts[cur][c]){ ll now=newnode(len[cur]+2);
            fail[now]=nexts[get_fail(fail[cur])][c];
            nexts[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=nexts[cur][c];
        cnt[last]++;
    }
    void count(a){ for(int i=p- 1; i>=0; i--) cnt[fail[i]]+=cnt[i]; }// The father adds the son's CNT, because if fail[v]=u, then u must be a subpalindrome of V!
}pam;
Copy the code

6. AC automata

AC automata is often used to solve multiple string matching/inclusion problems. There are three variations in the way queries can be made:

  1. Tag with an array of vis and, violent jump fail, but the time complexity can be as high as O (∣ text string ∣ ∗ ∣ pattern string ∣) O (| text is strung together, string together | | | * mode) O (∣ text string ∣ ∗ ∣ ∣ pattern string).
  2. After topO, dp delay accumulation is performed.
  3. The FAIL number is used to form the FAIL tree.
vector<ll>g[manx];
ll sz[manx];
void dfs(ll u){
    for(auto v: g[u]){
        dfs(v); sz[u]+=sz[v]; }}ll *query(string s){
	ll u=0,n=s.size(),ans=0;
	for(auto x: s){
		u=ac.trie[u][x-'a'];
		sz[u]++;
	}
	for(int i=0; i<=ac.cnt; i++)if(i! =ac.fail[i]) g[ac.fail[i]].pb(i);
    dfs(0);
    return sz;
}
Copy the code
struct AC{
    ll trie[manx][26],val[manx],fail[manx];
    ll cnt=0;
    void init(a){
        memset(trie[0].0.sizeof(trie[0])); cnt=1;
    }
    void add(string s, ll w){
        ll u=0; ll n=s.size(a);for(int i=0; i<n; i++){ ll v=s[i]-'a';
            if(! trie[u][v]){memset(trie[cnt],0.sizeof(trie[cnt]));
                trie[u][v]=cnt++;
                val[cnt- 1] =0;
            }
            u=trie[u][v];
        }
        val[u]+=w;
    }
    ll query(string s){
        ll u=0,n=s.size(),ans=0;
        for(int i=0; i<n; i++){ ll v=s[i]-'a',w=trie[u][v];
            // Skip fail
            u=trie[u][v];
        }
        return ans;
    }
    void build(a){
        queue<ll>q;
        for(int i=0; i<26; i++)if(trie[0][i]) q.push(trie[0][i]),fail[trie[0][i]]=0;
        while(q.size()){
            ll u=q.front(a); q.pop(a);Val [u]+=val[fail[u]];
            for(int i=0; i<26; i++)if(trie[u][i]) fail[trie[u][i]]=trie[fail[u]][i],q.push(trie[u][i]); 
                // ,val[trie[u][i]]|=val[fail[trie[u][i]]];
                else trie[u][i]=trie[fail[u]][i];
        }
    }
}ac;
Copy the code

5. Dynamic planning

Interval dp

for(int len=1; len<=n; len++)for(int l=1; l+len- 1<=n; l++){int r=l+len- 1;
        for(intk=l; k<r; k++) dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r]+anything)
    }
Copy the code

6. Graph theory

Front skills

Prior to the star

ll head[N],d[N];
bool vis[N];
struct node{
    ll next,v,w;
}a[N];
ll n,m,s,e,k;
void add(ll u,ll v,ll w){
    a[++k].v=v; a[k].next=head[u]; a[k].w=w; head[u]=k;
}
Copy the code

1. The short circuit

1.spfa

Can run negative weight most short-circuited, but unstable, vis array is maintained whether the current node is in the queue.

void spfa(a){
	queue<ll>q;
	for(int i=1; i<=n; i++) d[i]=inf,vis[i]=0;
	q.push(s); vis[s]=1; d[s]=0;
	while(q.size()){
		ll u=q.front(); q.pop();
		vis[u]=0;
		for(inti=head[u]; i; i=a[i].next){ ll v=a[i].v,w=a[i].w;if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				if(! vis[v]) q.push(v),vis[v]=1; }}}}Copy the code

2.dijkstra

More stable, vis array is to maintain the current node is not queued.

priority_queue<pair<ll,ll> >q;
void dij(a){
    for(int i=1; i<=n; i++) d[i]=inf,vis[i]=0;
   	d[s]=0; q.push(mp(0,s));
    while(q.size()){
        ll u=q.top().se; q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(inti=head[u]; i; i=a[i].next){ ll v=a[i].v,w=a[i].w;if(d[v]>d[u]+w){ d[v]=d[u]+w; q.push(mp(-d[v],v)); }}}}Copy the code

3.folyd

Can’t solve the negative weight problem.

for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)for(int j=1; j<=n; j++) d[i][j]=min(d[i][j],d[i][k]+d[k][j]);Copy the code

2. Minimum spanning tree

ll f[manx];
struct node{
    ll u,v,w;
}a[manx];
ll find(ll x){
    returnf[x]==x? x:f[x]=find(f[x]);
}
bool cmp(node x,node y){
    return x.w<y.w;
}
inline void kruskal(a){
    for(int i=1; i<=m; i++){ u=find(a[i].u),v=find(a[i].v);
        if(u==v) continue; 
        ans+=a[i].val;
        a[u]=v;
        total++;
        if(total==n- 1) break; }}Copy the code

3.LCA

The following is the multiplication method, and the tree chain partition method can refer to the data structure of this paper. The lg array is 2^ I, which might mean something a little different than other people’s arrays.

vector<ll>g[manx];
ll lg[manx],d[manx],f[manx][22];
ll n,m,rt;
inline void init(a){
    lg[0] =1;
    for(int i=1; i<=20; i++) lg[i]=lg[i- 1] < <1;
}
void dfs(ll u,ll pre){
    d[u]=d[pre]+1,f[u][0]=pre;
    for(int i=1; lg[i]<=d[u]; i++) f[u][i]=f[f[u][i- 1]][i- 1];
    for(auto v:g[u]){
        if(v==pre) continue;
        dfs(v,u); }}ll lca(ll x,ll y){
    if(d[x]<d[y]) swap(x,y);
    for(int i=20; i>=0; i--)if(d[x]-d[y]>=lg[i]) x=f[x][i];
    if(x==y) return x;
    for(int i=20; i>=0; i--)if(f[x][i]! =f[y][i]) x=f[x][i],y=f[y][i];return f[x][0];
}
Copy the code

4. Tree heuristic merging

/* Recursively light son recursive heavy son Update ans del Light son contribution reserved heavy son contribution time complexity O(nlogn) */
void cal(ll u,ll pre,ll f){
    if(f==1) calnow(a);else if(f==- 1) del(a);for(auto v:g[u]){
        if(v==pre) continue;
        cal(v,u,f); }}void dfs2(ll u,ll pre,ll f){
    for(auto v:g[u]){
        if(v==pre||v==son[u]) continue;
        dfs2(v,u,1);
    }
    if(son[u]) dfs2(son[u],u,0);
    for(auto v:g[u]){
        if(v==pre||v==son[u]) continue;
        cal(v,u,1);
    }
    calnow(a);if(f) del(a); }Copy the code

5.Tarjan

1. Strongly connected component

ll head[manx],dfn[manx],low[manx],ans[manx];
ll out[manx],col[manx],s[manx],in[manx];
bool vis[manx];
ll k=0,ti=0,top=0,cnt=0,n,m;
struct node {
    ll v,next;
}e[mamx*2];
void add(ll u,ll v){
    e[++k].v=v;
    e[k].next=head[u];
    head[u]=k;
}
void tarjan(ll x){
    dfn[x]=low[x]=++ti,vis[x]=1,s[++top]=x;
    for(inti=head[x]; i; i=e[i].next){ ll u=e[i].v;if(! dfn[u])tarjan(u),low[x]=min(low[x],low[u]);
        else if(vis[u]) low[x]=min(low[x],dfn[u]);
    }
    if(low[x]==dfn[x]){
        ++cnt;
        ll y;
        do{
            y=s[top--],vis[y]=0;
            col[y]=cnt;
            ans[cnt]++;
        }while(x!=y);
    }
}
void dosmall(a){
    for(int i=1; i<=n; i++)if(! dfn[i])tarjan(i);
    for(int i=1; i<=n; i++)for(intj=head[i]; j; j=e[j].next)if(col[e[j].v]! =col[i]) ++out[col[i]],++in[col[e[j].v]]; }Copy the code

2. Cut point

The conditions for cutting points are: For root nodes: more than 2 subtrees for non-root nodes: low[v]>= DFN [u]

ll head[manx],dfn[manx],low[manx];
bool vis[manx];
ll n,m,id,cnt,tot,k;
struct node {
    ll v,next;
}e[mamx*2];
void init(a){
    memset(vis,0.sizeof(vis));
    memset(head,0.sizeof(head));
    memset(dfn,0.sizeof(dfn));
    memset(low,0.sizeof(low));
    id=cnt=tot=k=0;
}
void add(ll u,ll v){
    e[++k].v=v;
    e[k].next=head[u];
    head[u]=k;
}
void tarjan(ll u,ll f){
    dfn[u]=low[u]=++id;
    int child=0;
    for(inti=head[u]; i; i=e[i].next){ ll v=e[i].v;if(! dfn[v]){ tarjan(v,u); low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]&&u! =f) vis[u]=1;
            if(u==f) child++;
        }
        low[u]=min(low[u],dfn[v]);
    }
    if(child>=2&&u==f) vis[u]=1; // If it is the root node and has more than one child node
}
int main(a)
{
    int n,u,v;
    char c;
    while(scanf("%d",&n),n){
        init();
        while(scanf("%d",&u),u){
            while(scanf("%d%c",&v,&c)){
                add(u,v),add(v,u);
                if(c=='\n') break; }}for(int i=1; i<=n; i++)if(! dfn[i]) tarjan(i,i);for(int i=1; i<=n; i++)if(vis[i])
                tot++;
        cout<<tot<<endl;
    }
    return 0;
}
Copy the code

3. The bridge

ll low[manx],dfn[manx],head[manx];
ll k,cnt,top,id,bridge;
struct node{
    ll v,next,w;
}a[mamx];
void init(a){
    memset(low,0.sizeof(low));
    memset(dfn,0.sizeof(dfn));
    memset(head,- 1.sizeof(head));
    top=cnt=k=id=0;
    bridge=inf;
}
void add(ll u,ll v,ll w){
    a[k].next=head[u];
    a[k].v=v;
    a[k].w=w;
    head[u]=k++;
}
void tarjan(ll u,ll pre){
    low[u]=dfn[u]=++id;
    for(inti=head[u]; i! =- 1; i=a[i].next){ ll v=a[i].v;if(i==(pre^1)) continue;
        if(! dfn[v]){ tarjan(v,i),low[u]=min(low[u],low[v]);if(dfn[u]<low[v]) bridge=min(bridge,a[i].w);
        }
        elselow[u]=min(low[u],dfn[v]); }}int main(a)
{
    ll n,m,u,v,w;
    while(scanf("%lld%lld",&n,&m),n+m){
        init();
        for(int i=1; i<=m; i++){ u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } ll tarjans=0;
        for(int i=1; i<=n; i++)if(! dfn[i]) tarjan(i,- 1),tarjans++;
        if(tarjans>1) {printf("0\n");
            continue;
        }
        if(bridge==inf) bridge=- 1;
        else if(bridge==0) bridge=1;
        printf("%lld\n",bridge);
    }
    return 0;
}
Copy the code