Educational Codeforces Round 35 (Rated for Div. 2)

A. Nearest Minimums

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int a[N], n, ans = 1e9;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    int t = *min_element (a + 1, a + n + 1);
    int l = -1e9;
    for (int i = 1; i <= n; i++) {
        if (a[i] == t)  ans = min (ans, i - l), l = i;
    }
    cout << ans;
}

B. Two Cakes

注意最后一次特判一下（已经死了的敌人是不会攻击我的）

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
int n, a, b, ans;

int main () {
    cin >> n >> a >> b;
    for (int i = 1; i <= min (a, n); i++) { //a被分了i块
        int j = n - i; //b被分了j块
        if (j > b || j <= 0)  continue;
        ans = max (ans, min (a / i, b / j));
    }
    cout << ans << endl;
}

C. Three Garlands

即 \(\frac{1}{k1}+\frac{1}{k2}+\frac{1}{k3} \geq 1\)
所以共四种情况：

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;

int main () {
    map<int, int> mp;
    for (int i = 0; i < 3; i++) {
        int x;  cin >> x;
        mp[x]++;
    }
    if (mp[1] >= 1 || mp[2] >= 2 || mp[3] >= 3 || (mp[4] == 2 && mp[2] == 1)) cout << "YES";
    else    cout << "NO";
}

D. Inversion Counting

思维题。

考虑反转区间后的奇偶性变化。
当前区间为 \([l,r]\)，则共有 \(len=r-l+1\) 个数，则有 \(x=\frac{len\times (len-1)}{2}\) 个数对。设其中逆序对数量为 \(cnt\)，则正序对数量为 \(x-cnt\)，反转 \([l,r]\) 之后，逆序对数量变为原正序对数量，即 \(x-cnt\)。故翻转前后逆序对差值为 \(x-2\times cnt\)。

又因为任何数加减偶数奇偶性不变，加减奇数奇偶性改变，所以只需看差值 \(x-2\times cnt\) 的奇偶性即可，而 \(2\times cnt\) 必为偶数，故看 \(x\) 就行。
只需算出初始逆序对数量，然后每次根据区间长度来决定逆序对数量是否改变。

#include <bits/stdc++.h>

using namespace std;
const int N = 1005;
int a[N], n, m, st;

int main () {
    cin >> n;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[j] > a[i])    st++;
        }
    }
    st &= 1;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        int len = r - l + 1;
        len = len * (len - 1) / 2;
        if (len & 1)    st ^= 1;
        if (st == 1)    cout << "odd\n";
        else    cout << "even\n";    
    }
}

//差值: len*(len-1)/2 - 2*x

E. Stack Sorting

递归处理。类似dp的思想。

\(f[x,l,r]\) 表示当前安排到第 \(x\) 个数，可用值范围在 \([l,r]\) 的安排方案
若第 \(x\) 个数为 \(a_x\)，且 \(a_x\) 在 \([l,r]\) 范围内，则 \(f[x,l,r]\) 可被划分为 \(f[x+1,l,a_x-1]\) 和 \(f[x+1+a_x-1,a_x+1,r]\)。
若第 \(x\) 个数未被安排，则直接贪心安排 \(r,r-1,r-2,...,l+1,l\)
特判冲突。

这样划分保证了连续段一定在一起，且连续的一定下降。

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int a[N], n, m;
bool suc = true;

void f (int x, int l, int r) {
    if (l > r || !suc)  return ;
    if (l == r) {
        if (a[x] && l != a[x]) suc = false;
        else    a[x] = l;
        return ;
    }
    if (a[x]) {
        if (a[x] >= l && a[x] <= r)     f (x + 1, l, a[x] - 1), f (x + 1 + a[x] - l, a[x] + 1, r);
        else    suc = false;
    }
    else {
        for (int i = 0; i < r - l + 1; i++)     a[x+i] = r - i;
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)    cin >> a[i];
    f (1, 1, n);
    if (!suc)   cout << "-1\n";
    else {
        for (int i = 1; i <= n; i++)    cout << a[i] << ' ';
    }
}

//f[l][r]: [l,r]可安排方案
//f[l][r] = a[x] + f[l][x-1] + f[x+1][r]

F. Tree Destruction

首先可以找到树上的一条直径

树的直径求法：任意找一个点进行dfs，找到离他最远的点，记为 x，再从 x 开始 dfs，找到离 x 最远的点 y。{x,y} 就是树的直径。（证明见oi-wiki）

对于树上的点，若该点不在直径上，则计算其距离直径两端点的最远距离（另一端点距离用倍增求lca算），计入贡献，然后把该点删掉。非直径点全部删完之后，再从端点开始，把直径一点一点删掉。

注意一些小细节：
对于非树上的点要从叶节点开始删，可用的处理方法是在 dfs 时记录点的 dfs 序，按dfs 序降序来进行删点（这是因为叶子节点的dfs 序一定比他父亲要大）。

注意取long long。

第二次dfs前要清空

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 2e5 + 5, M = N * 2;
int h[N], e[M], ne[M], idx;
ll n, d[N], maxd, id, len;
int st, ed, ff[N], dfn[N], idx2;
ll dep[N], f[N][35];
bool vis[N]; ///标记直径上的点
ll ans;
int p[N]; //根据dfs序来做直径外点删除

struct Node { //操作序列
    int l, r, del; //选l,r删del
};

void add (int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs (int u, int fa) {
    d[u] = d[fa] + 1;
    ff[u] = fa, dfn[u] = ++idx2;
    if (d[u] > maxd)    maxd = d[u], id = u;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (j == fa)    continue;
        dfs (j, u);
    }
}

void bfs (int root) {
    memset (dep, 0x3f, sizeof dep); //记得
    queue <int> q;
    q.push (root);
    dep[root] = 1, dep[0] = 0;

    while (!q.empty()) {
        int t = q.front();
        q.pop ();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dep[j] > dep[t] + 1) {
                dep[j] = dep[t] + 1;
                q.push (j);
                f[j][0] = t;
                for  (int k = 1; k <= 30; k++) {
                    f[j][k] = f[f[j][k-1]][k-1];
                }
            }
        }
    }
}

int lca (int a, int b) {
    if (dep[a] < dep[b])    swap (a, b); //确保a往上跳
    //cout << a << ' ' << b << endl;
    for (int k = 30; k >= 0; k--) {
        if (dep[f[a][k]] >= dep[b]) { //注意是>=
            a = f[a][k];
        }
        //cout << a << ' ';
    }
    //cout << endl;
    if (a == b)     return a;
    for (int k = 30; k >= 0; k--) {
        if (f[a][k] != f[b][k]) {
            a = f[a][k], b = f[b][k];
        }
        //cout << a << ' ' << b << endl;
    }
    return f[a][0];
}

bool cmp (int x, int y) { //dfs序更大的为叶子
    return dfn[x] > dfn[y];
}

int main () {
    memset (h, -1, sizeof h);
    scanf ("%d", &n);
    for (int i = 1; i < n; i++) {
        int a, b;
        scanf ("%d%d", &a, &b);
        add (a, b), add (b, a);
    }
    dfs (1, 0);
    st = id, vis[st] = true, maxd = 0, idx2 = 0;
    //cout << id << endl;

    memset (d, 0, sizeof d);
    dfs (st, 0);
    ed = id, vis[ed] = true, len = d[ed];
    int tt = ed;
    //cout << st << ' ' << ed << endl;
    while (ff[tt] != st)    tt = ff[tt], vis[tt] = true; //标记直径
    // for (int i = 1; i <= n; i++)   if (vis[i])    cout << i << ' '; cout << endl;
    // cout << len << endl; //直径长度
    
    vector<Node> v;
    bfs (st); //倍增求lca预处理
    // for (int i = 1; i <= n; i++)    cout << dep[i] << ' ';cout << endl;
    // for (int i = 1; i <= n; i++) {
    //     cout  << i << ' ' << ed << ' ' << lca (i, ed) << endl;
    //     cout << "================\n";
    // }
    // for (int i = 1; i <= n; i++)    cout << dfn[i] << ' '; cout << endl;
    for (int i = 1; i <= n; i++)    p[i] = i;
    sort (p + 1, p + n + 1, cmp);
    for (int i = 1; i <= n; i++) { //直径外的点找远端点
        int id = p[i];
        if (vis[id]) continue;
        //i到st距离为 d[i],i到ed距离为d[i]+d[ed]-2*d[lca]
        int p = lca (id, ed), l;
        int d1 = dep[id] - 1, d2 = dep[id] + dep[ed] - 2 * dep[p];
        // cout << "p: " << p << endl;
        // cout << "dep: " << dep[i] << ' ' << dep[ed] << ' ' << dep[p] << endl;
        // cout << i << ": " << d1 << ' ' << d2 << endl;
        if (d1 >= d2)   l = st, ans += d1;
        else    l = ed, ans += d2;
        v.push_back ({l, id, id});
    }
    // cout << ans << ' ';

    //删直径
    tt = ed;
    len--;
    while (ff[tt] != st) {
        ans += len--;
        v.push_back ({st, tt, tt});
        tt = ff[tt];
        //cout << ans << ' ';
    } 
    ans++;
    v.push_back ({st, tt, tt});

    printf ("%lld\n", ans);
    for (auto i : v)    printf ("%d %d %d\n", i.l, i.r, i.del);
    
    //cout << log2(2e5) << endl;
}

//求直径
//在直径外的点从叶子子开始随意删，直径最后处理，一个一个删

G. Mass Change Queries

线段树合并，线段树分裂。
注意到 \(a_i\) 的值域非常小，所以考虑从权值线段树入手。而维护整个区间不太好处理（难修改）。
所以对 \(1-100\) 每个值都建一棵线段树。
把 \([l,r]\) 范围内的 \(x\) 全部修改成 \(y\) 的实质就是，把线段树 \(x\) 上的区间 \([l,r]\) 分裂出来，合并到线段树 \(y\) 的区间 \([l,r]\) 上。

注意代码细节。注意空间大小

// LUOGU_RID: 117344656
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5, M = 105;
int va[N], n, m, ans[N];
int root[M], idx; //100颗权值线段树

struct Node {
    int l, r;
}st[N * M]; //2e5次询问 * 100棵树

void build (int &u, int l, int r, int v) { //建立权值线段树
    if (l > v || r < v) return ;
    if (u == 0)     u = ++idx; //开新树
    if (l == r)     return ;
    int mid = l + r >> 1; //值域二分
    build (st[u].l, l, mid, v), build (st[u].r, mid + 1, r, v);
}

int merge (int a, int b) {
    if (!a || !b)   return a + b;
    st[a].l = merge (st[a].l, st[b].l);
    st[a].r = merge (st[a].r, st[b].r);
    return a;
}

void spilt (int &a, int &b, int l, int r, int ql, int qr) {
    if (!a)     return ;
    if (l > qr || r < ql)   return ;
    if (l >= ql && r <= qr) {
        b = merge (a, b), a = 0; //分裂a的[l,r],合并到b的[l,r]上
        return ;
    }
    if (!b)     b = ++idx;
    int mid = l + r >> 1;
    spilt (st[a].l, st[b].l, l, mid, ql, qr);
    spilt (st[a].r, st[b].r, mid + 1, r, ql, qr);
}

void count (int u, int l, int r, int v) {
    if (!u)     return ;
    if (l == r) {
        ans[l] = v;
        return ;
    }
    int mid = l + r >> 1;
    count (st[u].l, l, mid, v);
    count (st[u].r, mid + 1, r, v);
}

int main () {
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++)    scanf ("%d", &va[i]), build (root[va[i]], 1, n, i);
    scanf ("%d", &m);
    while (m--) {
        int l, r, x, y;
        scanf ("%d%d%d%d", &l, &r, &x, &y);
        if (x == y)     continue;
        spilt (root[x], root[y], 1, n, l, r);
    }
    for (int i = 1; i <= 100; i++)  count (root[i], 1, n, i);
    for (int i = 1; i <= n; i++)    printf ("%d ", ans[i]);
}

//开100颗权值线段树, 改值就是线段树合并和分裂