[C++] Mo's Algorithm
It\'s probably not the best idea. I just wanted to check the feasibility.\n\nTime complexity: O((n+m)*sqrt(n)*log(n) + m*log(m))\n\n\nusing ti3 = tuple<int,int,
It\'s probably not the best idea. I just wanted to check the feasibility.\n\nTime complexity: ```O((n+m)*sqrt(n)*log(n) + m*log(m))```\n\n```\nusing ti3 = tuple<int,int,int>;\nconst int inf = 1e9;\n\nclass Solution {\npublic:\n    vector<bool> checkArithmeticSubarrays(vector<int>& a, vector<int>& ql, vector<int>& qr) {\n        int n = a.size(), q = ql.size(), sz = sqrt(n);\n        map<int,vector<ti3>> mo;\n        for (int i=0; i<q; i++) {\n            int l = ql[i], r = qr[i];\n            mo[l/sz].push_back({r,l,i});\n        }\n        \n        int i=0, j=0, mul = 0;\n        map<int,int> mp1, mp2;\n        mp1[a[0]]++;\n\n        auto inc1 = [&] (int x) { if (++mp1[x] == 2) mul++; };\n        auto dec1 = [&] (int x) {\n            if (mp1[x] == 2) mul--;\n            if (--mp1[x] == 0) mp1.erase(x);\n        }; \n        auto inc2 = [&] (int x) { mp2[x]++; };\n        auto dec2 = [&] (int x) { if (--mp2[x] == 0) mp2.erase(x); };\n        \n        auto lr = [&] (int x) {\n            auto it1 = mp1.lower_bound(x);\n            auto it2 = mp1.upper_bound(x);\n            int l = (it1 == mp1.begin()) ? inf : prev(it1)->first;\n            int r = (it2 == mp1.end()) ? inf : it2->first;\n            return make_pair(l,r);\n        };\n\n        auto push = [&] (int x) {\n            auto [l,r] = lr(x);\n            if (!mp1.count(x)) {\n                if (l != inf) inc2(x-l);\n                if (r != inf) inc2(r-x);\n                if (l != inf && r != inf) dec2(r-l);\n            }\n            inc1(x);\n        };\n\n        auto pop = [&] (int x) {\n            auto [l,r] = lr(x);\n            if (mp1[x] == 1) {\n                if (l != inf) dec2(x-l);\n                if (r != inf) dec2(r-x);\n                if (l != inf && r != inf) inc2(r-l);\n            }\n            dec1(x);\n        };\n        \n        vector<bool> ans(q);\n        for (auto &[_,rli] : mo) {\n            sort(rli.begin(), rli.end());\n            for (auto [r,l,idx] : rli) {\n                while (i!=l || j!=r) {\n                    if (r>j) push(a[++j]);\n                    else if (l<i) push(a[--i]);\n                    else if (r<j) pop(a[j--]);\n                    else if (l>i) pop(a[i++]);\n                }\n                if (mul+mp2.size()==1) ans[idx] = 1;\n            }\n        }\n        return ans;\n    }\n}; \n```
['C']