http://www.lydsy.com/JudgeOnline/problem.php?id=1227

離散化、樹狀數組。

const int N = int(1e5) + 9, K = 10 + 1; PII P[N]; int C[N][K]; int L[N], R[N], n, k; namespace BIT{ int S[N]; void Add(int x){ int d = -C[L[x]][k]*C[R[x]][k] + C[++L[x]][k]*C[--R[x]][k]; for (;x<=n;x+=low_bit(x)) S[x] += d; } int Sum(int x){ int z = 0; for (;x;x^=low_bit(x)) z += S[x]; return z; } int Sum(int l, int r){ return Sum(r) - Sum(l-1); } } using namespace BIT; void init(){ int _; RD(_,_,n); REP(i, n) RD(P[i].fi,P[i].se); RD(k); REP(i, n){C[i][0] = 1; REP_1_C(j, min(k, i)) C[i][j] = C[i-1][j-1] + C[i-1][j]; } sort(P, P+n); for (int x=1,i=0;i<n;++x){ int ii = i + 1; while (ii < n && P[ii].fi == P[i].fi) P[ii++].fi = x; P[i].fi = x; i = ii; } REP(i, n){ swap(P[i].fi, P[i].se); ++R[P[i].se]; } } int solve(){ int z = 0; sort(P, P+n); for (int i=0;i<n;){ int ii = i + 1; while (ii < n && P[ii].fi == P[i].fi) ++ii; int a = 0, b = ii-i; FOR(j, i, ii){ if (a >= k && b >= k) z += C[a][k]*C[b][k]*Sum(P[j-1].se+1, P[j].se-1); Add(P[j].se); ++a,--b; } i = ii; } return z; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); #endif init(); OT(solve() & 0x7fffffff); }