CF297 / Codeforces Round 180 (Div. 1)

README.md

链接 ᴮᵃᶜᵏᵘᵖ

a.biao.cpp

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

mt19937 mtr(chrono::system_clock::now().time_since_epoch().count());

const int N = 100 + 5;

int str[N];
int l, r;

inline void print()
{
    for (int i = l; i <= r; ++i)
    {
        printf("%d", str[i]);
    }
    puts("");
}

inline int parity()
{
    int res = 0;
    for (int i = l; i <= r; ++i)
    {
        res ^= (str[i] % 2 == 1);
    }
    return res;
}

int main()
{
    for (int i = 1; i <= 8; ++i)
    {
        str[i] = mtr() % 2;
    }
    l = 1, r = 8;
    print();
    puts("");
    while (r < N - 1)
    {
        int op = mtr() % 2;
        if (op == 1)
        {
            str[++r] = parity();
        }
        else
        {
            ++l;
        }
        printf("%d\n", op);
        print();
        puts("");
    }
}

a.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1000 + 5;

char a[N], b[N];

inline int count(char *str)
{
    int res = 0;
    for (char *now = str; *now != '\0'; ++now)
    {
        res += (*now == '1');
    }
    return res;
}

int main()
{
    scanf("%s %s", a, b);
    int cntA = count(a), cntB = count(b);
    if (cntA % 2 == 0 && cntA >= cntB)
    {
        puts("YES");
    }
    else if (cntA % 2 == 1 && cntA + 1 >= cntB)
    {
        puts("YES");
    }
    else
    {
        puts("NO");
    }
}

b.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;

int n, m, k;
int a[N], b[N];
int unq[N * 2];
int A[N * 2], B[N * 2];

int main()
{
    read(n), read(m), read(k);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
    }
    for (int i = 1; i <= m; ++i)
    {
        read(b[i]);
    }
    copy(a + 1, a + n + 1, unq + 1);
    copy(b + 1, b + m + 1, unq + n + 1);
    sort(unq + 1, unq + n + m + 1);
    int mx = unique(unq + 1, unq + n + m + 1) - unq;
    for (int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(unq + 1, unq + mx, a[i]) - unq;
        ++A[a[i]];
    }
    for (int i = 1; i <= m; ++i)
    {
        b[i] = lower_bound(unq + 1, unq + mx, b[i]) - unq;
        ++B[b[i]];
    }
    for (int i = mx; i >= 1; --i)
    {
        A[i] += A[i + 1];
        B[i] += B[i + 1];
        if (A[i] > B[i])
        {
            puts("YES");
            return 0;
        }
    }
    puts("NO");
    return 0;
}

c.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;

int n;
pii s[N];
int a[N], b[N];

int main()
{
    read(n);
    for (int i = 0; i < n; ++i)
    {
        read(s[i].first);
        s[i].second = i;
    }
    sort(s, s + n);
    int t = (int)ceil(n / 3.0);
    for (int i = 0; i < t; ++i)
    {
        a[s[i].second] = i;
        b[s[i].second] = s[i].first - i;
    }
    for (int i = t; i < n - t; ++i)
    {
        b[s[i].second] = i;
        a[s[i].second] = s[i].first - i;
    }
    for (int i = n - t, x; i < n; ++i)
    {
        x = n - 1 - i;
        b[s[i].second] = x;
        a[s[i].second] = s[i].first - x;
    }
    puts("YES");
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", a[i]);
    }
    puts("");
    for (int i = 0; i < n; ++i)
    {
        printf("%d ", b[i]);
    }
}

d.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1000 + 5;

int h, w, k;

char str[N];
bool hRes[N][N], wRes[N][N];
bool mp[N][N];

inline void solveKEq1()
{
    int res = 0, sum = h * (w - 1) + w * (h - 1);
    for (int i = 1; i < h * 2; ++i)
    {
        scanf("%s", str + 1);
        for (int j = 1; j <= w; ++j)
        {
            if (str[j] == 'E')
            {
                ++res;
            }
        }
    }
    if (sum * 3 > res * 4)
    {
        puts("NO");
        return;
    }
    puts("YES");
    for (int i = 1; i <= h; ++i)
    {
        for (int j = 1; j <= w; ++j)
        {
            putchar('1');
            putchar(' ');
        }
        putchar('\n');
    }
}

int main()
{
    read(h), read(w), read(k);
    if (k == 1)
    {
        solveKEq1();
        return 0;
    }
    for (int i = 1, layer = 0; i < h * 2; ++i)
    {
        scanf("%s", str + 1);
        if (i % 2 == 1)
        {
            ++layer;
            for (int j = 1; j < w; ++j)
            {
                hRes[layer][j] = (str[j] == 'N');
            }
        }
        else
        {
            for (int j = 1; j <= w; ++j)
            {
                wRes[layer][j] = (str[j] == 'N');
            }
        }
    }
    bool rev = h > w;
    if (rev)
    {
        swap(h, w);
        for (int i = 1; i <= w; ++i)
        {
            for (int j = 1; j <= w; ++j)
            {
                swap(hRes[i][j], wRes[j][i]);
            }
        }
    }
    for (int i = 1, fail; i <= h; ++i)
    {
        for (int j = 2; j <= w; ++j)
        {
            mp[i][j] = (hRes[i][j - 1] ? !mp[i][j - 1] : mp[i][j - 1]);
        }
        if (i > 1)
        {
            fail = 0;
            for (int j = 1; j <= w; ++j)
            {
                fail += (wRes[i - 1][j] != (mp[i][j] != mp[i - 1][j]));
            }
            if (fail * 2 > w)
            {
                for (int j = 1; j <= w; ++j)
                {
                    mp[i][j] ^= true;
                }
            }
        }
    }
    puts("YES");
    if (rev)
    {
        for (int i = 1; i <= w; ++i)
        {
            for (int j = 1; j <= h; ++j)
            {
                putchar('1' + mp[j][i]);
                putchar(' ');
            }
            putchar('\n');
        }
    }
    else
    {
        for (int i = 1; i <= h; ++i)
        {
            for (int j = 1; j <= w; ++j)
            {
                putchar('1' + mp[i][j]);
                putchar(' ');
            }
            putchar('\n');
        }
    }
    return 0;
}

d.pai.cpp

#include <bits/stdc++.h>
using namespace std;
int h, w, k;
int mp1[1005][1005], mp2[1005][1005], ans[1005][1005];
int main()
{
    cin >> h >> w >> k;
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j < w; j++)
        {
            char x = getchar();
            while (!isalpha(x))
                x = getchar();
            if (x == 'E')
                mp1[i][j] = 1;
            else
                mp1[i][j] = 0;
        }
        if (i != h)
        {
            for (int j = 1; j <= w; j++)
            {
                char x = getchar();
                while (!isalpha(x))
                    x = getchar();
                if (x == 'E')
                    mp2[i][j] = 1;
                else
                    mp2[i][j] = 0;
            }
        }
    }
    if (k == 1)
    {
        int ans = 0, tot = 0;
        for (int i = 1; i <= h; i++)
        {
            for (int j = 1; j < w; j++)
            {
                if (mp1[i][j] == 1)
                    ans++;
                tot++;
            }
        }
        for (int i = 1; i < h; i++)
        {
            for (int j = 1; j <= w; j++)
            {
                if (mp2[i][j] == 1)
                    ans++;
                tot++;
            }
        }
        if (ans * 4 >= tot * 3)
        {
            puts("YES");
            for (int i = 1; i <= h; i++)
            {
                for (int j = 1; j <= w; j++)
                {
                    putchar('1');
                    putchar(' ');
                }
                puts("");
            }
            return 0;
        }
        else
        {
            puts("NO");
            return 0;
        }
    }
    if (h <= w)
    {
        ans[1][1] = 0;
        for (int i = 2; i <= w; i++)
        {
            if (mp1[1][i - 1] == 0)
                ans[1][i] = ans[1][i - 1] ^ 1;
            else
                ans[1][i] = ans[1][i - 1];
        }
        for (int i = 2; i <= h; i++)
        {
            ans[i][1] = 0;
            for (int j = 2; j <= w; j++)
            {
                if (mp1[i][j - 1] == 0)
                    ans[i][j] = ans[i][j - 1] ^ 1;
                else
                    ans[i][j] = ans[i][j - 1];
            }
            int tmp = 0, tot = 0;
            for (int j = 1; j <= w; j++)
            {
                if ((ans[i][j] == ans[i - 1][j]) == mp2[i - 1][j])
                    tmp++;
                tot++;
            }
            if (tmp * 2 < tot)
            {
                for (int j = 1; j <= w; j++)
                    ans[i][j] ^= 1;
            }
        }
    }
    else
    {
        ans[1][1] = 0;
        for (int i = 2; i <= h; i++)
        {
            if (mp2[i - 1][1] == 0)
                ans[i][1] = ans[i - 1][1] ^ 1;
            else
                ans[i][1] = ans[i - 1][1];
        }
        for (int i = 2; i <= w; i++)
        {
            ans[1][i] = 0;
            for (int j = 2; j <= h; j++)
            {
                if (mp2[j - 1][i] == 0)
                    ans[j][i] = ans[j - 1][i] ^ 1;
                else
                    ans[j][i] = ans[j - 1][i];
            }
            int tmp = 0, tot = 0;
            for (int j = 1; j <= h; j++)
            {
                if ((ans[j][i] == ans[j][i - 1]) == mp1[j][i - 1])
                    tmp++;
                tot++;
            }
            if (tmp * 2 < tot)
            {
                for (int j = 1; j <= h; j++)
                    ans[j][i] ^= 1;
            }
        }
    }
    puts("YES");
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cout << 1 + ans[i][j] << ' ';
        }
        puts("");
    }
}

d.zjk.cpp

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>

using namespace std;

template <typename T>
void chkmax(T &x, T y) { x = x > y ? x : y; }
template <typename T>
void chkmin(T &x, T y) { x = x > y ? y : x; }
template <typename T>
void update(T &x, T y, T mod) { x = x + y > mod ? x + y - mod : x + y; }

typedef long long ll;

const int INF = (1ll << 30);

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl

template <typename T>
void read(T &x)
{
    x = 0;
    bool f = 1;
    char ch;
    do
    {
        ch = getchar();
        if (ch == '-')
            f = 0;
    } while (ch > '9' || ch < '0');
    do
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    } while (ch >= '0' && ch <= '9');
    x = f ? x : -x;
}

template <typename T>
void write(T x)
{
    if (x < 0)
        x = ~x + 1, putchar('-');
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

const int N = 1000 + 5;

int n, m, k, cnt, a[N][N];
char v[N][N], h[N][N];

int main()
{
    read(n);
    read(m);
    read(k);
    int sum = n * (m - 1) + (n - 1) * m;
    for (int i = 0; i < n; i++)
    {
        scanf("%s", h[i]);
        for (int j = 0; j < m - 1; j++)
            cnt += h[i][j] == 'E';
        if (i < n - 1)
        {
            scanf("%s", v[i]);
            for (int j = 0; j < m; j++)
                cnt += v[i][j] == 'E';
        }
    }
    if (k == 1)
    {
        if (cnt * 4 < sum * 3)
            return puts("NO"), 0;
        puts("YES");
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                printf("1 ");
            }
            puts("");
        }
        return 0;
    }
    puts("YES");
    bool flag = true;

    if (n > m)
    {
        flag = false;
        swap(n, m);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < m; j++)
            {
                swap(h[i][j], v[j][i]);
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        int cnt = 0;
        for (int j = 1; j < m; j++)
            if (h[i][j - 1] == 'N')
                a[i][j] = (!a[i][j - 1]);
            else
                a[i][j] = a[i][j - 1];
        if (i)
            for (int j = 0; j < m; j++)
                cnt += (v[i - 1][j] == 'E') != (a[i - 1][j] == a[i][j]);
        if (cnt * 2 >= m)
            for (int j = 0; j < m; j++)
                a[i][j] ^= 1;
    }
    if (flag)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                printf("%d ", a[i][j] + 1);
            }
            puts("");
        }
    }
    else
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                printf("%d ", a[j][i] + 1);
            }
            puts("");
        }
    }
    return 0;
}

e.cpp

#include <bits/stdc++.h>
#define watch(x) std::cout << "$ LINE @" << __LINE__ << " FUNC @" << __FUNCTION__ << "\n$ " \
                           << (#x) << ": " << x << std::endl

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template <typename Tp>
inline void read(Tp &x)
{
    static char c;
    static bool neg;
    x = 0, c = getchar(), neg = false;
    for (; !isdigit(c); c = getchar())
    {
        if (c == '-')
        {
            neg = true;
        }
    }
    for (; isdigit(c); c = getchar())
    {
        x = x * 10 + c - '0';
    }
    if (neg)
    {
        x = -x;
    }
}

const int N = 1e5 + 5;

int n, l[N], r[N];

struct Node
{
    int x, y, id;
    inline const Node *operator()(const int &x, const int &y, const int &id)
    {
        this->x = x;
        this->y = y;
        if (this->x > this->y)
        {
            swap(this->x, this->y);
        }
        this->id = id;
        return this;
    }
} node[N];

inline bool compareByX(const Node &lhs, const Node &rhs)
{
    return lhs.x < rhs.x;
}

inline bool compareByY(const Node &lhs, const Node &rhs)
{
    return lhs.y > rhs.y;
}

namespace BIT
{
#define lowbit(x) ((x) & -(x))

    int node[N * 2];
    inline void clear()
    {
        memset(node, 0, sizeof(node));
    }
    inline void add(int x, int val)
    {
        for (; x <= n * 2; x += lowbit(x))
        {
            node[x] += val;
        }
    }
    inline int query(int x)
    {
        int res = 0;
        for (; x > 0; x -= lowbit(x))
        {
            res += node[x];
        }
        return res;
    }

#undef lowbit
} // namespace BIT

int main()
{
    read(n);
    for (int i = 1, x, y; i <= n; ++i)
    {
        read(x), read(y);
        node[i](x, y, i);
    }
    sort(node + 1, node + n + 1, compareByX);
    for (int i = 1; i <= n; ++i)
    {
        l[node[i].id] = BIT::query(node[i].x) + BIT::query(n * 2) - BIT::query(node[i].y);
        BIT::add(node[i].y, 1);
    }
    BIT::clear();
    for (int i = n; i >= 1; --i)
    {
        r[node[i].id] = BIT::query(node[i].y) - BIT::query(node[i].x);
        BIT::add(node[i].y, 1);
    }
    BIT::clear();
    sort(node + 1, node + n + 1, compareByY);
    for (int i = 1; i <= n; ++i)
    {
        l[node[i].id] += BIT::query(n * 2) - BIT::query(node[i].y);
        BIT::add(node[i].x, 1);
    }
    ll ans = (ll)n * (n - 1) * (n - 2) / 6, sum = 0LL;
    for (int i = 1; i <= n; ++i)
    {
        ans -= (ll)l[i] * r[i];
        sum += (ll)(l[i] + r[i]) * (n - l[i] - r[i] - 1);
    }
    printf("%lld\n", ans - sum / 2);
}

e.luogu.cpp

/**
 * 题解 CF 297E Mystic Carvings
 * https://cdn.jsdelivr.net/gh/urlib/bin_7@0.0.4/cb/8d/cb/4c/cb8dcb4cca2b54c6a9271f2ee427a6dfc142b1f3d2775e3166a1cbfbc73922fd.pdf
 */

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 300010;
int n, l[N], r[N];
ll ans1, ans2;

struct node
{
    int x, y, id;
} a[N];

struct BIT
{
    int c[N];

    void add(int x, int val)
    {
        for (; x <= n * 2; x += x & -x)
            c[x] += val;
    }

    int ask(int x)
    {
        int sum = 0;
        for (; x; x -= x & -x)
            sum += c[x];
        return sum;
    }
} bit;

bool cmp1(node x, node y)
{
    return x.x < y.x;
}

bool cmp2(node x, node y)
{
    return x.y > y.y;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
        if (a[i].x > a[i].y)
            swap(a[i].x, a[i].y);
        a[i].id = i;
    }
    sort(a + 1, a + 1 + n, cmp1);
    for (int i = 1; i <= n; i++) //二维偏序求每一条弦的 l[i] 和 r[i]
    {
        l[a[i].id] += bit.ask(a[i].x) + bit.ask(n * 2) - bit.ask(a[i].y);
        bit.add(a[i].y, 1);
    }
    memset(bit.c, 0, sizeof(bit.c));
    for (int i = n; i >= 1; i--)
    {
        r[a[i].id] += bit.ask(a[i].y) - bit.ask(a[i].x);
        bit.add(a[i].y, 1);
    }
    memset(bit.c, 0, sizeof(bit.c));
    sort(a + 1, a + 1 + n, cmp2);
    for (int i = 1; i <= n; i++)
    {
        l[a[i].id] += bit.ask(n * 2) - bit.ask(a[i].y);
        bit.add(a[i].x, 1);
    }
    ans1 = 1LL * n * (n - 1) * (n - 2) / 6; //C(n,3)
    for (int i = 1; i <= n; i++)
    {
        ans1 -= 1LL * l[i] * r[i];
        ans2 += 1LL * (l[i] + r[i]) * (n - l[i] - r[i] - 1);
    }
    printf("%I64d", ans1 - ans2 / 2);
    return 0;
}

e.ref.cpp

#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>

using namespace std;

const int N = 444444;

int a[N], b[N], s[N], inter[N], inside[N], p[N], id[N];
int t;

void modify(int x, int v)
{
    while (x <= t)
    {
        s[x] += v;
        x = (x | (x - 1)) + 1;
    }
}

int find(int x)
{
    int v = 0;
    while (x > 0)
    {
        v += s[x];
        x &= x - 1;
    }
    return v;
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", a + i, b + i);
        if (a[i] > b[i])
        {
            int tmp = a[i];
            a[i] = b[i];
            b[i] = tmp;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        p[a[i]] = b[i];
        p[b[i]] = a[i];
        id[a[i]] = i;
        id[b[i]] = i;
    }
    t = 2 * n;
    for (int i = 1; i <= t; i++)
        s[i] = 0;
    for (int i = 1; i <= t; i++)
    {
        if (p[i] < i)
        {
            inside[id[i]] = find(i) - find(p[i] - 1);
            modify(p[i], 1);
        }
    }
    for (int i = 1; i <= n; i++)
        inter[i] = (b[i] - a[i] - 1) - 2 * inside[i];
    long long ans = (long long)n * (n - 1) * (n - 2) / 6;
    long long cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt1 += (long long)inter[i] * (n - inter[i] - 1);
        cnt2 += (long long)inside[i] * (n - inter[i] - inside[i] - 1);
    }
    ans -= (cnt1 / 2 + cnt2);
    cout << ans << endl;
    return 0;
}

sol.md

CF 297 题解

A

设函数 count() 返回一个字符串中 1 的个数。我们考虑这样一个事情，在串 a 中进行任意步操作，字符 1 的个数至多是 count(a) + count(a) % 2，而且单调不增。现在我们试图说明，只要这个个数大于等于 count(b)，就可以把 a 变成 b。如果 count(a) 是个奇数，先往后加个 1，让它变成偶数，方便讨论。接下来，我们从 a 的最后一位（如果不是 1，就从前面搞个 1 过来）开始，依次复刻 b。为啥可以搞个 1 过来，你都是偶数了，你前面删掉（可能的一堆 0）和第一个 1，变奇数，然后后面加个 1，就简称搞一个 1。这个时候，你碰到 0 就任意补全，因为是偶数，可以添 INF 个 0。碰到 1 就从前面搞一个过来。这样的话肯定能拼出 b 来。所以就构造出来了。

B

数据范围 1e9，先离散化一下，让范围降到 2e5。然后开个桶统计下每个值出现了几次，再做个后缀和。如果发现哪一位上的后缀和 A[i] > B[i] 了，直接把这之后的值全改 1e9 肯定是一种合算且合法的方法，直接 YES。否则就是 NO。

C

将给定的序列排序，下标从 0 开始，取 t = ceil(n / 3.0)。i = [0, t) 时，a[i] = i，i = [t, n - t) 时 b[i] = i，i = [n - t, n) 时 b[i] = n - 1 - i。对于 a 数组中间那段可以删除，对于 b 数组第一段可以删除。来自 https://www.zybuluo.com/994495jj/note/821088 的思路。

D

总条件数是 w * (h - 1) + h * (w - 1)。如果 k = 1，E 的个数 >= 3 / 4 总条件数，就合法否则不合法。然后，k > 1 的情况，只要两种颜色就能满足条件。如果 w < h 就转一下，让 w >= h。然后，从上到下，对于每个横行，先满足内部需求，再尝试满足当前横行和上面的横行之间的要求。如果发现夹在两个横行之间的满足的要求数 < w / 2，就把当前这个横行反转下。这样夹在中间的要求满足了至少一半，总共满足了（至少）h * (w - 1) + 1 / 2 * w * (h - 1) 个要求。而 3 / 4 总要求和这个数字差了 1 / 4 * (w - h)。由于之前的操作保证了 w >= h，这个构造是正确的。

E

三条弦之间的关系一共有五种，如图。

其中 2 和 5 是合法的（要么两两相交，要么全不相交），但是合法的方案比较难算，考虑从总方案 C(n, 3) 中减去不合法的方案，然而这个常用技巧没想到。假设我们已经求得每条弦左边，且不相交的弦的数量 l[i]，和右边的数量 r[i]，可以发现 1 的总数就是 sum(l[i] * r[i])。3 和 4 的共同点是从三条中的两条弦的眼光看，一条和自己相交，一条和自己不相交，这样的方案数是 (l[i] + r[i]) * (n - l[i] - r[i] - 1)。但是对于每个情况，重复计算了一次（从两条弦的眼光看都被计算了一次），除掉就是答案。考虑怎么计算 l[i], r[i]。这步可以用二维偏序做，参考 https://www.luogu.com.cn/blog/stoorz/solution-cf297e，发现 l[i] 需要满足 x' < x and (y' < x or y' > y) 或者 x' > y and y' > y。而 r[i] 需要满足 x' > x and y' < y。