C++ Three Reigions O(n) Solution Explained || Runtime < 80%
Intuition\n Describe your first thoughts on how to solve this problem. \n- Consider unidirectional pairs first where i>j for each pair (I,j).\n- Define solution
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Consider unidirectional pairs first where i>j for each pair (I,j).\n- Define solution for single line as f(x), where x is number of houses connected without getting involved with the shortcut. So f(x) returns {x-1, x-2,\u2026.., 2, 1, 0}. If y-x<=1, the answer is simply f(n).\n- Divide the graph into three regions: \u2018l\u2019 where each house belongs to [1,x) , \u2018m\u2019 where each house belongs to [x,y] , and \u2018r\u2019 where each house belongs to (y,n]. Then we classify the pairs into six categories: ll,lm,lr,mm,mr,rr. The first letter represents the region of the start point and the second letter represents the region of the destination\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nSet up six functions ll(), lm(), lr(), mm(), mr(), rr(). Each function will update the final answer a[] according to the pairs of the corresponding type:\n- ll: Both are to the left of x, so ll() is will update the answer by adding f(x-1)\n- rr: Simlar to ll(), rr() will add f(n-y) to the answer\n- mm: both are inside a circle of cf=(y-x+1) circumference. If i is the non-shortcut distance of a pair, then if(i<=cf/2) a[i]+=(y-x-i)  (without shortcut) else a[cf-i]+= (y-x-i) (with shortcut)\n- lr: we can simply the graph as a single line of three sections l, shortcut,r. So their length is l1, 1, l2. The line length is l1+l2+1. So the lr() will update the answer by adding f(l1+l2+1) - cases where both houses are within [1,y] or [x,n]. That gives us f(l1+l2+1) - f(l1+1) \u2013f(l2+1) + 1, the \u201C+1\u201D is due to that we eliminates the pair (x,y) twice\n- lm: find the mid point between x and y first, it should be x+h where h=(y-x+1)/2. So if the destination is <=x+h, we don\'t need shortcut. Otherwise we use shortcut. So the simplified graph for lm() is a line with two branches diverging from x. So one branch is x=h long and the other is x+(y-x-h)= y-h long. Handle each branch like a single-line problem, remove pairs that are both to x\u2019s left or x\u2019right.\n- mr: just reverse house numbers, so we can call lm directly to update the solution. \n# Note:\nSometimes region l or r may not exist that\u2019s why we use a lot min() or max() in the code. The above explanation only consider the unidirectional scenario, so for the final answer, each amount need to be doubled. \n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n# Code\n```\nclass Solution {\npublic:\n  \n    vector<long long> countOfPairs(int n, int x, int y) {\n       ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);\n       vector<long long> a(n+1,0);\n       if(x>y) {int tmp=x; x=y; y=tmp;}\n       if(y-x<2){//shortcut ignored\n           for(int i=1;i<=n-1;i++) a[i]=2*(n-i);\n           vector<long long> b(a.begin() + 1, a.end());\n           return b;\n       }  \n       ll(a,1,x-1);\n       lm(a,1,x-1,x,y);\n       lr(a,1,x-1,y+1,n);\n       mm(a,x,y);\n       mr(a,x,y,y+1,n);\n       rr(a,y+1,n); \n       vector<long long> b(a.begin() + 1, a.end());\n       return b;\n    }\nvoid ll(vector<long long>& a,int st, int ed){\n    if (ed<=st) return; \n    for (int i=1;i<=ed-st;i++) a[i]+=2*(ed-st+1-i);\n}\nvoid lm(vector<long long>&a,int st1, int st2, int ed1, int ed2){\n    if(st2<st1) return;\n    int k=ed1-st1;//x-1\n    int l= ed2-ed1;//y-x\n    int h= (1+l)/2;\n    for(int i=1;i<=k+h;i++) a[i]+=2*(k+h-i+1); //without shortcut\n    for(int i=1;i<=k-1;i++) \n         a[i]-=2*(k-i); //remove those pairs completely to x\'s left\n    for(int i=1;i<=h;i++) \n      a[i]-=2*(h-i+1); //remove those pairs completely to x\'s right(inclusive)\n    int z=k+l-h;\n  \n    for(int i=2;i<=z;i++) \n        a[i]+=2*(z-i+1);// with shortcut \n     for(int i=2;i<=k;i++) \n         a[i]-=2*(k-i+1); //remove those pairs completely to x\'s left(inclusive)\n  for(int i=2;i<=l-h;i++) \n      a[i]-=2*(l-h-i+1); //remove those pairs completely to x\'s right\n}\nvoid mm(vector<long long>&a,int st, int ed){\n    int l=ed-st;\n   int h= (l +1)/2;\n    for(int i=1;i<=l;i++){\n        if(i<=h) a[i]+=2*(l-i+1);\n        else a[l+1-i]+=2*(l-i+1);\n        //cout<<2*(l-i+1)<<endl;\n    }\n}\nvoid rr(vector<long long>& a,int st, int ed){\n    if (ed<=st) return;\n    for (int i=1;i<=ed-st;i++) a[i]+=2*(ed-st+1-i);\n}\n void lr(vector<long long>& a,int st1, int st2, int ed1, int ed2){\nif(st2<st1) return;\n     if(ed2<ed1) return;\n     int l1=st2-st1+1; int l2=ed2-ed1+1;\n     int l= l1 + 1+ l2;\n    // cout<<l1<<" "<<l2;\n    for (int i=1;i<=l;i++) a[i]+=2*(l+1-i)-max(0,2*(l1+2-i)) - max(0, 2*(l2+2-i));\n    a[1]+=2; // eliminate (x,y)\n}\nvoid mr(vector<long long>&a,int st1, int st2, int ed1, int ed2){\n    if (ed1>ed2) return;\n    //reverse house numbers \n    int n=ed2;\n    int s1= n+1-ed2;\n    int s2= n+1-ed1;\n    int e1= n+1-st2;\n    int e2= n+1-st1;\n    lm(a,s1,s2,e1,e2);\n}\n};\n```
['Array', 'C++']