2025牛客暑期多校训练营1-做题&补题记录

万众瞩目、备受期待的牛客暑期多校在浓厚的小学期氛围中拉开帷幕。为什么放假了还这么多事啊告诉我为什么为什么为什么。我想做算法题我不想写那无聊小组作业。哥们哥们哥们。

老许跑香港了，我和思洋两个人打。写了四道题然后打到两百多名，思洋一发F二血直接原地升天。最后5题rk81。泰牛。又被带飞。

---

G Symmetry Intervals

紧赶慢赶十二点零一才到教室，一开始有点没进状态。想清楚了发现很简单，一个指针指S，一个指针指T，一边扫一边维护贡献更新答案即可。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    //debug(n, q, s);
    while (q--) {
        string t;
        int a;
        cin >> t >> a;
        //debug(t, a);
        int i = a - 1, j = 0;
        int m = t.size();
        i64 ans = 0;
        i64 l = 0;
        while (i < n && j < m) {
            if (s[i] == t[j]) {
                l++;
            } else {
                ans += l * (l + 1) / 2;
                l = 0;
            }
            i++;
            j++;
        }
        if (l) {
            ans += l * (l + 1) / 2;
        }
        cout << ans << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

E Endless Ladders

翻译下题意，按$|{a^2-b^2}|$计算出一个递增数列，给一个值，计算这是第几项。感觉很有规律，放OEIS一查，发现除了前几项之外，后面都是除了模4不等于2的自然数。然后就找规律一写完事。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    i64 a, b;
    cin >> a >> b;
    i64 x = abs(a * a - b * b);
    if (x == 3) {
        cout << 1 << "\n";
        return;
    }
    if (x == 5) {
        cout << 2 << "\n";
        return;
    }
    x -= 3;
    cout << (x / 4) * 3 + (x % 4) << "\n";

}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

L Numb Numbers

糖丸。形式化题意，给一个数列，每次操作单点修改，操作之间不独立，问每次操作后严格小于第n/2大的数的数量。很多做法，我拿权值线段树维护，先用排名查询值，再用值查询排名。但是多测忘了清空了。改了半天。真得维护个vector线段树板子了。唉。

还有上海市赛说的要搞的NTT板子。赶紧提上日程吧。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 1
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 5e5 + 10;
constexpr int MOD = 998244353;

i64 a[N], aa[N], b[2 * N];

#define lc u<<1
#define rc u<<1|1
int t[N << 2];

void init(int u, int l, int r) {
    t[u] = 0;
    if (l == r) return;
    int mid = l + r >> 1;
    init(lc, l, mid);
    init(rc, mid + 1, r);
}

void insert(int u, int l, int r, int p, int v) {
    //debug(u, l, r, p, v);
    t[u] += v;
    if (l == r) {
        //t[u] += v;
        return;
    } 
    int mid = l + r >> 1;
    if (p <= mid) insert(lc, l, mid, p, v);
    else insert(rc, mid + 1, r, p, v);
    //t[u] = t[lc] + t[rc];
}

// 第k大
int kth(int u, int l, int r, int k) {
    if (l == r) return l;
    int mid = l + r >> 1;
    if (t[rc] >= k) return kth(rc, mid + 1, r, k);
    else return kth(lc, l, mid, k - t[rc]);
}

// 查询小于v的数的个数
int query(int u, int l, int r, int v) {
    //debug(u, l, r, v);
    if (l == r) {
        return 0;
    }
    int mid = l + r >> 1;
    if (v <= mid) return query(lc, l, mid, v);
    else return t[lc] + query(rc, mid + 1, r, v);
}

int query2(int u, int l, int r, int v) {
    if (l == r) return t[u];
    int mid = l + r >> 1;
    if (v <= mid) return query2(lc, l, mid, v);
    else return query2(rc, mid + 1, r, v);
}

void solve() {
    int n, q;
    cin >> n >> q;
    //memset(t, 0, 4 * __lg(n) * sizeof(int));

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        b[i] = a[i];
        aa[i] = a[i];
    }
    vector<array<int, 2>> quer(q);
    for (int i = 0; i < q; ++i) {
        auto& [p, v] = quer[i];
        cin >> p >> v;
        b[n + i] = aa[p - 1] += v;
    }
    sort(b, b + n + q);
    int m = unique(b, b + n + q) - b;
    //debug(m);
    //for (int i = 0; i < m; ++i) cout << b[i] << " \n"[i == m - 1];
    init(1, 1, m);
    for (int i = 0; i < n; ++i) {
        insert(1, 1, m, lower_bound(b, b + m, a[i]) - b + 1, 1);
        //debug(lower_bound(b, b + m, a[i]) - b + 1);
    }
    for (int i = 0; i < q; ++i) {
        auto [p, v] = quer[i];
        insert(1, 1, m, lower_bound(b, b + m, a[p - 1]) - b + 1, -1);
        //debug(lower_bound(b, b + m, a[p - 1]) - b + 1);
        a[p - 1] += v;
        insert(1, 1, m, lower_bound(b, b + m, a[p - 1]) - b + 1, 1);
        //debug(lower_bound(b, b + m, a[p - 1]) - b + 1);
        int x = kth(1, 1, m, n / 2);
        //debug(n / 2, x);
        cout << query(1, 1, m, x) << "\n";
        // for (int j = 1; j <= m; ++j) {
        //     cout << query2(1, 1, m, j) << " \n"[j == m];
        // }
        // for (int j = 1; j <= m; ++j) {
        //     cout << kth(1, 1, m, j) << " \n"[j == m];
        // }
    }
}

signed main() {
    
    FIO;
    TESTS {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

K Museum Acceptance

场上有点被过题数吓到，但是dfs再记忆化一下就做完了。还是不能太依赖榜单，相信自己的判断力。

/*

This code template was updated by Yukii_P on 2025/4/4.

*/
#include <bits/stdc++.h>
#define FIO cin.tie(0); ios::sync_with_stdio(false)
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define TEST
#define TESTS int t = 1; cin >> t; while (t--)

#if 0
#define int i64
#define inf 0x3f3f3f3f3f3f3f3fLL
#else
#define inf 0x3f3f3f3f
#endif

#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << #__VA_ARGS__ << " = "; dbg1(__VA_ARGS__)
void dbg2() { std::cerr << "\n"; }
template<typename T, typename... T2>
void dbg2(T x, T2... args) {
    std::cerr << ", " << x;
    dbg2(args...);
}
template<typename T, typename... T2>
void dbg1(T x, T2... args) {
    std::cerr << x;
    dbg2(args...);
}
#else
#define debug(...) 
#endif

using namespace std;
using i64 = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using pii = std::pair<int, int>;

inline char nc() {
    static char buf[1 << 20], *p1, *p2;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
#ifndef ONLINE_JUDGE
#define nc getchar
#endif
void read() {}
template<typename T, typename... T2> 
inline void read(T &x, T2 &... oth) {
    x = 0; char c = nc(), up = c;
    while(!isdigit(c)) up = c, c = nc();
    while(isdigit(c)) x = x * 10 + c - '0', c = nc();
    up == '-' ? x = -x : 0;
    read(oth...);
}

constexpr int N = 2e5 + 10;
constexpr int MOD = 998244353;

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> e(n + 1);
    vector<int> d(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        for (int j = 0; j < d[i]; ++j) {
            int v;
            cin >> v;
            e[i].push_back(v);
        }
    }
    set<int> st;
    set<array<int, 2>> st2;
    vector<int> ans(n + 1);
    //int ok = 0;
    auto dfs = [&](auto&& dfs, int u, int f) {
        //if (ok) return;
        if (f == e[u][d[u] - 1]) {
            if (st.contains(u)) {
                //ok = 1;
                return;
            }
            st.insert(u);
        }
        {
            int x = u, y = f;
            if (x > y) swap(x, y);
            st2.insert({x, y});
        }
        int j;
        for (int i = 0; i < e[u].size(); ++i) {
            if (e[u][i] == f) {
                j = i;
                break;
            }
        }
        if (j < d[u] - 1) j++;
        else j = 0;
        dfs(dfs, e[u][j], u);
    };
    for (int i = 1; i <= n; ++i) {
        if (!ans[i]) {
            st.clear();
            st2.clear();
            //ok = 0;
            dfs(dfs, i, e[i].back());
            for (int x : st) {
                ans[x] = st2.size();
            }
        }
        cout << ans[i] << "\n";
    }
}

signed main() {
    
    FIO;
    TEST {
        solve();
    }

    return 0;
}

/*

  _  _                            _____             _               _               _    
 | \| |    ___    _ _      ___   |_   _|    _ _    (_)    __ __    (_)    __ _     | |   
 | .` |   / _ \  | ' \    |___|    | |     | '_|   | |    \ V /    | |   / _` |    | |   
 |_|\_|   \___/  |_||_|   _____   _|_|_   _|_|_   _|_|_   _\_/_   _|_|_  \__,_|   _|_|_  
_|"""""|_|"""""|_|"""""|_|     |_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""|_|"""""| 
"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-'"`-0-0-' 

(Font: ASCII - Train)

"El Psy Kongroo." -- Hououin Kyoma

"私は極色カスタ推しです...だが、狽音ウルシと夜鳴トバリも推す :)" -- Yukii_P

*/

F Flight Tracker 2

我不到啊。二血泰牛了。完了看看咋补

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T,typename U>
ostream& operator<<(ostream& o,const tuple<T,U>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	o<<"[";
	for(int i=0;i<vec.size();++i){
		o<<vec[i];
		if(i!=vec.size()-1)o<<",";
	}
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 1e9+7;// 998244353;
constexpr double pi = acos(-1), eps = 1e-6;

double simpson(auto&& f, double l, double r) {
	double mid = (l + r) / 2.0;
	return (f(l) + 4.0 * f(mid) + f(r)) * (r - l) / 6.0;
}

double asr(auto&& f, double l, double r, double eps, double ans) {
	double mid = (l + r) / 2.0, l_ = simpson(f, l, mid), r_ = simpson(f, mid, r);
	if (fabs(l_ + r_ - ans) <= 15.0 * eps) return l_ + r_ + (l_ + r_ - ans) / 15.0;
	return asr(f, l, mid, eps / 2.0, l_) + asr(f, mid, r, eps / 2.0, r_);
}

void solve(){
	double r,d,theta;
	double ans=0;
	cin>>r>>d;
	{
		double u,v,w,x,y,z;
		cin>>u>>v>>w>>x>>y>>z;
		double dot=u*x+v*y+w*z,m1=sqrt(u*u+v*v+w*w),m2=sqrt(x*x+y*y+z*z);
		theta=acos(dot/m1/m2);
	}
	{
		auto calc=[](double R,double d)->double{
			double rad=d/R;
			double h=R*(1.0-cos(rad));
			return 2.0*pi*R*h;
		};
		double s=4.0*pi*r*r;
		double c=pi*r*0.5-d;
		if(c<eps){
			double l=r*2.0*pi-r*theta-2.0*d;
			if(l<eps)ans=s;
			else{
				double d2=d-0.5*pi*r;
				double d3=r*sin(d2/r);
//				double alpha=2.0*pi-theta-2.0*d/r;
				double alpha=pi-theta;
				auto f=[&](double x)->double{
					double r2=r*cos(x);
					if(d3-r2>eps)return 0.0;
					double beta=asin(d3/r2);
//					cout<<x<<" "<<d3/r2<<" "<<beta<<"\n";
					double arc=r2*(alpha-beta*2.0);
					return r*arc;
				};
				double deg=acos(d3/r/sin(alpha*0.5));
//				cout<<d3<<" "<<alpha<<" "<<d2<<" "<<sin(alpha*0.5)<<" "<<deg<<"\n";
				double sm=asr(f,0.0,deg,eps,simpson(f,0.0,deg));
//				cout<<sm*2.0<<"\n";
				ans=s-sm*2.0;
			}
		}
		else{
			ans=calc(r,d)+(s*0.5-calc(r,c))*theta/pi;
		}
	}
	cout<<fixed<<setprecision(18)<<ans<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

I Iron Bars Cutting

给了个区间dp思路，思洋具体实现的，但是有点可惜场上没调出来。

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i32 = int;
using i64 = long long;
using i128 = __int128;

template<typename T,typename U>
ostream& operator<<(ostream& o,const tuple<T,U>& t){
	return o<<"("<<get<0>(t)<<","<<get<1>(t)<<")";
}

template<typename T>
ostream& operator<<(ostream& o,const vector<T>& vec){
	o<<"[";
	for(int i=0;i<vec.size();++i){
		o<<vec[i];
		if(i!=vec.size()-1)o<<",";
	}
	return o<<"]\n";
}

constexpr int M = 2e5+5, mod = 1e9+7;// 998244353;
constexpr double pi = acos(-1), eps = 1e-9;
constexpr ll inf=1e18;

void solve(){
	int n;
	cin>>n;
	vector<ll> a(n),pre(n+1);
	for(auto& i:a)cin>>i;
	for(int i=1;i<=n;++i)pre[i]=pre[i-1]+a[i-1];
	
	using obj=vector<tuple<ll,ll>>;
	vector dp(n,vector<obj>(n));
	auto merge=[&](const obj& x,const obj& y,obj& z,ll b,ll c){
		ll cx=inf,cy=inf;
		size_t i=upper_bound(x.begin(),x.end(),make_tuple(b,inf))-x.begin();
		if(!i)return;
		cx=get<1>(x[i-1]);
		i=upper_bound(y.begin(),y.end(),make_tuple(b,inf))-y.begin();
		if(!i)return;
		cy=get<1>(y[i-1]);
		z.emplace_back(b,c+cx+cy);
	};
	for(int i=0;i<n;++i){
		dp[i][i].emplace_back(0,0);
	}
	for(int k=1;k<n-1;++k){
		for(int l=0,r=k;r<n;++l,++r){
			for(int mid=l;mid<r;++mid){
				ll l1=pre[mid+1]-pre[l],l2=pre[r+1]-pre[mid+1];
				ll b=abs(l1-l2);
				ll c=min(l1,l2);
				for(ll t=1;;++t){
					if((1ll<<t)>=l1+l2){
						c*=t;
						break;
					}
				}
				merge(dp[l][mid],dp[mid+1][r],dp[l][r],b,c);
			}
			ranges::sort(dp[l][r]);
			for(size_t i=1;i<dp[l][r].size();++i){
				get<1>(dp[l][r][i])=min(get<1>(dp[l][r][i]),get<1>(dp[l][r][i-1]));
			}
		}
	}
	for(int m=0;m<n-1;++m){
		obj ans;
		ll l1=pre[m+1],l2=pre[n]-pre[m+1];
		ll b=abs(l1-l2);
		ll c=min(l1,l2);
		for(ll t=1;;++t){
			if((1ll<<t)>=l1+l2){
				c*=t;
				break;
			}
		}
		merge(dp[0][m],dp[m+1][n-1],ans,b,c);
		if(ans.empty())cout<<"-1 ";
		else cout<<get<1>(ans[0])<<" ";
	}
	cout<<"\n";
	
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t{1};
	cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}

H Symmetry Intervals 2

没补。完了补。