倒着讲吧，这次打得不好，C题的脑筋急转弯想了半天没想出来，D题是之前一个cf做过的经典题型，但还是因为下标debug了很久，Profile Here。

Question D Count Increasing Quadruplets

题意

给定长为n的数组a，求满足要求的四元组(i, j, k, l)的数目:
- $0 \le i < j < k < l < n$
- $a[i] < a[k] < a[j] < a[l]$

题解

这个题目和Codeforces Round #789 Div.2 C.Tokitsukaze and Strange Inequality实在是太像了，也可能是因为这个套路太老了，导致我一下就想到了去年的这个题。

n的范围是4000，所以大概就是$O(n^2)$，或者$O(n^2logn)$的方法。这里其实两种方法都行，我们就说好理解的那种，后面的复杂度需要用到树状数组，而且本身对这个问题来说时间复杂度也比第一种前缀和要差。

比较经典的想法是求四元组就枚举其中若干个位置，固定之后求在这选定的若干个位置下满足约束的方案数相加即可。在这个问题我们就枚举中间两个下标j和k，当a[j]>a[k]时就计算这种枚举方式的贡献，即有多少(i, l)的二元组满足a[i] < a[k] 且 a[j] < a[l]。我们已经把问题从一个具有三个不等号的连不等式拆成了两个子不等式，求这个方案数就简单多了。先思考一下需要的复杂度，由于这样的枚举方式已经是$O(n^2)$，我们枚举内部只能是O(1)或O(logn)的询问，所以这个事情一定需要预处理出来。发现其实也不难，我们只需要有一个数组存着在a[1:i]之间有多少数比a[j]小就可以了。因此我们维护一个代表偏序关系的二维数组，对它做一维前缀和就可以了。具体可以看代码：

typedef long long ll;
const int maxn = 4e3 + 10;
class Solution {
public:
    int n, f[maxn][maxn];
    long long countQuadruplets(vector<int>& p) {
        n = p.size();
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                if(p[i - 1] > p[j - 1])
                    f[i][j] = 1;
            }        
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                f[i][j] += f[i][j - 1];
            }
        }

        ll ans = 0;
        for (int b = 2; b < n; b++){
            for (int c = b + 1; c < n; c++){
                if(p[b - 1] > p[c - 1]){
                    ans += 1ll * f[c][b - 1] * ((n - f[b][n]) - (c - f[b][c]));
                }
            }
        }

        return ans;
    }
};

Question C Put Marbles in Bags

题意

给定长为n的数组a，要求将数组a[1:n]不重不漏的分割成k条线段，每条包括a[i:j]的线段kk权重为两个端点的和，即w[kk]=a[i]+a[j]，求$min \sum_{i = 1}^{k} w[i]$

题解

首先我考虑是不是直接可以取前2k大和2k小然后相减，可以拿一些样例手动试一下，发现这个贪心的想法有点太假了，因为线段的要求还是需要满足某些选取下标的偏序关系。所以我一直没想出来，就调戏chatgpt去了，看看它能不能做出来，结果看他在一本正经地胡说八道。。

最后看题解还是脑筋急转弯，分成n条线段，等价于有n-1个分界点，也就是从n-1个分界点中选k-1个分界点，而分界点的代价恰好是这个分界点两侧数字的和。求所有k-1个选取的分界点和的最小值和题目求的最小值是等价的，这是因为它们两个之间只差a[1]和a[n]这两个常数项。

typedef long long ll;
class Solution {
public:
    ll putMarbles(vector<int>& weights, int k) {
        vector<ll> v;
        int n = weights.size();
        for(int i = 0; i < n - 1; i++){
            v.push_back(weights[i] + weights[i + 1]);
        }
        sort(v.begin(), v.end());
        ll resl = 0, resr = 0;
        for(int i = 0; i < min(k - 1, n - 1); i++){
            resl += v[i], resr += v[n - 1 - 1 - i];
        }
        return resr - resl;
    }
};

Question B Count Collisions of Monkeys on a Polygon

题意

在一个n边形的n个顶点上各有1个人，每个人只能选择向相邻顶点顺时针或逆时针方向移动一格（即每个人只有两种移动方式）。问经过每个人都移动且仅移动一次后，发生碰撞（移动过程交叉或某个顶点上有两个人）的方案数有多少？$n\le1e9$

题解

其实它还是个脑筋急转弯，我们换个方式来想，如果想不碰撞只有两种可能，所有人顺时针移动或逆时针移动。那么总方案数就是$2^n-2$，而n比较大，我们需要用快速幂就可以了。

typedef long long ll;
const ll MOD = 1e9 + 7;
class Solution {
public:
    ll quickpow(ll base, ll index){
        ll ret = 1;
        while(index){
            if(index & 1) ret *= base, ret %= MOD;
            base *= base, base %= MOD;
            index >>= 1;
        }
        return ret;
    }
    int monkeyMove(int n) {
        return (quickpow(2, n) + MOD - 2) % MOD;
    }
};

Question A Count Distinct Numbers on Board

题意

给定一个黑板，上面一开始只有一个正整数n。每轮可以将任意模黑板上的一个数x为1的数写在黑板上。重复若干轮后，问黑板上有多少个数？$(n\le1e9)$

题解

脑筋急转弯，应该想到类似数学归纳法的思路，即黑板上若有x，这一轮就可以把x-1写在黑板上。因此有限轮后1~n-1的所有数都会出现在黑板上。答案自然是n-1。

想到这里就会WA一发，因为n的数据范围包括1，而n=1时答案自然还是1。。