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

Posted by xiaodao
Category: BZOJ