Bloom Filter + SQRT decomposition
Intuitionuse bloom filter to save elements.Approachsqrt decomposition + bloom filterComplexity

Time complexity: O(qn​+n)


Space complexity: O(n​(BF_SIZE)/64+n
# Intuition
use bloom filter to save elements.

# Approach
sqrt decomposition + bloom filter

# Complexity
- Time complexity: $O(q \sqrt{n} + n)$

- Space complexity: $O(\sqrt{n}  (BF\_SIZE) / 64 + n)$

# Code
```cpp []
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // BloomFilter con 3 funciones hash
    struct BloomFilter {
        // Ajusta el tamaño para reducir colisiones (ej. 1e6)
        static const int BF_SIZE = 600000; 
        bitset<BF_SIZE> bits;

        // 1ra función hash
        int hash1(long long x) {
            x ^= (x << 13);
            x ^= (x >> 7);
            x ^= (x << 17);
            return (int)((x % BF_SIZE + BF_SIZE) % BF_SIZE);
        }

        // 2da función hash
        int hash2(long long x) {
            x = ~x + (x << 15); 
            x = x ^ (x >> 12);
            x = x + (x << 2);
            x = x ^ (x >> 4);
            x = x * 2057; 
            x = x ^ (x >> 16);
            return (int)((x % BF_SIZE + BF_SIZE) % BF_SIZE);
        }

        // 3ra función hash (podrías usar otra variante)
        int hash3(long long x) {
            // Un hash distinto, p. ej. basado en una mezcla
            x ^= 0x9e3779b97f4a7c15ULL; // constante de 64 bits
            x ^= (x >> 23);
            x *= 0xff51afd7ed558ccdULL;
            x ^= (x >> 23);
            x *= 0xc4ceb9fe1a85ec53ULL;
            x ^= (x >> 23);
            return (int)((x % BF_SIZE + BF_SIZE) % BF_SIZE);
        }

        void insertValue(long long val) {
            bits.set(hash1(val), true);
            bits.set(hash2(val), true);
            bits.set(hash3(val), true);
        }

        bool mightContain(long long val) {
            return bits.test(hash1(val)) 
                && bits.test(hash2(val)) 
                && bits.test(hash3(val))
                ;
        }
    };

    int circularDist(int i, int j, int n) {
        int diff = abs(i - j);
        return min(diff, n - diff);
    }

    vector<int> solveQueries(vector<int>& nums, vector<int>& queries) {
        int n = (int)nums.size();
        int q = (int)queries.size();
        int blockSize = (int) floor(sqrt(2 * n)) + 1;
        blockSize = min(blockSize, n);
        int numBlocks = (n + blockSize - 1) / blockSize;

        vector<BloomFilter> bloomFilters(numBlocks);

        vector<vector<int>> blockElements(numBlocks);

        for(int i = 0; i < n; i++){
            int b = i / blockSize;
            blockElements[b].push_back(i);
        }

        for(int b = 0; b < numBlocks; b++){
            for(int idx : blockElements[b]){
                long long val = nums[idx];
                bloomFilters[b].insertValue(val);
            }
        }

        vector<int> answer(q, -1);

        for(int i = 0; i < q; i++){
            int queryIndex = queries[i];
            long long val = nums[queryIndex];
            int startBlock = queryIndex / blockSize;

            int bestDist = INT_MAX;
            bool found = false;

            vector<int> blocksToCheck;
            bool t = 0;
            bool left = 0, right = 0;
            if (bloomFilters[startBlock].mightContain(val)) {
                for(int idx : blockElements[startBlock]) {
                    if(nums[idx] == val && idx != queryIndex) {
                        if (idx < queryIndex) left = 1;
                        else right = 1;
                        t = 1;
                        found = 1;
                        int dist = circularDist(queryIndex, idx, n);
                        bestDist = min(bestDist, dist);
                    }
                }
            }
            for(int d = 1; d < (t ? min(3, numBlocks) : numBlocks); d++){
                int leftBlock = startBlock - d;
                int rightBlock = startBlock + d;
                if (left && right) break;

                if (leftBlock < 0) leftBlock += numBlocks;
                if (rightBlock >= numBlocks) rightBlock -= numBlocks;

                if (!left && bloomFilters[leftBlock].mightContain(val)) {
                    left = 1;
                    blocksToCheck.emplace_back(leftBlock);
                }
                if (!right && bloomFilters[rightBlock].mightContain(val)) {
                    right = 1;
                    blocksToCheck.emplace_back(rightBlock);
                }
            }
            for(int b : blocksToCheck) {
                for(int idx : blockElements[b]) {
                    if(nums[idx] == val && idx != queryIndex) {
                        found = 1;
                        int dist = circularDist(queryIndex, idx, n);
                        bestDist = min(bestDist, dist);
                    }
                }
            }
            if(found) {
                answer[i] = bestDist;
            } else {
                answer[i] = -1;
            }
        }

        return answer;
    }
};

```
['C++']