동적 역순 쌍 계산 문제
문제 개요
길이가 \(n\)인 순열 \(a\)가 주어진다. 두 원소를 교환할 때마다 역순 쌍의 개수를 2로 나눈 나머지를 출력해야 한다.
입력 형식
첫 번째 줄에는 양의 정수 \(n\)이 주어진다.
두 번째 줄에는 순열 \(a\)를 구성하는 \(n\)개의 숫자가 주어진다.
세 번째 줄에는 질의 수 \(q\)가 주어진다.
다음 \(q\)줄에는 각각 두 개의 양의 정수가 주어지며, 이는 \(a_i\)와 ...
6월 11일 16:49에 게시됨
BIT(페니크 트리) 개념 정리 및 문제 풀이
BIT(페니크 트리) 개요
BIT(Binary Indexed Tree)는 구간 합을 빠르게 계산하고, 특정 인덱스의 값을 업데이트할 수 있는 자료구조입니다.
lowbit 연산을 기반으로 하여 시간 복잡도 O(log N)을 보장합니다.
P3374: 기본적인 BIT 연산
단일 값 갱신과 구간 합을 처리하는 가장 기초적인 템플릿 문제입니다.
#include <bits/stdc++.h>
using namespace std;
int n ...
5월 26일 07:58에 게시됨