2019 - 2020 ICPC, 아시아 자카르타 지역 대회 부분 해제

E. Songwriter
제목: 서열 A A A A 를 드 리 겠 습 니 다. 사전 서열 의 가장 작은 서열 B B B B 를 구성 하고 구조 요소 의 수치 범 위 를 [l, r] [l, r] [l, r] [l, r] 로 만족 시 켜 야 합 니 다. 또한 인접 요소 의 차 이 는 K K K 를 초과 하지 않 으 며 인접 요소 의 크기 관계 와 서열 A A A 가 대응 하 는 원소 유지 와 일치 합 니 다.
해법: 이 문 제 는 예전 에 풀 었 던 것 같 지만 이번 에는 풀 지 못 했 습 니 다. 우 리 는 L i, R i L 을 기억 합 니 다.{i},R_{i} Li, Ri 는 각각 B i B{i} Bi 의 합 법 적 인 수치 범위, 우 리 는 B B B 서열 을 거꾸로 밀어 L n = l, R n = r L 을 초기 화 합 니 다.{n}=l,R_{n} = r Ln = l, Rn = r, 만약 A i > A i + 1 A{i}>A_{i + 1} Ai > Ai + 1 그러면 R i = m i n (r, R i + 1 + k), L i = L i + 1 + 1 R{i}=min(r,R_{i+1}+k),L_{i}=L_{i + 1} + 1 Ri = min (r, Ri + 1 + k), Li = Li + 1 + 1, 만약 A i < A i + 1 A{i} Ai < Ai + 1, 그러면 R i = R i + 1 − 1, L i = m a x (l, L i + 1 − k) R{i}=R_{i+1}-1,L_{i} = max (l, L {i + 1} - k) Ri = Ri + 1 − 1, Li = max (l, Li + 1 − k), L i, R i L 구하 기{i},R_{i} Li, Ri 후 순 으로 구 조 를 밀어 내 면 됩 니 다.

#include 
using namespace std;
const int maxn = 1e5 + 10;
int L[maxn], R[maxn], a[maxn], b[maxn];
int main()
{
     
    int n, l, r, k;
    scanf("%d%d%d%d", &n, &l, &r, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    L[n] = l, R[n] = r;
    for (int i = n - 1; i; i--)
    {
     
        if (a[i] > a[i + 1])
        {
     
            R[i] = min(r, R[i + 1] + k);
            L[i] = L[i + 1] + 1;
        }
        else if (a[i] < a[i + 1])
        {
     
            L[i] = max(l, L[i + 1] - k);
            R[i] = R[i + 1] - 1;
        }
        else
            L[i] = L[i + 1], R[i] = R[i + 1];
        if (L[i] > R[i])
            return puts("-1"), 0;
    }
    int x = L[1];
    printf("%d", L[1]);
    for (int i = 2; i <= n; i++)
    {
     
        if (a[i] > a[i - 1])
            x = max(x + 1, L[i]);
        else if (a[i] < a[i - 1])
            x = max(L[i], x - k);
        printf(" %d", x);
    }
}

F. Regular Forestation
제목: 나무 한 그루 에 도수 의 최대 점 을 구하 고 도수 가 1 보다 많 으 면 이 점 이 뿌리 인 모든 하위 나무의 구조 가 같 고 출력 도수 가 같다.
해법: 누 드 트 리 hash, 하지만 모든 점 을 매 거 해 야 합 니 다. 그러면 뿌리 dp 를 바 꾸 어 모든 점 을 뿌리 로 하 는 나무 hash 를 구하 면 됩 니 다. 복잡 도 nlogn

#include 
#define ll long long
using namespace std;
const int maxn = 4005, mod1 = 998244353, mod2 = 1e9 + 7;
vector<int> G[maxn];
int p1[maxn], p2[maxn];
struct Hash
{
     
    int h1, h2, len;
} d[maxn];
vector<Hash> S[maxn];
int ans = -1;
bool cmp(int a, int b)
{
     
    return d[a].h1 < d[b].h1 || (d[a].h1 == d[b].h1 && d[a].h2 < d[b].h2);
}
Hash merge(Hash a, Hash b)
{
     
    Hash jie = Hash{
     0, 0, a.len + b.len};
    jie.h1 = (1ll * a.h1 * p1[b.len] + b.h1) % mod1;
    jie.h2 = (1ll * a.h2 * p2[b.len] + b.h2) % mod2;
    return jie;
}
void dfs(int u, int fa)
{
     
    d[u] = Hash{
     1, 1, 1};
    for (auto v : G[u])
        if (v != fa)
            dfs(v, u);
    sort(G[u].begin(), G[u].end(), cmp);
    for (auto v : G[u])
        if (v != fa)
            d[u] = merge(d[u], d[v]);
}
void dfs2(int u, int fa)
{
     
    d[u] = Hash{
     1, 1, 1};
    sort(G[u].begin(), G[u].end(), cmp);
    Hash cat{
     0, 0, 0};
    int jie = 1;
    S[u].push_back(Hash{
     1, 1, 1});
    for (auto v : G[u])
    {
     
        d[u] = merge(d[u], d[v]);
        if (cat.len == 0)
            cat = d[v];
        else if (cat.h1 != d[v].h1 || cat.h2 != d[v].h2)
                jie = 0;
        S[u].push_back(d[u]);
    }
    if (jie && G[u].size() > 1)
        ans = max(ans, (int)G[u].size());
    Hash nvshen{
     0, 0, 0};
    for (int i = G[u].size() - 1; ~i; i--)
    {
     
        d[u] = merge(S[u][i], nvshen);
        nvshen = merge(d[G[u][i]], nvshen);
        if (G[u][i] != fa)
            dfs2(G[u][i], u);
    }
}
int main()
{
     
    p1[0] = p2[0] = 1;
    for (int i = 1; i < maxn; i++)
    {
     
        p1[i] = 1ll * p1[i - 1] * 199967 % mod1;
        p2[i] = 1ll * p2[i - 1] * 199999 % mod2;
    }
    int n, u, v;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
     
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    dfs2(1, 0);
    printf("%d
", ans);
}

G. Performance Review
제목: n n n 의 개인 능력 치 를 제시 합 니 다. 당신 은 첫 번 째 사람 입 니 다. 그리고 m m 의 변동 을 제시 합 니 다. 매번 변동 회사 의 해고 능력 치가 가장 낮은 k k k 개인 은 모든 사람의 능력 치가 서로 다 르 도록 보장 한 다음 에 k k k 개인 에 가입 하고 그들의 능력 치 를 제시 합 니 다.그리고 m m 차 변동 후 잘 리 냐 고 물 었 습 니 다. 매번 작업 의 수정 은 영구적 으로 수정 되 었 습 니 다 (다음 작업 에 영향 을 줍 니 다).
해법: 우리 p i p{i} pi 는 전 i i 차 변동 중 능력 치가 나 보다 낮은 사람의 총 수량, s u m i sum{i} sumi 는 전 i i 차 작업 에서 자 른 사람의 수 를 합 쳐 라인 트 리 로 p i - s u m i p 를 유지 합 니 다.{i}-sum_{i} pi − sumi 의 최소 값 이면 됩 니 다. 최소 값 이 0 보다 적 으 면 잘 릴 것 입 니 다.

#include 
using namespace std;
const int maxn = 1e5 + 10;
int mn[maxn * 4], tag[maxn * 4], a[maxn];
vector<int> b[maxn];
#define ls o * 2
#define rs o * 2 + 1
#define mid (l + r) / 2
void pushdown(int o)
{
     
    if (tag[o])
    {
     
        tag[ls] += tag[o];
        tag[rs] += tag[o];
        mn[ls] += tag[o];
        mn[rs] += tag[o];
        tag[o] = 0;
    }
}
void up(int o, int l, int r, int ql, int qr, int v)
{
     
    if (l >= ql && r <= qr)
    {
     
        mn[o] += v;
        tag[o] += v;
        return;
    }
    pushdown(o);
    if (ql <= mid)
        up(ls, l, mid, ql, qr, v);
    if (qr > mid)
        up(rs, mid + 1, r, ql, qr, v);
    mn[o] = min(mn[ls], mn[rs]);
}
int main()
{
     
    int n, m, q, res = 0, sum = 0, k, x, v;
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
    {
     
        scanf("%d", &a[i]);
        if (i > 1 && a[i] < a[1])
            res++;
    }
    for (int i = 1; i <= m; i++)
    {
     
        scanf("%d", &k);
        sum += k;
        up(1, 1, m, i, i, res - sum);
        for (int j = 1; j <= k; j++)
        {
     
            scanf("%d", &x);
            if (x < a[1])
                res++;
            b[i].push_back(x);
        }
    }
    while (q--)
    {
     
        scanf("%d%d%d", &k, &x, &v);
        if (b[k][x - 1] > a[1])
        {
     
            if (v < a[1] && k < m)
                up(1, 1, m, k + 1, m, 1);
        }
        else
        {
     
            if (v > a[1] && k < m)
                up(1, 1, m, k + 1, m, -1);
        }
        b[k][x - 1] = v;
        if (mn[1] < 0)
            puts("0");
        else
            puts("1");
    }
}

J. Tiling Terrace 보충, 인터넷 부분 문제 풀이 의 복잡 도 의심... K. Addition Robot
제목: 문제 면 을 분명하게 말 하 다.
해법: 누 드 라인 트 리 유지 행렬 곱셈

#include 
#define ll long long
#define ls o * 2
#define rs o * 2 + 1
#define mid (l + r) / 2
using namespace std;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
void add(int &x, int y)
{
     
    x += y;
    if (x >= mod)
        x -= mod;
    if (x < 0)
        x += mod;
}
struct seg
{
     
    int A[2][2], B[2][2], tag;
    seg operator+(const seg &t) const
    {
     
        seg jie;
        jie.tag = 0;
        memset(jie.A, 0, sizeof(jie.A));
        memset(jie.B, 0, sizeof(jie.B));
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                for (int k = 0; k < 2; k++)
                {
     
                    add(jie.A[i][j], 1ll * A[i][k] * t.A[k][j] % mod);
                    add(jie.B[i][j], 1ll * B[i][k] * t.B[k][j] % mod);
                }
        return jie;
    }
} cat[maxn * 4];
char s[maxn];
void build(int o, int l, int r)
{
     
    if (l == r)
    {
     
        cat[o].A[0][0] = 1, cat[o].A[0][1] = 0, cat[o].A[1][0] = 1, cat[o].A[1][1] = 1;
        cat[o].B[0][0] = 1, cat[o].B[0][1] = 1, cat[o].B[1][0] = 0, cat[o].B[1][1] = 1;
        if (s[l] == 'B')
            swap(cat[o].A, cat[o].B);
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    cat[o] = cat[ls] + cat[rs];
}
void pushdown(int o)
{
     
    if (cat[o].tag)
    {
     
        swap(cat[ls].A, cat[ls].B);
        cat[ls].tag ^= 1;
        swap(cat[rs].A, cat[rs].B);
        cat[rs].tag ^= 1;
        cat[o].tag = 0;
    }
}
void up(int o, int l, int r, int ql, int qr)
{
     
    if (l >= ql && r <= qr)
    {
     
        swap(cat[o].A, cat[o].B);
        cat[o].tag ^= 1;
        return;
    }
    pushdown(o);
    if (ql <= mid)
        up(ls, l, mid, ql, qr);
    if (qr > mid)
        up(rs, mid + 1, r, ql, qr);
    cat[o] = cat[ls] + cat[rs];
}
seg qu(int o, int l, int r, int ql, int qr)
{
     
    if (l >= ql && r <= qr)
        return cat[o];
    pushdown(o);
    if (qr <= mid)
        return qu(ls, l, mid, ql, qr);
    else if (ql > mid)
        return qu(rs, mid + 1, r, ql, qr);
    else
        return qu(ls, l, mid, ql, qr) + qu(rs, mid + 1, r, ql, qr);
}
int main()
{
     
    int n, q, opt, l, r, a, b;
    scanf("%d%d%s", &n, &q, s + 1);
    build(1, 1, n);
    while (q--)
    {
     
        scanf("%d%d%d", &opt, &l, &r);
        if (opt == 1)
            up(1, 1, n, l, r);
        else
        {
     
            scanf("%d%d", &a, &b);
            seg jie = qu(1, 1, n, l, r);
            ll ans1 = 1ll * a * jie.A[0][0] + 1ll * b * jie.A[1][0];
            ll ans2 = 1ll * a * jie.A[0][1] + 1ll * b * jie.A[1][1];
            printf("%lld %lld
", ans1 % mod, ans2 % mod);
        }
    }
}