글 읽기 - 반례를 알 수 있을까요..?

comseung18 2년 전 0

세그먼트 트리를 이용하였는데,

노드 마다 구간의 왼쪽 원소, 오른쪽 원소, 노드에 나뭇잎을 붙일 때 구매하는 숫자 cnt 로 하였고,

구간을 합칠 때는 합칠 때 왼쪽 구간의 오른쪽 원소와 오른쪽 구간의 왼쪽 원소가 같으면 cnt 가 1개 덜 필요한걸로 하여 구성하였는데,

3% 에서 틀리네요. 혹시 제가 문제를 잘못이해한걸까요...?

#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define endl '\n'
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<vi > vvi;

const int mod = 1000000009;

struct node
{
    int left_ele, right_ele, cnt;
    node(){}
};

vector<node> seg;
node seg_init(int num, int le, int ri)
{
    if(le==ri)
    {
        cin >> seg[num].left_ele;
        seg[num].right_ele = seg[num].left_ele;
        seg[num].cnt = 1;
        return seg[num];
    }
    int mid = (le+ri)/2;

    node p = seg_init(num*2, le, mid);
    node q = seg_init(num*2+1, mid+1, ri);

    seg[num].left_ele = p.left_ele;
    seg[num].right_ele = q.right_ele;
    seg[num].cnt = p.cnt + q.cnt;

    if(p.right_ele == q.left_ele) seg[num].cnt--;
    return seg[num];
}
node seg_q(int num, int le, int ri, int x, int y)
{
    if(ri < x || y < le)
    {
        node ret;
        ret.cnt = 0;
        ret.left_ele = -1;
        ret.right_ele = -1;
        return ret;
    }
    if(x <= le && ri <= y)
    {
        return seg[num];
    }

    int mid = (le+ri)/2;
    node p = seg_q(num*2, le, mid, x, y);
    node q = seg_q(num*2+1, mid+1, ri ,x, y);
    if(p.left_ele == -1) return q;
    if(q.left_ele == -1) return p;
    node ret;
    ret.left_ele = p.left_ele;
    ret.right_ele = q.right_ele;
    ret.cnt = p.cnt + q.cnt;
    if(p.right_ele == q.left_ele) --ret.cnt;
    return ret;
}

node seg_u(int num, int le, int ri, int x, int y)
{
    if(ri < x || x < le) return seg[num];
    if(x <= le && ri <= x)
    {
        seg[num].left_ele = y;
        seg[num].right_ele = seg[num].left_ele;
        seg[num].cnt = 1;
        return seg[num];
    }

    int mid = (le+ri)/2;

    node p = seg_u(num*2, le, mid,x ,y);
    node q = seg_u(num*2+1, mid+1, ri, x, y);

    seg[num].left_ele = p.left_ele;
    seg[num].right_ele = q.right_ele;
    seg[num].cnt = p.cnt + q.cnt;

    if(p.right_ele == q.left_ele) seg[num].cnt--;
    return seg[num];
}
void solve()
{
    int n,q;
    cin >> n >> q;
    seg = vector<node>(4*n);

    seg_init(1, 1, n);
    int paint = -1;
    while(q--)
    {
        int t, a, b;
        cin >> t >> a >> b;
        if(t==1)
        {
            node tmp = seg_q(1, 1, n, a, b);
            if(paint == tmp.left_ele) tmp.cnt--;
            cout << tmp.cnt << endl;
            paint = tmp.right_ele;
        }
        else
        {
            seg_u(1, 1, n, a, b);
        }
    }
}

int main()
{
    fastio;
    int test_cases = 1;
    // cin >> test_cases;
    while(test_cases--)
    {
        solve();
    }
    return 0;
}

p_ce1052 2년 전 0

업데이트 부분에 문제가 있는 것 같습니다

반례입니다

6 3
1 2 2 2 3 4
1 1 4
2 1 2
1 1 4

답 : 2 1

출력 : 2 0

comseung18 2년 전 0

첫 날만 빈손이고 다음날부터는 전날에 썻던 본드 가져가는 건줄 알았는데, 매일매일 빈손으로 칠하는 거였네요. 정말 감사합니다. 😍

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 알 수 있을까요..?

comseung18 2년 전 0

p_ce1052 2년 전 0

comseung18 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말