https://codeforces.com/contest/1539

E. Game with Cards

题意：
玩 n 个回合游戏
初始时左右手各有一张值为 的卡片
每个回合会提供一张值为 k_i 的卡片，必须将其与左手或右手的卡片交换
要求每个回合后满足左右手的卡片值分别落在指定区间内
即 a_{l,i} \leq l \leq b_{l, i}, a_{r,i} \leq r \leq b_{r,i}

数据范围：
2 \leq n \leq 10 ^ 5
2 \leq m \leq 10^9
0 \leq k_i \leq m
0 \leq a_{l,i} \leq b_{l,i} \leq m,\ 0 \leq a_{r,i} \leq b_{r,i} \leq m

做法：
考虑每次交换对未来产生的影响，即其在未来能继续满足多少回合的区间
容易发现，这个“影响”越远越好
那么可以用dp来维护这个影响
f[i][0/1] 代表进行第 i 个回合，交换左/右手后，另一只手上的数字的最远影响范围
若记 g[i][0/1] 代表 k[i] 在左/右手时，满足 [i, g[i][0/1]] 的条件，而不满足 [i, g[i][0/1] + 1] 的条件
意会一下就能构造出转移方程，即满足条件且最大化 f[i][0/1]
那么考虑怎么获得 g[i][0/1]
即考虑这样一个问题：
给定一任意数组 a ，给 n 次询问，每次给出值 p ，求满足 a_i \geq p 的最小下标
挺显然可以用权值线段树离线维护，从右往左扫一遍
总复杂度 O(n + nlogn)

AC代码:

#include <iostream>
using namespace std;

#define int long long

const int MAX_N = 1E5 + 100;
const int INF = MAX_N;

class SegmentTree {
   private:
    int n, m;
    class Node {
       public:
        int a = INF, l, r;
    } a[20 * MAX_N];

    void modify(int n, int l, int r, int p, int x) {
        if (l == r) {
            a[n].a = min(a[n].a, x);
            return;
        }

        int mid = (l + r) >> 1;
        if (p <= mid) {
            if (!a[n].l) a[n].l = ++m;
            modify(a[n].l, l, mid, p, x);
        } else {
            if (!a[n].r) a[n].r = ++m;
            modify(a[n].r, mid + 1, r, p, x);
        }

        a[n].a = INF;
        if (a[n].l) a[n].a = min(a[n].a, a[a[n].l].a);
        if (a[n].r) a[n].a = min(a[n].a, a[a[n].r].a);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (0 == n) return INF;
        if (ll <= l && r <= rr) {
            return a[n].a;
        }

        int mid = (l + r) >> 1;
        int ret = INF;
        if (ll <= mid) ret = min(ret, query(a[n].l, l, mid, ll, rr));
        if (mid < rr) ret = min(ret, query(a[n].r, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) {
        n = _n;
        m = 1;
    }

    void modify(int p, int x) { modify(1, 1, n, p + 1, x); }

    int query(int l, int r) { return query(1, 1, n, l + 1, r + 1); }
};

int n, m;
int k[MAX_N];
int a[MAX_N][2];
int lt[MAX_N][2], rt[MAX_N][2];
int ans[MAX_N];

SegmentTree trr[2], trl[2];

int dp[MAX_N][2];
int lst[MAX_N][2];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    trl[0].init(m + 1);
    trl[1].init(m + 1);
    trr[0].init(m + 1);
    trr[1].init(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> k[i];
        cin >> lt[i][0] >> rt[i][0];
        cin >> lt[i][1] >> rt[i][1];
    }

    for (int i = n; i >= 1; --i) {
        trl[0].modify(lt[i][0], i);
        trr[0].modify(rt[i][0], i);
        trl[1].modify(lt[i][1], i);
        trr[1].modify(rt[i][1], i);

        a[i][0] = min(trl[0].query(k[i] + 1, m), trr[0].query(0, k[i] - 1)) - 1;
        a[i][1] = min(trl[1].query(k[i] + 1, m), trr[1].query(0, k[i] - 1)) - 1;
    }
    a[0][0] = trl[0].query(1, m) - 1;
    a[0][1] = trl[1].query(1, m) - 1;
    dp[0][0] = a[0][1];
    dp[0][1] = a[0][0];

    for (int i = 1; i <= n; ++i) {
        if (a[i][0] >= i) {
            if (-1 == dp[i - 1][1] || dp[i - 1][0] >= a[i - 1][1]) {
                dp[i][0] = dp[i - 1][0];
                lst[i][0] = 0;
            } else {
                dp[i][0] = a[i - 1][1];
                lst[i][0] = 1;
            }

            if (dp[i][0] < i) dp[i][0] = -1;
        } else {
            dp[i][0] = -1;
        }

        if (a[i][1] >= i) {
            if (-1 == dp[i - 1][0] || dp[i - 1][1] >= a[i - 1][0]) {
                dp[i][1] = dp[i - 1][1];
                lst[i][1] = 1;
            } else {
                dp[i][1] = a[i - 1][0];
                lst[i][1] = 0;
            }

            if (dp[i][1] < i) dp[i][1] = -1;
        } else {
            dp[i][1] = -1;
        }
    }

    if (-1 != dp[n][0]) {
        cout << "Yes" << endl;

        ans[n + 1] = 0;
        for (int i = n; i >= 2; --i) {
            ans[i] = lst[i][ans[i + 1]];
        }
        for (int i = 2; i <= n + 1; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else if (-1 != dp[n][1]) {
        cout << "Yes" << endl;

        ans[n + 1] = 1;
        for (int i = n; i >= 2; --i) {
            ans[i] = lst[i][ans[i + 1]];
        }
        for (int i = 2; i <= n + 1; ++i) {
            cout << ans[i] << ' ';
        }
        cout << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

心路历程：
思路想了一会，但是显然完全没想清楚
线段树维护的东西一直在修修补补（主要是端点值），dp方程也一直在改
小错误相当多，乱WA了20发才过
另外还读错题意了

Bob holds one card with number 0 in the left hand and one in the right hand

这一句我直接用翻译拿到的是，左手是0右手是1
留着以后下饭用

F. Strange Array

题意：
给一个数组，对于每个数要求计算一个“奇怪值”，定义如下
任选一个子区间，排序后（相等值任意调换），每个值到中心位置（偶数取右侧）的距离将对奇怪值产生贡献
一个数的奇怪值就是它的贡献的最大值

数据范围：
1 \leq n \leq 2·10^5,\ 1\leq a_i \leq n

做法：
子区间排序后当前数距中位数的距离，直接维护显然困难
考虑换一种角度想这个东西
记子区间内大于当前数的数量有 p， 小于当前数的数量有 q
则这一距离可以转化为一个用 p, q 表示的式子，大致是 abs(p - q)/2，再上下取整弄一下
问题转化为了对于每个数，寻找子区间来最大化与最小化 p - q
更进一步的，维护的区间可以从待询问的数那里拆成左右两半分别维护，最后加起来即可
这个东西可以用线段树离线维护
考虑从小到大依次加入数字，那么未加入的都是比当前值大的
考虑一个数组 c 来记录这个关系，若 a_i < a_{cur} 这一位取-1，大于则为 1
那么一个区间的 p - q 即为 \Sigma c_i
最后考虑一下等于的情况该怎么处理就好了

AC代码：

#include <iostream>
#include <map>
#include <vector>
using namespace std;

const int MAX_N = 2E5 + 100;
const int INF = MAX_N;

class SegmentTree1 {
   private:
    int n;
    int a[MAX_N << 2];
    int lz[MAX_N << 2];

    void modify(int n, int l, int r, int ll, int rr, int x) {
        if (ll <= l && r <= rr) {
            a[n] += x;
            lz[n] += x;
            return;
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        if (ll <= mid) modify(n << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(n << 1 | 1, mid + 1, r, ll, rr, x);
        a[n] = max(a[n << 1], a[n << 1 | 1]);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return a[n];
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        int ret = -INF;
        if (ll <= mid) ret = max(ret, query(n << 1, l, mid, ll, rr));
        if (mid < rr) ret = max(ret, query(n << 1 | 1, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) { n = _n; }

    void modify(int l, int r, int x) { modify(1, 1, n, l, r, x); }

    int query(int l, int r) { return query(1, 1, n, l, r); }
};

class SegmentTree2 {
   private:
    int n;
    int a[MAX_N << 2];
    int lz[MAX_N << 2];

    void modify(int n, int l, int r, int ll, int rr, int x) {
        if (ll <= l && r <= rr) {
            a[n] += x;
            lz[n] += x;
            return;
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        if (ll <= mid) modify(n << 1, l, mid, ll, rr, x);
        if (mid < rr) modify(n << 1 | 1, mid + 1, r, ll, rr, x);
        a[n] = min(a[n << 1], a[n << 1 | 1]);
    }

    int query(int n, int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) {
            return a[n];
        }

        int mid = (l + r) >> 1;
        if (lz[n]) {
            modify(n << 1, l, mid, l, mid, lz[n]);
            modify(n << 1 | 1, mid + 1, r, mid + 1, r, lz[n]);
            lz[n] = 0;
        }

        int ret = INF;
        if (ll <= mid) ret = min(ret, query(n << 1, l, mid, ll, rr));
        if (mid < rr) ret = min(ret, query(n << 1 | 1, mid + 1, r, ll, rr));
        return ret;
    }

   public:
    void init(int _n) { n = _n; }

    void modify(int l, int r, int x) { modify(1, 1, n, l, r, x); }

    int query(int l, int r) { return query(1, 1, n, l, r); }
};

int n;
map<int, vector<int>> mp;
SegmentTree1 tr1, tr2;
SegmentTree2 tr3, tr4;
int ans[MAX_N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    tr1.init(n);
    tr2.init(n);
    tr3.init(n);
    tr4.init(n);
    for (int i = 1; i <= n; ++i) {
        int u;
        cin >> u;
        mp[u].push_back(i);

        tr1.modify(i, i, i);
        tr2.modify(i, i, n - i + 1);
        tr3.modify(i, i, i);
        tr4.modify(i, i, n - i + 1);
    }
    // init

    for (auto it : mp) {
        for (int i : it.second) {
            tr3.modify(i, n, -2);
            tr4.modify(1, i, -2);
        }

        for (int i : it.second) {
            int lA = tr2.query(1, i) - tr2.query(i, i);
            int rA = tr1.query(i, n) - tr1.query(i, i);
            int lB = tr4.query(1, i) - tr4.query(i, i);
            int rB = tr3.query(i, n) - tr3.query(i, i);
            ans[i] = max(abs((lA + rA + 1) / 2), abs((lB + rB) / 2));
        }

        for (int i : it.second) {
            tr1.modify(i, n, -2);
            tr2.modify(1, i, -2);
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << ' ';
    }
    cout << endl;

    return 0;
}

心路历程：
反应过来思路挺快的，写第一遍代码也挺快的
只是没想得太清楚，线段树没想够该用多少棵，等于的情况也只考虑了一半
调了蛮久的