import sys
input = sys.stdin.readline
mod = 10**9+7
def makeseg(start,end,x):
if start==end:
sseg[x] = mseg[x] = data[start]
else:
mid = (start+end)//2
makeseg(start,mid,x*2); makeseg(mid+1,end,x*2+1)
sseg[x] = sseg[x*2]+sseg[x*2+1]
mseg[x] = mseg[x*2]*mseg[x*2+1]%mod
def updateseg(i,start,end,x):
if start==end:
sseg[x] = mseg[x] = data[start]
else:
mid = (start+end)//2
if i <= mid:
updateseg(i,start,mid,x*2)
else:
updateseg(i,mid+1,end,x*2+1)
sseg[x] = sseg[x*2]+sseg[x*2+1]
mseg[x] = mseg[x*2]*mseg[x*2+1]%mod
def sumseg(a,b,start,end,x,sseg,mseg):
if a==start and b==end:
return sseg[x],mseg[x]
mid = (start+end)//2
if b <= mid:
return sumseg(a,b,start,mid,x*2,sseg,mseg)
if a > mid:
return sumseg(a,b,mid+1,end,x*2+1,sseg,mseg)
s1,m1 = sumseg(a,mid,start,mid,x*2,sseg,mseg)
s2,m2 = sumseg(mid+1,b,mid+1,end,x*2+1,sseg,mseg)
return s1+s2,m1*m2%mod
for _ in range(int(input())):
N,K = map(int,input().split())
data = [i for i in range(1,N+1)]
sseg = [0]*4*N; mseg = [0]*4*N
makeseg(0,N-1,1)
sseg1 = sseg[:]; mseg1 = mseg[:]
for _ in range(K):
q,a,b = map(int,input().split())
if q:
print("YES" if sumseg(a,b,0,N-1,1,sseg,mseg)==sumseg(a,b,0,N-1,1,sseg1,mseg1) else "NO")
else:
data[a],data[b] = data[b],data[a]
updateseg(a,0,N-1,1); updateseg(b,0,N-1,1)세그먼트 트리로 해결하였다.
문제의 의도와는 약간 다른 방식으로 해결하였다.
일단 풀이를 설명하면,
1. 1~N에 대해서 구간합에 대한 세그먼트 트리와 구간곱에 대한 세그먼트 트리를 만든다. (sseg = 구간합, mseg = 구간곱)
2. 갱신하지 않은 원래 세그먼트 트리를 저장해둔다. (sseg1,mseg1)
3. DVD 위치를 바꾸면 세그먼트 트리를 갱신한다.
4. 확인하는 경우 a,b일 때 a~b의 구간합과 구간곱이 원래의 값과 같다면 YES를, 아니라면 NO를 출력한다.
예를들어, 3~5 구간을 체크한다면, 구간합이 12 (=3+4+5), 구간곱이 60 (=3*4*5)가 나오면 3,4,5가 모두 있다고 판단하고 YES를 출력하는 것이다.
풀이가 통과한 것으로 봐서 생각했을 때는 테스트케이스에서는 반례가 없다고 판단되는데, 무조건 항상 성립하는지에 대한 증명은 하지 못했다.
원래 이 문제가 의도한 풀이는 구간곱, 구간합이 아니라 최대, 최소에 대한 세그먼트 트리를 이용하는 것이라고 한다. 비둘기집 원리에 의해서 a,b 구간의 최솟값이 a 최댓값이 b인 경우 a~b가 모두 있다고 판단할 수 있기 때문이다.
굉장히 참신한 아이디어였다.
오늘의 교훈) 비둘기집 원리를 풀이에 활용하자