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);
}
