「解题报告」Codeforces Round 668 (Div. 2)

两场 Div.2 爆肝上蓝系列……

比赛链接

A. Permutation Forgery

这题是精心构造样例给选手降智啊….卡了我半小时 /kk
实际上反过来输出就好了啊…

const int CN = 110;
int a[CN], n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = n; i >= 1; i--) printf("%d ", a[i]); puts("");

B. Array Cancellation

容易发现答案就是后缀和的最大值…证明显然啊，就算了吧…

#define int long long
const int CN = 1e5 + 5;
int n, a[CN];
n = read(); for(int i = 1; i <= n; i++) a[i] = read();
int ans = max(0ll, a[n]); for(int i = n - 1; i; i--) a[i] += a[i + 1], ans = max(ans, a[i]);
printf("%lld", ans), puts("");

C. Balanced Bitstring

容易发现模 $k$ 相同的位置， 字符应当是相同的，那么模拟即可。

const int CN = 1e6 + 10;
int T, n, k; char a[CN], s[CN];
ios :: sync_with_stdio(false);
cin >> n >> k >> a;
    
for(int i = 0; i < k; i++) s[i] = '?'; bool flag = true;
for(int i = 0; i < n && flag; i++)
    if(a[i] != '?') {
        if(s[i % k] == '?') s[i % k] = a[i];
        else if(s[i % k] != a[i]) flag = false;
    }
    
int cnt0 = 0, cnt1 = 0;
for(int i = 0; i < k; i++)
    cnt1 += (s[i] == '1'), cnt0 += (s[i] == '0');
if(cnt0 > (k / 2) || cnt1 > (k / 2)) flag = false;

flag ? puts("YES") : puts("NO");

D. Tree Tag

容易发现初始位置看似是无用的，那么把树的直径找出来判断即可。

const int CN = 1e5 + 5;
int T, n, a, b, da, db;

class fs {public: int to,nxt; void init(int t,int n) {to = t, nxt = n;} } E[CN << 1];
int hd[CN], ecnt = 0; void add(int x,int y) {E[++ecnt].init(y, hd[x]); hd[x] = ecnt;}
void hinit() {for(int i = 0; i <= n; i++) hd[i] = 0;}

int d[CN], dm;
void dinit() {for(int i = 0; i <= n; i++) d[i] = 0;}
void dfs(int u, int p){
    for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) d[v] = d[u] + 1, dfs(v, u);}
}

int fa[CN][21], dep[CN];
void finit(){
    for(int i = 0; i <= 20; i++) for(int j = 0; j <= n; j++) fa[j][i] = 0;
    for(int i = 0; i <= n; i++) dep[i] = 0;
}
void pc(int u, int p){
    fa[u][0] = p, dep[u] = dep[p] + 1;
    for(int k = hd[u]; k; k = E[k].nxt) {int v = E[k].to; if(v ^ p) pc(v, u);}
}
int lca(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int k = 20; k + 1; k--) if(dep[ fa[u][k] ] >= dep[v]) u = fa[u][k];
    if(u ^ v) {for(int k = 20; k + 1; k--) if(fa[u][k] ^ fa[v][k]) u = fa[u][k], v = fa[v][k]; u = fa[u][0];}
    return u;
}
int dis(int u, int v) {return dep[u] + dep[v] - 2 * dep[lca(u, v)];}

int main() { T = read(); while(T--){ 
    hinit(), ecnt = 0;
    n = read(), a = read(), b = read(), da = read(), db = read();
    for(int i = 1; i < n; i++) {int u = read(), v = read(); add(u, v), add(v, u);}

    finit(), pc(1, 0);
    for(int k = 1; k <= 20; k++) for(int i = 1; i <= n; i++) fa[i][k] = fa[ fa[i][k - 1] ][k - 1];
    if(dis(a, b) <= da) {puts("Alice"); continue;}

    dinit(), dfs(1, 0); int mx = 0, p;
    for(int i = 1; i <= n; i++) mx = mx < d[i] ? p = i, mx = d[i] : mx;

    dinit(), dfs(p, 0), dm = 0;
    for(int i = 1; i <= n; i++) dm = max(dm, d[i]);

    if(2 * da >= dm) puts("Alice");
    else if(db >= 2 * da + 1) puts("Bob");
    else puts("Alice");
}}

E. Fixed Point Removal

容易发现一个点能否被消除仅与询问的左边界 $l$ 有关，设 $p_i$ 为可以令 $a_i$ 消除的最大的 $l$，则答案是 $\sum\limits_{i=l}^r[p_i\ge l]$，这是一个愉快的二维数点。
考虑 $p_i$ 如何求出，容易观察到如下性质：

1. 若 $a_i > i$，则可以定义 $p_i = 0$；
2. 若 $a_i = i$，显然 $p_i=i$；
3. 若 $a_i < i$，则 $p_i=\max m, \text{s.t.} \left( \sum\limits_{j=m}^{i-1}[p_j\ge m]\right) \ge i - a_i$

前两条都好处理，最后一条二分即可，套一个静态主席树解决二维数点，时间复杂度 $O(n\log^2 n+q\log n)$。

代码：

const int CN = 3e5 + 5;

class SGT {
  public: int d[CN * 50], ch[CN * 50][2], rt[CN], idx; SGT(){idx = 0;}
    #define lc ch[u][0]
    #define rc ch[u][1]
    void md(int &u, int v, int l, int r, int p){
        if(!u) u = ++idx;
        if(l == r) return (void)(d[u] = d[v] + 1);
        int m = (l + r) >> 1;
        if(p <= m) rc = ch[v][1], md(lc, ch[v][0], l, m, p);
        else lc = ch[v][0], md(rc, ch[v][1], m + 1, r, p);
        d[u] = d[lc] + d[rc];
    }
    int qu(int u, int v, int l, int r, int p){
        if(l == r) return d[u] - d[v];
        int m = (l + r) >> 1;
        if(p <= m) return d[rc] - d[ch[v][1]] + qu(lc, ch[v][0], l, m, p);
        else return qu(rc, ch[v][1], m + 1, r, p);
    }
} D;

int n, q, p[CN];

int main()
{
    n = read(), q = read();
    for(int i = 1; i <= n; i++){
        int ai = read();
        if(ai > i) p[i] = 0;
        else if(ai == i) p[i] = i;
        else{
            int l = 0, r = i - 1, m, minus = i - ai;
            while(l < r){
                m = (l + r + 1) >> 1;
                int cur = D.qu(D.rt[i - 1], D.rt[m - 1], 0, n, m);
                if(cur >= minus) l = m;
                else r = m - 1;
            }
            p[i] = l;
        }
        D.md(D.rt[i], D.rt[i - 1], 0, n, p[i]);
    }

    while(q--){
        int l = read(), r = read(); l++, r = n - r;
        printf("%d", D.qu(D.rt[r], D.rt[l - 1], 0, n, l)), puts("");
    }
}