cafelier@SRM

TCO12 R2C 500

04:32 |

左下にある点の個数と右下にある点の個数を２パスで数えて３パス目で集計したけれど、１パスでできるなあと気づいて感心して書き直した物。

template<typename T=LL>
struct FenwickTree
{
   vector<T> x;
   FenwickTree(size_t n) : x(n) {}

   void incr( int k, const T& a ) { // z[k] += a;
      for(; k < x.size(); k|=k+1)
         x[k] += a;
   }
   T sum(int i, int j) { // Sigma z[i,j) excl.
      return sum_impl(j-1) - sum_impl(i-1);
   }
   T sum_impl(int j) { // Sigma z[0,j] incl.
      T v = T();
      for(; j>=0; j=(j&(j+1))-1)
         v += x[j];
      return v;
   }
};

template<typename T>
std::vector<int> compress(std::vector<T>& xs)
{
   std::vector< pair<T,int> > xi;
   for(int i=0; i<xs.size(); ++i)
      xi.push_back( make_pair(xs[i], i) );
   sort(xi.begin(), xi.end());

   std::vector<int> result(xs.size());
   for(int k=0; k<xi.size(); ++k)
      result[xi[k].second] = k;
   return result;
}

class ThreePoints { public:
   long long countColoring(int N,
      int xzero, int xmul, int xadd, int xmod,
      int yzero, int ymul, int yadd, int ymod)
   {
      vector<int> x(N), y(N);
      x[0] = xzero; for(int i=1; i<N; ++i) x[i] = (x[i-1] * LL(xmul) + xadd) % xmod;
      y[0] = yzero; for(int i=1; i<N; ++i) y[i] = (y[i-1] * LL(ymul) + yadd) % ymod;
      x = compress(x);
      y = compress(y);

      vector< pair<int,int> > y_desc;
      for(int i=0; i<N; ++i)
         y_desc.push_back(make_pair(y[i], x[i]));
      sort(y_desc.rbegin(), y_desc.rend());

      LL result = 0;
      FenwickTree<> p(N), sp(N);
      for(int i=0; i<N; ++i) {
         const int x = y_desc[i].second;
         LL sp_  = p.sum(x+1, N);
         LL ssp_ = sp.sum(x+1, N);
         p.incr(x, 1);
         sp.incr(x, sp_);
         result += sp_*(sp_-1)/2 - ssp_;
      }
      return result;
   }
};

• 配列に突っ込みやすくするために座標を 0 ～ N-1 に圧縮する。で、
• p[x] はその x 座標にある点の数
• sp[x] はその x 座標にある点、より右上にある点の数
• y 座標が大きい点から順に情報を入れていく
  • p[cur.x] += 1;
  • sp[cur.x] += (p[cur.x+1]+p[cur.x+2]+...);
  • 現在の点curを左下にする三角形の個数は sp*(sp-1)/2。
  • ただし、そのうちxとyが同じ順に増えるものは除く。その個数は sp[cur.x+1]+sp[cur.x+2]+...
• 以上