CF 283E Cow Tennis Tournament

2015.01.10 11:19 Sat| 1 visits oi_2015| 2015_刷题日常| Text

Solution

显然这道题可以转化为求不符合条件的三元组的个数,即答案为 $C_n^3 - \sum \limits {i = 1} ^n C{A[i]}^2)$ ,其中 A[i] 为一头奶牛能够取得胜利的次数。

可以发现,对于奶牛 i 而言,A[i] = 战力小于它的奶牛个数 - 经反转后能够战胜它的奶牛个数 + 经反转后它所能战胜的奶牛个数。后两部分可以用线段树+lazy标记维护区间异或得到。

Code

#include <bits/stdc++.h>
using namespace std;

#define N 400005
#define lson (pos << 1)
#define rson (pos << 1 | 1)


inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch-'0'; ch = getchar(); }
    return x * f;
}

vector<int> v1[N], v2[N];
long long n, k, s[N], sum[N], tag[N];

inline void reverse(int pos, int l, int r)
{
    tag[pos] ^= 1;
    sum[pos] = r - l + 1 - sum[pos];
}

void lazy(int pos, int l, int r)
{
    int mid = (l + r) >> 1;
    reverse(lson, l, mid);
    reverse(rson, mid + 1, r);
    tag[pos] ^= 1;
}

void modify(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
    {
        reverse(pos, l, r);
        return ;
    }
    if (tag[pos]) lazy(pos, l, r);
    int mid = (l + r) >> 1;
    if (x <= mid) modify(lson, l, mid, x, y);
    if (y > mid) modify(rson, mid + 1, r, x, y);
    sum[pos] = sum[lson] + sum[rson];
}

int query(int pos, int l, int r, int x, int y)
{
    if (x <= l && r <= y)
        return sum[pos];
    if (tag[pos]) lazy(pos, l, r);
    int mid = (l + r) >> 1, re = 0;
    if (x <= mid) re += query(lson, l, mid, x, y);
    if (y > mid) re += query(rson, mid + 1, r, x, y);
    return re;
}

int main()
{
    cin >> n >> k;
    for (int i = 1; i <= n; ++i)
        s[i] = read();
    sort (s + 1, s + n + 1);
    for (int i = 1; i <= k; ++i)
    {
        int l = lower_bound(s+1, s+n+1, read()) - s,
            r = upper_bound(s+1, s+n+1, read()) - s;
        v1[l].push_back(r - 1), v2[r].push_back(l);
    }
    long long ans = n * (n - 1) * (n - 2) / 6;
    for (int i = 1; i <= n; ++i)
    {
        for (auto j: v1[i])
            if (j >= i) modify(1, 1, n, i, j);
        for (auto j: v2[i])
            if (i - 1 >= j)modify(1, 1, n, j, i - 1);
        long long t = i - 1;
        if (i > 1) t -= query(1, 1, n, 1, i - 1);
        if (i < n) t += query(1, 1, n, i + 1, n);
        ans -= t * (t - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}