Problem 1: Stack Elimination with Color Constraints

Given a sequence where each element possesses a color and value, process multiple queries. For each query $[L, R]$, simulate a monotonic stack traversal from left to right: pop the top while it is less than or equal to the current value or shares the same color. Determine how many positions within the interval would completely empty the stack.

Approach

Process queries offline, sorting by the right endpoint $R$. As we iterate through the sequence, we maintain the bottom element of the stack that would be formed for each possible left endpoint $L$.

A position contributes to the answer if it pops the stack bottom, occurring precisely when the new element is either smaller than or equal to the bottom, or is the smallest element greater than the bottom with a matching color.

The bottom values form a strictly decreasing sequence. Group consecutive positions with identical stack bottoms and colors into segments. When adding a new element at position $i$, identify the rightmost segment with a bottom value less than the current element. If the preceding segment shares the current element's color, merge these suffix segments into a single new segment. Each update modifies at most one segment boundary, allowing amortized $O(1)$ maintenance via a union-find structure.

Utilize a Fenwick tree (Binary Indexed Tree) too maintain the count of valid positions across segments, supporting point updates and prefix sum queries.

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 500005;

int seqColor[MAXN], seqVal[MAXN];
int queryAns[MAXN], queryL[MAXN];
int head[MAXN], nxt[MAXN], queryId[MAXN];
int parent[MAXN], maxVal[MAXN], segColor[MAXN];
int bit[MAXN];
int n, q;

char buf[1 << 20], *p1 = buf, *p2 = buf;
inline char readc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    int x = 0; char c = readc();
    while (c < '0' || c > '9') c = readc();
    for (; c >= '0' && c <= '9'; c = readc()) x = x * 10 + (c ^ 48);
    return x;
}

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void bitAdd(int idx, int delta) {
    for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
}

int bitSum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & -idx) res += bit[idx];
    return res;
}

void extend(int pos) {
    int cur = parent[pos] = pos;
    while (find(cur) > 1) {
        int prev = find(find(cur) - 1);
        if (seqVal[pos] >= maxVal[prev]) {
            cur = parent[find(cur)] = prev;
        } else if (seqColor[pos] == segColor[prev]) {
            cur = parent[find(cur)] = prev;
        } else break;
    }
    int root = find(cur);
    maxVal[root] = seqVal[pos];
    segColor[root] = seqColor[pos];
    bitAdd(root, 1);
    bitAdd(pos + 1, -1);
    
    for (int i = head[pos]; i; i = nxt[i]) {
        queryAns[i] = bitSum(queryL[i]);
    }
}

int main() {
    n = read(); q = read();
    for (int i = 1; i <= n; ++i) seqColor[i] = read();
    for (int i = 1; i <= n; ++i) seqVal[i] = read();
    
    for (int i = 1; i <= q; ++i) {
        queryL[i] = read();
        int r = read();
        nxt[i] = head[r];
        head[r] = i;
    }
    
    for (int i = 1; i <= n; ++i) extend(i);
    for (int i = 1; i <= q; ++i) printf("%d\n", queryAns[i]);
    return 0;
}

Problem 2: Intersecting but Incomparable Sets

Given $n$ sets, find any pair of sets $A$ and $B$ such that $A \cap B \neq \emptyset$, $A \not\subseteq B$, and $B \not\subseteq A$. The sum of all set sizes is $O(n)$.

Approach

If no such pair exists, the inclusion relationships form a collection of disjoint chains. Process sets in decreasing order of size. Maintain a global bucket owner[x] indicating the smallest set (by size) currently known to contain element $x$.

When examining a set $S$, check all its elements. If all elements map to the same owner in the bucket, $S$ extends the current chain. If different owners are found, $S$ and the set corresponding to the smallest such owner form a valid answer pair. This works because sets processed earlier are larger, ensuring the incomparability condition.

Time complexity is $O(n)$ as each element is processed exactly once.

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

const int MAXN = 2000005;
const int INF = 0x3f3f3f3f;

vector<int> elements[MAXN], bySize[MAXN];
int owner[MAXN], setSize[MAXN];
int n;

char buf[1 << 20], *p1 = buf, *p2 = buf;
inline char readc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
    int x = 0; char c = readc();
    while (c < '0' || c > '9') c = readc();
    for (; c >= '0' && c <= '9'; c = readc()) x = x * 10 + (c ^ 48);
    return x;
}

bool checkAndReport(int idx) {
    if (elements[idx].empty()) return false;
    int candidate = owner[elements[idx][0]];
    bool found = false;
    for (int x : elements[idx]) {
        if (owner[x] != candidate) {
            found = true;
            if (setSize[owner[x]] < setSize[candidate]) candidate = owner[x];
        }
    }
    if (found) {
        printf("YES\n%d %d\n", candidate, idx);
    }
    return found;
}

void updateBuckets(int idx) {
    for (int x : elements[idx]) owner[x] = idx;
}

void reset(int n) {
    for (int i = 0; i <= n; ++i) {
        owner[i] = 0;
        elements[i].clear();
        bySize[i].clear();
    }
}

void solve() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int k = read();
        setSize[i] = k;
        bySize[k].push_back(i);
        elements[i].resize(k);
        for (int j = 0; j < k; ++j) elements[i][j] = read();
    }
    
    for (int sz = n; sz >= 0; --sz) {
        for (int idx : bySize[sz]) {
            if (checkAndReport(idx)) {
                reset(n);
                return;
            }
            updateBuckets(idx);
        }
    }
    puts("NO");
    reset(n);
}

int main() {
    setSize[0] = INF;
    int T = read();
    while (T--) solve();
    return 0;
}

Problem 3: Summation of Min-Max Functions

Each element has $m$ attributes ($m \leq 4$). Define $f(i,j) = \min_{k=1}^m (a_{i,k} + a_{j,k}) + \max_{k=1}^m (a_{i,k} + a_{j,k})$. Compute $\sum_{i=1}^n \sum_{j=1}^n f(i,j)$.

Approach

Decompose $f(i,j)$ into separate $\min$ and $\max$ components. For the $\min$ component, iterate over which dimension $d$ provides the minimum value. This imposes $m-1$ inequality constraints on the other dimensions. Transform coordinates to convert the problem into counting pairs satisfying these constraints, solvable via 3D partial order.

Specifically, if dimension $d$ is minimal, then $a_{i,d} + a_{j,d} \leq a_{i,k} + a_{j,k}$ for all $k \neq d$. Rearranging yields $a_{i,d} - a_{i,k} \leq -(a_{j,d} - a_{j,k})$. Create points from the array elements with coordinates derived from these differences, then apply CDQ divide and conquer combined with a Fenwick tree to count valid pairs efficiently.

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

typedef long long ll;
const int MAXN = 400005;

struct Point {
    int x, y, z, w;
    bool isQuery;
} pts[MAXN], temp[MAXN];

int bitCnt[MAXN];
ll bitSum[MAXN], result;
int coord[MAXN], uniqLen;
int n, m;

inline void bitClear(int idx) {
    for (; idx <= uniqLen && bitCnt[idx]; idx += idx & -idx) {
        bitCnt[idx] = 0;
        bitSum[idx] = 0;
    }
}

inline void bitUpdate(int idx, int val) {
    for (int i = idx; i <= uniqLen; i += i & -i) {
        bitSum[i] += val;
        bitCnt[i]++;
    }
}

inline ll bitQuerySum(int idx) {
    ll res = 0;
    for (int i = idx; i > 0; i -= i & -i) res += bitSum[i];
    return res;
}

inline int bitQueryCnt(int idx) {
    int res = 0;
    for (int i = idx; i > 0; i -= i & -i) res += bitCnt[i];
    return res;
}

bool cmpY(const Point& a, const Point& b) {
    if (a.y != b.y) return a.y < b.y;
    if (a.isQuery != b.isQuery) return a.isQuery;
    if (a.x != b.x) return a.x > b.x;
    return a.z > b.z;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    
    int i = l, j = mid + 1, tp = 0;
    while (i <= mid && j <= r) {
        if (cmpY(pts[i], pts[j])) {
            if (!pts[i].isQuery) bitUpdate(pts[i].z, pts[i].w);
            temp[++tp] = pts[i++];
        } else {
            if (pts[j].isQuery) {
                result += bitQuerySum(pts[j].z - 1);
                result += (ll)bitQueryCnt(pts[j].z - 1) * pts[j].w;
            }
            temp[++tp] = pts[j++];
        }
    }
    while (j <= r) {
        if (pts[j].isQuery) {
            result += bitQuerySum(pts[j].z - 1);
            result += (ll)bitQueryCnt(pts[j].z - 1) * pts[j].w;
        }
        temp[++tp] = pts[j++];
    }
    for (int k = l; k < i; ++k) if (!pts[k].isQuery) bitClear(pts[k].z);
    while (i <= mid) temp[++tp] = pts[i++];
    for (int k = r; k >= l; --k) pts[k] = temp[tp--];
}

void solvePartialOrder(int total) {
    sort(pts + 1, pts + total + 1, [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        if (a.isQuery != b.isQuery) return a.isQuery;
        if (a.y != b.y) return a.y > b.y;
        return a.z > b.z;
    });
    for (int i = 1; i <= total; ++i) coord[i] = pts[i].z;
    sort(coord + 1, coord + total + 1);
    uniqLen = unique(coord + 1, coord + total + 1) - coord - 1;
    for (int i = 1; i <= total; ++i)
        pts[i].z = lower_bound(coord + 1, coord + uniqLen + 1, pts[i].z) - coord;
    cdq(1, total);
}

namespace Solution {
    int a[4][MAXN];
    void run() {
        for (int d = 0; d < m; ++d) 
            for (int i = 1; i <= n; ++i) 
                scanf("%d", &a[d][i]);
        
        int total = n * 2;
        for (int dom = 0; dom < m; ++dom) {
            for (int other = 0; other < m; ++other) if (dom != other) {
                for (int i = 1; i <= n; ++i) {
                    pts[i] = {a[dom][i] - a[other][i], a[dom][i] - a[other][i], a[dom][i] - a[other][i], a[dom][i], false};
                    pts[i + n] = {a[other][i] - a[dom][i] + 1, a[other][i] - a[dom][i] + 1, a[other][i] - a[dom][i] + 1, a[dom][i], true};
                }
                solvePartialOrder(total);
            }
        }
        printf("%lld\n", result);
    }
}

int main() {
    scanf("%d%d", &m, &n);
    Solution::run();
    return 0;
}

Bonus: Minimizing $y$ in $xy\gcd(x,y) = z$

Given positive integers $x$ and $z$, find the minimum positive integer $y$ satisfying $xy\gcd(x,y) = z$, or determine no solution exists.

Approach

Perform prime factorization analysis. Let $p$ be a prime with exponents $a$ in $x$, $b$ in $y$, and $c$ in $z$. The equation becomes $\min(a,b) + a + b = c$. Solving for $b$ yields: $$b = c - a - \frac{\min(c-a, 2a)}{2}$$

This implies $y$ can be constructed with out explicit factorization using the identity: $$y = \frac{z/x}{\sqrt{\gcd(x^2, z/x)}}$$

Verify that $z$ is divisible by $x$. Compute $t = \gcd(x^2, z/x)$. Check if $t$ is a perfect square using integer square root with error correction. If valid, output $(z/x)/\sqrt{t}$.

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

ll isqrt(ll x) {
    ll r = sqrt((long double)x);
    while ((r + 1) * (r + 1) <= x) ++r;
    while (r * r > x) --r;
    return r;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int x;
        ll z;
        cin >> x >> z;
        if (z % x != 0) {
            cout << "-1\n";
            continue;
        }
        ll quo = z / x;
        ll g = gcd((ll)x * x, quo);
        ll s = isqrt(g);
        if (s * s != g) {
            cout << "-1\n";
        } else {
            cout << quo / s << "\n";
        }
    }
    return 0;
}