백준14648 쿼리 맛보기

작성일 | In

문제 링크

  • https://www.acmicpc.net/problem/14648

문제 출처

  • 제1회 천하제일 코딩대회 예선 D번

시간복잡도

  • O(NQ)

풀이

n이 1000, q가 10000이니까 O(nq)로 하면 충분히 통과합니다. 이 문제는 문제 내용 그대로 따라가면서 하면 통과하는 문제입니다.

  1. n, q, 수열을 입력받습니다.
  2. 쿼리를 입력받습니다.
  3. 쿼리가 1이면 a부터 b까지 다 더한 후 출력하고 swap합니다.
  4. 쿼리가 2면 c부터 d까지 더한 값에서 a부터 b를 더한 값을 빼서 출력합니다.
  5. 2~4를 q번 반복합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, q;
ll arr[1010];

int main(){
	cin >> n >> q;
	for(int i=1; i<=n; i++){
		cin >> arr[i];
	}
	for(int i=0; i<q; i++){
		int op;
		cin >> op;
		if(op == 1){
			int a, b;
			cin >> a >> b;
			int s1 = 0;
			for(int j=a; j<=b; j++) s1 += arr[j];
			cout << s1 << endl;
			swap(arr[a], arr[b]);
		}

		if(op == 2){
			int a, b, c, d;
			cin >> a >> b >> c >> d;
			int s1 = 0, s2 = 0;
			for(int j=a; j<=b; j++) s1 += arr[j];
			for(int j=c; j<=d; j++) s2 += arr[j];
			cout<<s1-s2<<endl;
		}
	}
}