2024-03-08

-수들의 합 7(2268, 백준)

 기본적인 세그먼트트리 구간합 문제이다. 세그먼트트리를 구성해준 다음 쿼리마다 연산을 수행해 주면 된다. 범위가 크기때문에 64bit자료형을 사용해야 하고, 문제의 쿼리에서 항상 x > y임이 주어지지 않았음에 주의하자.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

long long n, m;
long long arr[1000010];
long long segtree[4000010];

long long init(long long s, long long e, long long node) {
	if (s == e) return segtree[node] = arr[s];
	long long mid = (s + e) / 2;
	return segtree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}

long long sum(long long s, long long e, long long low, long long high, long long node) {
	if (low > e || s > high) return 0;
	if (low <= s && e <= high) return segtree[node];
	long long mid = (s + e) / 2;
	return sum(s, mid, low, high, node * 2) + sum(mid + 1, e, low, high, node * 2 + 1);
}

void update(long long s, long long e, long long node, long long idx, long long dis) {
	if (idx < s || idx > e) return;
	segtree[node] += dis;
	long long mid = (s + e) / 2;
	if (s != e) {
		update(s, mid, node * 2, idx, dis);
		update(mid + 1, e, node * 2 + 1, idx, dis);
	}
}

int main()
{
	long long i, j;
	scanf("%lld %lld", &n, &m);
	for (i = 1; i <= n; i++) arr[i] = 0;
	init(1, n, 1);
	for (i = 0; i < m; i++) {
		long long a, b, c;
		scanf("%lld %lld %lld", &a, &b, &c);
		if (a == 0) {
			long long mx = max(b, c), mn = min(b, c);
			printf("%lld\n", sum(1, n, mn, mx, 1));
		}
		else if (a == 1) {
			long long dis = c - arr[b];
			update(1, n, 1, b, dis);
			arr[b] = c;
		}
	}
	return 0;
}

-최솟값과 최댓값(2357, 백준)

 세그먼트트리를 이용한 최대최소값을 구하는 기본적인 세그트리 문제였다. 마찬가지로 각 쿼리에 해당하는 구간에서의 최소, 최대를 구해주면 된다. 값 갱신 함수를 작성하지않아도 되 구현이 비교적 쉬웠다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int n, m;
int arr[100010];
int Ltree[400010], Mtree[400010];

int Linit(int s, int e, int node)
{
	if (s == e) return Ltree[node] = arr[s];
	int mid = (s + e) / 2;
	return Ltree[node] = min(Linit(s, mid, node * 2), Linit(mid + 1, e, node * 2 + 1));
}

int Lfind(int s, int e, int node, int low, int high)
{
	if (low > e || s > high) return 2e9;
	if (low <= s && e <= high) return Ltree[node];
	int mid = (s + e) / 2;
	return min(Lfind(s, mid, node * 2, low, high), Lfind(mid + 1, e, node * 2 + 1, low, high));
}

int Minit(int s, int e, int node)
{
	if (s == e) return Mtree[node] = arr[s];
	int mid = (s + e) / 2;
	return Mtree[node] = max(Minit(s, mid, node * 2), Minit(mid + 1, e, node * 2 + 1));
}

int Mfind(int s, int e, int node, int low, int high)
{
	if (low > e || s > high) return 0;
	if (low <= s && e <= high) return Mtree[node];
	int mid = (s + e) / 2;
	return max(Mfind(s, mid, node * 2, low, high), Mfind(mid + 1, e, node * 2 + 1, low, high));
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 1; i <= n; i++) scanf("%d", &arr[i]);
	Minit(1, n, 1);
	Linit(1, n, 1);
	for (j = 0; j < m; j++) {
		int x, y;
		scanf("%d %d", &x, &y);
		printf("%d %d\n", Lfind(1, n, 1, x, y), Mfind(1, n, 1, x, y));
	}
	return 0;
}

-달려라 홍준(1306, 백준)

 위의 문제와 같은 로직을 이용해서 풀되, 앞뒤에서 k값만큼 떨어진 범위에서 모든 최댓값을 구해주면 된다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

int n, m, arr[1000010];
int segtree[4000010];

int init(int s, int e, int node)
{
    if(s == e) return segtree[node] = arr[s];
    int mid = (s+e)/2;
    return segtree[node] = max(init(s, mid, node*2), init(mid+1, e, node*2+1));
}

int mxfind(int s, int e, int low, int high, int node)
{
    if(low > e || high < s) return 0;
    if(low <= s && e <= high) return segtree[node];
    long long mid = (s + e)/2;
    return max(mxfind(s, mid, low, high, node*2), mxfind(mid + 1, e, low, high, node*2+1));
}

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++) scanf("%d", &arr[i]);
    init(1, n, 1);
    for(i=m;i<=n-m+1;i++) {
        int low = i - m + 1;
        int high = i + m - 1;
        printf("%d\n", mxfind(1, n, low, high, 1));
    }
    return 0;
}

-좌표 압축(18870, 백준)

 좌표압축 기본문제이다. 주어진 배열을 인덱스와 함께 저장해 값을 기준으로 정렬해준다. 앞에서부터 값을 늘려가며 ans배열에 저장해준다.(값이 같다면 늘리지않는다.) 대소비교를 쉽게 하고싶을 때 사용되는 것 같다.

<소스 코드>

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector <pair<int, int>> vec;
int ans[1000010];

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		vec.push_back({ x, i });
	}
	sort(vec.begin(), vec.end());
	int idx = 0;
	for (i = 0; i < n; i++) {
		ans[vec[i].second] = idx++;
		if (i < n - 1 && vec[i].first == vec[i + 1].first) idx--;
	}
	for (i = 0; i < n; i++) printf("%d ", ans[i]);
	return 0;
}

-멀티 버스 I I(18869, 백준)

 좌표압축 응용 문제였다. 같은 순서면 됨으로 주어지는 모든 배열을 압축해준 뒤 같다면 ans를 증가시켜가며 답을 구했다.

<소스 코드>

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int n, m;
vector <pair<int, int>> vec[110];
int small[110][10010];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < n; i++) {
		for (j = 0; j < m; j++) {
			int x;
			scanf("%d", &x);
			vec[i].push_back({x, j});
		}
		sort(vec[i].begin(), vec[i].end());
		int idx = 0;
		for (j = 0; j < m; j++) {
			small[i][vec[i][j].second] = idx++;
			if (j < m - 1 && vec[i][j].first == vec[i][j + 1].first) idx--;
		}
	}
	int ans = 0;
	for (i = 0; i < n - 1; i++) {
		int ch;
		for (j = i + 1; j < n; j++) {
			ch = 1;
			for (int k = 0; k < m; k++) {
				if (small[i][k] != small[j][k]) ch = 0;
			}
			if (ch == 1) ans++;
		}
	}
	printf("%d", ans);
}