1 sounds like the minimum value we can get. Why? Is it always true?

When n ≤ 2, we can do nothing.

When n ≥ 3, since , n - 1 isn't a divisor of n, so we can choose it and get 1 as the result.

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  scanf("%d", &n);
  if (n == 2) {
    puts("2");
  } else {
    puts("1");
  }
  return 0;
}

Consider the number of people wearing hats of the same color.

let b_i = n - a_i represent the number of people wearing the same type of hat of i-th person.

Notice that the person wearing the same type of hat must have the same bs. Suppose the number of people having the same b_i be t, there would be exactly kinds of hats with b_i wearers. Therefore, t must be a multiple of b_i. Also this is also sufficient, just give b_i people a new hat color, one bunch at a time.

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n;
pair<int,int> a[maxn];
int Ans[maxn],cnt;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first;
        a[i].first=n-a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    for(int l=1,r=0;l<=n;l=r+1){
        for(r=l;r<n&&a[r+1].first==a[r].first;++r);
        if((r-l+1)%a[l].first){
            cout<<"Impossible"<<endl;
            return 0;
        }
        for(int i=l;i<=r;i+=a[l].first){
            cnt++;
            for(int j=i;j<i+a[l].first;++j)Ans[a[j].second]=cnt;
        }
    }
    cout<<"Possible"<<endl;
    for(int i=1;i<=n;i++)cout<<Ans[i]<<' ';
	return 0;
}

No hint here :)

Let f[i][j] be the ways that there're j bricks of a different color from its left-adjacent brick among bricks numbered 1 to i. Considering whether the i-th brick is of the same color of i - 1-th, we have f[i][j] = f[i - 1][j] + f[i - 1][j - 1](m - 1). f[1][0] = m and the answer is f[n][k].

Also, there is a possibly easier solution. We can first choose the bricks of a different color from its left and then choose a different color to color them, so the answer can be found to be simply .

//quadratic
#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
int n,m,k;
long long f[2005][2005];
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	f[1][0]=m;
	for(int i=1;i<n;++i)
		for(int j=0;j<=k;++j)
			(f[i+1][j]+=f[i][j])%=MOD,
			(f[i+1][j+1]+=f[i][j]*(m-1))%=MOD;
	printf("%d\n",int(f[n][k]));
}

//linear
#include <bits/stdc++.h>
using namespace std;
const int MOD=998244353;
typedef long long ll;
ll fac[2333],rfac[2333];
ll qp(ll a,ll b)
{
	ll x=1; a%=MOD;
	while(b)
	{
		if(b&1) x=x*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return x;
}
int n,m,k;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	fac[0]=1;
	for(int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%MOD;
	rfac[n]=qp(fac[n],MOD-2);
	for(int i=n;i;--i)
		rfac[i-1]=rfac[i]*i%MOD;
	printf("%lld\n",m*qp(m-1,k)%MOD*fac[n-1]%MOD
	*rfac[k]%MOD*rfac[n-1-k]%MOD);
}

Consider the MST of the graph.

Consider the minimum spanning tree formed from the n vertexes, we can find that the distance between two vertexes is the maximum weight of edges in the path between them in the minimum spanning tree (it's clear because of the correctness of Kruskal algorithm).

Take any minimum spanning tree and consider some edge in this spanning tree. If this edge has all special vertexes on its one side, it cannot be the answer. Otherwise, it can always contribute to the answer, since for every special vertex, we can take another special vertex on the other side of this edge. Therefore, answers for all special vertexes are the maximum weight of the edges that have special vertexes on both sides.

Besides implementing this directly, one can also run the Kruskal algorithm and maintain the number of special vertexes of each connected component in the union-find-set. Stop adding new edges when all special vertexes are connected together and the last edge added should be the answer.

#include<bits/stdc++.h>
#define L long long
#define vi vector<int>
#define pb push_back
using namespace std;
int n,m,t,f[100010],p;
bool a[100010];
inline int fa(int i)
{
    return f[i]==i?i:f[i]=fa(f[i]);
}
struct edge
{
    int u,v,w;
    inline void unit()
    {
        u=fa(u);
        v=fa(v);
        if(u!=v)
          {
           if(a[u])
             f[v]=u;
           else
             f[u]=v;
           if(a[u] && a[v])
             p--;
           if(p==1)
             {
              for(int i=1;i<=t;i++)
                printf("%d ",w);
              printf("\n");
              exit(0);
             }
          }
    }
}x[100010];
inline bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int main()
{
    int i,j;
    scanf("%d%d%d",&n,&m,&t);
    p=t;
    for(i=1;i<=t;i++)
      {
       scanf("%d",&j);
       a[j]=1;
      }
    for(i=1;i<=m;i++)
      scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w);
    sort(x+1,x+m+1,cmp);
    for(i=1;i<=n;i++)
      f[i]=i;
    for(i=1;i<=m;i++)
      x[i].unit();
    return 0;
}

How to solve n = 2?

Let , x_max = 2 × 10⁵.

Since x_2i = s_2i - s_2i - 1 = t_2i² - t_2i - 1² ≥ (t_2i - 1 + 1)² - t_2i - 1² = 2t_2i - 1 + 1, so 2t_2i - 1 + 1 ≤ x_max, t_2i - 1 < x_max.

For every , we can precalculate all possible (a, b)s so that x = b² - a²: enumerate all possible a , then for every a enumerate b from small to large starting from a + 1 and stop when b² - a² > x_max, record this (a, b) for x = b² - a². Since , then , its complexity is .

Now, we can try to find a possible s from left to right. Since x_2i - 1 is positive, we need to ensure t_2i - 2 < t_2i - 1. Becuase x_2i = t_2i² - t_2i - 1², we can try all precalculated (a, b)s such that x_2i = b² - a². If we have several choices, we should choose the one that a is minimum possible, because if the current sum is bigger, it will be harder for the remaining number to keep positive.

Bonus: Solve n ≤ 10³, x_2i ≤ 10⁹.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n;
ll sq[100099];
#define S 200000
vector<pii> v[S+55];
int main()
{
	for(int i=1;i<=S;++i)
	{
		if(i*2+1>S) break;
		for(int j=i+1;j*(ll)j-i*(ll)i<=S;++j)
			v[j*(ll)j-i*(ll)i].push_back(pii(i,j));
	}
	scanf("%d",&n);
	for(int i=2;i<=n;i+=2)
	{
		int x; scanf("%d",&x);
		for(auto t:v[x])
			if(sq[i-2]<t.first)
			{
				sq[i-1]=t.first,sq[i]=t.second;
				break;
			}
		if(!sq[i-1])
		{puts("No"); return 0;}
	}
	puts("Yes");
	for(int i=1;i<=n;++i)
		printf("%lld%c",sq[i]*(ll)sq[i]-sq[i-1]
		*(ll)sq[i-1]," \n"[i==n]);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> d[200099];
ll su[100099],x[100099];
int main()
{
	for(int i=1;i<=200000;++i)
		for(int j=i;j<=200000;j+=i)
			d[j].push_back(i);
	scanf("%d",&n);
	for(int i=2;i<=n;i+=2)
		scanf("%lld",x+i);
	for(int i=2;i<=n;i+=2)
	{
		for(auto j:d[x[i]])
		{
			int a=j,b=x[i]/j;
			if(((a+b)&1)||a>=b) continue;
			int s1=(b-a)/2;
			if(su[i-2]<(ll)s1*s1)
				x[i-1]=(ll)s1*s1-su[i-2];
		}
		if(x[i-1]==0)
		{
			puts("No");
			return 0;
		}
		su[i-1]=su[i-2]+x[i-1];
		su[i]=su[i-1]+x[i];
	}
	puts("Yes");
	for(int i=1;i<=n;i++)
		printf("%lld%c",x[i]," \n"[i==n]);
}

What about parity?

Assuming the number of 1s changed from a to b after flipping a range of length s.

Let the number of 1s in the range before this flip be be t, then b - a = (l - t) - t = s - 2t, so .

So if we made a query l, r, the parities of the lengths of [1, r] and [l, n] are different, we can find out which one is actually flipped by parity of delta. Also if we only want [1, r] or [l, n] to be flipped and nothing else, we can keep querying l, r and record all the flips happened until it's the actual case (since flipping a range twice is equivalent to no flipping at all). The expected number of queries needed is 3.

Since , it's easy to arrive at such arrangements.

When , try to query (1, 1), (1, 1), (2, 2), (2, 2), (3, 3), (3, 3)...(n, n), (n, n) and use the method described above to flip [1, 1], [1, 1], [1, 2], [1, 2], [1, 3], [1, 3]...[1, n], [1, n]. Thus we'll know s₁, s₁ + s₂, s₁ + s₂ + s₃...s₁ + s₂ + ... + s_n and s becomes obvious.

When , try to query (2, n), (2, n), (1, 2), (1, 2), (2, 3), (2, 3)...(n - 1, n), (n - 1, n) and use the method described above to flip [2, n], [2, n], [1, 2], [1, 2][1, 3], [1, 3]...[1, n], [1, n]. Thus we'll know s₂ + s₃ + ... + s_n, s₁ + s₂, s₁ + s₂ + s₃...s₁ + s₂ + ... + s_n and s also becomes obvious.

Also, we can flip every range only once instead of twice by recording whether every element is currently flipped or not, although it will be a bit harder to write.

#include <bits/stdc++.h>
using namespace std;
int n,ss[10005],sn=0,q[333];
bool tf(int l,int r)
{
	cout<<"? "<<l<<" "<<r<<endl<<flush;
	cin>>ss[++sn];
	return (ss[sn]-ss[sn-1])&1;
}
int main()
{
	cin>>n>>ss[0]; q[n]=ss[0];
	for(int i=1;i<n;++i)
	{
		int j=i-n%2;
		if(j==0)
		{
			int t[2]={0,0},u=ss[sn];
			while(t[0]!=1||t[1]!=0)
				t[tf(2,n)]^=1;
			int v=ss[sn];
			q[i]=q[n]-(n-1-v+u)/2;
			while(t[0]||t[1])
				t[tf(2,n)]^=1;
		}
		else
		{
			int t[2]={0,0},u=ss[sn];
			while(t[0]!=1||t[1]!=0)
				t[(tf(j,i)^i)&1]^=1;
			int v=ss[sn];
			q[i]=(i-v+u)/2;
			while(t[0]||t[1])
				t[(tf(j,i)^i)&1]^=1;
		}
	}
	cout<<"! ";
	for(int i=1;i<=n;++i)
		printf("%d",q[i]-q[i-1]);
	cout<<endl<<flush;
}

How does "merge" work? What is this "mergesort" actually doing?

First, consider how "merge" will work when dealing with two arbitrary arrays. Partition every array into several blocks: find all elements that are larger than all elements before them and use these elements as the start of the blocks. Then, by 'merging' we're just sorting these blocks by their starting elements. (This is because that when we decided to put the start element of a block into the result array, the remaining elements in the block will be sequentially added too since they're smaller than the start element)

Now back to the merge sort. What this "mergesort" doing is basically dividing the array into several segments (i.e. the ranges reaching the depth threshold). In every segment, the relative order stays the same when merging, so the expected number of inversions they contribute is just (for a segment of length l). Again suppose every segment is divided into blocks aforementioned, we're just sorting those blocks altogether by the beginning elements.

Let's consider inversions formed from two blocks in two different segments. Say the elements forming the inversion are initially the i-th and j-th of those two segments (from left to right), then the blocks they belong start from the maximum of the first i-th and the first j-th of those two segments. Consider the maximum among these i + j numbers, if it is one of these two elements, the inversion can't be formed. The probability that the maximum is neither i nor j is , and if the maximum is chosen, there are 50% percent of odds that the order of i and j is different from that of two maximums, because these two elements' order can be changed by swapping these two elements while leaving the maximums' order unchanged. So their probability of forming an inversion is just .

Enumerate two blocks and i and precalculate the partial sum of reciprocals, we can calculate the expectation of inversions formed from these two blocks in O(n) time. However, there might be O(n) blocks. But there is one more property for this problem: those segments are of at most two different lengths. By considering same length pairs only once, we can get a O(n) or solution.

Bonus: solve this problem when the segments' length can be arbitary and n ≤ 10⁵.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define SZ 123456
int n,k,MOD,ts[SZ],tn=0;
ll inv[SZ],invs[SZ];
ll qp(ll a,ll b)
{
	ll x=1; a%=MOD;
	while(b)
	{
		if(b&1) x=x*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return x;
}
void go(int l,int r,int h)
{
	if(h<=1||l==r) ts[++tn]=r-l+1;
	else
	{
		int m=(l+r)>>1;
		go(l,m,h-1); go(m+1,r,h-1);
	}
}
map<ll,int> cnt;
ll calc(int a,int b)
{
	ll ans=a*(ll)b%MOD;
	for(int i=1;i<=a;++i)
		ans-=(invs[i+b]-invs[i])*2LL,ans%=MOD;
	return ans;
}
int main()
{
	scanf("%d%d%d",&n,&k,&MOD);
	for(int i=1;i<=max(n,2);++i)
		inv[i]=qp(i,MOD-2),
		invs[i]=(invs[i-1]+inv[i])%MOD;
	go(1,n,k); ll ans=0;
	for(int i=1;i<=tn;++i)
		++cnt[ts[i]],ans+=ts[i]*(ll)(ts[i]-1)/2,ans%=MOD;
	for(auto t:cnt)
		if(t.se>=2)
			ans+=calc(t.fi,t.fi)*((ll)t.se*(t.se-1)/2%MOD),ans%=MOD;
	for(auto a:cnt)
		for(auto b:cnt)
			if(a.fi<b.fi)
				ans+=calc(a.fi,b.fi)*((ll)a.se*b.se%MOD),ans%=MOD;
	ans=ans%MOD*inv[2]%MOD;
	ans=(ans%MOD+MOD)%MOD;
	printf("%d\n",int(ans));
}

What will be counted twice?

Warning: This editorial is probably new and arcane for ones who are not familiar with this field. If you just want to get a quick idea about the solution, you can skip all the proofs (they're wrapped in spoiler tags).

Some symbols: All indices of strings start from zero. x^R stands for the reverse of string x. (e.g. 'abc'^R = 'cba'), xy stands for concatenation of x and y. (e.g. x = 'a', y = 'b', xy = 'ab'), x^a stands for concatenation of a copies of x (e.g. x = 'ab', x² = 'abab'). x[a, b] stands for the substring of x starting and ending from the a-th and b-th character. (e.g. 'abc'[1, 2] = 'bc')

Border of x: strings with are common prefix & suffix of x. Formally, x has a border of length t (x[0, t - 1]) iff x_i = x_{|x| - t + i} ().

Period of x: x has a period of length t iff x_i = x_i + t (0 ≤ i < |x| - t). When t||x| we also call t a full period. From the formulas it's easy to see x has a period of length t iff x has a border of length |x| - t. ()

Power: x is a power iff the minimum full period of x isn't |x|. e.g. abab is a power.

Lemma 1 (weak periodicity lemma): if p and q are periods of s, p + q ≤ |s|, gcd(p, q) is also a period of s.

Lemma 2: Let S be the set of period lengths  ≤ |s| / 2 of s, if S is non-empty, .

Let border(x) be the longest (not-self) border of x. e.g. border('aba') = 'a', border('ab') = ".

If x is a palindrome, its palindromic prefix and suffix must be its border. Therefore, its (not-self) longest palindromic prefix (suffix) is border(x).

If S = pq, p and q are palindromic and non-empty, we call (p, q) a palindromic decomposition of S. If S = pq, p and q are palindromic, q is non-empty (p can be empty) we call (p, q) a non-strict palindromic decomposition of S.

Lemma 3: if S = x₁ x₂ = y₁ y₂ = z₁ z₂, |x₁| < |y₁| < |z₁|, x₂, y₁, y₂, z₁ are palindromic and non-empty, then x₁ and z₂ are also palindromic.

Lemma 4: Suppose S has some palindromic decomposition. Let the longest palindromic prefix of S be a, S = ax, longest palindromic suffix of S be b, S = yb. At least one of x and y is palindromic.

Lemma 5: S = p₁ q₁ = p₂ q₂ (|p₁| < |p₂|, p₁, q₁, p₂, q₂ are palindromic, q₁ and q₂ are non-empty), then S is a power.

Lemma 6: Let S = p₁ q₁ = p₂ q₂ = ... = p_t q_t be all non-strict palindromic decompositions of S, h be the minimum full period of S. When t ≠ 0, t = |S| / h.

Lemma 7: Let S = p₁ q₁ = p₂ q₂ = ... = p_t q_t be all non-strict palindromic decompositions of S. (|p_i| < |p_i + 1|) For every , at least one of p_i = border(p_i + 1) and q_i + 1 = border(q_i) is true.

Lemmas are ready, let's start focusing on this problem. A naive idea is to count the number of palindromes in A and in B, and multiply them. This will obviously count a string many times. By Lemma 7, suppose S = xy, to reduce counting, we can check if using border(x) or border(y) to replace x or y can also achieve S. If any of them do, reduce the answer by 1, then we're done.

So for a palindromic string x in A, we want to count strings that are attainable from both x and border(x) and subtract from the answer. Finding x and border(x) themselves can be simply done by the palindromic tree.

Let x = border(x)w, we want to count Ts in B that T = wS and both T and S are palindromic. Since |w| is the shortest period of x, w can't be a power.

If |w| > |S|, w = S + U. S are U are both palindromes. Since w is not a power, it can be decomposed to be two palindromes in at most one way (Lemma 5). We can find that only way (by checking maximal palindromic suffix & prefix) and use hashing to check if it exists in B.

If |w| ≤ |S|, if S is not maximum palindromic suffix of T, w must be a power (Lemma 2), so we only need to check maximum palindromic suffixes (i.e. S = border(T)).

We need to do the similar thing to ys in B, then adding back both attainable from border(x) and border(y). Adding back can be done in a similar manner, or directly use hashing to find all matching w s.

Finding maximal palindromic suffix and prefix of substrings can be done by binary-lifting on two palindromic trees (one and one reversed). Let up_i, j be the resulting node after jumping through fail links for 2^j steps from node i. While querying maximal palindromic suffix for s[l, r], find the node corresponding to the maximal palindromic suffix of s[1, r] (this can be stored while building palindromic tree). If it fits into s[l, r] we're done. Otherwise, enumerate j from large to small and jump 2^j steps (with the help of up) if the result node is still unable to fit into s[l, r], then jump one more step to get the result.

#include <bits/stdc++.h>

using namespace std;

const int N = 234567;
const int LOG = 18;
const int ALPHA = 26;
const int base = 2333;
const int md0 = 1e9 + 7;
const int md1 = 1e9 + 9;

struct hash_t {
  int hash0, hash1;

  hash_t(int hash0 = 0, int hash1 = 0):hash0(hash0), hash1(hash1) {
  }

  hash_t operator + (const int &x) const {
    return hash_t((hash0 + x) % md0, (hash1 + x) % md1);
  };

  hash_t operator * (const int &x) const {
    return hash_t((long long)hash0 * x % md0, (long long)hash1 * x % md1);
  }

  hash_t operator + (const hash_t &x) const {
    return hash_t((hash0 + x.hash0) % md0, (hash1 + x.hash1) % md1);
  };

  hash_t operator - (const hash_t &x) const {
    return hash_t((hash0 + md0 - x.hash0) % md0, (hash1 + md1 - x.hash1) % md1);
  };

  hash_t operator * (const hash_t &x) const {
    return hash_t((long long)hash0 * x.hash0 % md0, (long long)hash1 * x.hash1 % md1);
  }

  long long get() {
    return (long long)hash0 * md1 + hash1;
  }
} ha[N], hb[N], power[N];

struct palindrome_tree_t {
  int n, total, p[N], pos[N], value[N], parent[N], go[N][ALPHA], ancestor[LOG][N];
  char s[N];

  palindrome_tree_t() {
    parent[0] = 1;
    value[1] = -1;
    total = 1;
    p[0] = 1;
  }

  int extend(int p, int w, int n) {
    while (s[n] != s[n - value[p] - 1]) {
      p = parent[p];
    }
    if (!go[p][w]) {
      int q = ++total, k = parent[p];
      while (s[n] != s[n - value[k] - 1]) {
        k = parent[k];
      }
      value[q] = value[p] + 2;
      parent[q] = go[k][w];
      go[p][w] = q;
      pos[q] = n;
    }
    return go[p][w];
  }

  void init() {
    for (int i = 1; i <= n; ++i) {
      p[i] = extend(p[i - 1], s[i] - 'a', i);
    }
    for (int i = 0; i <= total; ++i) {
      ancestor[0][i] = parent[i];
    }
    for (int i = 1; i < LOG; ++i) {
      for (int j = 0; j <= total; ++j) {
        ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
      }
    }
  }

  int query(int r, int length) {
    r = p[r];
    if (value[r] <= length) {
      return value[r];
    }
    for (int i = LOG - 1; ~i; --i) {
      if (value[ancestor[i][r]] > length) {
        r = ancestor[i][r];
      }
    }
    return value[parent[r]];
  }

  bool check(int r, int length) {
    r = p[r];
    for (int i = LOG - 1; ~i; --i) {
      if (value[ancestor[i][r]] >= length) {
        r = ancestor[i][r];
      }
    }
    return value[r] == length;
  }
} A, B, RA, RB;

map<long long, int> fa, fb, ga, gb;
long long answer;
char a[N], b[N];
int n, m;

hash_t get_hash(hash_t *h, int l, int r) {
  return h[r] - h[l - 1] * power[r - l + 1];
}

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  scanf("%s %s", a + 1, b + 1);
  n = strlen(a + 1);
  m = strlen(b + 1);
  A.n = RA.n = n;
  B.n = RB.n = m;
  for (int i = 1; i <= n; ++i) {
    A.s[i] = RA.s[n - i + 1] = a[i];
    ha[i] = ha[i - 1] * base + a[i];
  }
  for (int i = 1; i <= m; ++i) {
    B.s[i] = RB.s[m - i + 1] = b[i];
    hb[i] = hb[i - 1] * base + b[i];
  }
  power[0] = hash_t(1, 1);
  for (int i = 1; i <= max(n, m); ++i) {
    power[i] = power[i - 1] * base;
  }
  A.init();
  B.init();
  RA.init();
  RB.init();
  answer = (long long)(A.total - 1) * (B.total - 1);
  for (int i = 2; i <= A.total; ++i) {
    ++fa[get_hash(ha, A.pos[i] - A.value[i] + 1, A.pos[i]).get()];
    int p = A.parent[i];
    if (p < 2) {
      continue;
    }
    int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i];
    if (A.value[i] <= A.value[p] << 1) {
      ++ga[get_hash(ha, l, r).get()];
    }
  }
  for (int i = 2; i <= B.total; ++i) {
    ++fb[get_hash(hb, B.pos[i] - B.value[i] + 1, B.pos[i]).get()];
    int p = B.parent[i];
    if (p < 2) {
      continue;
    }
    int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p];
    if (B.value[i] <= B.value[p] << 1) {
      ++gb[get_hash(hb, l, r).get()];
    }
  }
  for (int i = 2; i <= A.total; ++i) {
    int p = A.parent[i];
    if (p < 2) {
      continue;
    }
    int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i];
    long long value = get_hash(ha, l, r).get();
    if (gb.count(value)) {
      answer -= gb[value];
    }
    int longest_palindrome_suffix = A.query(r, r - l + 1);
    if (longest_palindrome_suffix == r - l + 1) {
      continue;
    }
    if (RA.check(n - l + 1, r - l + 1 - longest_palindrome_suffix)) {
      int length = r - l + 1 - longest_palindrome_suffix;
      if (fb.count(get_hash(ha, l, l + length - 1).get()) && fb.count((get_hash(ha, l, r) * power[length] + get_hash(ha, l, l + length - 1)).get())) {
        --answer;
      }
      continue;
    }
    int longest_palindrome_prefix = RA.query(n - l + 1, r - l + 1);
    if (A.check(r, r - l + 1 - longest_palindrome_prefix)) {
      int length = longest_palindrome_prefix;
      if (fb.count(get_hash(ha, l, l + length - 1).get()) && fb.count((get_hash(ha, l, r) * power[length] + get_hash(ha, l, l + length - 1)).get())) {
        --answer;
      }
      continue;
    }
  }
  for (int i = 2; i <= B.total; ++i) {
    int p = B.parent[i];
    if (p < 2) {
      continue;
    }
    int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p];
    long long value = get_hash(hb, l, r).get();
    if (ga.count(value)) {
      answer -= ga[value];
    }
    int longest_palindrome_suffix = B.query(r, r - l + 1);
    if (longest_palindrome_suffix == r - l + 1) {
      continue;
    }
    if (RB.check(m - l + 1, r - l + 1 - longest_palindrome_suffix)) {
      int length = longest_palindrome_suffix;
      if (fa.count(get_hash(hb, r - length + 1, r).get()) && fa.count((get_hash(hb, r - length + 1, r) * power[r - l + 1] + get_hash(hb, l, r)).get())) {
        --answer;
      }
      continue;
    }
    int longest_palindrome_prefix = RB.query(m - l + 1, r - l + 1);
    if (B.check(r, r - l + 1 - longest_palindrome_prefix)) {
      int length = r - l + 1 - longest_palindrome_prefix;
      if (fa.count(get_hash(hb, r - length + 1, r).get()) && fa.count((get_hash(hb, r - length + 1, r) * power[r - l + 1] + get_hash(hb, l, r)).get())) {
        --answer;
      }
      continue;
    }
  }
  for (int i = 2; i <= A.total; ++i) {
    int p = A.parent[i];
    if (p < 2) {
      continue;
    }
    int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i];
    if (A.value[i] > A.value[p] << 1) {
      ++ga[get_hash(ha, l, r).get()];
    }
  }
  for (int i = 2; i <= B.total; ++i) {
    int p = B.parent[i];
    if (p < 2) {
      continue;
    }
    int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p];
    if (B.value[i] > B.value[p] << 1) {
      ++gb[get_hash(hb, l, r).get()];
    }
  }
  for (auto p : ga) {
    answer += (long long)p.second * gb[p.first];
  }
  printf("%lld\n", answer);
  return 0;
}

Let's investigate the total number of allocated segment tree nodes.

Initially we will allocate O(nlogn) such nodes (O(logn) for each).

For every spliting attempt we will allocate at most O(logn) more, so it will also be O(nlogn) in total. The reason is obviously we will recursively split only either left child or right child of a node.

So the total number of allocated segment tree nodes will at most be only O(nlogn).

Let's consider merging, except for 'nothing to merge', every time we call merge, the total number of allocated segment tree nodes will decrease by 1 (t2 isn't useful anymore). Obviously 'nothing to merge' will only be called when its father is really merged, so they will have nothing to do with complexity.

the total number of allocated segment tree nodes is O(nlogn), for every useful merge it will decrease 1, so the total complexity of all merges is O(nlogn).