Advanced: C++ solution with Mo's Algorithm
We note that the queries are offline, and can be solved in Mo\'s order. Lets store all the current "alive" numbers in a multiset (vals in my code). Additionally
We note that the queries are offline, and can be solved in [Mo\'s order](https://www.hackerearth.com/practice/notes/mos-algorithm/). Lets store all the current "alive" numbers in a multiset (`vals` in my code). Additionally, store the *differences* between consecutive alive numbers in another multiset (`diffs` in my code).\n\nAs we proceed in Mo\'s order, we will do a bunch of `add` and `remove` operations. To process these updates, we do `O(1)` updates to both multisets. For example, let\'s say our numbers are `[5,10]` and we add `7`. We will delete the difference `10-5=5`, and add the differences `7-5=2` and `10-7=3`. Removals are processed similarly.\n\nWhen we reach a query, we simply need to check whether all differences are equal (since this represents an arithmetic sequence).\n\nThe time complexity is `O(Nsqrt(N)logN + MlogM)`. Note that this time complexity should be fast enough to work for much larger `N and M`, like perhaps up to `N,M <= 50000`, while the naive quadratic solution would fail.\n\n```cpp\n#define vi array<int,3>\n#define sz(x) ((int) (x).size())\n#define all(x) (x).begin(), (x).end()\n\nclass Solution {\npublic:\n    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {\n        int N = sz(nums);\n        int M = sz(l);\n        \n        vector<vi> queries(M,vi{});\n        for (int i = 0; i < M; i++) {\n            queries[i] = {l[i],r[i],i};\n        }\n        \n        sort(all(queries),mo_cmp);\n        \n        multiset<int> diffs;\n        multiset<int> vals;\n        vector<bool> ans(M);\n        \n        int L = 0;\n        int R = -1;\n        for (vi q: queries) {\n            while(R < q[1]) {\n                R++;\n                add(nums[R],diffs,vals);\n            }\n            while(R > q[1]) {\n                remove(nums[R],diffs,vals);\n                R--;\n            }\n\n            while(L < q[0]) {\n                remove(nums[L],diffs,vals);\n                L++;\n            }\n            while(L > q[0]) {\n                L--;\n                add(nums[L],diffs,vals);\n            }\n\n            // Store the answer into required position.\n            ans[q[2]] = good(diffs);\n        }\n        \n        return ans;\n    }\n    \n    static bool mo_cmp(const vi &x, const vi &y) {\n        const int BLOCK_SIZE = 23; //this should be equal to sqrt(N), for example 200 is nice\n        int block_x = x[0] / BLOCK_SIZE;\n        int block_y = y[0] / BLOCK_SIZE;\n        if(block_x != block_y)\n            return block_x < block_y;\n        return x[1] < y[1];\n    }\n    \n    bool good(multiset<int>& ms) {\n        if (ms.empty()) return true;\n        return ((*ms.begin())==(*(--ms.end())));\n    }\n\n    bool single(multiset<int>& ms, int n) {\n        auto it = ++ms.lower_bound(n);\n        return (it==ms.end()) || (n<*it);\n    }\n    \n    void add(int n, multiset<int>& diffs, multiset<int>& vals) {\n        vals.insert(n);\n        if (sz(vals)==1) return;\n        \n        if (single(vals,n)) {\n            if (n==*vals.begin()) {\n                int R = *vals.upper_bound(n);\n                diffs.insert(R-n);\n            } else if (n==*(--vals.end())) {\n                int L = *(--vals.lower_bound(n));\n                diffs.insert(n-L);\n            } else {\n                int L = *(--vals.lower_bound(n));\n                int R = *vals.upper_bound(n);\n                diffs.erase(diffs.lower_bound(R-L));\n                diffs.insert(n-L);\n                diffs.insert(R-n);\n            }\n        } else {\n            diffs.insert(0);\n        }\n    }\n    \n    void remove(int n, multiset<int>& diffs, multiset<int>& vals) {        \n        if (single(vals,n)) {\n            if (n==*vals.begin()) {\n                int R = *vals.upper_bound(n);\n                diffs.erase(diffs.lower_bound(R-n));\n            } else if (n==*(--vals.end())) {\n                int L = *(--vals.lower_bound(n));\n                diffs.erase(diffs.lower_bound(n-L));\n            } else {\n                int L = *(--vals.lower_bound(n));\n                int R = *vals.upper_bound(n);\n                diffs.insert(R-L);\n                diffs.erase(diffs.lower_bound(n-L));\n                diffs.erase(diffs.lower_bound(R-n));\n            }\n        } else {\n            diffs.erase(diffs.lower_bound(0));\n        }\n        vals.erase(vals.lower_bound(n));\n    }\n};\n```
['C']