for (int i = n - 1; i >= 0; --i) {
	next[i] = i + 1;
	while (next[i] != n && a[i] <= a[next[i]])
		next[i] = next[next[i]];
}

Now, let's compare them side by side:

for (int i = n — 1; i >= 0; --i) {
	while (!st.empty() && a[st.top()] >= a[i])
		st.pop();
	next[i] = st.empty() ? n : st.top();
	st.push(i);
}

for (int i = n — 1; i >= 0; --i) {
	next[i] = i + 1;
	while (next[i] != n && a[i] <= a[next[i]])
		next[i] = next[next[i]];
}

// In the name of Allah.

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

const int MAX_N = 1e3 + 14, B = 60;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        ll x, y;
        cin >> x >> y;
        if (y > x) {
            cout << "-1\n";
            continue;
        }
        bool seen = false;
        for (int i = B - 1; i >= 0; --i) {
            if ((x >> i & 1) > (y >> i & 1))
                seen = true;
            if (seen && (x >> i & 1) == 0) {
                x ^= (1ll << i + 1);
                x |= (1ll << i + 1) - 1;
                break;
            }
        }
        if (popcount((unsigned long long) x) == 1)
            cout << (1ll << popcount((unsigned long long) x)) - (y == 0) << '\n';
        else
            cout << (1ll << popcount((unsigned long long) x)) - (y != 0) << '\n';
    }
}

// In the name of Allah.

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

const int MAX_N = 1e6 + 1, MAX_P = MAX_N * 2;
int mark[MAX_N], mat[MAX_N][2], is_prime[MAX_P], par[MAX_N];
vector<int> g[MAX_N], cer_prefix[MAX_N], cer_suffix[MAX_N];

bool dfs(int v) {
    if (mark[v])
        return 0;
    mark[v] = 1;
    for (auto u : g[v])
        if (mat[u][1] == -1 || dfs(mat[u][1]))
            return mat[v][0] = u, mat[u][1] = v, 1;
    return 0;
}

int maximum_matching(int l, int n) {
    fill(mat[l], mat[n + 1], -1);
    bool br = 0;
    int ans = 0;
    while (br ^= 1) {
        fill(mark + l, mark + n + 1, false);
        for (int i = l; i <= n; i++)
            if (mat[i][0] == -1 && dfs(i))
                ans++, br = 0;
    }
    return ans;
}

void print(int n) {
    if (n == 0)
        return;
    if (n == 1) {
        cout << "1 ";
        return;
    }
    if (par[n] == -1) {
        for (int i = n; i >= 1; i--) {
            if (i % 2 == 1) {
                for (int j = i + 1; j <= n; j += 2)
                    if (is_prime[i + j])
                        g[i].push_back(j);
            }
            else
                for (int j = i + 1; j <= n; j += 2)
                    if (is_prime[i + j])
                        g[j].push_back(i);
            if (i % 2 != n % 2 && maximum_matching(i, n) == (n - i) / 2 + 1) {
                for (int j = i; j <= n; ++j) {
                    if (j % 2) {
                        cer_prefix[n].push_back(j);
                        cer_suffix[n].push_back(mat[j][0]);
                    }
                    g[j].clear();
                }
                ranges::reverse(cer_suffix[n]);
                par[n] = i - 1;
                break;
            }
        }
    }
    for (auto x : cer_prefix[n])
        cout << x << ' ';
    print(par[n]);
    for (auto x : cer_suffix[n])
        cout << x << ' ';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    fill_n(is_prime, MAX_P, true);
    for (int p = 2; p * p < MAX_P; ++p)
        for (int i = p * p; i < MAX_P; i += p)
            is_prime[i] = false;
    fill_n(par, MAX_N, -1);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        print(n);
        cout << '\n';
    }
}

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

bool prime(ll n){
  for(int i=2; i*i<=n; i++){
    if(n%i==0)  return false;
  }
  return true;
}

void f(ll n){
  if(n==1)  cout<<1<<" ";
  if(n!=0){
  ll i=1, a=1;
  if(n%2!=0)  i=2;
  for(; i<=n; i++){  
    if(prime(n+i)){
      a=i;
      break;
    }
  }
    for(;i<(n+a-i); i++)  cout<<i<<" ";
    f(a-1);
    for(; i<=n; i++)   cout<<i<<" ";
  }
}

int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--){
      ll n;
      cin>>n;
      f(n);
      cout<<endl;
    }
}

// In the name of Allah.

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

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};


const int MAX_N = 2e2 + 14, D = 10;
int n, k;
ModInt cache[2][D][D][D][D][2 * D], zero, one = 1;
ModInt dp(int n, int last, int max_streak, int streak_l, int streak_r);

ModInt& dp(int n, int last, int l, int r, int max_streak, int streak) {
    if (last < 0 || last >= D)
        return zero;
    if (n == 1)
        return streak == 0 && l <= last && last <= r ? one : zero;
    return cache[n & 1][last][l][r][max_streak][streak + D];
}

ModInt dp(int n, int last, int l, int r, int max_streak, int streak_l, int streak_r) {
    ModInt ans = 0;
    for (int s = streak_l; s <= streak_r; ++s)
        ans += dp(n, last, l, r, max_streak, s);
    return ans;
}

ModInt dp(int n, int last, int l, int r, int max_streak) {
    return dp(n, last, l, r, max_streak, -max_streak, max_streak) - (max_streak
                                                                         ? dp(n, last, l, r, max_streak - 1,
                                                                              -max_streak + 1, max_streak - 1)
                                                                         : 0);
}

ModInt dp_pure(int n, int last, int l, int r, int max_streak) {
    assert(l <= r);
    if (l == r)
        return dp(n, last, l, r, max_streak);
    return dp(n, last, l, r, max_streak) - dp(n, last, l + 1, r, max_streak) - dp(n, last, l, r - 1, max_streak) + dp(
        n, last, l + 1, r - 1, max_streak);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 2; i <= n; ++i) {
        fill(cache[i & 1][0][0][0][0], cache[(i & 1) + 1][0][0][0][0], ModInt());
        for (int l = 0; l < D; ++l)
            for (int r = 0; r < D; ++r)
                for (int last = i == n ? 0 : l; last <= (i == n ? D - 1 : r); ++last)
                    for (int max_streak = 0; max_streak < D; ++max_streak)
                        for (int streak = -max_streak; streak <= max_streak; ++streak) {
                            ModInt& ans = dp(i, last, l, r, max_streak, streak);
                            if (streak > 1)
                                ans = dp(i - 1, last - 1, l, r, max_streak, streak - 1);
                            else if (streak < -1)
                                ans = dp(i - 1, last + 1, l, r, max_streak, streak + 1);
                            else if (streak == 0)
                                ans = dp(i - 1, last, l, r, max_streak, -max_streak, max_streak);
                            else if (streak == 1)
                                ans = dp(i - 1, last - 1, l, r, max_streak, -max_streak, 0);
                            else if (streak == -1)
                                ans = dp(i - 1, last + 1, l, r, max_streak, 0, max_streak);
                        }
    }

    ModInt ans;
    for (int i = 0; i < D; ++i) {
        for (int row_streak = -D + 1; row_streak < D; ++row_streak)
            for (int col_streak = -D + 1; col_streak < D; ++col_streak)
                if ((row_streak + 1) * (col_streak + 1) <= k)
                    for (int l = 0; l < D; ++l)
                        for (int r = l; r < D; ++r) {
                            int cl = max(0, i - l), cr = min(D - 1, D - 1 + i - r);
                            ans += dp_pure(n, i, l, r, row_streak) * dp(n, i, cl, cr, col_streak);
                        }
    }
    cout << ans << '\n';
}

// In the name of Allah.

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

const int MAX_N = 1e5 + 14;

int ask(int i, int j, int k) {
    cout << "? " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
    int x;
    cin >> x;
    return x;
}

int main() {
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        int a[4];
        a[0] = ask(1, 2, 3);
        a[1] = ask(0, 2, 3);
        a[2] = ask(0, 1, 3);
        a[3] = ask(0, 1, 2);
        int p[n];
        for (int i = 0; i < 4; ++i)
            p[i] = accumulate(a, a + 4, 0) / 3 - a[i];
        for (int i = 4; i < n; ++i)
            p[i] = ask(0, 1, i) - p[0] - p[1];
        cout << "! ";
        for (int i = 0; i < n; ++i)
            cout << p[i] << " ";
        cout << endl;
    }
}

t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    s = input()
    ans = s[0]
    sum = 0
    for i in range(1, n):
        if s[i] == ans[-1] or (i + 1 < n and s[i] == s[i + 1]):
            sum += ans[-1] == s[i]
            ans += s[i]
    print(sum)

// In the name of Allah.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n];
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        int mn = *min_element(a, a + n);
        cout << mn * (ll) n + n - count(a, a + n, mn) << endl;
    }
}

// In the name of Allah.

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

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};


const int MAX_N = 1e6 + 1;

int phi[MAX_N];

ModInt factor[MAX_N], ans[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i < MAX_N; i++) {
        phi[i] += i;
        for (int j = i * 2; j < MAX_N; j += i)
            phi[j] -= phi[i];
    }

    fill_n(factor, MAX_N, 1);
    int n;
    cin >> n;
    while (n--) {
        int a;
        cin >> a;
        factor[a] *= (ModInt(a) / phi[a] + 1);
    }

    ModInt total;

    for (int i = MAX_N - 1; i >= 1; i--) {
        ans[i] = 1;
        for (int j = i; j < MAX_N; j += i)
            ans[i] *= factor[j];
        for (int j = i * 2; j < MAX_N; j += i)
            ans[i] -= ans[j];
        ans[i] -= 1;
        total += ans[i] / i;
    }
    cout << total << '\n';
}

// In the name of Allah.

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

const int B = 20, MAX_N = 1 << B;

const int MOD = 1e9 + 7;

struct ModInt {
    int x;

    bool operator==(const ModInt& rhs) const {
        return x == rhs.x;
    }

    bool operator!=(const ModInt& rhs) const {
        return !(rhs == *this);
    }

    ModInt(ll x = 0) : x(((x % MOD) + MOD) % MOD) {
    }

    explicit operator int() const {
        return x;
    }

    friend ModInt operator+(const ModInt& l, const ModInt& r) {
        return l.x + r.x;
    }

    ModInt& operator+=(const ModInt& o) {
        return *this = *this + o;
    }

    friend ModInt operator-(const ModInt& l, const ModInt& r) {
        return l.x - r.x;
    }

    ModInt operator-() const {
        return -x;
    }

    ModInt& operator-=(const ModInt& o) {
        return *this = *this - o;
    }

    friend ModInt operator*(const ModInt& l, const ModInt& r) {
        return (ll)l.x * r.x;
    }

    ModInt& operator*=(const ModInt& o) {
        return *this = *this * o;
    }

    ModInt pow(ll b) const {
        ModInt ans = 1;
        ModInt a = *this;
        for (; b; b >>= 1, a = a * a)
            if (b & 1)
                ans *= a;
        return ans;
    }

    ModInt rev() const {
        return pow(MOD - 2);
    }

    friend ModInt operator/(const ModInt& l, const ModInt& r) {
        return l * r.rev();
    }

    ModInt& operator/=(const ModInt& o) {
        return *this = *this / o;
    }

    friend ostream& operator<<(ostream& os, const ModInt& anInt) {
        os << anInt.x;
        return os;
    }
};

ModInt fac[MAX_N] = {1}, rfac[MAX_N] = {1};

ModInt c(int n, int r) {
    return n < r || r < 0 ? 0 : fac[n] * rfac[r] * rfac[n - r];
}

void prep() {
    for (int i = 1; i < MAX_N; ++i)
        fac[i] = fac[i - 1] * i;
    rfac[MAX_N - 1] = fac[MAX_N - 1].rev();
    for (int i = MAX_N - 2; i >= 0; --i)
        rfac[i] = (i + 1) * rfac[i + 1];
}


ModInt cnt[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    prep();
    int n, k;
    cin >> n >> k;
    while (n--) {
        int a;
        cin >> a;
        cnt[a] += 1;
    }
    for (int i = 0; i < B; ++i)
        for (int mask = 0; mask < MAX_N; ++mask)
            if (mask >> i & 1)
                cnt[mask] += cnt[mask ^ (1 << i)];
    for (auto& dp : cnt)
        dp = c((int) dp, k);
    for (int i = 0; i < B; ++i)
        for (int mask = 0; mask < MAX_N; ++mask)
            if (mask >> i & 1)
                cnt[mask] -= cnt[mask ^ (1 << i)];
    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << cnt[x] << '\n';
    }
}

B = 30
MOD = 10 ** 9 + 7


def count(n, b):
    return n // (2 ** (b + 1)) * 2 ** b + max(0, n % (2 ** (b + 1)) - 2 ** b)


t = int(input())
while t > 0:
    t -= 1
    c, n = map(int, input().split())
    if c == 1:
        a = [i for i in range(n)]
        for i in range(2, n - 1, 4):
            a[i], a[i + 1] = a[i + 1], a[i]
        if n % 4 == 3:
            a = [a[-2]] + a[:-2] + [a[-1]]
        print(*a)
    else:
        ans = 0
        for b in range(B):
            ones = count(n, b)
            zeros = n - ones
            cur_ans = (ones // 2) * (ones // 2 + 1)
            if ones % 2 == 1:
                cur_ans += ones // 2 + 1
            cur_ans += (ones + 1) // 2 * zeros
            ans += cur_ans * 2 ** b
        print(ans % MOD)

// In the name of Allah.

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


const int B = 30;
const int MOD = 1e9 + 7;

long long count(long long n, int b) {
    long long cycle = 1LL << (b + 1);
    long long full = n / cycle;
    long long res = full * (1LL << b);
    long long rem = n % cycle;
    long long add = max(0LL, rem - (1LL << b));
    return res + add;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int c;
        long long n;
        cin >> c >> n;
        if (c == 1) {
            int m = static_cast<int>(n);
            vector<int> a(m);
            for (int i = 0; i < m; ++i) {
                a[i] = i;
            }
            for (int i = 2; i < m - 1; i += 4) {
                swap(a[i], a[i + 1]);
            }
            if (m % 4 == 3) {
                vector<int> new_a;
                new_a.push_back(a[m - 2]);
                for (int i = 0; i < m - 2; ++i) {
                    new_a.push_back(a[i]);
                }
                new_a.push_back(a[m - 1]);
                a = new_a;
            }
            for (size_t i = 0; i < a.size(); ++i) {
                if (i != 0) {
                    cout << ' ';
                }
                cout << a[i];
            }
            cout << endl;
        } else {
            long long ans = 0;
            for (int b = 0; b < B; ++b) {
                long long ones = count(n, b);
                long long zeros = n - ones;
                long long half = ones / 2;
                long long cur_ans = half * (half + 1) % MOD;
                if (ones % 2 == 1) {
                    cur_ans += half + 1;
                }
                cur_ans += ((ones + 1) / 2) * zeros % MOD;
                ans = (ans + cur_ans * (1LL << b)) % MOD;
            }
            ans %= MOD;
            cout << ans << endl;
        }
    }
}

// In the name of Allah.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int a[n], prefix_gcd[n + 1] = {};
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            prefix_gcd[i + 1] = gcd(prefix_gcd[i], a[i]);
        }
        int suffix_gcd = 0, ans = 1;
        for (int i = n - 1; i >= 0; --i) {
            ans = max(ans, gcd(prefix_gcd[i], suffix_gcd));
            suffix_gcd = gcd(suffix_gcd, a[i]);
        }
        cout << ans << '\n';
    }
}

// In the name of Allah.

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

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N];
map<int, ll> cache[MAX_N];

ll solve(int v, int k) {
    if (cache[v].count(k))
        return cache[v][k];
    ll& ans = cache[v][k];
    ans = (v + 1) ^ k;
    vector<array<ll, 2>> child;
    for (auto u : g[v])
        if (k % g[v].size())
            child.push_back({solve(u, k / g[v].size()), solve(u, k / g[v].size() + 1)});
        else
            ans += solve(u, k / g[v].size());
    if (g[v].empty() || k % g[v].size() == 0)
        return ans;
    sort(child.begin(), child.end(), [](array<ll, 2> a, array<ll, 2> b) {
        return a[1] - a[0] > b[1] - b[0];
    });
    for (int i = 0; i < child.size(); ++i)
        ans += child[i][i < k % child.size()];
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        for (int i = 1; i < n; ++i) {
            int p;
            cin >> p;
            --p;
            g[p].push_back(i);
        }
        cout << solve(0, k) << '\n';
        fill(g, g + n, vector<int>());
        fill(cache, cache + n, map<int, ll>());
    }
}

// In the name of Allah.

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

const int MAX_N = 1e5 + 14, LG = 17;

int n, a[MAX_N], st[MAX_N], ft[MAX_N], sp[LG][MAX_N];
vector<int> g[MAX_N], appear[MAX_N];

void dfs(int v = 0, int p = -1) {
    static int time = 0;
    sp[0][time] = a[v];
    appear[a[v]].push_back(time);
    st[v] = time++;
    for (int u : g[v])
        if (u != p)
            dfs(u, v);
    ft[v] = time;
}

int count(int x, int l, int r) {
    return ranges::lower_bound(appear[x], r) - ranges::lower_bound(appear[x], l);
}

int get(int l, int r, int c1, int c2) {
    return get<1>(max(tuple{count(c1, l, r), c1}, tuple{count(c2, l, r), c2}));
}

int king(int l, int r) {
    int ans = 0;
    int p = l;
    for (int i = 0; i < LG; ++i)
        if (r - p >> i & 1) {
            ans = get(l, r, ans, sp[i][p]);
            p += 1 << i;
        }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v;
        --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }
    dfs();
    for (int k = 1; k < LG; ++k)
        for (int i = 0; i + (1 << k) <= n; ++i)
            sp[k][i] = get(i, i + (1 << k), sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        int sz = st[v] - st[u] + ft[u] - ft[v];
        if (!(st[u] <= st[v] && ft[v] <= ft[u]) || sz % 2) {
            cout << "NO\n";
            continue;
        }
        int c1 = king(st[u], st[v]), c2 = king(ft[v], ft[u]);
        int max_count = max(count(c1, st[u], st[v]) + count(c1, ft[v], ft[u]),
                            count(c2, st[u], st[v]) + count(c2, ft[v], ft[u]));
        // cerr << max_count << endl;
        cout << (max_count * 2 > sz ? "NO\n" : "YES\n");
    }
}

The first step is to realize the solution to a well known dp problem for finding f(A) for a given array. We define dp[i][0] to be the maximum sum for element 1..i where I am allowed to pick element i+1 and dp[i][1] be the maximum sum for element 1...i where I may or may not be allowed to pick i+1 th element. defining such states ensures that dp[i][1]>=dp[i][0] the transition will be such dp[i][0]=dp[i-1][1] and dp[i][1]=max(dp[i][0],dp[i-1][0]+a[i]) where dp[n][1] will be the answer for entire array.

in other words dp[i][1] can use all elements 1....i whereas dp[i][0] can oonly use 1...i-1 elements

Defining it to allow dp[i][1]>=dp[i][0] helps us maintain dp[i][1]-dp[i][0] as one of the states of DP of the original problem where only on basis of the difference we get which elements would be picked in future and sum of dp[i][0] will always be taken in sum out of the excess dp[i][1]-dp[i][0] do we take into account the future dp transitions which is gauranteed to be within the range of just 1 additional element ai which is not allowed in dp[i][0] but is allowed to use in dp[i][1] and hence the difference is within the range of ai<=1e4

SO for the original problems the DP states are ans_dp[i][j] representing that among all subsets/subsequences (total 2^i) of the first i numbers ans_dp[i][j] elements have a differencce between their dp[i][1] and dp[i][0] to be j, note that it is not neccessary that the subsequences have the ith element in them it is just upto i among all subsequences including ai as well as not including ai

to transition from i to i+1 for all subsequences which is not taking a_(i+1) we can directly update for them ans_dp[i+1][j]+=ans_dp[i][j] later as they will have the same difference now considering all subsequces having a_(i+1) in them since dp[i+1][1]=max(dp[i][1],dp[i][0]+a_(i+1)) and dp[i+1][0]=dp[i][1] therefore for all differences j in ans_dp[i][j] where j=dp[i][1]-dp[i][0]>=a_(i+1) will be added to difference j=0 for the next state i+1 and for all j<a_(i+1) we will have gap between for the next state dp[i+1][1]-dp[i+1][0] to be dp[i][0]+a_(i+1)-dp[i][1] =a_(i+1)-j and for all these sequences while storing the gap for the next term we can forget the total common in both dp[i][0] and dp[i][1] by the time we have computed for i we have already added all dp[i][0] terms to the final_answer now for every term we are adding a_(i+1) we should add dp[i][1]-dp[i][0]=j to the final_answer to which n-(i+1) elements remain giving 2^(n-(i+1)) subsequences*j will be added for each of them to the final answer and we have transitioned with remaining gaps for the next as well as adding the answers upto dp[i+1][0] for all numbers.

// In the name of Allah.

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

const int MAX_N = 1e5 + 14;

vector<int> g[MAX_N];

bool mark[MAX_N];
int par[MAX_N];

void dfs(int v = 0, int p = -1) {
    for (auto u : g[v])
        if (u != p){
            par[u] = v;
            dfs(u, v);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i < n; ++i) {
            int v, u;
            cin >> v >> u;
            g[v].push_back(u);
            g[u].push_back(v);
        }
        dfs();
        array cer{0, 0};
        int ans = 1;
        mark[0] = true;
        for (int i = 1; i < n; ++i) {
            if (mark[i]) {
                ++ans;
                continue;
            }
            int v = i;
            while (!mark[v]) {
                mark[v] = true;
                v = par[v];
            }
            auto it = find(cer.begin(), cer.end(), v);
            if (it == cer.end())
                break;
            *it = i;
            ++ans;
        }
        cout << ans << ' ';
        for (int k = 3; k <= n; ++k)
            cout << (k <= g[0].size() + 1) << ' ';
        cout << '\n';
        fill(g, g + n, vector<int>());
        fill(mark, mark + n, false);
    }
}

First, set all numbers to one. Increase if necessary.

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    triplets = [[] for i in range(n + 1)]
    while k > 0:
        k -= 1
        l, r, m = map(int, input().split())
        triplets[m].append((l - 1, r))  # [l, r)
    a = [1] * n
    for i in range(1, n + 1):
        for rng in triplets[i]:
            if min(a[rng[0]:rng[1]]) == i:
                a[rng[0]:rng[1]] = [i + 1] * (rng[1] - rng[0])
    if n + 1 in a:
        print(-1)
    else:
        print(*a)

Don't pick numbers that if you pick them, AND will not become k for sure. Pick everything else.

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    ans = []
    cur = (1 << 30) - 1
    for i in range(n):
        if a[i] & k == k:
            ans.append(i + 1)
            cur &= a[i]
    if cur == k:
        print('YES', '\n', len(ans), '\n', *ans)
    else:
        print('NO')

Backtrack and dp both work.

// In the name of Allah.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAX_N = 3000;

int n, a[MAX_N], b[MAX_N];
map<array<int, 2>, int> cache[MAX_N];
int solve(int i = 0, int mx = INT_MIN, int level = INT_MIN) {
    if (i == n)
        return 0;
    if (cache[i].contains({mx, level}))
        return cache[i][{mx, level}];
    if (b[i] <= level || a[i] > level)
        return cache[i][{mx, level}] = solve(i + 1, max(mx, b[i]), max(level, mx + b[i])) + (b[i] <= level);
    return cache[i][{mx, level}] = max(solve(i + 1, max(mx, a[i]), max(level, mx + a[i])) + 1,
        solve(i + 1, max(mx, b[i]), max(level, mx + b[i])));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            cache[i].clear();
        }
        for (int i = 0; i < n; ++i) {
            cin >> b[i];
            if (a[i] > b[i])
                swap(a[i], b[i]);
        }
        cout << solve() << '\n';
    }
}

Use some primes, and also 6.

MAX_N = 2000000
is_p = [True] * MAX_N
for i in range(2, MAX_N):
    if not is_p[i]:
        continue
    for j in range(i * i, MAX_N, i):
        is_p[j] = False

prs = [i for i in range(2, MAX_N) if is_p[i]]

t = int(input())

while t > 0:
    t -= 1
    n, k = map(int, input().split())
    if k > n * (n - 1) / 2:
        print(-1)
        continue
    ptr = len(prs) - 1
    while n or k:
        if k >= n - 1:
            print(prs[ptr], end=' ')
            ptr -= 1
            k -= n - 1
            n -= 1
        else:
            if ptr > 0:
                ptr = 1
                print(6, end=' ')
            else:
                print(2, end=' ')
            n -= 1
    print()

DSU, but hard!

// In the name of Allah.

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 200000;

int p[MAX_N], val[MAX_N], k[MAX_N], rev[MAX_N];
// if p[i] == -1: a[i] = val[i]
// o.w. a[i] = k[i] + rev[i] * a[p[i]]

int root(int v) {
    if (p[v] == -1)
        return v;
    int r = root(p[v]);
    if (r == p[v])
        return r;
    // a[v] = k[v] + rev[v] * a[p[v]]
    // a[p[v]] = k[p[v]] + rev[p[v]] * a[r]
    // => a[v] = k[v] + rev[v] * k[p[v]] + rev[v] * rev[p[v]] * a[r]

    // a[v] = k'[v] + rev'[v] * a[r]
    k[v] += rev[v] * k[p[v]];
    rev[v] *= rev[p[v]];
    return p[v] = r;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    fill(p, p + n, -1);
    fill(val, val + n, -1);
    fill(rev, rev + n, 1);
    while (q--) {
        int t, i, j, qk;
        cin >> t >> i >> j;
        --i;
        --j;
        if (t == 1) {
            cin >> qk;
            // a[i] + a[j] = qk
            int ri = root(i), rj = root(j);
            // cerr << ri << ' ' << rj << '\n';
            if (ri == rj) {
                // cerr << "r: " << rev[i] << ' ' << rev[j] << '\n';
                if (val[ri] != -1 || rev[i] != rev[j])
                    continue;
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[ri]
                // => 2 * rev[i] * a[ri] = qk - k[i] - k[j]
                // a[ri] = (qk - k[i] - k[j]) / (2 * rev[i])
                // cerr << "found!\n";
                val[ri] = (qk - k[i] - k[j]) / (2 * rev[i]);
            }
            else {
                // Make ri parent of rj
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[rj]
                if (val[rj] != -1) {
                    // k[i] + rev[i] * a[ri] + k[j] + rev[j] * a[rj] = qk
                    val[ri] = (qk - (k[i] + k[j] + rev[j] * val[rj])) * rev[i];
                    continue;
                }
                // a[rj] = k[rj] + rev[rj] * a[ri]
                // a[rj] = (qk - (k[i] + rev[i] * a[ri] + k[j])) * rev[j]
                // a[rj] = rev[j] * (qk - k[i] - k[j]) - rev[i] * rev[j] * a[ri]
                k[rj] = rev[j] * (qk - k[i] - k[j]);
                rev[rj] = -rev[i] * rev[j];
                p[rj] = ri;
            }
        }
        else {
            int ri = root(i), rj = root(j);
            if (val[ri] != -1 && val[rj] != -1)
                cout << k[i] + rev[i] * val[ri] + k[j] + rev[j] * val[rj] << '\n';
            else if (ri == rj && rev[i] != rev[j]) {
                // a[i] = k[i] + rev[i] * a[ri]
                // a[j] = k[j] + rev[j] * a[ri]
                cout << k[i] + k[j] << '\n';
            }
            else
                cout << "-1\n";
        }
    }
}

We’re not done yet. After we complete this series, you’ll be able to evaluate our claims and find an IDE or editor that meets what we've covered.

While configuring VSCode for an on-site contest can be challenging (and sometimes impossible), CLion is already set up for C++. You might prefer using VSCode for online contests if you’re more comfortable with it, but CLion can be a good choice for on-site contests due to its similarity to VSCode.

Answer