Array Block Division Part 1

Problem Link

Range Addition, Point Query

This is a fundamental template problem for array block division. For each complete block, we maintain an addition mark representing the value added to the entire block. When processing an operation range, we split it into several complete blocks and at most two incomplete blocks. For elements in incomplete blocks, we directly modify each element. For complete blocks, we simply update their addition marks. During queries, we return the sum of the original element and its block's addition mark.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAX_N = 5e5 + 5;
const int MAX_M = 2e3 + 5;

int n;
vector<int> arr(MAX_N);
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<int> lazyAdd(MAX_M);

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

void updateRange(int left, int right, int value) {
    if (blockId[left] == blockId[right]) {
        for (int i = left; i <= right; i++)
            arr[i] += value;
    } else {
        for (int i = left; i <= blockEnd[blockId[left]]; i++)
            arr[i] += value;
            
        for (int i = blockStart[blockId[right]]; i <= right; i++)
            arr[i] += value;
            
        for (int i = blockId[left] + 1; i < blockId[right]; i++)
            lazyAdd[i] += value;
    }
}

int main() {
    int op, l, r, c;
    n = readInt();
    int blockSize = sqrt(n);
    int blockCount = ceil(n * 1.0 / blockSize);

    for (int i = 1; i <= blockCount; i++) {
        blockStart[i] = (i - 1) * blockSize + 1;
        blockEnd[i] = i * blockSize;
    }
    blockEnd[blockCount] = n;

    for (int i = 1; i <= n; i++) {
        arr[i] = readInt();
        blockId[i] = (i - 1) / blockSize + 1;
    }

    for (int i = 1; i <= n; i++) {
        op = readInt();
        l = readInt();
        r = readInt();
        c = readInt();

        if (op == 0)
            updateRange(l, r, c);
        else
            cout << arr[r] + lazyAdd[blockId[r]] << endl;
    }

    return 0;
}

Array Block Division Part 2

Problem Link

Range Addition, Query Elements Less Than X

This problem utilizes the binary search concept in block division. Given a sorted array a, we need to find the count of elements less than x in the range [l, r]. If we find the first endex p where the element is >= x and the first index q where the element is > x, then q-1 is the last index with value x. The count of elements equal to x is q-p.

The solution approach is similar to the previous problem. We maintain an addition mark for each complete block and an auxiliary array b that mirrors array a but with each block sorted. For range additions, we follow the same approach as before but also need to update array b and maintain its sorted property. During queries, we scan incomplete blocks directly and use binary search (lower_bound and upper_bound) on complete blocks. Remember to adjust the search value by subtracting the block's addition mark.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 5e4 + 5;
const int MAX_M = 2e3 + 5;

int n;
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<long long> arr(MAX_N), sortedArr(MAX_N);
vector<long long> lazyAdd(MAX_M);

void updateRange(int left, int right, long long value) {
    if (blockId[left] == blockId[right]) {
        for (int i = left; i <= right; i++) {
            arr[i] += value;
        }
        
        for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
            sortedArr[i] = arr[i];
        }
        
        sort(sortedArr.begin() + blockStart[blockId[left]], 
             sortedArr.begin() + blockEnd[blockId[left]] + 1);
    } else {
        for (int i = left; i <= blockEnd[blockId[left]]; i++) {
            arr[i] += value;
        }
        
        for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
            sortedArr[i] = arr[i];
        }
        
        sort(sortedArr.begin() + blockStart[blockId[left]], 
             sortedArr.begin() + blockEnd[blockId[left]] + 1);

        for (int i = blockStart[blockId[right]]; i <= right; i++) {
            arr[i] += value;
        }
        
        for (int i = blockStart[blockId[right]]; i <= blockEnd[blockId[right]]; i++) {
            sortedArr[i] = arr[i];
        }
        
        sort(sortedArr.begin() + blockStart[blockId[right]], 
             sortedArr.begin() + blockEnd[blockId[right]] + 1);

        for (int i = blockId[left] + 1; i < blockId[right]; i++) {
            lazyAdd[i] += value;
        }
    }
}

int queryRange(int left, int right, long long x) {
    int count = 0;
    int pos;

    if (blockId[left] == blockId[right]) {
        for (int i = left; i <= right; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                count++;
            }
        }
    } else {
        for (int i = left; i <= blockEnd[blockId[left]]; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                count++;
            }
        }

        for (int i = blockStart[blockId[right]]; i <= right; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                count++;
            }
        }

        for (int i = blockId[left] + 1; i < blockId[right]; i++) {
            pos = lower_bound(sortedArr.begin() + blockStart[i], 
                             sortedArr.begin() + blockEnd[i] + 1, 
                             x - lazyAdd[i]) - sortedArr.begin();
            count += pos - blockStart[i];
        }
    }

    return count;
}

int main() {
    int op, l, r;
    long long c;
    cin >> n;
    int blockSize = sqrt(n);
    int blockCount = ceil(n * 1.0 / blockSize);

    for (int i = 1; i <= blockCount; i++) {
        blockStart[i] = (i - 1) * blockSize + 1;
        blockEnd[i] = i * blockSize;
    }
    blockEnd[blockCount] = n;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        sortedArr[i] = arr[i];
        blockId[i] = (i - 1) / blockSize + 1;
    }

    for (int i = 1; i <= blockCount; i++) {
        sort(sortedArr.begin() + blockStart[i], 
             sortedArr.begin() + blockEnd[i] + 1);
    }

    for (int i = 1; i <= n; i++) {
        cin >> op >> l >> r >> c;

        if (op == 0) {
            updateRange(l, r, c);
        } else {
            cout << queryRange(l, r, c * c) << endl;
        }
    }

    return 0;
}

Array Block Division Part 3

Problem Link

Range Addition, Query Predecessor

This problem also utilizes binary search concepts. We maintain addition marks as in the previous problem. The key difference is that we're querying for the predecessor (maximum element less than x) and need to adjust our binary search accordingly. When using binary search, we take the index returned by lower_bound minus 1, and we must always consider the addition marks in both the binary search and direct scanning approaches.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 1e3 + 5;

int n;
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<long long> arr(MAX_N), sortedArr(MAX_N);
vector<long long> lazyAdd(MAX_M);

void updateRange(int left, int right, long long value) {
    if (blockId[left] == blockId[right]) {
        for (int i = left; i <= right; i++) {
            arr[i] += value;
        }

        for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
            sortedArr[i] = arr[i];
        }

        sort(sortedArr.begin() + blockStart[blockId[left]], 
             sortedArr.begin() + blockEnd[blockId[left]] + 1);
    } else {
        for (int i = left; i <= blockEnd[blockId[left]]; i++) {
            arr[i] += value;
        }

        for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
            sortedArr[i] = arr[i];
        }

        sort(sortedArr.begin() + blockStart[blockId[left]], 
             sortedArr.begin() + blockEnd[blockId[left]] + 1);

        for (int i = blockStart[blockId[right]]; i <= right; i++) {
            arr[i] += value;
        }

        for (int i = blockStart[blockId[right]]; i <= blockEnd[blockId[right]]; i++) {
            sortedArr[i] = arr[i];
        }

        sort(sortedArr.begin() + blockStart[blockId[right]], 
             sortedArr.begin() + blockEnd[blockId[right]] + 1);

        for (int i = blockId[left] + 1; i < blockId[right]; i++) {
            lazyAdd[i] += value;
        }
    }
}

long long queryPredecessor(int left, int right, long long x) {
    int pos;
    long long result = -1;

    if (blockId[left] == blockId[right]) {
        for (int i = left; i <= right; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                result = max(result, arr[i] + lazyAdd[blockId[i]]);
            }
        }
    } else {
        for (int i = left; i <= blockEnd[blockId[left]]; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                result = max(result, arr[i] + lazyAdd[blockId[i]]);
            }
        }

        for (int i = blockStart[blockId[right]]; i <= right; i++) {
            if (arr[i] + lazyAdd[blockId[i]] < x) {
                result = max(result, arr[i] + lazyAdd[blockId[i]]);
            }
        }

        for (int i = blockId[left] + 1; i < blockId[right]; i++) {
            if (sortedArr[blockStart[i]] + lazyAdd[i] >= x) {
                continue;
            }

            pos = lower_bound(sortedArr.begin() + blockStart[i], 
                             sortedArr.begin() + blockEnd[i] + 1, 
                             x - lazyAdd[i]) - sortedArr.begin();
            result = max(result, sortedArr[pos - 1] + lazyAdd[i]);
        }
    }

    return result;
}

int main() {
    int op, l, r;
    long long c;
    cin >> n;
    int blockSize = sqrt(n);
    int blockCount = ceil(n * 1.0 / blockSize);

    for (int i = 1; i <= blockCount; i++) {
        blockStart[i] = (i - 1) * blockSize + 1;
        blockEnd[i] = i * blockSize;
    }
    blockEnd[blockCount] = n;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        blockId[i] = (i - 1) / blockSize + 1;
    }

    for (int i = 1; i <= blockCount; i++) {
        for (int j = blockStart[i]; j <= blockEnd[i]; j++) {
            sortedArr[j] = arr[j];
        }

        sort(sortedArr.begin() + blockStart[i], 
             sortedArr.begin() + blockEnd[i] + 1);
    }

    for (int i = 1; i <= n; i++) {
        cin >> op >> l >> r >> c;

        if (op == 0) {
            updateRange(l, r, c);
        } else {
            cout << queryPredecessor(l, r, c) << endl;
        }
    }

    return 0;
}

Array Block Division Part 4

Problem Link

This problem utilizes the maintenance concept in block division. We maintain both an addition mark for each complete block and the sum of elements in each block. This allows us to compute the sum of a complete block in O(1) time.

For range addition operations, if we're modifying an incomplete block, we directly update individual elements while maintaining the block sum. If we're modifying a complete block, we simply update the block sum by adding (block length × value), taking care of modulo operations.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAX_N = 5e4 + 5;
const int MAX_M = 1e3 + 5;

int n;
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<long long> arr(MAX_N);
vector<long long> blockSum(MAX_M);
vector<long long> lazyAdd(MAX_M);

void updateRange(int left, int right, long long value) {
	if (blockId[left] == blockId[right]) {
		for (int i = left; i <= right; i++) {
			arr[i] += value;
			blockSum[blockId[i]] += value;
		}
	} else {
		for (int i = left; i <= blockEnd[blockId[left]]; i++) {
			arr[i] += value;
			blockSum[blockId[i]] += value;
		}
		for (int i = blockStart[blockId[right]]; i <= right; i++) {
			arr[i] += value;
			blockSum[blockId[i]] += value;
		}
		for (int i = blockId[left] + 1; i < blockId[right]; i++) {
			lazyAdd[i] += value;
			blockSum[i] += (blockEnd[i] - blockStart[i] + 1) * value;
		}
	}
}

long long queryRange(int left, int right, long long mod) {
	long long result = 0;
	mod++;
	if (blockId[left] == blockId[right]) {
		for (int i = left; i <= right; i++) {
			result = (result + arr[i] + lazyAdd[blockId[i]]) % mod;
		}
	} else {
		for (int i = left; i <= blockEnd[blockId[left]]; i++) {
			result = (result + arr[i] + lazyAdd[blockId[i]]) % mod;
		}
		for (int i = blockStart[blockId[right]]; i <= right; i++) {
			result = (result + arr[i] + lazyAdd[blockId[i]]) % mod;
		}
		for (int i = blockId[left] + 1; i < blockId[right]; i++) {
			result = (result + blockSum[i]) % mod;
		}
	}
	return result;
}

int main() {
	int op, l, r;
	long long c;
	cin >> n;
	int blockSize = sqrt(n);
	int blockCount = ceil(n * 1.0 / blockSize);
	for (int i = 1; i <= blockCount; i++) {
		blockStart[i] = (i - 1) * blockSize + 1;
		blockEnd[i] = i * blockSize;
	}
	blockEnd[blockCount] = n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		blockId[i] = (i - 1) / blockSize + 1;
		blockSum[blockId[i]] += arr[i];
	}
	for (int i = 1; i <= n; i++) {
		cin >> op >> l >> r >> c;
		if (op == 0) {
			updateRange(l, r, c);
		} else {
			cout << queryRange(l, r, c) << endl;
		}
	}
	return 0;
}

Array Block Division Part 5

Problem Link

Range Square Root, Range Sum

This problem cleverly applies the maintenance concept. If an element is ≤ 1, we don't need to apply square root operations. We maintain the maximum value in each block. If the maximum value in a block is ≤ 1, we skip operations on that block. Otherwise, we apply square root operations to each element in the block and update both the block maximum and block sum.

The time complexity of this solution is theoretically complex, but due to the limited value range, the number of square root operations is also limited. With compiler optimizations, it can pass the time constraints.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

const int MAX_N = 5e4 + 5;
const int MAX_M = 1e3 + 5;
const long long INF = 1e16 + 5;

int n;
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<long long> arr(MAX_N);
vector<long long> blockSum(MAX_M);
vector<long long> blockMax(MAX_M);

void updateRange(int left, int right) {
	if (blockId[left] == blockId[right]) {
		if (blockMax[blockId[left]] <= 1) {
			return;
		}
		for (int i = left; i <= right; i++) {
			blockSum[blockId[i]] = blockSum[blockId[i]] - arr[i] + sqrt(arr[i]);
			arr[i] = sqrt(arr[i]);
		}
		blockMax[blockId[left]] = -INF;
		for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
			blockMax[blockId[left]] = max(blockMax[blockId[left]], arr[i]);
		}
	} else {
		if (blockMax[blockId[left]] > 1) {
			for (int i = left; i <= blockEnd[blockId[left]]; i++) {
				blockSum[blockId[i]] = blockSum[blockId[i]] - arr[i] + sqrt(arr[i]);
				arr[i] = sqrt(arr[i]);
			}
			blockMax[blockId[left]] = -INF;
			for (int i = blockStart[blockId[left]]; i <= blockEnd[blockId[left]]; i++) {
				blockMax[blockId[left]] = max(blockMax[blockId[left]], arr[i]);
			}
		}
		if (blockMax[blockId[right]] > 1) {
			for (int i = blockStart[blockId[right]]; i <= right; i++) {
				blockSum[blockId[i]] = blockSum[blockId[i]] - arr[i] + sqrt(arr[i]);
				arr[i] = sqrt(arr[i]);
			}
			blockMax[blockId[right]] = -INF;
			for (int i = blockStart[blockId[right]]; i <= blockEnd[blockId[right]]; i++) {
				blockMax[blockId[i]] = max(blockMax[blockId[i]], arr[i]);
			}
		}
		for (int i = blockId[left] + 1; i < blockId[right]; i++) {
			if (blockMax[i] > 1) {
				for (int j = blockStart[i]; j <= blockEnd[i]; j++) {
					blockSum[i] = blockSum[i] - arr[j] + sqrt(arr[j]);
					arr[j] = sqrt(arr[j]);
				}
				blockMax[i] = sqrt(blockMax[i]);
			}
		}
	}
}

long long queryRange(int left, int right) {
	long long result = 0;
	if (blockId[left] == blockId[right]) {
		for (int i = left; i <= right; i++) {
			result += arr[i];
		}
	} else {
		for (int i = left; i <= blockEnd[blockId[left]]; i++) {
			result += arr[i];
		}
		for (int i = blockStart[blockId[right]]; i <= right; i++) {
			result += arr[i];
		}
		for (int i = blockId[left] + 1; i < blockId[right]; i++) {
			result += blockSum[i];
		}
	}
	return result;
}

int main() {
	int op, l, r, c;
	cin >> n;
	int blockSize = sqrt(n);
	int blockCount = ceil(n * 1.0 / blockSize);
	for (int i = 1; i <= blockCount; i++) {
		blockStart[i] = (i - 1) * blockSize + 1;
		blockEnd[i] = i * blockSize;
		blockMax[i] = -INF;
	}
	blockEnd[blockCount] = n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
		blockId[i] = (i - 1) / blockSize + 1;
		blockSum[blockId[i]] += arr[i];
		blockMax[blockId[i]] = max(blockMax[blockId[i]], arr[i]);
	}
	for (int i = 1; i <= n; i++) {
		cin >> op >> l >> r >> c;
		if (op == 0) {
			updateRange(l, r);
		} else {
			cout << queryRange(l, r) << endl;
		}
	}
	return 0;
}

Array Block Division Part 6

Problem Link

Point Insertion, Point Query

Since the array length can change, we can't use traditional arrays and block division. We use vectors to maintain each block. When inserting, we directly use the vector's insert function. However, if we allow unlimited insertions, block sizes will become unbalenced, defeating the purpose of block division. Therefore, when a block becomes too large (exceeding 20 × sqrt(n)), we forcefully rebalance the blocks.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAX_N = 2e5 + 5;
const int MAX_M = 1e3 + 5;

int n, blockSize, blockCount;
int arr[MAX_N];
int blockId[MAX_N];
vector<int> blocks[MAX_M];

void rebuild()
{
	int total = 0, sz;
	for (int i = 1; i <= blockCount; i++)
	{
		sz = blocks[i].size();
		for (int j = 0; j < sz; j++)
			arr[++total] = blocks[i][j];
		blocks[i].clear();
	}
	if (!total)
		total = n;
	blockSize = sqrt(total);
	blockCount = ceil(total * 1.0 / blockSize);
	for (int i = 1; i <= total; i++)
		blockId[i] = (i - 1) / blockSize + 1;
	for (int i = 1; i <= total; i++)
		blocks[blockId[i]].push_back(arr[i]);
}

void insertAt(int pos, int value)
{
	int currentBlock = 1;
	while (currentBlock <= blockCount && pos > blocks[currentBlock].size())
	{
		pos -= blocks[currentBlock].size();
		currentBlock++;
	}
	blocks[currentBlock].insert(blocks[currentBlock].begin() + pos - 1, value);
	if (blocks[currentBlock].size() > 5 * blockSize)
		rebuild();
}

int queryAt(int pos)
{
	int currentBlock = 1;
	while (currentBlock <= blockCount && pos > blocks[currentBlock].size())
	{
		pos -= blocks[currentBlock].size();
		currentBlock++;
	}
	return blocks[currentBlock][pos - 1];
}

int main()
{
	int op, l, r, c;
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	rebuild();
	for (int i = 1; i <= n; i++)
	{
		cin >> op >> l >> r >> c;
		if (op == 0)
			insertAt(l, r);
		else
			cout << queryAt(r) << endl;
	}
	return 0;
}

Array Block Division Part 7

Problem Link

Range Multiplication, Range Addition, Point Query

Similar to segment trees, we need to maintain both addition and multiplication marks. The priority of these marks needs careful consideration. When updating addition marks, multiplication marks remain unchanged. However, when updating multiplication marks, both the original sequence values and addition marks must be adjusted.

We can conceptualize this with addition mark 'a' and multiplication mark 'm'. For an original value 'x', after multiplying by 'n', the value becomes n × (x × m + a) = n × x × m + n × a. When operating on incomplete blocks, we must first apply the marks to the original sequence to ensure correct ordering of operations.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 1e3 + 5;
const int MOD = 10007;

int n;
vector<int> blockId(MAX_N);
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<long long> arr(MAX_N);
vector<long long> addMark(MAX_M);
vector<long long> mulMark(MAX_M);

void clearBlock(int blockNum)
{
	for (int i = blockStart[blockNum]; i <= blockEnd[blockNum]; i++)
		arr[i] = ((arr[i] * mulMark[blockNum]) % MOD + addMark[blockNum]) % MOD;
	mulMark[blockNum] = 1;
	addMark[blockNum] = 0;
}

void addRange(int left, int right, long long value)
{
	if (blockId[left] == blockId[right])
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= right; i++)
			arr[i] = (arr[i] + value) % MOD;
	}
	else
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= blockEnd[blockId[left]]; i++)
			arr[i] = (arr[i] + value) % MOD;
		clearBlock(blockId[right]);
		for (int i = blockStart[blockId[right]]; i <= right; i++)
			arr[i] = (arr[i] + value) % MOD;
		for (int i = blockId[left] + 1; i < blockId[right]; i++)
			addMark[i] = (addMark[i] + value) % MOD;
	}
}

void mulRange(int left, int right, long long value)
{
	if (blockId[left] == blockId[right])
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= right; i++)
			arr[i] = (arr[i] * value) % MOD;
	}
	else
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= blockEnd[blockId[left]]; i++)
			arr[i] = (arr[i] * value) % MOD;
		clearBlock(blockId[right]);
		for (int i = blockStart[blockId[right]]; i <= right; i++)
			arr[i] = (arr[i] * value) % MOD;
		for (int i = blockId[left] + 1; i < blockId[right]; i++)
		{
			mulMark[i] = (mulMark[i] * value) % MOD;
			addMark[i] = (addMark[i] * value) % MOD;
		}
	}
}

long long queryPoint(int pos)
{
	return ((arr[pos] * mulMark[blockId[pos]]) % MOD + addMark[blockId[pos]]) % MOD;
}

int main()
{
	int op, l, r;
	long long c;
	cin >> n;
	int blockSize = sqrt(n);
	int blockCount = ceil(n * 1.0 / blockSize);
	for (int i = 1; i <= blockCount; i++)
	{
		blockStart[i] = (i - 1) * blockSize + 1;
		blockEnd[i] = i * blockSize;
		mulMark[i] = 1;
	}
	blockEnd[blockCount] = n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		blockId[i] = (i - 1) / blockSize + 1; 
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> op >> l >> r >> c;
		if (op == 0)
			addRange(l, r, c);
		else if (op == 1)
			mulRange(l, r, c);
		else
			cout << queryPoint(r) << endl;
	}
	return 0;
}

Array Block Division Part 8

Problem Link

Range Assignment, Query Elements Equal to X

This problem is similar to Part 2 but requires optimizaton to avoid timeout. We maintain a mark indicating the value assigned to a complete block, initialized to infinity (meaning no assignment). For each query, if there are incomplete blocks at the ends, we scan them directly. If an element equals x, we increment the count; otherwise, we set the element to x.

For complete blocks, if there's an assignment mark, we check if it equals x. If it does, the entire block equals x, and we add the block length to our count. Otherwise, we update the block mark to x. If there's no assignment mark, we perform a direct scan and update, then set the mark. Remember to clear marks before operations.

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
#define int long long

const int MAX_N = 1e5 + 5;
const int MAX_M = 1e3 + 5;
const long long INF = 1e18;

int n;
vector<int> arr(MAX_N);
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<long long> lazyAssign(MAX_M);

void clearBlock(int blockNum)
{
	if (lazyAssign[blockNum] == INF)
		return;
	for (int i = blockStart[blockNum]; i <= blockEnd[blockNum]; i++)
		arr[i] = lazyAssign[blockNum];
	lazyAssign[blockNum] = INF;
}

int solveRange(int left, int right, long long x)
{
	int count = 0;
	if (blockId[left] == blockId[right])
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= right; i++)
		{
			if (arr[i] == x)
				count++;
			else
				arr[i] = x;
		}
	}
	else
	{
		clearBlock(blockId[left]);
		for (int i = left; i <= blockEnd[blockId[left]]; i++)
		{
			if (arr[i] == x)
				count++;
			else
				arr[i] = x;
		}
		clearBlock(blockId[right]);
		for (int i = blockStart[blockId[right]]; i <= right; i++)
		{
			if (arr[i] == x)
				count++;
			else
				arr[i] = x;
		}
		for (int i = blockId[left] + 1; i < blockId[right]; i++)
		{
			if (lazyAssign[i] != INF)
			{
				if (lazyAssign[i] == x)
					count += (blockEnd[i] - blockStart[i] + 1);
				else
					lazyAssign[i] = x;
			}
			else
			{
				for (int j = blockStart[i]; j <= blockEnd[i]; j++)
				{
					if (arr[j] == x)
						count++;
					else
						arr[j] = x;
				}
				lazyAssign[i] = x;
			}
		}
	}
	return count;
}

signed main()
{
	int l, r, c;
	cin >> n;
	int blockSize = sqrt(n);
	int blockCount = ceil(n * 1.0 / blockSize);
	for (int i = 1; i <= blockCount; i++)
	{
		blockStart[i] = (i - 1) * blockSize + 1;
		blockEnd[i] = i * blockSize;
		lazyAssign[i] = INF;
	}
	blockEnd[blockCount] = n;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
		blockId[i] = (i - 1) / blockSize + 1;
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> l >> r >> c;
		cout << solveRange(l, r, c) << endl;
	}
	return 0;
}

Array Block Division Part 9

Problem Link

Static Range Mode Query

This is the most challenging problem in the series. The key observation is that the mode of range [l, r] can only be the mode of the left incomplete block, the right incomplete block, or the mode of the complete blocks in between.

We can optimize by preprocessing. Let f[i][j] be the mode of blocks from i to j. For queries, we can directly use this preprocessed table. To check if a number is the mode efficiently, we first discretize the sequence. For each value, we store its positions in a vector. This allows us to count occurrences in a range using binary search.

The block size is crucial here. Using sqrt(n) causes timeouts, but values between 150-300 have been tested successfully. We also need mappings between values and their discretized indices.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 1e3 + 5;

int n;
vector<int> blockStart(MAX_M), blockEnd(MAX_M);
vector<int> blockId(MAX_N);
vector<int> arr(MAX_N), val(MAX_N), cnt(MAX_N);
vector<vector<int>> pos(MAX_MAX_N);
vector<vector<int>> f(MAX_M, vector<int>(MAX_M));
map<int, int> valueToRank;

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

int getFrequency(int left, int right, int x)
{
	return upper_bound(pos[x].begin(), pos[x].end(), right) - 
	       lower_bound(pos[x].begin(), pos[x].end(), left);
}

void preprocess(int blockNum)
{
	int currentMode = 0, maxFreq = 0;
	fill(cnt.begin(), cnt.end(), 0);
	for (int i = blockStart[blockNum]; i <= n; i++)
	{
		cnt[arr[i]]++;
		if (cnt[arr[i]] > maxFreq)
		{
			maxFreq = cnt[arr[i]];
			currentMode = arr[i];
		}
		else if (cnt[arr[i]] == maxFreq && val[arr[i]] < val[currentMode])
			currentMode = arr[i];
		f[blockNum][blockId[i]] = currentMode;
	}
}

int queryRange(int left, int right)
{
	int currentMode = 0, currentFreq, maxFreq = 0;
	if (blockId[left] == blockId[right])
	{
		for (int i = left; i <= right; i++)
		{
			currentFreq = getFrequency(left, right, arr[i]);
			if (currentFreq > maxFreq)
			{
				maxFreq = currentFreq;
				currentMode = arr[i];
			}
			else if (currentFreq == maxFreq && val[arr[i]] < val[currentMode])
				currentMode = arr[i];
		}
	}
	else
	{
		currentMode = f[blockId[left] + 1][blockId[right] - 1];
		maxFreq = getFrequency(left, right, currentMode);
		for (int i = left; i <= blockEnd[blockId[left]]; i++)
		{
			currentFreq = getFrequency(left, right, arr[i]);
			if (currentFreq > maxFreq)
			{
				maxFreq = currentFreq;
				currentMode = arr[i];
			}
			else if (currentFreq == maxFreq && val[arr[i]] < val[currentMode])
				currentMode = arr[i];
		}
		for (int i = blockStart[blockId[right]]; i <= right; i++)
		{
			currentFreq = getFrequency(left, right, arr[i]);
			if (currentFreq > maxFreq)
			{
				maxFreq = currentFreq;
				currentMode = arr[i];
			}
			else if (currentFreq == maxFreq && val[arr[i]] < val[currentMode])
				currentMode = arr[i];
		}
	}
	return val[currentMode];
}

int main()
{
	int l, r, rankCount = 0;
	n = readInt();
	int blockSize = 150;
	int blockCount = ceil(n * 1.0 / blockSize);
	for (int i = 1; i <= blockCount; i++)
	{
		blockStart[i] = (i - 1) * blockSize + 1;
		blockEnd[i] = i * blockSize;
	}
	blockEnd[blockCount] = n;
	for (int i = 1; i <= n; i++)
	{
		arr[i] = readInt();
		blockId[i] = (i - 1) / blockSize + 1;
		if (!valueToRank.count(arr[i]))
		{
			valueToRank[arr[i]] = ++rankCount;
			val[rankCount] = arr[i];
		}
		arr[i] = valueToRank[arr[i]];
		pos[arr[i]].push_back(i);
	}
	for (int i = 1; i <= blockCount; i++)
		preprocess(i);
	for (int i = 1; i <= n; i++)
	{
		l = readInt();
		r = readInt();
		cout << queryRange(l, r) << endl;
	}
	return 0;
}