Problems
원형으로 1~N 사이의 자연수가 배열되어 있다.
이 중 어느 한 지점을 끊어 직선으로 만들었을 때, 수들이 1, 2, 3, ..., N의 순서로 배열되도록 할 수 있는지 판별할 것이다.
그냥은 너무 쉽기 때문에, 두 위치에 적혀있는 수를 교환(swap)한 뒤 판별하는 것을 Q회 반복해보자.
두번째 예제에 대한 그림이다.
Input
첫 줄에 N과 Q가 공백으로 구분되어 주어진다. (1<=N<=300000, 1<=Q<=300000)
그 다음 줄에는 초기 숫자들의 배열을 나타내는 크기 N의 순열이 주어진다.
그 다음 Q개의 줄에 걸쳐, ai와 bi가 공백으로 구분되어 주어진다. 이는 값 ai와 bi를 바꾼 뒤 답을 구하라는 뜻이다.
Output
Q개의 쿼리에 대한 답을 한 줄에 하나씩 순서대로 출력하여라.
각 쿼리에 대해, 만약 어느 한 지점을 끊어 직선으로 만들었을 때, 수들을 1, 2, 3, ..., N의 순서로 배열할 수 있다면 DA, 그렇지 않다면 NE를 출력하여라.
Subtask
| # | Score | Condition |
|---|---|---|
| #1 | 15 | N<=500, Q<=500 |
| #2 | 35 | N<=5000, Q<=5000 |
| #3 | 50 | 제한 없음 |
Example #1
5 2
2 3 4 5 1
1 3
3 1
NE
DA
Example #2
4 2
2 3 1 4
4 2
3 4
NE
DA
Example #3
6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4
NE
NE
DA
NE
DA
Hint
Source
COCI 2022/2023 Contest #3 2번
You must sign in to write code.