【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目

class Solution {
public:
  vector<long long> countOfPairs(int n, int x, int y) {   
    vector<long long> vRet(n);
    if (x == y)
    {
      vRet.clear();
      for (int i = n - 1; i >= 0; i--)
      {
        vRet.emplace_back(i * 2);
      }
      return vRet;
    }
    if (x > y )
    {
      swap(x, y);
    }
    x--;
    y--;
    int i = 0;
#define Path1(j) (j - i -1 )
    auto Path2 = [&i,&x,&y]( const int j)
    {
      return abs(i - x) + abs(j - y);
    };
    vector<long long> vDiff(n);
    auto Add = [&](int left, int len)
    {
      if (len <= 0)
      {
        return;
      }
      vDiff[left] += 2 ;
      vDiff[left+len] -= 2 ;
    };
    for (; i < x; i++)
    {
      //j 在[y,n)
      const int iy = max(i + 1, y);
      if (n - iy > 0)
      {
        Add(Path2(iy), n - iy);
      } 
      //j在(i,y)
      if( y - i -1 > 0 )
      {//i->x->y-j [j0,y)
        const int j0 = (x + y + 2) / 2; 
        Add(Path2(y-1), y - j0);
        //(i,j0)
        Add(0, j0 - i - 1);
      }
    }
    for (; i < n; i++)
    {
      //j在(max(y-1,i),n)
      if (2*i <= x + y-1)
      {//i->x->y-j
        Add(Path2(max(y-1, i) +1), n - max(y-1, i) -1);
      }
      else
      {
        Add(Path1(max(y-1, i) +1), n - max(y-1, i) -1);
      }
      //j在(i,y)
      if (y - i - 1 > 0)
      {
        int j0 = min(y,(2 * i + y - x + 2) / 2);
        j0 = max(j0, i + 1);
        //if (y - j0 >= 0)
        {
          //j在[j0,y) i->x->y-j 
          Add(Path2(y - 1), y - j0);
          //j在(i,j0)
          Add(0, j0 - i - 1);
        }
      }
    }
    long long cur=0;
    for (int i = 0; i < n; i++)
    {
      cur += vDiff[i];
      vRet[i] = cur;
    }
    return vRet;
  }
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int n,  x,  y;
  {
    Solution sln;
    n = 6, x = 1, y = 5;
    auto res = sln.countOfPairs(n, x, y);
    Assert(res, vector<long long>{ 12, 14, 4, 0, 0, 0 });
  }
  {
    Solution sln;
    n = 3, x = 2, y = 2;
    auto res = sln.countOfPairs(n, x, y);
    Assert(res, vector<long long>{4, 2, 0});
  }
  {
    Solution sln;
    n = 4, x = 1, y = 1;
    auto res = sln.countOfPairs(n, x, y);
    Assert(res, vector<long long>{6, 4, 2, 0});
  }
  {
    Solution sln;
    n = 5, x = 2, y = 4;
    auto res = sln.countOfPairs(n, x, y);
    Assert(res, vector<long long>{10, 8, 2, 0, 0});
  }
  {
    Solution sln;
    n = 3, x = 1, y = 3;    
    auto res = sln.countOfPairs(n,x,y);
    Assert(res, vector<long long>{6, 0, 0});
  }   
  {
    Solution sln;
    n = 2, x = 2, y = 2;
    auto res = sln.countOfPairs(n, x, y);
    Assert(res, vector<long long>{2, 0});
  }
}