문제
원형으로 1~N 사이의 자연수가 배열되어 있다.
이 중 어느 한 지점을 끊어 직선으로 만들었을 때, 수들이 1, 2, 3, ..., N의 순서로 배열되도록 할 수 있는지 판별할 것이다.
그냥은 너무 쉽기 때문에, 두 위치에 적혀있는 수를 교환(swap)한 뒤 판별하는 것을 Q회 반복해보자.
두번째 예제에 대한 그림이다.
입력
첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1<=N<=300000, 1<=Q<=300000)
그 다음 줄에는 초기 숫자들의 배열을 나타내는 크기 N의 순열이 주어진다.
그 다음 Q개의 줄에 걸쳐, ai와 bi가 공백으로 구분되어 주어진다. 이는 값 ai와 bi를 바꾼 뒤 답을 구하라는 뜻이다.
출력
Q개의 쿼리에 대한 답을 한 줄에 하나씩 순서대로 출력하여라.
각 쿼리에 대해, 만약 어느 한 지점을 끊어 직선으로 만들었을 때, 수들을 1, 2, 3, ..., N의 순서로 배열할 수 있다면 DA, 그렇지 않다면 NE를 출력하여라.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 15점 | N<=500, Q<=500 |
| #2 | 35점 | N<=5000, Q<=5000 |
| #3 | 50점 | 제한 없음 |
예제1
입력
52
23451
13
31
출력
NE
DA
예제2
입력
42
2314
42
34
출력
NE
DA
예제3
입력
65
215634
31
34
32
45
54
출력
NE
NE
DA
NE
DA
힌트
출처
COCI 2022/2023 Contest #3 2번