冲刺NOIP2021模拟27

T1

这种无序序列先排个序

发现序列\(a\)最终状态是固定的，即操作完并排序后只有一种可能的序列

设\(c_i\)表示\(a_i\)加了多少次

这个时候加的总数是固定的，最优方案是\(c_i\)升序和\(b_i\)降序后相乘

那么要满足最大的c尽量大

倒序加a即可

T2

发现有贡献的只有全局 mex

然后左端点固定，mex有单调性

然后枚举右端点，维护mex恰好为全局mex的左端点

然后简单dp

T3

考虑建出两棵克鲁斯卡尔重构树，分别满足x，y的lca是原树上的x，y路径上的最小值和最大值

然后满足题目限制的x，y在两棵树上分别互为祖先

这个可以对第一棵树求出dfs序，然后dfs第二棵树，树状数组维护x的祖先的第一棵树的dfs序

代码

T1

#include 
using namespace std;
#define ull unsigned long long
const int N = 1e6 + 4;
struct ans_ {
    int a, num;
};
int n;
int c[N];
int a[N], b[N];
deque dui;
inline bool cmp(int a, int b) { return a > b; }
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
int main() {
    FILE* x = freopen("openhook.in", "r", stdin);
    x = freopen("openhook.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    ull ans = 0;
    int maxx = a[n];
    for (int i = n - 1; i; --i) {
        if (a[i] != a[i + 1]) {
            dui.push_front({ a[i], a[i + 1] - a[i] });
        }
        if (!dui.size()) {
            c[i] = maxx - a[i] + 1;
            ++maxx;
        } else {
            c[i] = dui.front().a - a[i];
            --dui.front().num;
            ++dui.front().a;
            if (!dui.front().num)
                dui.pop_front();
        }
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; ++i) ans += 1ull * c[i] * b[i];
    cout << ans << endl;
    return 0;
}

T2

#include 
using namespace std;
const int N = 3.7e7 + 4;
const int mod = 1e9 + 7;
int n;
int mex;
int a[N];
int f[N];
int ton[N];
inline void md(int& x) {
    if (x >= mod)
        x -= mod;
    return;
}
void init() {
    for (int i = 0; i <= n; ++i) ton[i] = 0;
    return;
}
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
int main() {
    FILE* p = freopen("clods.in", "r", stdin);
    p = freopen("clods.out", "w", stdout);
    int t = read();
    while (t--) {
        n = read();
        if (n == 3.7e7) {
            int x = read();
            int y = read();
            a[1] = 0;
            for (int i = 2; i <= 3.7e7; ++i) a[i] = (a[i - 1] * x + y + i) & 262143;
        } else
            for (int i = 1; i <= n; ++i) a[i] = read();
        mex = 0;
        init();
        for (int i = 1; i <= n; ++i) {
            ++ton[a[i]];
            while (ton[mex]) ++mex;
        }
        int now = 0;
        init();
        for (int i = 1; i <= n; ++i) {
            ++ton[a[i]];
            while (ton[now]) ++now;
            if (now >= mex) {
                now = i;
                break;
            }
        }
        int sum = 1;
        int st = now;
        now = 1;
        --ton[a[st]];
        for (int i = 1; i <= n; ++i) f[i] = 0;
        for (int i = st; i <= n; ++i) {
            ++ton[a[i]];
            while (now < i && (a[now] > mex || (ton[a[now]] - 1))) {
                md(sum += f[now]);
                --ton[a[now]];
                ++now;
            }
            f[i] = sum;
        }
        cout << f[n] << endl;
    }
    return 0;
}

T3

#include 
using namespace std;
const int N = 2e6 + 11;
struct qxxx {
    int v, next;
} cc[2 * N];
struct ed_ {
    int x, y;
} e[N];
int n;
int f[N];
int tre[N];
int siz[N];
int dfn[N], st;
int first[N], cnt;
int sta[N], num;
long long ans;
vector mx[N];
vector mn[N];
void pre() {
    for (int i = 1; i <= n; ++i) f[i] = i;
    return;
}
void insert(int x, int val) {
    for (; x <= n; x += (x & -x)) tre[x] += val;
    return;
}
int query(int x) {
    int sum = 0;
    for (; x; x -= (x & -x)) sum += tre[x];
    return sum;
}
int find(int x) {
    if (x == f[x])
        return x;
    return f[x] = find(f[x]);
}
void qxx(int u, int v) {
    cc[++cnt] = (qxxx){ v, first[u] };
    first[u] = cnt;
    return;
}
inline int max_(int a, int b) { return a > b ? a : b; }
inline int min_(int a, int b) { return a > b ? b : a; }
inline bool cmpmx(ed_ a, ed_ b) { return max_(a.x, a.y) < max_(b.x, b.y); }
inline bool cmpmn(ed_ a, ed_ b) { return min_(a.x, a.y) > min_(b.x, b.y); }
inline int read() {
    int s = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') ch = getchar();
    while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s;
}
void pre_tre() {
    pre();
    sort(e + 1, e + n, cmpmn);
    for (int x, y, j = 1; j < n; ++j) {
        x = e[j].x;
        y = e[j].y;
        x = find(x);
        y = find(y);
        if (x < y)
            f[y] = x, mn[x].push_back(y);
        else
            f[x] = y, mn[y].push_back(x);
    }
    pre();
    sort(e + 1, e + n, cmpmx);
    for (int x, y, j = 1; j < n; ++j) {
        x = e[j].x;
        y = e[j].y;
        x = find(x);
        y = find(y);
        if (x < y)
            f[x] = y, mx[y].push_back(x);
        else
            f[y] = x, mx[x].push_back(y);
    }
    return;
}
void dfs_mn(int x) {
    siz[x] = 1;
    dfn[x] = ++st;
    for (int y, i = 0; i < mn[x].size(); ++i) {
        y = mn[x][i];
        dfs_mn(y);
        siz[x] += siz[y];
    }
    return;
}
void get_ans(int x) {
    ans += query(dfn[x] + siz[x] - 1) - query(dfn[x]);
    insert(dfn[x], 1);
    for (int y, i = 0; i < mx[x].size(); ++i) {
        y = mx[x][i];
        get_ans(y);
    }
    insert(dfn[x], -1);
    return;
}
signed main() {
    FILE* p = freopen("charity.in", "r", stdin);
    p = freopen("charity.out", "w", stdout);
    n = read();
    read();
    for (int x, i = 2; i <= n; ++i) {
        x = read();
        e[i - 1] = (ed_){ x, i };
    }
    pre_tre();
    dfs_mn(1);
    get_ans(n);
    cout << ans << endl;
    return 0;
}