# 某岛

… : "…アッカリ～ン . .. . " .. .
June 22, 2022

## Problem B. Fake Plastic Trees

const int N = int(2e5) + 9;

int n, z;

void dfs(int u) {
LL s = 0; for (int v: adj[u]) dfs(v), s += r[v];
if (s < l[u]) ++z;
else checkMin(r[u], s);
}

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

Rush {
REP_1(i, n) RD(l[i],r[i]);
z = 0; dfs(1);
cout << z << endl;
}
}


## Problem D. Decinc Dividing

const int N = int(2e5) + 9;

int a[N], f[N], g[N], n;
// f_i, in inc, max dec
// g_i, in dec, min inc

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n); REP(i, n) RD(a[i]);
LL z = 0; int p = n;
DWN(i, n, 0) {
f[i] = n+1; g[i] = 0;
FOR(j, i+1, n) {
int fj = 0, gj = n+1;
if (a[j-1] < a[j]) checkMax(fj, f[j-1]);
if (g[j-1] < a[j]) checkMax(fj, a[j-1]);
if (a[j-1] > a[j]) checkMin(gj, g[j-1]);
if (f[j-1] > a[j]) checkMin(gj, a[j-1]);
if (fj == f[j] && gj == g[j]) break;
f[j] = fj; g[j] = gj;
if (fj == 0 && gj == n+1) {
p = j;
break;
}
}
z += p-i;
}
cout << z << endl;
}


## Problem E. Outermost Maximums

– 将最左边的最大值修改为它左边的次大值。
– 将最右边的最大值修改为它右边的次大值。

//13542
//..?.. +1
//..<?. +1
//.??>. +2
//.<<?? +2
//???>> +3


## Problem F. I Might Be Wrong

### 题解

– 是否已经排序
– 是否再进行一次操作可以完成排序
– 否则进行一次操作，使得下标尽可能向右移，继续迭代