Well, we gave you enough hints in the examples. I believe you can already guess it.

for i in range(int(input())):
    x,y=map(int,input().split())
    if x==y==1:
        print(1)
    else:
        print(y-x)

Assume that you chose some two indices $$$i$$$ and $$$j$$$ included in the subsequence, such that $$$i<l$$$ and $$$j>r$$$. Does this actually help decrease the answer in any way?

import sys
input=lambda:sys.stdin.readline().rstrip()
 
for _ in range(int(input())):
    n,l,r=map(int,input().split());l-=1
    arr=[*map(int,input().split())]
    brr=arr[:l]+sorted(arr[l:])
    crr=sorted(arr[:r])[::-1]+arr[r:]
    print(min(sum(brr[l:r]),sum(crr[l:r])))

The answer after choosing two vertices is decided by the degrees of the two vertices, and whether the two vertices are adjacent. Can you find a clean solution where you don't have to care about the latter?

Sure, you can do DP on tree, but that's not what we want you to use. Think easier.

import sys
input=lambda:sys.stdin.readline().rstrip()
for i in range(int(input())):
    n=int(input())
    deg=[0]*n
    adj=[[] for i in range(n)]
    for i in range(n-1):
        u,v=map(int,input().split())
        u-=1;v-=1
        deg[u]+=1
        deg[v]+=1
        adj[u].append(v)
        adj[v].append(u)
    ans=1
    mans=0
    sdeg=sorted(deg)
    for i in range(n):
        ans=deg[i]
        ideg=[]
        for v in adj[i]:
            ideg.append(deg[v])
        ideg.append(deg[i])
        ideg.sort(reverse=True)
        rem=[]
        mx=-1
        for d in ideg:
            if sdeg[-1]==d:
                sdeg.pop()
                rem.append(d)
        rem.reverse()
        if sdeg:
            mx=max(mx,sdeg[-1])
        for v in adj[i]:
            mx=max(mx,deg[v]-1)
        for d in rem:
            sdeg.append(d)
        mans=max(ans+mx-1,mans)
    print(mans)

The maximum score $$$g(x_a,x_b)$$$ after performing $$$x_a$$$ times with two points on $$$y=0$$$, and $$$x_b$$$ times with two points on $$$y=2$$$, can be easily computed in $$$\mathcal{O}(1)$$$ time. But naively checking all possible number of operations takes $$$\mathcal{O}(nm)$$$ time. Is there a property we can abuse so that we can solve for each $$$k$$$ faster?

$$$g(x_a,x_b)$$$ is a function consisting of two prefix sums, each for a strictly decreasing sequence.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
 
int main()
{
  cin.tie(0)->sync_with_stdio(0);
  int t;cin>>t;
  while(t--)
  {
    int n,m;cin>>n>>m;
    vector<ll>arr(n),brr(m);
    for(ll&i:arr)cin>>i;
    for(ll&i:brr)cin>>i;
    sort(begin(arr),end(arr));
    sort(begin(brr),end(brr));
    vector<ll>asum(n+2),bsum(m+2);
    for(int i=1;i<=n;i++)asum[i]=asum[i-1]+(arr[n-i]-arr[i-1]);
    for(int i=1;i<=m;i++)bsum[i]=bsum[i-1]+(brr[m-i]-brr[i-1]);
    vector<ll>ans{0};
    // maximize asum[ka]+bsum[kb]
    // s.t. ka+kb = x
    //      ka*2+kb <= n -> ka*2+(x-ka) <= n -> ka+x <= n   -> ka <= n-x
    //      ka+kb*2 <= m -> ka+2*(x-ka) <= m -> 2*x-ka <= m -> ka >= 2*x-m
    //      ka >= 0, x-ka >= 0
    for(int x=1;2*x-m<=n-x;x++)
    {
      ll L=max(0,2*x-m),R=min(x,n-x);
      if(L>R)break;
      auto f=[&](int ka){return asum[ka]+bsum[x-ka];};
      while(R-L>3)
      {
        ll mL=(L*2+R)/3,mR=(L+R*2)/3;
        if(f(mL)>f(mR))R=mR;
        else L=mL;
      }
      ll mans=0;
      for(int i=L;i<=R;i++)
      {
        mans=max(mans,f(i));
      }
      ans.push_back(mans);
    }
    int kmax=(int)size(ans)-1;
    cout<<kmax<<"\n";
    for(int i=1;i<=kmax;i++)cout<<ans[i]<<" \n"[i==kmax];
  }
}

When $$$(u,v)$$$ is a good pair, $$$f(u,v)$$$ is actually simply represented as follows.

Naively calculating this for all good pairs takes $$$\mathcal{O}(n^2)$$$ time. Can you find a different representation where we can count wiser?

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int t;cin>>t;
    while(t--)
    {
        ll n;cin>>n;
        vector<ll>d(n,0),s(n),dc(n),dcs;
        vector<vector<ll>>adj(n);
        for(int i=1;i<n;i++)
        {
            int u,v;cin>>u>>v;
            u--;v--;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        auto dfs1=[&](auto dfs1,int v,int p=-1)->void
        {
            dc[d[v]]++;
            ll sz=1;
            for(int w:adj[v])if(w!=p)
            {
                d[w]=d[v]+1;
                dfs1(dfs1,w,v);
                sz+=s[w];
            }
            s[v]=sz;
        };
        dfs1(dfs1,0);
        dcs=dc;
        for(int i=n-2;i>=0;i--)dcs[i]+=dcs[i+1];
        ll ans=0,ans2=0;
        auto dfs2=[&](auto dfs2,int v,int p=-1)->void
        {
            // v is min
            ans+=2*d[v]*(dcs[d[v]]-s[v]);
            // v is lca
            ll subcnt=s[v]-1,lcnt=0;
            for(int w:adj[v])if(w!=p)
            {
                lcnt+=(subcnt-s[w])*s[w];
                dfs2(dfs2,w,v);
            }
            ans2+=(2*d[v]+1)*(lcnt/2);
        };
        dfs2(dfs2,0);
        for(int i=0;i<n;i++)
        {
            ans2+=i*dc[i]*(dc[i]-1);
        }
        cout<<ans-ans2<<"\n";
    }
}

The subproblem where you find the number of different balanced bracket sequences of length $$$2k$$$ is already well-known.

Now recall everyone's favorite data structure to solve problems related to balanced bracket sequences — the stack!

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll md=998244353;
 
int main()
{
    int t;cin>>t;
    vector<ll>ctl(5050);
    ctl[0]=1;
    for(int n=1;n<5050;n++)
    {
        for(int i=1;i<=n;i++)
        {
            ctl[n]=(ctl[n]+ctl[i-1]*ctl[n-i]%md)%md;
        }
    }
    while(t--)
    {
        int n;cin>>n;
        ll ans=ctl[n];
        cout<<ans<<" ";
        string s(2*n+2,'.');
        s[0]='(';s[2*n+1]=')';
        for(int a=0;a<n;a++)
        {
            int i,j;cin>>i>>j;
            ans=1;
            s[i]='(';
            s[j]=')';
            string stk;
            for(char c:s)
            {
                if(c==')')
                {
                    int cnt=0;
                    while(stk.back()!='(')
                    {
                        cnt++;
                        stk.pop_back();
                    }
                    stk.pop_back();
                    ans=(ans*ctl[cnt/2])%md;
                }
                else stk+=c;
            }
            cout<<ans<<" \n"[a+1==n];
        }
    }
}

In the solution of the easy subtask, we manually enumerated the minimal balanced subsequences, each time in $$$\mathcal{O}(n)$$$.

You can show that most minimal balanced subsequences do not change when a new clue is added. What data structure will you choose in order to utilize this fact as much as possible?

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll nil=-1;
const ll md=998244353;
 
ll pw(ll a,ll b)
{
    ll c=1;
    while(b>0)
    {
        if(b&1)c=c*a%md;
        a=a*a%md;
        b>>=1;
    }
    return c;
}
 
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    vector<ll>fac(1010101,1),ctl(505050);
    for(int i=1;i<1010101;i++)fac[i]=fac[i-1]*i%md;
    for(int i=0;i<505050;i++)
    {
        ctl[i]=fac[i*2]*pw(fac[i]*fac[i+1]%md,md-2)%md;
    }
    ll t;cin>>t;
    while(t--)
    {
        ll n;cin>>n;
        vector<ll>L(n*2,nil),R(n*2,nil),P(n*2,nil),S(n*2);
        auto update=[&](ll x)
        {
            S[x]=1;
            if(L[x]!=nil)S[x]+=S[L[x]];
            if(R[x]!=nil)S[x]+=S[R[x]];
        };
        auto rotate=[&](ll x)
        {
            ll dummy;
            ll p=P[x];
            ll b=nil;
            if(p==nil)return;
            if(x==L[p])
            {
                L[p]=b=R[x];
                R[x]=p;
            }
            else
            {
                R[p]=b=L[x];
                L[x]=p;
            }
            P[x]=P[p];P[p]=x;
            if(b!=nil)P[b]=p;
            (P[x]!=nil?p==L[P[x]]?L[P[x]]:R[P[x]]:dummy)=x;
            update(p);update(x);
        };
        auto splay=[&](ll x)
        {
            while(P[x]!=nil)
            {
                ll p=P[x];
                ll g=P[p];
                if(g!=nil)
                {
                    if((x==L[p])==(p==L[g]))rotate(p);
                    else rotate(x);
                }
                rotate(x);
            }
        };
        update(0);
        for(int i=1;i<n*2;i++)
        {
            L[i]=i-1;
            P[i-1]=i;
            update(i);
        }
        splay(0);
        ll ans=ctl[n];
        cout<<ans<<" ";
        for(int i=0;i<n;i++)
        {
            ll li,ri;cin>>li>>ri;
            //li=(li+ans%(2*n))%(2*n);
            //ri=(ri+ans%(2*n))%(2*n);
            li--;ri--;
            splay(li);
            ans=ans*pw(ctl[S[li]/2],md-2)%md;
            ll lli=L[li];
            if(L[li]!=nil)P[L[li]]=nil;
            if(R[li]!=nil)P[R[li]]=nil;
            L[li]=nil;
            R[li]=nil;
            update(li);
            // now L[li] separated from tree
            // should not be affected in splay ri
            splay(ri);
            ll lri=L[ri];
            ll rri=R[ri];
            if(L[ri]!=nil)P[L[ri]]=nil;
            if(R[ri]!=nil)P[R[ri]]=nil;
            L[ri]=nil;
            R[ri]=nil;
            update(ri);
            if(lri!=nil)
            {
                splay(lri);
                ans=ans*ctl[S[lri]/2]%md;
            }
            if(lli!=nil&&rri!=nil)
            {
                while(L[rri]!=nil)rri=L[rri];
                splay(lli);
                splay(rri);
                P[lli]=rri;
                L[rri]=lli;
                update(rri);
                ans=ans*ctl[S[rri]/2]%md;
            }
            else if(lli!=nil||rri!=nil)
            {
                if(lli!=nil)
                {
                    splay(lli);
                    ans=ans*ctl[S[lli]/2]%md;
                }
                else
                {
                    splay(rri);
                    ans=ans*ctl[S[rri]/2]%md;
                }
            }
            L[ri]=li;
            P[li]=ri;
            update(ri);
            // make dummy tree (for invariant maintaining)
            cout<<ans<<" \n"[i+1==n];
        }
    }
}

Consider maintaining the MBSes directly, but instead of using a complex data structure, we will use a small-to-large trick with linked lists. Precisely, every time we have to split a linked list, we will identify the smaller section and split it out in $$$\mathcal{O}(|small|)$$$ time, and then the amortized time complexity will be $$$\mathcal{O}(n \log n)$$$. In this solution, we do not consider bracket pairs as MBSes, for a specific reason.

Given a linked list of indices and two nodes on it, we can identify the smaller section in $$$\mathcal{O}(|small|)$$$ by iterating over both lists at the same time, interlacing the operations. The list which hit the end earlier will be the smaller one, and then we immediately know the value of $$$|small|$$$.

The issue is that you cannot identify the size of both lists in $$$\mathcal{O}(|small|)$$$ time. This is hard to fix using only a linked list. Instead, we will also maintain the implicit rooted tree structure of the bracket sequence. The MBSes correspond to vertices, and the bracket pairs correspond to edges. Initially, the tree just consists of one vertex of $$$2n$$$ brackets.

Now, for each list node, we add a pointer to the corresponding tree vertex. Now we can know which tree vertex the list node corresponds to immediately, and if we bookkeep size informations in the tree vertices, we can also find the sum of two list sizes in $$$\mathcal{O}(1)$$$. Therefore we can now know the size of both lists in $$$\mathcal{O}(|small|)$$$ time.

The only issue is with how to maintain the pointers to the tree vertices. But no problem, you can just do the small-to-large for this also. After splitting the tree vertex into two vertices and one edge, redirect the smaller list to the new smaller vertex. Theoretically there are enough ways to do this, such as swapping vertex indices. Also it is notable that it is not necessary to maintain the whole tree in this process, it is quite sufficient to just maintain it implicitly by just maintaining a sequence of sizes.

The problem is solved online with $$$\mathcal{O}(n \log n)$$$ amortized time complexity.

#pragma GCC optimize("O3,unroll-loops")

#include <iostream>
#include <numeric>
#include <vector>

constexpr int MAX_N = 3e5;
constexpr long long MOD = 998244353;

struct _inv_small {
  long long data[MAX_N + 2] = {0};
  constexpr _inv_small() {
    data[1] = 1;
    for (int i = 2; i <= MAX_N; i += 2) {
      data[i] = MOD - (MOD / i) * data[MOD % i] % MOD;
      data[i + 1] = MOD - (MOD / (i + 1)) * data[MOD % (i + 1)] % MOD;
    }
  }
};

constexpr _inv_small __inv_small;
#define inv_small(x) __inv_small.data[x]

#define inv(x) (x < MAX_N ? inv_small(x) : data[(x) - MAX_N])
struct _inv {
  long long data[MAX_N + 3] = {0};
  constexpr _inv() {
    for (int i = 0; i <= MAX_N + 1; i += 2) {
      data[i] = MOD - (MOD / (i + MAX_N)) * inv(MOD % (i + MAX_N)) % MOD;
      data[i + 1] = MOD - (MOD / (i + MAX_N + 1)) * inv(MOD % (i + MAX_N + 1)) % MOD;
    }
  }
};
#undef inv

constexpr _inv __inv;
#define inv(x) (x < MAX_N ? inv_small(x) : __inv.data[(x) - MAX_N])

struct _catalan {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = (4 * i - 2) * data[i - 1] % MOD * inv(i + 1) % MOD;
      data[i + 1] = (4 * i + 2) * data[i] % MOD * inv(i + 2) % MOD;
    }
  }
};

constexpr _catalan __catalan;
#define catalan(x) __catalan.data[x]

struct _catalan_inv {
  long long data[MAX_N + 2] = {1};
  constexpr _catalan_inv() {
    for (int i = 1; i <= MAX_N; i += 2) {
      data[i] = inv(2) * inv(2 * i - 1) % MOD * data[i - 1] % MOD * (i + 1) % MOD;
      data[i + 1] = inv(2) * inv(2 * i + 1) % MOD * data[i] % MOD * (i + 2) % MOD;
    }
  }
};

constexpr _catalan_inv __catalan_inv;
#define catalan_inv(x) __catalan_inv.data[x]

int main() {
  std::cin.tie(0)->sync_with_stdio(0);

  int t;
  std::cin >> t;

  for (int _ = 0; _ < t; ++_) {
    int n;
    std::cin >> n;

    std::vector<bool> used(2 * n + 2);

    std::vector<int> point(2 * n + 2);
    std::iota(point.begin(), point.end(), 1);

    std::vector<int> size(2 * n + 2);

    std::vector<int> parent = {0};
    std::vector<int> parent_idx(2 * n + 2);

    used[0] = true;
    point[0] = 2 * n + 2, point[2 * n + 1] = 2 * n + 1;
    size[0] = 2 * n;

    long long ans = catalan(n);

    std::cout << ans << " ";

    for (int i = 0, l, r; i < n; ++i) {
      std::cin >> l >> r;

      point[l] = r + 1, point[r] = r;
      used[l] = true;

      int p = parent[parent_idx[l]];

      int out_ptr = p + 1, ins_ptr = l + 1;
      int out_size = 0, ins_size = 0;

      while (point[out_ptr] != out_ptr && point[ins_ptr] != ins_ptr) {
        out_size += !used[out_ptr];
        ins_size += !used[ins_ptr];
        out_ptr = point[out_ptr];
        ins_ptr = point[ins_ptr];
      }

      ans = (ans * catalan_inv(size[p] / 2)) % MOD;

      int upd_ptr;
      if (point[out_ptr] == out_ptr) {
        upd_ptr = p + 1;
        parent.push_back(p);
        parent[parent_idx[l]] = l;

        ins_size = size[p] - 2 - out_size;
        size[p] = out_size, size[l] = ins_size;
      } else {
        upd_ptr = l + 1;
        parent.push_back(l);

        out_size = size[p] - 2 - ins_size;
        size[p] = out_size, size[l] = ins_size;
      }

      ans = (ans * catalan(size[p] / 2)) % MOD * catalan(size[l] / 2) % MOD;

      while (point[upd_ptr] != upd_ptr) {
        parent_idx[upd_ptr] = parent.size() - 1;
        upd_ptr = point[upd_ptr];
      }

      std::cout << ans << " ";
    }

    std::cout << '\n';
  }
}