link。

理一下逻辑，主要讲一下我做题时的疑惑和其它题解没提到的细节。

首先容易看到，一个必然不劣的贪心策略是把尽量靠近根的层铺成同样的字符。也许会有疑惑，字符串是否本质不同的判定每个位置地位相等。然而在这题里面字符串个数的贡献是和结点所为根的子树大小有关的，所以这个贪心不劣。

设树的最大深度为 $d$，那么如果我们能实现每层都铺成同样的字符，答案就是不同长度的字符串个数，也就是 $d$。

考虑构造出答案为 $d+1$ 的情况，这时候贪心就跑不出来了，具体情况是，会出现一层既有 a 又有 b，其他层都是 pure a 或 pure b。

主要问题就在于 miscellaneous level 放在哪里，才能让答案最小。直觉地，我们认为把它放在尽量低（离根更远）的 level 会更优。但是其实贡献结束的地方是叶子，所以其实我们应该把它放在叶子尽量多的 level。这个时候答案为 $d+1$。

根据以上的推理，我们得出一个论断：最优答案在 $d$ 和 $d+1$ 出现。剩下的问题就是如果判断是前者还是后者。

其实这是一个简单可达性 dp 可以解决的问题，将每一个 level 压成一个 item，其体积为当层的结点个数。但是这个是 $O(n^2)$ 的，要考虑优化。有两种解决的道路，分析后可以发现一个根号规模的结论，或者用 std::bitset 优化 dp。

注意 std::bitset 优化 dp 后状态略有不同……

#include<bits/stdc++.h>
#define cmin(x, y) x = std::min(x, y)
#define cmax(x, y) x = std::max(x, y)
#define fors(i, l, r, ...) for(int i = (l), REP##i = (r), ##__VA_ARGS__; i <= REP##i; ++i)
#define dfors(i, r, l, ...) for(int i = (r), REP##i = (l), ##__VA_ARGS__; i >= REP##i; --i)
// observation: amount different answers would be 2: maximum depth, or, it plus 1
int n, _x, dep[100100], nod[100100], leaf[100100], len, vol[100100];
// params: @nod[i]: amout of nodes at level i; @leaf[i]: amout of leaves at lv i;
//     #vol[i]: volume of i-th item
std::bitset<100100> f[2100]; // if can assign it to j perfectly within lefmost i items
std::vector<int> adj[100100], zip[100100];
void pre_dfs(const int x) {
    nod[dep[x]]++,leaf[dep[x]] += adj[x].empty();
    for(const int y : adj[x]) dep[y] = dep[x]+1,pre_dfs(y);
}
int pre_zip() {
    static int vis[100100], tot;
    fors(i, 1, len) {
        if(!vis[nod[i]]) vol[vis[nod[i]] = ++tot] = nod[i];
        zip[vis[nod[i]]].emplace_back(i);
    }
    return tot; // amount of items
}
signed main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cin >> n >> _x;
    fors(i, 1, n-1, f) std::cin >> f,adj[f].emplace_back(i+1);
    pre_dfs(dep[1] = 1),len = *std::max_element(dep+1, dep+n+1); // processing basic information
    int m = pre_zip(); // compressing levels with same amout of nodes
    fors(i, f[0][0] = 1, m, tmp) {
        f[i] = f[i-1],tmp = zip[i].size();
        for(int j = 1; j <= tmp; j *= 2) tmp -= j,f[i] |= (f[i]<<(vol[i]*j));
        if(tmp > 0) f[i] |= (f[i]<<(vol[i]*tmp));
    }
    std::vector<bool> k(len);
    std::function<void(int, int)> find_path = [&](const int rem, int t) { // reviving way we DP through
        if(rem == 0) return;
        for(const int x : zip[rem]) {
            if(vol[rem] > t || f[rem-1][t]) break;
            t -= vol[rem],k[x-1] = 1;
        }
        find_path(rem-1, t);
    };
    if(f[m][_x]) { // when greedy strategy runs well
        std::cout << len << "\n";
        find_path(m, _x);
        fors(i, 1, n) std::cout << (k[dep[i]-1]?'a':'b');
        return std::cout << "\n", 0;
    }
    std::cout << len+1 << "\n"; // otherwise the answer would be maximum depth plus 1
    int tmp = std::numeric_limits<int>::max(), tmp1 = -1;
    dfors(i, _x, 0) if(f[m][i]) {
        tmp = i; break;
    }
    find_path(m, tmp);
    fors(i, 1, len) if(!k[i-1] && leaf[i] >= _x-tmp) {
        tmp1 = i; break;
    }
    fors(i, 1, n) {
        if(dep[i] == tmp1 && adj[i].empty()) std::cout << (tmp == _x?'b':(++tmp, 'a'));
        else std::cout << (k[dep[i]-1]?'a':'b');
    }
    return std::cout << "\n", 0;
}

link。

调起来真的呕吐，网上又没篇题解。大概是个不错的题。

首先行和列一定是独立的，所以我们把行列分开考虑。这样的问题就弱化为：在一个长度为 $n$ 的格子带上，有 $n$ 个物品，每个物品 $x$ 对应一个区间 $[l_x,r_x]$，分配每个物品的居所使得各住各的，求出其中的固定点。

把物品放在左部，把格子放在右部，即构造一个二部图。那么问题就是求出其最大匹配的必要边。先考虑如何求这个的最大匹配，这是个经典贪心吧，把每个区间按 $l$ 排序，然后枚举位置，优先填入 $r$ 小的物品。跑完后（即规定好方向后）对整个图跑缩点，两端点不在同一连通块的边即为必要边。

这个的边数是 $O(n^2)$ 的，因为连边一下连一个区间，考虑利用这个来优化。线段树的高度不高吧，而且能够用来刻画一个区间，于是用这个东西来优化连边。

具体一点是，线段树上父亲对两个儿子连边，物品就对线段树上自己的区间连边即可。注意清空的时候带脑子……

#include<bits/stdc++.h>
using namespace std;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
void eof(const char IO) {if(IO == -1) exit(0);}
template<typename T=int> T read() {
    T x=0; char IO=getchar(); bool f=0; eof(IO);
    while(IO<'0' || IO>'9')    f|=IO=='-',eof(IO=getchar());
    while(IO>='0' && IO<='9')    x=x*10+(IO&15),eof(IO=getchar());
    return f?-x:x;
}
int n,A[100100],B[100100],C[100100],D[100100],rec1[100100],rec2[100100],tot,ans1[100100],ans2[100100];
int col[400100],dfn[400100],low[400100],dfsnt,colnt,sta[400100],top,mat[400100],inst[400100];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
struct node{
    int l,r,id;
    friend bool operator<(const node& x,const node& y) {return x.l < y.l;}
} cur[100100];
vector<node> ans;
vector<vector<int>> e;
void DFS(const int now) {
    inst[sta[++top] = now] = 1;
    dfn[now] = low[now] = ++dfsnt;
    for(const int y : e[now]) {
        if(!dfn[y]) DFS(y),cmin(low[now], low[y]);
        else if(inst[y]) cmin(low[now], dfn[y]);
    }
    if(low[now]^dfn[now]) return;
    colnt++;
    int y; do {
        inst[y = sta[top--]] = 0;
        col[y] = colnt;
    } while(y != now);
}
#define mem(x, w, n) memset(x, w, n)
void sweep() {
    e.clear();
    mem(col, 0, min(size_t(n*4*30), sizeof(col)));
    mem(dfn, 0, min(size_t(n*4*30), sizeof(dfn)));
    mem(low, 0, min(size_t(n*4*30), sizeof(low)));
    mem(sta, 0, min(size_t(n*4*30), sizeof(sta)));
    mem(inst, 0, min(size_t(n*4*30), sizeof(inst)));
    mem(mat, 0, min(size_t(n*4*30), sizeof(mat)));
    // puts("DEBUGGING ----------");
    // for(int* i : {col, dfn, low, sta, inst}) {
    //     for(int j = 0;  j < 233; ++j) printf(" %d",i[j]);
    //     puts("");
    // }
    // puts("END___D__D__D____D___D_");
    tot = dfsnt = colnt = top = 0;
    while(q.size()) q.pop();
}
int tr[400100],reid[400100];
void addedge(const int one, const int ano) {
    // printf("add:%d %d\n",one,ano);
    if(one >= int(e.size())) e.resize(one+1);
    e[one].push_back(ano);
}
void build(const int now, int l, int r) {
    // printf("  %d  %d\n",l,r);
    tr[now] = ++tot;
    if(l == r) return reid[l] = tot,void();
    int mid = (l+r)>>1;
    build(now<<1, l, mid),build(now<<1|1, mid+1, r);
    addedge(tr[now], tr[now<<1]),addedge(tr[now], tr[now<<1|1]);
}
void lin(int x,int y,int k,const int now = 1,int l = 1,int r = n) {
    if(l>y || r<x || x>y) return;
    if(l>=x && r<=y) return addedge(k, tr[now]),void();
    int mid = (l+r)>>1;
    lin(x, y, k, now<<1, l, mid),lin(x, y, k, now<<1|1, mid+1, r);
}
bool solve(int rec[], int ans[]) {
    sweep();
    static int l[100100], r[100100];
    for(int i=1; i<=n; ++i) l[i] = cur[i].l,r[i] = cur[i].r;
    sort(cur + 1, cur + n + 1);
    for(int i=1, p=1; i<=n; ++i) {
        while(p <= n && cur[p].l <= i) q.emplace(cur[p].r, cur[p].id),p++;
        if(!q.size() || q.top().first<i) return 0;
        mat[q.top().second] = i;
        q.pop();
    }
    tot = n;
    build(1, 1, n);
    // printf("  tot: %d\n", tot);
    // for(int i=1; i<=4*n; ++i) printf(" %d",tr[i]);
    // puts("");
    for(int i=1; i<=n; ++i) {
        addedge(reid[mat[i]], i);
        lin(l[i], mat[i]-1, i);
        lin(mat[i]+1, r[i], i);
    }
    for(int i=1; i<=tot; ++i) if(!dfn[i]) DFS(i);
    // for(int i=1; i<=tot; ++i) printf(" %d",col[i]);
    for(int i=1; i<=n; ++i) rec[i] = col[i] != col[reid[mat[i]]],ans[i] = mat[i];
    return 1;
}
signed main() {
    while(n = read(),233) {
        for(int i=1; i<=n; ++i) A[i] = read(),B[i] = read(),C[i] = read(),D[i] = read();
        for(int i=1; i<=n; ++i) cur[i] = (node){A[i], C[i], i};
        if(!solve(rec1, ans1)) {
            puts("-1");
            goto Fail;
        }
        for(int i=1; i<=n; ++i) cur[i] = (node){B[i], D[i], i};
        if(!solve(rec2, ans2)) {
            puts("-1");
            goto Fail;
        }
        vector<node>().swap(ans);
        for(int i=1; i<=n; ++i) if(rec1[i] && rec2[i]) ans.push_back((node){i, ans1[i], ans2[i]});
        cout<<ans.size()<<endl;
        for(const auto [x, y, z] : ans) printf("%d %d %d\n", x, y, z);
        Fail:;
    }
    return 0;
}

前言

这场比赛的锅貌似有点多…在准备的时候就已经推迟过三次，在这里为对各位比赛时造成的困扰抱歉。这是出题组第一次放比赛，欢迎批评指正。

主要问题在于 C 的数据造水了，hack 数据造反了于是没有 hack 到。D 的数据也不强。再次感到抱歉，并且努力做出改正。

最后重拾一下出比赛的初心以及发表一些 mozheng & Chuni 言论：罚金一百万元（不是），以及为自己的 Welcome to NHK 做一个 Sunny Side 式的收尾，或者称之为小结。总之都没差啦……虽然只是举个例子，但我们要告诉你的，就是这样的故事。

A

给出两种构造方式：

• 考虑 $d$ 的每一位，如果当前位为 $0$，则不对答案产生影响；如果当前位为 $1$，又因为 $1\text{ xor }1\text{ xor }0=0,1\text{ or }1\text{ or }0=1$，所以把 $a,b,c$ 其中两个按位或上 $2^i$ 即可。
• $\begin{cases}a=d\\b=\text{lowbit}(d)\\c=d\text{ xor }\text{lowbit}(d)\end{cases}$

当然这两种方式并无什么不同。无解的情况是 $d=2^n$。

#include<bits/stdc++.h>
int ans[3],d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    for(int now=0; d; d^=d&-d)    ans[now]|=d&-d,ans[(now+=1)%=3]|=d&-d;
    printf("%d %d %d\n",ans[0],ans[1],ans[2]);
    return 0;
}

#include<bits/stdc++.h>
int d;
signed main() {
    scanf("%d",&d);
    if((d&-d)==d)    return puts("-1"),0;
    printf("%d %d %d\n",d,(d&-d),d-(d&-d));
    return 0;
}

B

首先 $a_1=x_1$，考虑第二位，因为保证有解，所以 $x_2\mid x_1$，同理可得 $\forall i\in(1,n],x_i\mid x_{i-1}$，可以预见数据中最多有 $\log$ 个非 $1$ 数，于是不断往上推即可。

#include<bits/stdc++.h>
int n,x,pre,now,vis[2000100];
signed main() {
    scanf("%d\n%d",&n,&x);
    vis[pre=now=x]=1;
    printf("%d ",x);
    for(int i=1; i<n; ++i) {
        scanf("%d",&x);
        if(pre!=x)    pre=now=x;
        else    while(vis[now])    now+=pre;
        vis[now]=1;
        printf("%d ",now);
    }
    return 0;
}

C

首先我们有个 $\mathcal {O}(nm)$ 的暴力遍历做法，读者很容易想到这样遍历了太多冗余的点。

于是很自然地想到将一个块缩成一个点。具体的，对于每一列，我们将障碍物隔开的一列点看成一个点，这样的店最多有 $2k$ 个。

然后 dp 即可，$dp_i=[(\sum_{j=1}^idp_j)>0]$。

然后要注意一个块能否转移到另一个块的判断条件有细节：并不是看两个块是联通，而是定义 $mx_i$ 为能到达第 $i$ 个块的最低点（贪心），看从 $mx_j$ 起是否能到达 $mx_i$，再更新 $mx_i$。

当然好像有更简便的做法，余不会。

同时存在更优的做法，为了代码的简便起见并没有作为 std，欢迎分享。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
#define LL long long
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
const int MAXN = 5005, MAXM = 1e7 + 5;
vector <int> v[MAXM], cx;
map <int, bool> vis;
map <int, int> lst;
struct Point {
    int X, Y, Y_;
}arr[MAXN];
int n, m, k, tot, mx, mn[MAXN];
int pre[MAXM];
bool dp[MAXN];
bool check(int x, int y) {
    if(arr[x].X == arr[y].X - 1) {
        if(arr[x].Y_ < arr[y].Y) return 0;
        if(arr[x].Y > arr[y].Y_) return 0;
        if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
            mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
        }
        return 0;
    }
    if(arr[x].Y > arr[y].Y_) return 0;
    if(max(arr[y].Y, mn[x]) >= arr[y].Y && max(arr[y].Y, mn[x]) <= arr[y].Y_) {
        mn[y] = min(mn[y], max(arr[y].Y, mn[x])); return 1;
    }
    return  0;
}
int main() {
    int x, y;
    scanf("%d%d%d", &n, &m, &k); memset(mn, 0x3f, sizeof(mn));
    for(int i = 1; i <= k; i ++) {
        scanf("%d%d", &x, &y); v[x].push_back(y); cx.push_back(x); mx = max(mx, x);
    }
    sort(cx.begin(), cx.end());
    int Lst = 0;
    for(auto i : cx) {
        if(vis[i]) continue;
        pre[i] = 1;
        lst[i] = Lst; Lst = i; sort(v[i].begin(), v[i].end()); vis[i] = 1;
        int las = 0;
        for(auto j : v[i]) {
            if(j == las) { las ++; continue; }
            tot ++; arr[tot].X = i; arr[tot].Y = las; arr[tot].Y_ = j - 1; las = j + 1;
        }
        if(las <= m) tot ++, arr[tot].X = i, arr[tot].Y = las, arr[tot].Y_ = m;
    }
    for(int i = 1; i <= 10000000; i ++) pre[i] += pre[i - 1];
//    for(int i = 1; i <= tot; i ++) {
//        printf("%d %d %d\n", arr[i].X, arr[i].Y, arr[i].Y_);
//    }
    if(!tot) { printf("Yes"); return 0; }
    if(vis[0]) {
        if(arr[1].Y != 0) { printf("No"); return 0; }
        dp[1] = 1; mn[1] = 0;
    }
    else {
        for(int i = 1; i <= tot; i ++) if(arr[i].X == arr[1].X) dp[i] = 1, mn[i] = arr[i].Y, dp[i] = 1;
    }
    for(int i = 1; i <= tot; i ++) {
        for(int j = 1; j < i; j ++) {
            if(arr[j].X == arr[i].X) continue;
            if(((arr[j].X + 1 < arr[i].X && pre[arr[i].X - 1] - pre[arr[j].X] == 0) || arr[j].X + 1 == arr[i].X) && arr[j].X == lst[arr[i].X] && check(j, i)) {
                dp[i] |= dp[j];
            }
        }
    }
    if(vis[n]) {
        if(arr[tot].Y_ != m) { printf("No"); return 0; }
        if(dp[tot]) printf("Yes");
        else printf("No");
    }
    else {
        bool ans = 0;
        for(int i = 1; i <= tot; i ++) if(arr[i].X == mx) ans |= dp[i];
        if(ans) printf("Yes");
        else printf("No");
    }
    return 0;
}

D

你考虑维护 $n$ 个单调队列。第 $i$ 个单调队列的数满足：$\sum_{d=1}^ia_dc_d$，其中 $c_i$ 一定为正数。

每次我们取 $n$ 个单调队列的队头最小值 $r$，设其在第 $i$ 个队列，那么我们将 $a_d+r$ 放入第 $d$ 个队列中。（$i<d\le n$）

可以证明，由于 $a$ 数组为正数，这样队列一定是单调的。

一直这样做 $k$ 次，取 $r_k$ 即可。时间复杂度：$\mathcal {O}(nk)$。数据可以（？）把带 $\mathrm {log}$ 做法卡掉。

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <ctime>
#include <queue>
#define LL long long
using namespace std;
const int MAXN = 85;
queue <LL> que[MAXN];
int n, k, a[MAXN], num;
LL minn;
int main() {
    scanf("%d%d", &n, &k); k --;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    que[0].push(0);
    for(int i = 1; i <= k + 1; i ++) {
        minn = 9e18;
        for(int j = 0; j <= n; j ++) if(!que[j].empty() && que[j].front() < minn) minn = que[j].front(), num = j;
        while(que[0].size()) que[0].pop();
        que[num].pop();
        for(int j = num; j <= n; j ++) que[j].push(minn + a[j]);
    }
    printf("%lld", minn);
    return 0;
}

E

$f_i(\Delta)$ 表示第 $v_i$ 这个点在坐标加 $\Delta$ 时距离自己最近的 $c$ 点的距离。那么这个画出来就是一条折线，由若干条斜率为 $1$ 或 $-1$ 的直线拼接而成。再设 $F(\Delta)=\sum\limits_{i=1}^{b}f_i(\Delta)$，也就是取 $\Delta$ 时，题面中要求的距离之和。

在折线的拐点上研究，设 $\textbf{G}_i$ 为 $f_i(\Delta)$ 图像上所有拐点的集合，再设 $\textbf{G}'=\bigcup\limits_{i=1}^{b}\textbf{G}_i$。w.l.o.g，提出两个数 $a,b,s.t.(a,f(a)),(b,f(b))\in\textbf{G}'$，且不存在 $c,s.t.(c,f(c))\in\textbf{G}',c-a>0,b-c>0$，即 $a,b$ 是紧相邻的。换而言之，就是把所有 $v$ 点的图像拼在一起，取两个相邻的 $a,b$ 拐点来研究。

现在我们可以求出 $F(a)$，以及拐点后的直线斜率，从而可以求出 $F(b)$。以此，扫一遍就行了。

我们举个例子来画图：

这个就是 $f(\Delta)$ 的图像（我把多个 $i$ 的拼在一起的）。现在假设我们取的 $a,b$ 两点就是图中的蓝点（当然，$a,b$ 之间没有其他拐点，因为 $a,b$ 是紧相邻的），这意味着我确定了 $a$ 点处的 $\Delta$，那么就可以算出 $F(a)$ 了，如此往后面扫，每次取最大值就行了。

/*
每个点处在每个区间的值是不相同的，但是是一个折线。
当它在[vi,vi+1]中间时，如果靠vi更近，则为与vi的距离，否则为与vi+1的距离。
那我们现在知道了每个点移动多少之后的答案。
这条折线有的地方是斜率-1，有的地方是斜率为+1.
那么我们把所有的折线加在一起。一共有ab个点，我们维护一下每一段的斜率，然后求下最大值就好…… 

1 1 1
0
0

4
10
3
0 0 1 1 3 3 3 3 4 4
0 1 4

13 2 9
2 9
0 1 2 3 5 6 7 11 12
*/ 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<long long> pri;
const long long INF=1e18;
long long l,n,m,a[1010],b[1010],delup,deldown,sols[4000010],cur,ans,s,mxs;
double mxp;
struct line
{
    long long l,r,num;
}lin[2000010];
long long nothingtimes;
void donothing()
{
    ++nothingtimes;
}
long long ABS(long long x)
{
    return x>=0?x:-x;
}
long long lint;
int main()
{
    scanf("%lld %lld %lld",&l,&n,&m);
    for(long long i=1;i<=n;++i)    scanf("%lld",&a[i]);
    for(long long i=1;i<=m;++i)    scanf("%lld",&b[i]);
    deldown=0;
    delup=l-b[m];
    deldown<<=1;
    delup<<=1;
    for(long long i=1;i<=n;++i)//第i个目标点 
    {
        for(long long j=1;j<m;++j)//位于第j个与第j+1个点之间 距离都*2了，因为中点可能不在格点上。 
        {
            //靠左
            long long l=a[i]*2-(b[j]+b[j+1]),r=(a[i]-b[j])*2;
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=-1;
                }
            }
            //靠右 
            l=a[i]*2-b[j+1]*2,r=a[i]*2-(b[j]+b[j+1]);
            if(l>delup||r<deldown||l>=r)    donothing();
            else
            {
                if(l<deldown)    l=deldown;
                if(r>delup)    r=delup;
                if(l>=r)    donothing();
                else
                {
                    lin[++lint].l=l;
                    lin[lint].r=r;
                    lin[lint].num=1;
                }
            }
        }
        //在第1个前面
        long long l=a[i]*2-b[1]*2,r=delup;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=1;
            }
        }
        //在第n个后面
        l=deldown,r=a[i]*2-b[m]*2;
        if(l>delup||r<deldown||l>=r)    donothing();
        else
        {
            if(l<deldown)    l=deldown;
            if(r>delup)    r=delup;
            if(l>=r)    donothing();
            else
            {
                lin[++lint].l=l;
                lin[lint].r=r;
                lin[lint].num=-1;
            }
        }
    }
    for(long long i=1;i<=lint;++i)
    {
        pri.push_back(lin[i].l);
        pri.push_back(lin[i].r);
    }
    sort(pri.begin(),pri.end());
    pri.erase(unique(pri.begin(),pri.end()),pri.end());
    s=pri.size();
    for(long long i=1;i<=lint;++i)
    {
        lin[i].l=lower_bound(pri.begin(),pri.end(),lin[i].l)-pri.begin()+1;
        lin[i].r=lower_bound(pri.begin(),pri.end(),lin[i].r)-pri.begin()+1;
    }
    for(long long i=1;i<=lint;++i)
    {
        sols[lin[i].l]+=lin[i].num;
        sols[lin[i].r]-=lin[i].num;
    }
    mxp=-1;
    mxs=-1;
    for(long long i=1;i<=n;++i)
    {
        long long nowpos=a[i]*2+deldown,minn=INF;
        for(long long j=1;j<=m;++j)    minn=min(minn,ABS(nowpos-b[j]*2));
        cur+=minn;
    }
    if(cur<=l*2)
    {
        mxp=deldown;
        mxs=cur;
    }
    for(long long i=1;i<=s;++i)    sols[i]+=sols[i-1];
    for(long long i=1;i<s;++i)
    {
        if(cur>l*2)
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                mxs=l*2;
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
            }
            cur=tmp;
        }
        else
        {
            long long tmp=cur+sols[i]*(pri[i]-pri[i-1]);
            if(tmp<=l*2)
            {
                if(tmp>=mxs)
                {
                    mxp=pri[i];
                    mxs=tmp;
                }
            }
            else
            {
                mxp=(l*2-cur)*1.0/sols[i]+pri[i-1];
                mxs=l*2;
            }
            cur=tmp;
        }
    }
    if(mxp==-1)    printf("NO\n");
    else    printf("%.6lf\n",mxp/2);
    return 0;
}

F

首先我们定义 $sec(i)$ 表示包含 $0 \sim i-1$ 的最小区间。因为添加新的元素不会使区间变小， 所以 $sec(i) \subseteq sec(i + 1)$ ，因此对于每个包含 $sec(i)$ 的区间， 它肯定是包含 $sec(1\sim i)$ 。若这个区间并不包含 $sec(i + 1)$ ， 则也可以得到这个区间不包含 $sec(i + 1 \sim n)$ 所以， 这个区间的贡献应该是 $i$ 。

将这 $i$ 的贡献分别分到 $sec(1 \sim i)$ 中， 我们的问题就变成了， 每一次添加元素后， $\large\sum \limits_{j= 1}^{i}$ 包含 $sec(j)$ 的区间个数。考虑一次插入后答案的变化，同时规定 $sec(0) = \varnothing$：

一次插入的数 $x$ 一定满足 $\exists y \in [0, i - 1], x \in sec(y), x \notin sec(y + 1)$ 。而这个 $y$ 是唯一的（这个应该很好想吧）。

所以， 我们可以预处理出每一个 $x$ 对应的 $y$ 。当插入 $x$ 的时候， 相当于在所有 $sec(1 \sim y)$ 的左（或右）边增加了 $1$ 个点。

此时增加的区间数量即是 $sec(1 \sim y)$ 右（或左）边的点个数之和（注意， 对于一个点是可以重复计算的）， 这里只需要用两个线段树分别记录 $sec(i)$ 左右当前各有多少点了。

Bonus：Solve it in $O(n)$！

#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 1000000
#define L(p) (p << 1)
#define R(p) ((p << 1) | 1) 
#define make_mid(l,r) int mid = (l + r) >> 1

int s[MAXN + 5];
pair <int, int> si[MAXN + 5];
int sl[MAXN + 5], sr[MAXN + 5];
struct node {
    long long v;
    long long sign;
    int h, t;
}s1[(MAXN << 4) + 5], s2[(MAXN << 4) + 5];

void build (int p, int l, int r) {
    s1[p].h = l;
    s1[p].t = r;
    s1[p].sign = 0;
    s1[p].v = 0;
    s2[p].h = l;
    s2[p].t = r;
    s2[p].sign = 0;
    s2[p].v = 0;
    if (l == r) {
        return ;
    }
    make_mid (l, r);
    build (L(p), l, mid);
    build (R(p), mid + 1, r);
}
void downloadl (int p) {
    if (s1[p].sign && s1[p].h < s1[p].t) {
        s1[L(p)].sign += s1[p].sign;
        s1[R(p)].sign += s1[p].sign;
        s1[L(p)].v += (s1[L(p)].t - s1[L(p)].h + 1) * s1[p].sign;
        s1[R(p)].v += (s1[R(p)].t - s1[R(p)].h + 1) * s1[p].sign;
        s1[p].sign = 0;
    }
}
void downloadr (int p) {
    if (s2[p].sign && s2[p].h < s2[p].t) {
        s2[L(p)].sign += s2[p].sign;
        s2[R(p)].sign += s2[p].sign;
        s2[L(p)].v += (s2[L(p)].t - s2[L(p)].h + 1) * s2[p].sign;
        s2[R(p)].v += (s2[R(p)].t - s2[R(p)].h + 1) * s2[p].sign;
        s2[p].sign = 0;
    }
}
void changel (int p, int l, int r, long long x) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        s1[p].v += x * (s1[p].t - s1[p].h + 1);
        s1[p].sign += x;
        
        return ;
    }
    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        changel (L(p), l, r, x);
    }
    if (r > mid) {
        changel (R(p), l, r, x);
    }
    s1[p].v = s1[L(p)].v + s1[R(p)].v;
}
void changer (int p, int l, int r, long long x) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        s2[p].v += x * (s2[p].t - s2[p].h + 1);
        s2[p].sign += x;
        
        return ;
    }
    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        changer (L(p), l, r, x);
    }
    if (r > mid) {
        changer (R(p), l, r, x);
    }
    s2[p].v = s2[L(p)].v + s2[R(p)].v;
}
long long Suml (int p, int l, int r) {
    downloadl (p);
    if (s1[p].h >= l && s1[p].t <= r) {
        return s1[p].v;
    }
    
    long long sum = 0;
    
    make_mid (s1[p].h, s1[p].t);
    if (l <= mid) {
        sum += Suml (L(p), l, r);
    }
    if (r > mid) {
        sum += Suml (R(p), l, r);
    }
    
    return sum;
}
long long Sumr (int p, int l, int r) {
    downloadr (p);
    if (s2[p].h >= l && s2[p].t <= r) {
        return s2[p].v;
    }
    
    long long sum = 0;
    
    make_mid (s2[p].h, s2[p].t);
    if (l <= mid) {
        sum += Sumr (L(p), l, r);
    }
    if (r > mid) {
        sum += Sumr (R(p), l, r);
    }
    
    return sum;
}

int main () {
    int n;
    
    scanf ("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int x;
        
        scanf ("%d", &x);
        s[x + 1] = i;//处理出i插入到的是哪个位置
    }
    build (1, 1, n);//初始两棵线段树
    //初始 sec(i)
    //----------------------------------------------
    si[1].first = s[1];
    si[1].second = s[1];
    for (int i = 2; i <= n; i ++) {
        si[i].first = min (si[i - 1].first, s[i]);
        si[i].second = max (si[i - 1].second, s[i]);
    }
    //----------------------------------------------
    //处理出 i 所对应的 y 且处理出到底是在 sec(y) 的左还是右
    for (int i = n - 1; i >= 1; i --) {
        for (int j = si[i + 1].first; j < si[i].first; j ++) {
            sr[j] = i;
        }
        for (int j = si[i + 1].second; j > si[i].second; j --) {
            sl[j] = i;
        }
    }
    
    long long ans = 0;//保存每次插入的答案
    long long Ans = 0;//保存最终答案
    
    for (int i = 1; i <= n; i ++) {
        if (sl[s[i]]) {
            ans += Suml (1, 1, sl[s[i]]);
            changer (1, 1, sl[s[i]], 1);
        }
        if (sr[s[i]]) {
            ans += Sumr (1, 1, sr[s[i]]);
            changel (1, 1, sr[s[i]], 1);
        }
        ans ++;//添加了 i 以后会多出 sec() ， 此处将其加入答案中
        changel (1, i, i, 1);
        changer (1, i, i, 1);
        Ans += ans;
    }
    printf ("%lld", Ans);
}

For some reason...

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
template<typename T=int> T read() {
    T x=0; char IO=getchar(); bool f=0;
    while(IO<'0' || IO>'9')    f|=IO=='-',IO=getchar();
    while(IO>='0' && IO<='9')    x=x*10+(IO&15),IO=getchar();
    return f?-x:x;
}
int n, a[1000100], mn[1000100], mx[1000100], pos1[1000100], pos2[1000100];
ll ans, _ans;
struct segment_tree {
    ll sum[4000100], tag[4000100];
    void up(const int now) {sum[now] = sum[now<<1]+sum[now<<1|1];}
    void down(const int now, int l, int r) {
        if(!tag[now]) return;
        int mid = (l+r)>>1;
        tag[now<<1] += tag[now],tag[now<<1|1] += tag[now];
        sum[now<<1] += (mid-l+1)*tag[now],sum[now<<1|1] += (r-mid)*tag[now];
        tag[now] = 0;
    }
    void go(int x, int y, ll k, const int now=1, int l=1, int r=n) {
        if(l > y || r < x) return;
        if(l >= x && r <= y) return tag[now] += k,sum[now] += (r-l+1)*k,void();
        int mid = (l+r)>>1; down(now, l, r);
        go(x, y, k, now<<1, l, mid),go(x, y, k, now<<1|1, mid+1, r);
        up(now);
    }
    ll ask(int x, int y, const int now=1, int l=1, int r=n) {
        if(l > y || r < x) return 0;
        if(l >= x && r <= y) return sum[now];
        int mid = (l+r)>>1; down(now, l, r);
        return ask(x, y, now<<1, l, mid)+ask(x, y, now<<1|1, mid+1, r);
    }
} t1, t2;
signed main() {
    freopen("sh.in", "r", stdin);
    freopen("sh.out", "w", stdout);
    n = read();
    for(int i = 1; i <= n; ++i) a[read()+1] = i;
    mn[1] = mx[1] = a[1];
    for(int i = 2; i <= n; ++i) mn[i] = min(mn[i-1], a[i]),mx[i] = max(mx[i-1], a[i]);
    for(int i = n-1; i; --i) {
        for(int j = mx[i+1]; j > mx[i]; --j) pos1[j] = i;
        for(int j = mn[i+1]; j < mn[i]; ++j) pos2[j] = i;
    }
    for(int i = 1; i <= n; ++i) {
        if(pos1[a[i]]) ans += t1.ask(1, pos1[a[i]]),t2.go(1, pos1[a[i]], 1);
        if(pos2[a[i]]) ans += t2.ask(1, pos2[a[i]]),t1.go(1, pos2[a[i]], 1);
        ans++,_ans += ans;
        t1.go(i, i, 1),t2.go(i, i, 1);
    }
    cout << _ans << "\n";
    return 0;
}

发现终于最讨厌的还是和自己的相同的人的样子。

A

傻逼题，不算复杂度差不多得了，显然交换 $S$ / $T$ 的选出区间中的任意位置不影响答案，于是前缀和即可。

B

清新题，只不过我的确不会...部分分设置不太合理。

你考虑用 $O(h ^ 2 w ^ 2)$ 的时间钦定两个点 $(x_1, y_1), (x_2, y_2)$ 研究线段，同时令 $a = |x_1 - x_2|, b = |y_1 - y_2|$。如果你做过 仪仗队 那么很容易想到中间一共有 $\gcd(a, b)$ 个点，把这些点当作盒子，把它们拍到序列上，则我们有 $\gcd(a, b) - 1$ 个盒子，$n - 2$ 个点（钦定端点必选）。如果我们令 $k=\lfloor\frac{d}{{\rm dis}((0, 0), (\frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)}))}\rfloor$，则每个球放进的盒子编号需差 $\geqslant k$。

赋予组合意义，则每个球存在「体积」的概念，且该「体积」为 $k - 1$，考虑将其压缩， 那么答案式子就出来了 $\binom{\gcd(a, b) - 1 - (k - 1) - (n - 2)(k - 1)}{n - 2}$，那个 $k - 1$ 是右端点已经必选了，所以少了 $k - 1$ 个盒子。

考虑优化，注意答案取决于 $a$ 和 $b$，可以乘个系数来优化。

C

清新题，部分分非常暗示。

有个显然的 observation 是一个结点一定从子树中至多选两个未被选择的结点转移，那么就可以直接可并堆启发式合并什么的来转移。

主要问题是为什么不是儿子中选呢？你考虑一个结点 $x$，其父亲 $pre(x)$ 只有 $x$ 一个儿子，而 $x$ 有三个儿子，并且 $x$ 把其中两个儿子选完了，那么 $pre(x)$ 一定是从 $x$ 的另一个儿子转移上来，所以必须把子树考虑完。

D

你出你🐎的 BM 呢😅😅。

题意大概是这样，「每次操作选出区间中的一个 LIS（strictly），满足其开端是极靠近左端点且大于 $A$ 的位置，答案即这个 LIS 的末尾，做一个轮换后弹出序列末端」。

首先做几个观察。

Observation 1：每次被弹出的都是区间最大值。

证明：显然，你考虑有一个最大的值在钦定的 LIS 的前或后，都会被先行选择 / 扩展进来。

Observation 2（key observation）：如果对一个区间插入若干个值，插入顺序不影响最终序列的长相。

证明：每次插入进去的值不可能成为序列的最大值，所以弹出的数固定。并且插入进的数是根据严格偏序关系插进去的，所以顺序不影响长相。

仅凭以上两个观察，此题的奇怪操作怎么看也不像是个 ${\rm polylog}$，选择对序列做 Sqrt Decomposition，接下来我们探讨整块间的处理方式和散块的做法，因为操作的特殊性我们并不需要做 8 种情况的伞兵讨论。

• 整块间：你考虑每个整块上维护一个大根堆，然后整块的后继继承该整块的最大值，该整块去除其最大值即可；
• 散块：把所有需要插入的元素存一个懒标在右边散块放出来，因为 Observation 2，我们贪心优先把值较小的懒标放出去即可。

#include <bits/stdc++.h>
template <class T> inline void chmax(T& a, const T b) { a = a > b ? a : b; }
template <class T> inline void chmin(T& a, const T b) { a = a < b ? a : b; }
inline long long rd() {
  long long x = 0; bool f = 0; char ch = getchar();
  while (ch < '0' || ch > '9') f |= (ch == '-'), ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + (ch & 15), ch = getchar();
  return f ? -x : x;
}
/** @brief
 * 选出一个 LIS，满足开始是极靠近 l 的大于 A 的位置，答案即序列的末端，然后用 A 替换序列开头，做一个轮换，弹出序列末端
 * Observation 1：每次被弹出的都是区间最大值
 * Trick：序列分块
 * Section 1：整块
   * 整块上维护一个堆，整块间下一块继承上一块的最大值
 * Section 2：散块
   * 维护一个小根堆，每次散块暴力重构
 * key observation：插入顺序不影响序列的长相
*/
constexpr int BS = 650;
int n, m, a[400100], pos[400100];
int L[660], R[660];
std::priority_queue<int> max[660];
std::priority_queue<int, std::vector<int>, std::greater<int>> tag[660];
void push(int i, int x) { max[i].emplace(x); }
void setBound(int i) { L[i] = (i - 1) * BS + 1, R[i] = i * BS; }
int Qry(int i, int l, int r, int x) {
  if (tag[i].size()) {
    for (int j = L[i]; j <= R[i]; ++j)
      if (int t = a[j]; tag[i].top() < t)
        a[j] = tag[i].top(), tag[i].pop(), tag[i].emplace(t);
  }
  while (max[i].size()) max[i].pop();
  while (tag[i].size()) tag[i].pop();
  for (int j = l; j <= r; ++j)
    if (a[j] > x) std::swap(a[j], x);
  for (int f = L[i]; f <= R[i]; ++f) push(pos[L[i]], a[f]);
  return x;
}
int Mdf(int i, int x) {
  if (x >= max[i].top()) return x;
  int res = max[i].top(); max[i].pop();
  max[i].emplace(x), tag[i].emplace(x);
  return res;
}
signed main() {
  n = rd(), m = rd();
  for (int i = 1; i <= n; ++i)
    push(pos[i] = (i - 1) / BS + 1, a[i] = rd());
  for (int i = 1; i <= pos[n]; ++i) setBound(i);
  R[pos[n]] = n;
  for (int l, r, a; m--;) {
    l = rd(), r = rd(), a = rd();
    if (pos[l] == pos[r] && l <= r) printf("%d\n", Qry(pos[l], l, r, a));
    else {
      a = Qry(pos[l], l, R[pos[l]], a);
      for (int u = pos[l] + 1 > pos[n] ? 1 : pos[l] + 1; u != pos[r]; u = u + 1 > pos[n] ? 1 : u + 1)
        a = Mdf(u, a);
      printf("%d\n", Qry(pos[r], L[pos[r]], r, a));
    }
  }
  return 0;
}