Sum Of Imbalance Numbers Of All Subarrays - Made Easy
Note  \nprev is used to keep the track of number of indices where\n(sarr[i+1] - sarr[i] > 1) for each subarray.\n\n# Approach\nWe just simply brute force for ea
# Note  \nprev is used to keep the track of number of indices where\n(sarr[i+1] - sarr[i] > 1) for each subarray.\n\n# Approach\nWe just simply brute force for each subarray say the range from [i,j] as [l,r].\nKeep on adding all the elements in ordered set.\nOrdered Set is used to get the just smallest & greater element in [l,r] of current element.\n\nNow if adding this element reduces the difference between just greater & smaller element then we reduce the prev.\ne.g. os = {2,4}, curr = 3\nNow due to diff between 2 & 4 being 2 this subarray was contributing to the answer, but now as of we add 3 the subarray in sorted form becomes = {2,3,4} & so this subarray contributes as 0 & thus we reduces the prev.\n\nAnd now when the newly added element is contributing to the ans, then we simply increment prev,\ne.g. os = {5} curr = 1\nos = {1,5} we check left & right of curr, calculate the diff & if the diff != 1 then we simply increase the prev\n\n# Complexity\n- Time complexity: $$O(n*n*log(n))$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n#include<bits/stdc++.h>\n#include<iomanip>\n#include <deque>\n#include <bitset>\n#include <cstdint>\n#include <ext/pb_ds/assoc_container.hpp> // Common file\n#include <ext/pb_ds/tree_policy.hpp>\nusing namespace __gnu_pbds;\n#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>\n#define ll long long int\n#define all(a) a.begin(),a.end()\n#define enter(a) for(ll i=0;i<a.size();i++) cin>>a[i];\n#define forj(n) for (ll j = 0; j < n; j++)\n#define show(a) for(auto e: a) cout<<e<<" "; cout<<endl;\nusing namespace std;\n\nclass Solution {\npublic:\n    int sumImbalanceNumbers(vector<int>& v) {\n        ll n = v.size(),ans = 0;\n        for(ll i = 0;i<n;++i){\n            ordered_set os;\n            ll prev = 0;\n            for(ll j = i;j<n;++j){\n                if(os.find(v[j]) != os.end()){\n                    ans+=prev;\n                    continue;\n                }\n                os.insert(v[j]);\n\n                ll idx = os.order_of_key(v[j]);\n                ll l = -1,r = -1;\n                if(idx > 0){\n                    l = v[j]-(*os.find_by_order(idx-1));\n                }\n                if(idx+1 < os.size()){\n                    r = (*os.find_by_order(idx+1))-v[j];\n                }\n\n                // Check if we can reduce prev or not\n                if(l == 1 and r == 1){--prev;}\n\n                // If it\'s only 1 element in the subarray then no need to perform any increments\n                if((l != 1) and (r != 1) and (os.size() > 1)){++prev;}\n                ans += prev;\n            }\n        }\n        return ans;\n    }\n};\n```
['Ordered Set', 'C++']