APIO 2019

https://apio2019.ru/

https://oj.uz/problems/source/389

https://koosaga.com/232

내가 참가한 첫번째 apio 대회이다. 대회 결과는... 30점으로 매우 참혹한 점수가 나왔다.

나는 대회시간에 device 를 읽고 어려운 수학문제라 판단하여 기본적인 부분점수만 긁고 풀지 않았는데, 이것이 가장 쉬운 문제였다. 대신 나는 마지막 문제였던 lamps에 모든 시간을 쏟아부었고, 결국 완벽한 풀이를 찾은 후 2D segment tree 구현, 경로압축까지 구현을 끝냈는데 MLE가 나서 결국 이것도 섭태밖에 긁지 못했다. 나중에 다시 풀어보니 경로압축 없이 fenwick + dynamic segment tree 하나만 있어도 AC가 나왔다...

이번 년도의 문제들은 평소보다 비교적 쉬웠다고 할 수 있다. (특히 작년에 비해서)

1. Device

문제를 잘 읽어보면 x=t+[t/B] (mod A) , y=t (mod B) 일때 (x, y)를 세어야 한다.

가장 먼저 생각해 볼 것은 언젠가는 (x, y) 에 주기성이 생길 것이라는 것이다. 이제 이 주기만 구해보자.

y=t (mod B) 에서 t를 하나씩 증가하다보면 B를 주기로 y가 반복된다. 동시에 x에 [t/B] 항이 있는것으로 t가 B만큼 증가하면 이 값도 B를 주기로 1씩 증가한다는 것을 알 수 있다. 다시 말해, 정확히 B가 증가하면 x는 1+B가 증가한다.

(1+B)k mod A 가 0이 되는 최소의 k를 p라 한다면, 주기 q=pB 가 된다.

A|(1+B)p 이고, gcd(A, 1+B)=g라 하면 A/g | (1+B)/g p 이고, A/g, (1+B)/g 는 서로소이므로 p=A/g가 된다.

결론적으로, 찾고있는 주기는 A*B/gcd(A, 1+B) 가 된다. 이제 주기 T를 구했으니 답을 구해보자.

[0, T) 구간 위에 입력으로 주어지는 구간들을 색칠해 보자.

구간이 [0, T) 를 완전히 덮는다면 답은 T이고, 아니라면 l<=r 일 때, l>r일때로 나누어 각각 색칠해준 후, 마지막에 한번의 스위핑을 통해 답의 개수를 세주면 된다.

이때 주의해야할 것은 A, B는 10^18 이하이기 때문에 계산 과정에서 오버플로우가 날 수 있으니 이를 유의해야 한다.

시간 복잡도 : O(NlgN)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e6;
const ll INF = numeric_limits<ll>::max();
 
ll a, b, n, ans;
pll arr[MAXN+10];
 
int main()
{
    int i, j;
 
    scanf("%lld%lld%lld", &n, &a, &b);
    for(i=1; i<=n; i++) scanf("%lld%lld", &arr[i].first, &arr[i].second);
 
    ll g=__gcd(a, (b+1)%a);
    a/=g;
 
    bool over = false;
    if(INF/b<a) over=true;
    else a*=b;
 
    if(over)
    {
        for(i=1; i<=n; i++) ans+=arr[i].second-arr[i].first+1;
        return !printf("%lld", ans);
    }
 
    vector<pll> A;
    for(i=1; i<=n; i++)
    {
        if(arr[i].second-arr[i].first+1>=a) return !printf("%lld", a);
        arr[i].first%=a;
        arr[i].second%=a;
 
        if(arr[i].second<arr[i].first) A.push_back({arr[i].first, a-1}), A.push_back({0, arr[i].second});
        else A.push_back(arr[i]);
    }
 
    sort(A.begin(), A.end());
 
    ll s=-1, e=-2;
    for(i=0; i<A.size(); i++)
    {
        if(e<A[i].first) ans+=e-s+1, s=A[i].first;
        e=max(e, A[i].second);
    }
    ans+=e-s+1;
    printf("%lld", ans);
}

2. Lamps

먼저, 지금 당장 어떤 두 점이 연결되어 있는지를 어떻게 확인할 수 있을까? 연결된 가로등의 도로들은 하나의 구간을 이룬다. 이 구간을 [s, e]라 표현하고 이를 이차원 좌표평면상에 플로팅 하면 여러 개의 점들로 표현이 된다.

이제 이미 있는 구간 [l, r]에 대해서 a->b로 갈 수 있는지 확인하기 위해서는 [l, r]안에 [a, b]가 속하는지만 확인하면 된다. 이는 l<=a && b<=r, 즉 2차원 좌표평면 상에서는 a, b의 왼쪽 위쪽에 점이 있는지 확인하면 된다.

이제 이것을 이용하여 문제를 풀어 보자. 만약 처음 이후 가로등의 갱신 쿼리가 들어오지 않는다고 생각해보자. 처음에 있던 구간은 Q+1만큼의 시간 동안 성능을 발휘할 가능성이 있다. 이제 만약 어떤 점이 시간 t에 삭제된다고 생각하자. 원래는 Q+1만큼의 성능을 발휘할 가능성이 있었지만, 시간 t이후로는 성능이 없어지기 때문에 t만큼 빼준다고 생각하면 된다. 

답을 구할 때는 일단 그 점의 왼쪽 위의 점들의 합을 구한다. 그런데, 각 점들은 지금 남은 시간만큼의 가능성을 더 갖고 있기 때문에 이 값은 점의 수 * 남은 시간의 값이 추가로 더해져 있을 것이다. 이를 해결하기 위하여 단순히 점들의 값의 합 뿐만 아니라 점들의 수의 합도 구해서 같이 계산해주면 된다.

이와 같이 현재 남은 시간의 값을 점들에 더해주거나 빼주면 된다. 이제 필요한 연산은 N*N 평면에서 점 하나에 어떤 값들을 더해주거나 빼주고, 주어진 구간 안에 있는 점들의 값의 합을 구하는 것이다. 이는 2D segment tree를 이용하면 구현할 수 있다. 

하지만 메모리 제한을 초과한다. 이를 해결하기 위하여 2d segment tree를 최적화하는 여러 방법들을 사용해 보자. 

1. 바깥쪽 segment tree는 굳이 segment tree일 필요가 없다. 가장 효율적이고 구현도 짧은 Fenwick Tree로 바꾸자. -> AC!

2. 안쪽의 Dynamic segment tree 는 IOI 2013 game 의 경로 압축 트릭을 이용하자.

3. 포인터는 느리니 모두 배열로 고정 할당 한 다음 하나씩 배정해주자.

4. 아에 2D Segment Tree를 쓰지 말자!

오프라인 문제이고 2차원 평면 상의 합 쿼리이므로 분할정복과 Fenwick Tree 하나로 해결할 수 있다.

시간 복잡도 : O(Qlg^2N)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 3e5;
 
int N, Q, A[MAXN+10];
 
set<int> S, E;
pii range(int x) { return pii(*(--S.upper_bound(x)), *E.lower_bound(x)); }
 
pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }
 
struct Node1
{
    pll val;
    Node1 *lc, *rc;
    Node1() : lc(NULL), rc(NULL) {}
};
Node1 *tree[MAXN+10];
 
void update1(Node1 *node, int tl, int tr, int x, pll val)
{
    node->val=node->val+val;
    if(tl==tr) return;
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x, val);
    }
}
 
pll query1(Node1 *node, int tl, int tr, int l, int r)
{
    if(tr<l || r<tl) return pll(0, 0);
    if(l<=tl && tr<=r) return node->val;
    int mid=tl+tr>>1;
    pll ret(0, 0);
    if(node->lc!=NULL) ret=ret+query1(node->lc, tl, mid, l, r);
    if(node->rc!=NULL) ret=ret+query1(node->rc, mid+1, tr, l, r);
    return ret;
}
 
void update2(int y, int x, pll val)
{
    int i, j; y=N-y+1;
    for(i=y; i<=N; i+=(i&-i)) update1(tree[i], 1, N, x, val);
}
 
pll query2(int y, int x)
{
    int i, j;
    pll ret(0, 0); y=N-y+1;
    for(i=y; i>0; i-=(i&-i)) ret=ret+query1(tree[i], 1, N, 1, x);
    return ret;
}
 
int main()
{
    int i, j;
 
    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%1d", &A[i]);
    for(i=1; i<=N; i++) tree[i]=new Node1();
 
    set<int>::iterator it, jt;
    for(i=1; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
    for(i=1; i<=N; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);
 
    for(it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update2(*jt, *it, pll(Q+1, 1));
 
    for(i=1; i<=Q; i++)
    {
        char st[10];
        int a, b;
 
        scanf("%s", st);
        if(st[0]=='t')
        {
            scanf("%d", &a);
 
            if(A[a]==0)
            {
                if(S.find(a+1)!=S.end() && E.find(a-1)!=E.end())
                {
                    update2(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    update2(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    E.erase(a-1);
                }
                else if(S.find(a+1)!=S.end())
                {
                    update2(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    S.insert(a);
                }
                else if(E.find(a-1)!=E.end())
                {
                    update2(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    E.erase(a-1);
                    E.insert(a);
                }
                else
                {
                    S.insert(a);
                    E.insert(a);
                }
                update2(range(a).second, range(a).first, pll((Q-i+1), 1));
                A[a]=1;
            }
            else
            {
                int s, e;
                tie(s, e)=range(a);
 
                update2(range(a).second, range(a).first, pll(-(Q-i+1), -1));
                if(s==e)
                {
                    S.erase(a);
                    E.erase(a);
                }
                else if(s==a)
                {
                    S.erase(a);
                    S.insert(a+1);
                    update2(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                else if(e==a)
                {
                    E.erase(a);
                    E.insert(a-1);
                    update2(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                }
                else
                {
                    S.insert(a+1);
                    E.insert(a-1);
                    update2(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                    update2(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                A[a]=0;
            }
        }
        else
        {
            scanf("%d%d", &a, &b); b--;
            pll ret=query2(b, a);
            printf("%lld\n", ret.first-ret.second*(Q-i+1));
        }
    }
}

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 3e5;
 
int N, Q, A[MAXN+10];
 
set<int> S, E;
pii range(int x) { return pii(*(--S.upper_bound(x)), *E.lower_bound(x)); }
 
pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }
 
struct Data
{
    int t, y, x; pll val;
    bool operator < (const Data &p) const { return x<p.x; }
};
vector<Data> todo;
 
struct BIT
{
    pll tree[MAXN+10];
    void update(int i, pll v) { for(; i<=N; i+=(i&-i)) tree[i]=tree[i]+v; }
    pll query(int i) { pll ret(0, 0); for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }
    void flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=pll(0, 0); }
}bit;
 
void update(int y, int x, pll v) { todo.push_back({0, N-y+1, x, v}); }
void query(int y, int x, ll v) { todo.push_back({0, 0, 0, {0, 0}}); todo.back()={1, N-y+1, x, {v, todo.size()-1}}; }
 
pll ans[MAXN*10+10];
 
void solve(int s, int e)
{
    int i, j;
    if(s==e)
    {
        if(todo[s].t)
        {
            pll ret=ans[s];
            printf("%lld\n", ret.first-ret.second*todo[s].val.first);
        }
        return;
    }
 
    int mid=s+e>>1;
    solve(s, mid);
 
    vector<Data> A, B;
    for(i=s; i<=mid; i++) if(!todo[i].t) A.push_back(todo[i]);
    for(i=mid+1; i<=e; i++) if(todo[i].t) B.push_back(todo[i]);
 
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
 
    for(i=0, j=0; i<B.size(); i++)
    {
        for(; j<A.size() && A[j].x<=B[i].x; j++) bit.update(A[j].y, A[j].val);
        ans[B[i].val.second]=ans[B[i].val.second]+bit.query(B[i].y);
    }
    for(j=0; j<A.size(); j++) bit.flush(A[j].y);
 
    solve(mid+1, e);
}
 
int main()
{
    int i, j;
 
    scanf("%d%d", &N, &Q);
    for(i=1; i<=N; i++) scanf("%1d", &A[i]);
 
    set<int>::iterator it, jt;
    for(i=1; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
    for(i=1; i<=N; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);
 
    for(it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update(*jt, *it, pll(Q+1, 1));
 
    for(i=1; i<=Q; i++)
    {
        char st[10];
        int a, b;
 
        scanf("%s", st);
        if(st[0]=='t')
        {
            scanf("%d", &a);
 
            if(A[a]==0)
            {
                if(S.find(a+1)!=S.end() && E.find(a-1)!=E.end())
                {
                    update(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    update(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    E.erase(a-1);
                }
                else if(S.find(a+1)!=S.end())
                {
                    update(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
                    S.erase(a+1);
                    S.insert(a);
                }
                else if(E.find(a-1)!=E.end())
                {
                    update(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
                    E.erase(a-1);
                    E.insert(a);
                }
                else
                {
                    S.insert(a);
                    E.insert(a);
                }
                update(range(a).second, range(a).first, pll((Q-i+1), 1));
                A[a]=1;
            }
            else
            {
                int s, e;
                tie(s, e)=range(a);
 
                update(range(a).second, range(a).first, pll(-(Q-i+1), -1));
                if(s==e)
                {
                    S.erase(a);
                    E.erase(a);
                }
                else if(s==a)
                {
                    S.erase(a);
                    S.insert(a+1);
                    update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                else if(e==a)
                {
                    E.erase(a);
                    E.insert(a-1);
                    update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                }
                else
                {
                    S.insert(a+1);
                    E.insert(a-1);
                    update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
                    update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
                }
                A[a]=0;
            }
        }
        else
        {
            scanf("%d%d", &a, &b); b--;
            query(b, a, Q-i+1);
        }
    }
 
    solve(0, todo.size()-1);
}

3. Bridges

가장 먼저 중요한 섭태 4를 풀어 보자.

업데이트가 없으니 전체 간선과 쿼리를 모두 가중치가 감소하는 순서대로 정렬한 후에, 하나씩 추가하면서 Union-Find 자료구조를 통하여 답을 구해주면 된다.

이제 업데이트가 있는 경우를 생각해 보자.

IOI Elephants, 단조성이 없는 CHT 와 같은 주저장소-부저장소 의 아이디를 이용하여 해결할 수 있다. 전체 쿼리를 B개의 묶음씩 나누고 생각하자.

지금 보고 있는 버킷 이전의 업데이트는 모두 처리했다면, 이번 버킷에서 업데이트되지 않는 간선들은 이전의 업데이트 결과를 그대로 유지할 것이다. 이들은 내림차순으로 정렬해놓고 섭태 4와 똑같이 해결하면 된다.

이제 지금 버킷의 쿼리도 마찬가지로 내림차순으로 정렬해놓고 문제를 해결해 나갈 것이다. 어떠한 쿼리를 처리할 때까지 영향을 주는 업데이트들 중 지금 버킷이 아닌 것들은 이미 Union-Find 에 삽입되어 있을 것이다. 이제 각 쿼리마다 최대 B개의 업데이트들을 Naive 하게 하나씩 보며 Union-Find 에 삽입한다. 중요한 것은 Union-Find에 삽입한 후에는 다시 원래 상태로 돌려줘야 한다는 것이다. 이는 dynamic connectivty 문제에서 사용한 복구가 되는 union-find 자료구조를 이용하면 해결할 수 있다. 

다음 버킷으로 넘어갈 때에는 계속 정렬된 간선 집합을 갖고 있어야 한다. 이는 merge sort 와 비슷하게 두개의 정렬된 집합들을 합쳐주면 된다.

시간 제한이 촉박한 문제이기 때문에 버킷의 크기 상수를 잘 잡아 주어야 하는데, sqrtN 인 300정도로 잡으면 TLE가 나오지만 버킷 사이즈를 조금 더 키우는 대신 전체 연산의 횟수를 줄이기 위하여 800정도로 AC를 받았다. 

시간 복잡도 : O(QsqrtNlogN + NsqrtNlogN)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
 
struct Edge
{
    int u, v, w, idx;
    bool operator < (const Edge &p) const { return w>p.w; }
};
 
struct Query
{
    int t, u, w, idx;
    bool operator < (const Query &p) const { return w>p.w; }
};
 
int N, M, Q, SQ=1000;
int t[MAXN+10];
Edge edge[MAXN+10];
Query query[MAXN+10];
 
vector<int> S;
int Par[MAXN+10], Rank[MAXN+10];
vector<pii> ans;
 
void init()
{
    S.clear();
    for(int i=1; i<=N; i++) Par[i]=i, Rank[i]=1;
}
 
int cnt=0;
 
int Find(int x) { return x==Par[x] ? x : Find(Par[x]); }
 
void Union(int x, int y)
{
    x=Find(x); y=Find(y);
    if(x==y) return;
    if(Rank[x]<Rank[y]) swap(x, y);
    Rank[x]+=Rank[y];
    Par[y]=x;
    S.push_back(y);
    cnt++;
    //printf("UNION %d %d\n", x, y);
}
 
void Restore()
{
    if(S.empty()) return;
    //printf("RESTORE %d %d\n", S.back(), Par[S.back()]);
    Rank[Par[S.back()]]-=Rank[S.back()];
    Par[S.back()]=S.back();
    S.pop_back();
}
 
int main()
{
    int i, j, k, p;
 
    scanf("%d%d", &N, &M);
    for(i=1; i<=M; i++)
    {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); edge[i].idx=i;
        if(edge[i].u>edge[i].v) swap(edge[i].u, edge[i].v);
    }
    scanf("%d", &Q);
    for(i=1; i<=Q; i++) scanf("%d%d%d", &query[i].t, &query[i].u, &query[i].w), query[i].idx=i;
 
    vector<Edge> E;
    for(i=1; i<=M; i++) E.push_back(edge[i]);
    sort(E.begin(), E.end());
 
    for(i=0; i<=Q/SQ; i++)
    {
        int s=max(1, i*SQ), e=min(Q, i*SQ+SQ-1);
        init();
 
        //printf("============\n");
        //for(auto it : E) printf("%d %d %d\n", it.u, it.v, it.w);
        //printf("============\n");
 
        vector<Edge> E1, E2;
 
        vector<Query> up, qu;
        vector<int> up2;
        for(j=s; j<=e; j++)
        {
            if(query[j].t==1) up.push_back(query[j]), up2.push_back(query[j].u);
            else qu.push_back(query[j]);
        }
 
        sort(up2.begin(), up2.end());
        up2.erase(unique(up2.begin(), up2.end()), up2.end());
        sort(qu.begin(), qu.end());
 
        for(j=0; j<E.size(); j++) if(!binary_search(up2.begin(), up2.end(), E[j].idx)) E1.push_back(E[j]);
 
        for(j=0, k=0; j<qu.size(); j++)
        {
            //printf("!!!!!!!!!!QUERY SOLVING %d %d!!!!!!!\n", qu[j].u, qu[j].w);
            for(; k<E.size() && E[k].w>=qu[j].w; k++)
            {
                if(binary_search(up2.begin(), up2.end(), E[k].idx)) continue;
                //printf("!%d %d\n", E[k].u, E[k].v);
                Union(E[k].u, E[k].v);
            }
 
            cnt=0;
 
            for(p=0; p<up2.size(); p++) t[up2[p]]=edge[up2[p]].w;
            for(p=0; p<up.size() && up[p].idx<qu[j].idx; p++) t[up[p].u]=up[p].w;
            for(p=0; p<up2.size(); p++) if(t[up2[p]]>=qu[j].w) Union(edge[up2[p]].u, edge[up2[p]].v);
            ans.push_back({qu[j].idx, Rank[Find(qu[j].u)]});
            while(cnt--) Restore();
        }
 
        //printf("!%d %d %d\n", E.size(), E1.size(), E2.size());
 
        for(p=0; p<up.size(); p++) edge[up[p].u].w=up[p].w;
        for(p=0; p<up2.size(); p++) E2.push_back(edge[up2[p]]);
 
        if(E1.size()+E2.size()!=M) while(1);
 
        sort(E2.begin(), E2.end());
        E.clear(); E.resize(M);
        merge(E1.begin(), E1.end(), E2.begin(), E2.end(), E.begin());
    }
 
    sort(ans.begin(), ans.end());
    for(auto it : ans) printf("%d\n", it.second);
}