NEERC 2016 选做

发表于 | 更新于 | 分类于 | 阅读次数：

Q：弟啊你 NEERC 2015 咋还没做完呢
A：咕了（指太菜看不懂题解）

2016-2017 ACM-ICPC Northeastern European Regional Contest (NEERC 16)

  • B - Binary Code
  • C - Cactus Construction
  • D - Delight for a Cat
  • G - Game on Graph
  • I - Indiana Jones and the Uniform Cave
  • K - Kids Designing Kids
  • L - List of Primes
  • M - Mole Tunnels

C - Cactus Construction

题意简述

给定一棵仙人掌（$n\le 5\times 10^5$），你需要构造它。
初始时，每个点颜色都为1，每个点都是仅有一个点的子图。
你有三种操作：

  1. $join(u, v)$：把子图 $v$ 合并进子图 $u$。
  2. $connect(u, a, b)$：把子图 $u$ 中颜色为 $a$ 的所有点与颜色为 $b$ 的所有点连边。
    注意若原本存在颜色 $a$ 的点与颜色 $b$ 的点之间有边，会连出重边，然而众所周知仙人掌是没有重边的，所以要避免这种情况。
  3. $recolor(u, a, b)$：把子图 $u$ 中颜色为 $a$ 的所有点改为颜色 $b$。

假设你的操作数量是 $m$，操作间出现过的颜色数量是 $c$，那么你需要保证 $m\le 10^6, c\le 4$。

主要思路

考虑树怎么做。从下往上合并，保证子树内只有根的颜色是 $2$，其他都是 $1$。合并一个儿子的时候把儿子改成颜色 $3$，合并连上后，再把颜色 $3$ 改成 $1$。
考虑环怎么做。我们选定一个「根」，那么剩下的部分就是一条链。
我们把链头染成颜色 $2$，在接入下一个点时选择一个链上当前未出现的颜色 $c$，把新接入的点染成该色，再把另一色的原本的链尾和新接入的点连边，再把原本的链尾改成颜色 $1$。
整条链做完后，把链尾染成颜色 $2$，用类似合并儿子的方法接入「根」即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef pair<int, int> PII;
typedef vector<int> VI;
#define SZ(x) ((int)x.size())
#define pb emplace_back
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("cactus.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    Templ(_Tp) inline INPUT& operator >>(_Tp &x){
        x = 0;
        reg char c(*s++);
        while(c < 48) c = *s++;
        while(c > 47) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("cactus.out", "w")){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        return *this;
    }
    inline OUTPUT& operator <<(char x){
        *s++ = x;
        return *this;
    }
    ~OUTPUT(){
        fwrite(buf, 1, s - buf, F);
        fclose(F);
    }
}fout;

struct qry{
    int t, a, b, c;
    inline qry(int _t, int _a, int _b, int _c)
        : t(_t), a(_a), b(_b), c(_c){}
};
vector<qry> ans;
#define join(a, b) ans.pb(qry(0, a, b, 0))
#define recolor(a, b, c) ans.pb(qry(1, a, b, c))
#define connect(a, b, c) ans.pb(qry(2, a, b, c))
inline void print_ans(){
    fout << SZ(ans) << '\n';
    for(reg qry x: ans){
        if(!x.t) fout << 'j' << ' ' << x.a << ' ' << x.b << '\n';
        else fout << "rc"[x.t - 1] << ' ' << x.a << ' ' << x.b << ' ' << x.c << '\n';
    }
}

#define N 100010
int n, m;
VI E[N], T[N];

namespace Tarjan{
int dfn[N], low[N], pc, cc;
int sk[N], *st(sk);
void dfs(const int &u){
    dfn[u] = low[u] = ++ pc;
    *++st = u;
    for(Rint v: E[u]){
        if(!dfn[v]){
            dfs(v), chkmin(low[u], low[v]);
            if(low[v] >= dfn[u]){
                ++cc, T[u].pb(cc);
                do{
                    T[cc].pb(*st);
                }while(*st-- != v);
            }
        }else{
            chkmin(low[u], dfn[v]);
        }
    }
}
int main(){
    cc = n;
    dfs(1);
    return 0;
}
}

int id[N];

void dfs(const int &u){
    if(u <= n){
        id[u] = u;
        recolor(u, 1, 2);
        for(Rint v: T[u]){
            dfs(v);
            recolor(id[v], 2, 3);
            join(id[u], id[v]);
            connect(id[u], 2, 3);
            recolor(id[u], 3, 1);
        }
    }else{
        if(SZ(T[u]) == 1){
            Rint v = T[u][0];
            dfs(v), id[u] = id[v];
            return;
        }
        dfs(T[u][0]), id[u] = id[T[u][0]];
        dfs(T[u][1]);
        recolor(id[T[u][1]], 2, 4);
        join(id[u], id[T[u][1]]);
        connect(id[u], 2, 4);
        Rint tl = 4, nc = 3;
        //tail color, next color
        for(Rint v: T[u]) if(!id[v]){
            dfs(v);
            recolor(id[v], 2, nc);
            join(id[u], id[v]);
            connect(id[v], 3, 4);
            recolor(id[u], tl, 1);
            swap(tl, nc);
        }
        recolor(id[u], tl, 2);
    }
}

int main() {
    fin >> n >> m;
    FOR(i, 1, m){
        Rint k, u, v;
        fin >> k >> u;
        FOR(i, 1, k - 1){
            fin >> v;
            E[u].pb(v), E[v].pb(u);
            u = v;
        }
    }
    Tarjan::main();
    dfs(1);
    print_ans();
    return 0;
}

G - Game on Graph

题意简述

一张有向图，两人0,1在玩游戏。游戏规则非常简单：图上有一棋子，两人轮流操作，每人每次将棋子沿当前位置的某条出边移动，不能动的人就输了。
但是由于一些特殊原因，0最希望游戏永远不要停止；若无法达到，其也会尽可能追求赢。1最不希望游戏永远不停止；若可以使游戏停止，其宁愿输。
现在请对于每个点作为棋子的开始点，每个人作为先手，求最后的状态是什么（赢/输/无法结束）。
$n\le 10^5, m\le 2\times 10^5$。

主要思路

设一个游戏状态为一个二元组 $(x, c)$ 表示当前棋子在点 $x$，此时操作的是 $c$。
0若1无论如何操作都可以使游戏无法结束，他就会令游戏无法结束；否则1会阻止游戏无法结束。
1若0无论如何操作都可以自己赢，那他会使自己赢；否则0会阻止1赢。
而其余的情况，0会赢。

考虑清楚这一点之后，就可以设 $ending(x, c), winning(x, c)$ 分别表示 $(x, c)$ 状态能否结束、1能否赢。

考虑用反向 bfs 来求 $ending$。
首先，显然对于所有没有出度的状态 $(x, c)$，它们均能结束。把这些状态全扔队列里。
考虑 $(x, 1)$ 如何能够结束：只要它的下一个可能状态中有一个可以结束，它就能结束；
而 $(x, 0)$ 要结束，必须要它的每一个下一个可能状态都可以结束。

同样用反向 bfs 来求 $winning$，可以发现转移方式完全一致。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef pair<int, int> PII;
typedef vector<int> VI;
#define pb emplace_back
#define fr first
#define sc second
#define MP make_pair
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("game.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    Templ(_Tp) inline INPUT& operator >>(_Tp &x){
        x = 0;
        reg char c(*s++);
        while(c < 48) c = *s++;
        while(c > 47) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("game.out", "w")){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 32;
        return *this;
    }
    inline OUTPUT& operator <<(char x){
        *s++ = x;
        return *this;
    }
    ~OUTPUT(){
        fwrite(buf, 1, s - buf, F);
        fclose(F);
    }
}fout;

//0: D - W - L
//1: W - L - D

#define N 100010
int n, m;
VI to[N], fm[N];
//正向边 / 反向边
int oud[N];

inline void init(){
    fin >> n >> m;
    Rint u, v;
    FOR(i, 1, m){
        fin >> u >> v;
        to[u].pb(v);
        fm[v].pb(u);
    }
}

queue<PII> Q;
inline void work(bool (*f)[2]){
    FOR(i, 1, n) oud[i] = to[i].size();
    FOR(i, 1, n) FOR(c, 0, 1) if(f[i][c]) Q.push(MP(i, c));
    while(!Q.empty()){
        PII now = Q.front();
        Q.pop();
        Rint u = now.fr;
        if(now.sc){
            for(int v: fm[u]) if(!f[v][0] && !--oud[v]){
                f[v][0] = 1;
                Q.push(MP(v, 0));
            }
        }else{
            for(int v: fm[u]) if(!f[v][1]){
                f[v][1] = 1;
                Q.push(MP(v, 1));
            }
        }
    }
}

bool endable[N][2], winning[N][2];
//endable[u][c]: 从 u 开始、c 先手时，1 是否能令其结束
//winning[u][c]: 从 u 开始、c 先手时，1 能否胜出

int main() {
    init();
    FOR(i, 1, n) if(to[i].empty())
        endable[i][0] = endable[i][1] = winning[i][0] = 1;
    work(endable);
    work(winning);
    FOR(i, 1, n){
        if(!endable[i][0]) fout << 'D';
        else if(winning[i][0]) fout << 'L';
        else fout << 'W';
    }
    fout << '\n';
    FOR(i, 1, n){
        if(winning[i][1]) fout << 'W';
        else if(endable[i][1]) fout << 'L';
        else fout << 'D';
    }
    return 0;
}

K - Kids Designing Kids

题意简述

给你三个01矩阵 $A, B, C$。
问是否能够通过平移 $B$ 并与 $A$ 异或（并删去全为0的部分行列）获得 $C$。若是顺便输出 $B$ 的平移方法。
$w, h\le 10^3$。

主要思路

完全没思路，看了一眼题解。

Find the top-left freckle in each of three given pictures.
We’ll prove that after moving the figures, some two of these three freckles must be in the same point.

大概就是说：三个最左上的1有两个移动后在同一位置。于是检验三种就可以了。
被打傻了.jpg

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define N 2020

const bool __file__ = [&](){
    freopen("kids.in", "r", stdin);
    freopen("kids.out", "w", stdout);
    return true;
}();

char buf[N];
bool dt[N][N];
#define T 1000

struct G{
    int X, Y;
    bool a[N][N];
    inline G(const bool &__empty__){
        if(__empty__){
            memset(a, 0, sizeof(a));
            X = Y = 0;
        }
    }
    inline G(){
        int n, m;
        scanf("%d%d", &n, &m);
        FOR(i, 1, n){
            scanf("%s", buf + 1);
            FOR(j, 1, m) if(buf[j] == '*'){
                if(!X) X = -i, Y = -j;
                a[i + X + T][j + Y + T] = 1;
            }
        }
    }
    inline void mv(int x, int y){
        X += x, Y += y;
        memcpy(dt, a, sizeof(dt));
        FOR(i, 0, T * 2) FOR(j, 0, T * 2){
            if(i - x < 0 || i - x > T * 2 ||
                j - y < 0 || j - y > T * 2)
                a[i][j] = 0;
            else a[i][j] = dt[i - x][j - y];
        }
    }
}A, B, C;

inline bool chk(const G &a, const G &b, G &c){
    G t(true);
    int X = 0xffff, Y = 0xffff;
    FOR(i, 0, T * 2) FOR(j, 0, T * 2){
        t.a[i][j] = a.a[i][j] ^ b.a[i][j];
        if(X == 0xffff && t.a[i][j])
            X = T - i, Y = T - j;
    }
    if(X == 0xffff) X = Y = 0;
    t.mv(X, Y);
    FOR(i, 0, T * 2) FOR(j, 0, T * 2){
        if(t.a[i][j] != c.a[i][j]) return false;
    }
    c.X -= X, c.Y -= Y;
    return true;
}

const bool __main__ = [&](){
    if(chk(A, B, C) || chk(B, C, A) || chk(C, A, B))
        printf("YES\n%d %d\n", B.Y - A.Y, B.X - A.X);
    else puts("NO");
    return true;
}();

int main() {
    return 0;
}

L - List of Primes

题意简述

现在有无穷个（不可重）集合，每个集合中全都是质数。把它们先按照元素总和、再按照字典序排序。
每个集合输出，集合开始先输出[，集合结束输出]，无论两个元素还是两个集合之间都要用,连接。
则会形成一个无限长的字符串，下列为前70个字符。

1
[2], [3], [2, 3], [5], [2, 5], [7], [3, 5], [2, 7], [2, 3, 5], [3, 7],

求第 $l$ 到第 $r$ 个字符，$l,r\le 10^{18}, r - l\le 10^5$。

主要思路

猜想集合的和不会太大（事实证明是2099）。
于是直接类似背包地 dp 一下即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
typedef long long i64;
#define FORit(i, a, b) for (auto *i = (a), *ed_##i = (b); i != ed_##i; ++i)
} // namespace my_std
using namespace my_std;

#define MMR (1 << 18)
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("list.out", "w")), s(buf){}
    inline OUTPUT& operator <<(const char &x){
        *s++ = x;
        return *this;
    }
    ~OUTPUT(){ fwrite(buf, 1, s - buf, F), fclose(F); }
}fo;


#define N 330
#define M 2100

int pr[N], pc;
int len[N];
int m0[10];
inline void init_p(){
    static bool b[M + 20];
    FOR(i, 2, M){
        if(!b[i]) pr[++pc] = i;
        for(Rint j(1); i * pr[j] <= M && j <= pc; ++j){
            b[i * pr[j]] = 1;
        }
    }
    m0[0] = 1;
    FOR(i, 1, 9) m0[i] = m0[i - 1] * 10;
    FOR(i, 1, pc){
        len[i] = 2;
        FOR(o, 0, 5) len[i] += m0[o] <= pr[i];
    }
    // FOR(i, 1, pc) fo << pr[i] << " " << i << "\n";
}

i64 cnt[N][M + 10], sum[N][M + 10];
//(i, S): 目前集合中不小于 pr[i] 的数和为 S
inline void init_f(){
    ROF(i, pc, 1){
        const int P = pr[i];
        cnt[i][0] = 1, sum[i][0] = 2;
        // FOR(j, 1, P - 1){
        //     cnt[i][j] = cnt[i + 1][j];
        //     sum[i][j] = sum[i + 1][j];
        // }
        FOR(j, P, M){
            cnt[i][j] = cnt[i + 1][j - P] + cnt[i + 1][j];
            sum[i][j] = sum[i + 1][j - P] + sum[i + 1][j] + 
                        cnt[i + 1][j - P] * len[i];
        }
    }
}

i64 L, R, T;
int sk[N], st, slen;

#define pcr(x)               \
    ++T, L <= T && T <= R && \
        (fo << char(x), 1)
// inline void pcr(char x){
//     ++T, L <= T && T <= R &&
//         (fo << x, 1);
// }
inline void write(int x){
    static int tmp[20];
    Rint *top = tmp;
    do{
        *++top = (x % 10) ^ 48, x /= 10;
    }while(x);
    while(top != tmp) pcr(*top), --top;
}

void work(const int &K, const int &S){
    const int P = pr[K];
    // printf("work(%d, %d): %d\n", K, S, T);
    if(S < 0 || T > R) return;
    if(S == 0){
        pcr('[');
        FOR(i, 1, st - 1){
            write(sk[i]);
            pcr(','), pcr(' ');
        }
        if(st > 0){
            write(sk[st]);
            pcr(']'), pcr(','), pcr(' ');
        }
        return;
    }
    if(S < P) return;
    reg i64 res;
    sk[++st] = P;
    slen += len[K];
    res = slen * cnt[K + 1][S - P] + sum[K + 1][S - P];
    // printf("res: %lld\n", res);
    if(T + res < L) T += res;
    else work(K + 1, S - P);

    sk[st--] = 0;
    slen -= len[K];
    res = slen * cnt[K + 1][S] + sum[K + 1][S];
    if(T + res < L) T += res;
    else work(K + 1, S);
}

int main() {
    FILE *fi = fopen("list.in", "r");
    fscanf(fi, "%lld%lld", &L, &R);
    fclose(fi);
    init_p();
    init_f();
    FOR(S, 2, M){
        if(T > R) break;
        i64 res = sum[1][S];
        if(T + res < L) T += res;
        else work(1, S);
        if(T > R) break;
    }
    return 0;
}

M - Mole Tunnels

题意简述

有一棵 $1$ 为根 $n$ 个点边全为 $(i, \lfloor\frac{i}{2}\rfloor)$ 的树。
树上每个点有食物 $c_i$。有 $m$ 只鼹鼠，分别在点 $p_i$。
对于每个 $k\le m$ 求：若前 $k$ 只鼹鼠都去找一个食物（即点 $x$ 不能有超过 $c_x$ 只鼹鼠），鼹鼠的总路程最小是多少。
$n, m\le 10^5$，保证食物够。

主要思路

某人表示：这不是经典题吗
我一看，Luogu 6122
怎么做啊，自闭了。

首先有个简单的费用流思路：

  • 总路径长度：所有树边流量为正无穷，费用为 $1$。
  • 鼹鼠的终点要有食物：相当于 $i$ 向汇点连一条流量为 $c_i$ 费用为 $0$ 的边。
  • 进入一只鼹鼠：相当于源点向 $p_i$ 连一条流量为 $1$ 费用为 $0$ 的边。

考虑费用流的过程。
新加入一只鼹鼠时，设其出发点为 $u$，到达的点为 $v$，则我们会在 $u$ 到 $v$ 的路径经过的每条边上建一条费用为 $-1$ 流量为 $1$ 的反向边。而对 $v$ 的选择，其实就是选使得 $u\to v$ 路径上总费用最小（且 $v$ 到汇点的边未流满）的点 $v$。

注意到二叉树的树高为 $O(\log n)$，所以可以暴力枚举 $u$ 的所有祖先 $a$。对每个节点 $a$，维护 $a$ 子树内使得 $a\to v$ 路径上总费用最小（且 $v$ 到汇点的边未流满）的点 $v$，记为 $pos(a) = v$。
对于所有祖先 $a$，取 $pos(a)$ 中最优的一个，作为真实的 $v$。然后在 $u\to v$ 的路径上添加反向边，并更新 $u, v$ 及其所有祖先的 $pos$ 即可。

$O(n\log n)$。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <bits/stdc++.h>
namespace my_std {
using namespace std;
#define reg register
#define Rint register int
#define FOR(i, a, b) for (register int i = (a), ed_##i = (b); i <= ed_##i; ++i)
#define ROF(i, a, b) for (register int i = (a), ed_##i = (b); i >= ed_##i; --i)
typedef long long i64;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define pb push_back
#define fr first
#define sc second
#define pq priority_queue
#define MP make_pair
#define Templ(T) template <typename T>
Templ(_Tp) inline int chkmin(_Tp &x, _Tp y) { return x > y ? x = y, 1 : 0; }
Templ(_Tp) inline int chkmax(_Tp &x, _Tp y) { return x < y ? x = y, 1 : 0; }
} // namespace my_std
using namespace my_std;

#define MMR (1 << 23)
struct INPUT{
    FILE *F;
    char buf[MMR], *s, *t;
    INPUT(): F(fopen("mole.in", "r")){
        t = (s = buf) + fread(buf, 1, MMR, F);
        fclose(F);
    }
    Templ(_Tp) inline INPUT& operator >>(_Tp &x){
        x = 0;
        reg char c(*s++);
        while(c < 48) c = *s++;
        while(c > 47) x = x * 10 + c - 48, c = *s++;
        return *this;
    }
}fin;
struct OUTPUT{
    FILE *F;
    char buf[MMR], *s;
    OUTPUT(): F(fopen("mole.out", "w")){ s = buf; }
    inline OUTPUT& operator <<(int x){
        static int tmp[10];
        Rint *top = tmp;
        do{
            *++top = (x % 10) ^ 48, x /= 10;
        }while(x);
        while(top != tmp) *s++ = *top--;
        *s++ = 32;
        return *this;
    }
    ~OUTPUT(){
        fwrite(buf, 1, s - buf, F);
        fclose(F);
    }
}fout;

#define inf 0777777
#define N 100010
int n, m;
int c[N];
int f[N], p[N];
int up[N], dn[N];

#define lc ((t) << 1)
#define rc ((t) << 1 | 1)
#define fa ((t) >> 1)

int ans;

inline void upd(const int &t){
    f[t] = inf;
    if(lc <= n && chkmin(f[t], f[lc] + (dn[lc] ? -1 : 1)))
        p[t] = p[lc];
    if(rc <= n && chkmin(f[t], f[rc] + (dn[rc] ? -1 : 1)))
        p[t] = p[rc];
}
inline void work(const int &u){
    Rint res = inf, w = 0, v = 0;
    for(Rint t = u, k = 0; t; t = fa){
        if(chkmin(res, f[t] + k))
            w = t, v = p[t];
        if(fa) k += up[t] ? -1 : 1;
    }
    --c[v];
    fout << (ans += res);
    for(Rint t = u; t != w; t = fa){
        if(up[t]) --up[t];
        else ++dn[t];
        if(c[t]) f[t] = 0, p[t] = t;
        else upd(t);
    }
    for(Rint t = v; t != w; t = fa){
        if(dn[t]) --dn[t];
        else ++up[t];
        if(c[t]) f[t] = 0, p[t] = t;
        else upd(t);
    }
    for(Rint t = w; t; t = fa){
        if(c[t]) f[t] = 0, p[t] = t;
        else upd(t);
    }
}

int main() {
    fin >> n >> m;
    FOR(i, 1, n) fin >> c[i];
    FOR(i, 1, n) f[i] = inf;
    ROF(t, n, 1){
        if(c[t]) f[t] = 0, p[t] = t;
        if(fa && chkmin(f[fa], f[t] + 1))
            p[fa] = p[t];
    }
    Rint x;
    FOR(i, 1, m) work((fin >> x, x));
    return 0;
}