Problem Statement

Given a sequence of length n: S1, S2, S3, ..., Sn, process T queries. Each query provides four integers l, r, a, b. For all indices i ∈ [l, r], answer two questions:

1. Count of positions where Si ∈ [a, b]
2. Number of distinct values among Si that satisfy Si ∈ [a, b]

Constraints: n ≤ 10^5, T ≤ 10^6

Analysis of Failed Approaches

Attempt 1: Pure Block Decomposition on Values

For the first query type, we can precompute sumLess[i][j] representing the count of numbers smaller than j in the first i blocks. Preprocessing takes O(n × totalBlocks).

The approach:

• To count numbers in [a, b] within full blocks: res = sumLess[vR-1][b] - sumLess[vL][b] - (sumLess[vR-1][a-1] - sumLess[vL][a-1])
• Process partial blocks by brute force

However, for the second query (counting distinct values), using numLess[i][j] for the count of distinct values less than j fails because the same value may appear in multiple blocks, and simple subtraction creates duplicates.

Attempt 2: Triple-Dimensional Precomputation

Attempted to store num[i][j][k] representing distinct values in blocks i through j that are ≤ k. This requires O(n × blockCount²) space, which becomes prohibitive with n = 10^5 and T = 10^6. Time complexity also becomes unmanageable.

Correct Solution: Mo's Algorithm with Value Domain Decomposition

Mo's algorithm transforms offline queries by sorting them strategically, allowing us to move from one query's range to the next in near-cnostant amortized time. Instead of partitioning the original sequence, we sort all queries and apply block decomposition to their order.

Core Idea

We maintain a sliding window representing the current query range [currentL, currentR]. As we transition between queries, we expand or contract this window using add and del operations on individual elements.

for each query in sorted order:
    while currentL > query.l: add(s[--currentL])
    while currentL < query.l: del(s[currentL++])
    while currentR < query.r: add(s[++currentR])
    while currentR > query.r: del(s[currentR--])
    answer first query type using value decomposition
    answer second query type using value decomposition

Value Domain Block Decomposition

For each value x in the sequence, we track:

• cnt[x]: frequency of value x in current range
• blockCount[i]: total frequency in block i
• blockDistinct[i]: number of distinct values present in block i

void add(int x) {
    if (cnt[x] == 0) blockDistinct[valueBlock[x]]++;
    blockCount[valueBlock[x]]++;
    cnt[x]++;
}

void del(int x) {
    cnt[x]--;
    blockCount[valueBlock[x]]--;
    if (cnt[x] == 0) blockDistinct[valueBlock[x]]--;
}

Query Processing

To answer queries on value range [a, b]:

For counting all occurrences (first query type):

int queryCount(int a, int b) {
    int result = 0;
    int blockA = valueBlock[a], blockB = valueBlock[b];
    
    if (blockB - blockA <= 1) {
        for (int i = a; i <= b; i++) result += cnt[i];
        return result;
    }
    
    // Full blocks
    for (int i = blockA + 1; i < blockB; i++)
        result += blockCount[i];
    
    // Partial blocks
    for (int i = a; i <= blockEnd[blockA]; i++) result += cnt[i];
    for (int i = blockStart[blockB]; i <= b; i++) result += cnt[i];
    
    return result;
}

For counting distinct values (second query type):

int queryDistinct(int a, int b) {
    int result = 0;
    int blockA = valueBlock[a], blockB = valueBlock[b];
    
    if (blockB - blockA <= 1) {
        for (int i = a; i <= b; i++) result += (cnt[i] > 0);
        return result;
    }
    
    // Full blocks
    for (int i = blockA + 1; i < blockB; i++)
        result += blockDistinct[i];
    
    // Partial blocks
    for (int i = a; i <= blockEnd[blockA]; i++) result += (cnt[i] > 0);
    for (int i = blockStart[blockB]; i <= b; i++) result += (cnt[i] > 0);
    
    return result;
}

Query Sorting

Sort queries by block of left endpoint, then by right endpoint within each block:

bool compareQueries(const Query& x, const Query& y) {
    if (valueBlock(x.l) != valueBlock(y.l))
        return x.l < y.l;
    return x.r < y.r;
}

Complete Implementation

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

const int MAX_N = 100010;
const int MAX_Q = 1000010;
const int MAX_VAL = 100010;

struct Query {
    int l, r, a, b, idx;
};

int n, queryCount;
int arr[MAX_N];
int valueBlockId[MAX_VAL];

int blockSize, blockTotal;
int blockStart[350], blockEnd[350];

int currentL = 1, currentR = 0;

int frequency[MAX_VAL];
int blockFreq[350];
int blockUnique[350];

int answerCount[MAX_Q];
int answerDistinct[MAX_Q];

Query queries[MAX_Q];

int readInt() {
    int x = 0, sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + c - '0';
        c = getchar();
    }
    return x * sign;
}

void initializeValueBlocks() {
    blockSize = sqrt(MAX_VAL);
    blockTotal = (MAX_VAL - 1) / blockSize + 1;
    
    for (int i = 1; i <= blockTotal; i++) {
        blockStart[i] = blockEnd[i-1] + 1;
        blockEnd[i] = blockStart[i] + blockSize - 1;
    }
    blockEnd[blockTotal] = MAX_VAL;
    
    for (int i = 1; i <= MAX_VAL; i++)
        valueBlockId[i] = (i - 1) / blockSize + 1;
}

void addElement(int value) {
    if (frequency[value] == 0)
        blockUnique[valueBlockId[value]]++;
    blockFreq[valueBlockId[value]]++;
    frequency[value]++;
}

void removeElement(int value) {
    frequency[value]--;
    blockFreq[valueBlockId[value]]--;
    if (frequency[value] == 0)
        blockUnique[valueBlockId[value]]--;
}

int countInRange(int a, int b) {
    int result = 0;
    int blockA = valueBlockId[a];
    int blockB = valueBlockId[b];
    
    if (blockB - blockA <= 1) {
        for (int i = a; i <= b; i++)
            result += frequency[i];
        return result;
    }
    
    for (int i = blockA + 1; i < blockB; i++)
        result += blockFreq[i];
    
    for (int i = a; i <= blockEnd[blockA]; i++)
        result += frequency[i];
    
    for (int i = blockStart[blockB]; i <= b; i++)
        result += frequency[i];
    
    return result;
}

int distinctInRange(int a, int b) {
    int result = 0;
    int blockA = valueBlockId[a];
    int blockB = valueBlockId[b];
    
    if (blockB - blockA <= 1) {
        for (int i = a; i <= b; i++)
            result += (frequency[i] > 0);
        return result;
    }
    
    for (int i = blockA + 1; i < blockB; i++)
        result += blockUnique[i];
    
    for (int i = a; i <= blockEnd[blockA]; i++)
        result += (frequency[i] > 0);
    
    for (int i = blockStart[blockB]; i <= b; i++)
        result += (frequency[i] > 0);
    
    return result;
}

bool queryComparator(const Query& x, const Query& y) {
    int blockX = valueBlockId[x.l];
    int blockY = valueBlockId[y.l];
    if (blockX != blockY) return blockX < blockY;
    return x.r < y.r;
}

int main() {
    initializeValueBlocks();
    
    n = readInt();
    queryCount = readInt();
    
    for (int i = 1; i <= n; i++)
        arr[i] = readInt();
    
    for (int i = 1; i <= queryCount; i++) {
        queries[i].idx = i;
        queries[i].l = readInt();
        queries[i].r = readInt();
        queries[i].a = readInt();
        queries[i].b = readInt();
    }
    
    sort(queries + 1, queries + queryCount + 1, queryComparator);
    
    for (int i = 1; i <= queryCount; i++) {
        while (currentL < queries[i].l) removeElement(arr[currentL++]);
        while (currentL > queries[i].l) addElement(arr[--currentL]);
        while (currentR < queries[i].r) addElement(arr[++currentR]);
        while (currentR > queries[i].r) removeElement(arr[currentR--]);
        
        answerCount[queries[i].idx] = countInRange(queries[i].a, queries[i].b);
        answerDistinct[queries[i].idx] = distinctInRange(queries[i].a, queries[i].b);
    }
    
    for (int i = 1; i <= queryCount; i++) {
        printf("%d %d\n", answerCount[i], answerDistinct[i]);
    }
    
    return 0;
}

Complexity Analysis

• Preprocessing: O(n) for building value blocks
• Query Sorting: O(T log T)
• Mo's Algorithm Movement: O((n + T) × sqrt(n)) amortized
• Range Queries: O(sqrt(MAX_VAL)) per query using value block decomposition
• Space: O(MAX_VAL + T) for frequency arrays and answers

This solution efficiently handles the massive constraint of T ≤ 10^6 queries by leveraging Mo's algorithm's ability to process offline queries in amortized O(1) per movement, combined with value domain decomposition for fast range queries.