0으로 초기화된 길이 N의 정수 배열 A에 대해, 다음 쿼리를 구현해 주세요.
1. 배열의 i번째 원소에 k를 대입하는 쿼리. (SET)
즉, A[i] = k
2. 배열의 i번째 원소부터 j번째 원소까지의 합을 구하는 쿼리. (SUM) 즉, return A[i] + A[i + 1] + ... + A[j] 쿼리 수는 총 Q개가 들어옵니다.
초기 입력 : N (Q는 따로 입력으로 주어지지 않음)
조건)
1 <= N <= 10^38
1 <= Q <= 10^5
-10^18 <= k <= 10^18
입출력 예시
입력:
출력:
3 1 10===========================================
이번에는 PS같은 문제네요!
출제 신청
Algorithm design manual ch3인가 4인가에 비슷한문제 있었음
거기서도 N 저렇게 큼?
그건 저런 ps식 문제는 아니었고 시간복잡도 얼마이하로 하라던가 그런조건있었던걸로 기억함 자료구조 챕터였는데
그거 아마 세그먼트 트리일거임 저거 N 4배 크기 배열 잡고해야할텐데
쉽네
이건 제한시간이 1초 이하가 아니면 너무 쉬울 것 같은데? 그냥 map으로 박아서 구간합 박으면 되니까.
제한시간이 1초 미만이면 좀 어렵겠네.
이 문제에서 제일 좃같은 경우는 쿼리가 10만개랐으니까 처음 5만개는 10^38 범위 내에서 골고루 5만개를 흩뿌려 박는거고 뒤에 5만개는 전부 구간합 쿼리로 들어오면서 2~49987번째, 5~49996번째, 3~49992번째 이런 식으로 짜증나게 들어오는 경우임. 근데 시간 제한이 넉넉하면 그냥 무지성 std::map 써도 3초 안에 다 해결됨
내가 낸건데 map이나 dictionary 는 당연히 정해 아님 1초안에 답이 나와야함
ㄴ 테케 좀 만들어 줘
오늘 퇴근하고 올릴게여
인풋압축 + 세그트리?
... 빅인티저 없는 언어는 직접 구현해야 돼? 왜 굳이 k 제한을 저렇게 높인거야