글 읽기 - 반례를 알고 싶습니다

wnsgur1714 4년 전 0

먼저 쿼리 2를 계산하는 쿼리 순서대로 바꾼 다음,

그다음 세그먼트 트리로 각 쿼리 2를 계산했습니다.

그리고 다시 쿼리 2를 순서대로 정렬한 뒤 출력했는데...

어디서 틀렸는지 알고 싶습니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct quary1{
    int num;
    int change;
};

struct quary2{
    int value;
    int number;
    int num;
    int start, endd;
};

bool q2s(quary2 a, quary2 b){
    if(a.num >= b.num){
        return false;
    }
    else{
        return true;
    }
}

bool q2e(quary2 a, quary2 b){
    if(a.number >= b.number){
        return false;
    }
    else{
        return true;
    }
}

int n, m;
int arr[100001];
int tree[200001];
vector<quary1> q1;
vector<quary2> q2;

void stt(int node, int start, int endd){ // set the tree
    if(start == endd){
        tree[node] = arr[start];
    }
    else{
        int mid = (start+endd)/2;
        stt(node*2, start, mid);
        stt(node*2+1, mid+1, endd);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
}

int ftt(int node, int start, int endd, int ns, int ne){ // find the tree
    if(start > ne || endd < ns){
        return 0;
    }
    else if(start >= ns && endd <= ne){
        return tree[node];
    }
    else{
        int mid = (start + endd)/2;
        return ftt(node*2, start, mid, ns, ne) + ftt(node*2+1, mid+1, endd, ns, ne);
    }
}

void ctt(int node, int start, int endd, int nf, int cn){// change the tree
    if(start == endd){
        arr[start] = cn;
        tree[node] = cn;
        return;
    }
    int mid = (start+endd)/2;
    if(nf <= mid){
        ctt(node*2, start, mid, nf, cn);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    if(nf > mid){
        ctt(node*2+1, mid+1, endd, nf, cn);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio();
    cin >> n;
    for(int i = 1 ; i <= n ; i++){
        cin >> arr[i];
    }
    stt(1, 1, n);
    cin >> m;
    int num;
    for(int i = 1 ; i <= m ; i++){
        cin >> num;
        if(num == 1){
            quary1 a;
            cin >> a.num >> a.change;
            q1.push_back(a);
        }
        if(num == 2){
            quary2 a;
            cin >> a.num >> a.start >> a.endd;
            a.number = i;
            q2.push_back(a);
        }
    }
    sort(q2.begin(), q2.end(), q2s);
    int now = 0;
    for(int i = 0 ; i < q2.size() ; i++){
        while(now != q2[i].num){
            ctt(1, 1, n, q1[now].num, q1[now].change);
            now++;
        }
        q2[i].value = ftt(1, 1, n, q2[i].start, q2[i].endd);
    }
    sort(q2.begin(), q2.end(), q2e);
    for(int i = 0 ; i < q2.size() ; i++){
        cout << q2[i].value << "\n";
    }
    return 0;
}

adh0463 4년 전 0

경계값 분석해보세요,

1. 데이터 개수는 10^5, 요소값은 10^6이니, 그냥 구간합만 구해도 int로 채울 수 없습니다.

2. 여기서 사용되는 tree 배열의 크기를 확인해주세요. 님이 짜신 세그 트리에서 인덱스가 벗어나는 구간이 있더군요. 대충 400001 크기 주니 잘 도네요.

wnsgur1714 4년 전 1

해결되었습니다!

값의 크기를 잘못 알았네요..... 감사합니다!

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

문제

문제

출처

ICPC

반례를 알고 싶습니다

wnsgur1714 4년 전 0

adh0463 4년 전 0

wnsgur1714 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말