문제
원형으로 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
입력
5 2
2 3 4 5 1
1 3
3 1
출력
NE
DA
예제2
입력
4 2
2 3 1 4
4 2
3 4
출력
NE
DA
예제3
입력
6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4
출력
NE
NE
DA
NE
DA
힌트
출처
COCI 2022/2023 Contest #3 2번