TopCoder TCO Round2C 500 ThreePoints

// （BITのコードは省略）

#define all(c) (c).begin(), (c).end()
#define iter(c) __typeof((c).begin)
#define cpresent(c, e) (find(all(c), (e)) != (c).end())
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define tr(c, i) for(iter(c) i = (c).begin(); i != (c).end(); ++i)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)

typedef long long ll;

const static int inf = 1e18;
const static int mod = 1000000007;

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<pair<ll, int> > x(n);
    vector<pair<ll, int> > y(n);
    vector<int> perm(n);
    x[0] = mp(xzero, 0);
    y[0] = mp(yzero, 0);
    rep(i, n-1) {
      x[i+1].first = (x[i].first * xmul + xadd) % xmod;
      x[i+1].second = i+1;
      y[i+1].first = (y[i].first * ymul + yadd) % ymod;
      y[i+1].second = i+1;
    }

    sort(all(x));
    sort(all(y));
    map<int, int> ranky;
    rep(i, n) {
      ranky[y[i].second] = i;
    }

    rep(i, n) {
      perm[i] = ranky[x[i].second];
    }

    ll ans = 0;
    vector<ll> ur(n);
    {
      BIT<ll> bity(n);
      for(int i = n-1; i >= 0; --i) {
	ur[i] = n-i-1-(bity.sum(0, perm[i]));
	ans += ur[i]*(ur[i]-1)/2;
	bity.update(perm[i], 1ll);
      }
    }

    {
      BIT<ll> bity2(n);
      vector<ll> ld(n);
      for(int i = 0; i < n; ++i) {
	ld[i] = bity2.sum(0, perm[i]);
	ans -= ur[i] * ld[i];
	bity2.update(perm[i], 1ll);
      }
    }

    return ans;
  }
};