1484D - Playlist - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

const int N = (1 << 17);
const int INF = 1e9 + 13;

int gcd(int a, int b) {
    if(!b) return a;
    return gcd(b, a % b);
}
int t[2 * N], p[2 * N];
void update(int pos, int val, int l = 0, int r = N - 1, int v = 1) {
    if(l == r) {
        t[v] = val; 
        p[v] = pos;
        return;
    }
    int m = (l + r) / 2;
    if(pos <= m) update(pos, val, l, m, 2 * v);
    else update(pos, val, m + 1, r, 2 * v + 1);
    t[v] = min(t[2 * v], t[2 * v + 1]);
    p[v] = (t[2 * v] <= t[2 * v + 1] ? p[2 * v] : p[2 * v + 1]);
}
pair<int, int> get(int ql, int qr, int l = 0, int r = N - 1, int v = 1) {
    if(r < ql || l > qr || ql > qr) return {INF, N};
    if(ql <= l && r <= qr) {
        return {t[v], p[v]};
    }
    int m = (l + r) / 2;
    pair<int, int> t1 = get(ql, qr, l, m, 2 * v);
    pair<int, int> t2 = get(ql, qr, m + 1, r, 2 * v + 1);
    return {min(t1.first, t2.first), (t1.first <= t2.first ? t1.second : t2.second)};
}   
set<int> elems;
set<int>::iterator prev(int x) {
    if(elems.empty()) return elems.end();
    return (*elems.begin() < x ? --elems.lower_bound(x) : --elems.end());
}
set<int>::iterator next(int x) {
    if(elems.empty()) return elems.end();
    return (*(--elems.end()) > x ? elems.upper_bound(x) : elems.begin());
}
void solve() {
    vector<int> ans;

    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) 
        cin >> a[i];
    for(int i = 0; i < n; i++) {
        elems.insert(i);
        update(i, gcd(a[i], a[(i + n - 1) % n]));
    }
    int lb = 0;
    while(!elems.empty()) {
        pair<int, int> vi;
        vi = get(*next(lb), n - 1);
        if(vi.first != 1) {
            vi = get(0, n - 1);
            if(vi.first != 1) 
                break;
        }
        update(vi.second, INF);
        elems.erase(vi.second);
        int nx = *next(vi.second), pr = *prev(vi.second);
        ans.push_back(vi.second);
        update(nx, gcd(a[nx], a[pr]));
        lb = nx;
    }
    cout << (int)ans.size() << ' ';
    for(int c : ans) cout << c+1 << ' ';
    elems.clear();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--) {
        solve();
        cout << '\n';
    }
}