문제
백준 온라인 저지에는 많은 "수열과 쿼리" 문제가 있습니다. 그러나 그중 대다수는 Diamond 이상의 티어를 가지고 있기에, 흐즈로는 언젠가는 어렵지 않은 "수열과 쿼리" 문제를 내겠다고 다짐하였습니다. 그렇게 탄생한 문제가 이것입니다.
수열의 연속 부분 수열 $[a_l,a_{l+1},a_{l+2},\cdots,a_{r-1},a_r]$에서 모든 원소가 서로 일치할 때, 이러한 구간 $[l,r]$을 수열 $a$의 연속 일치 구간이라고 합니다. 또한, 수열 $a$의 어떤 연속 일치 구간이 다른 어떤 $a$의 연속 일치 구간에도 완전히 포함되지 않는다면 이를 수열 $a$의 중요한 연속 일치 구간이라고 합니다.
여러분은 인덱스가 1ドル$부터 시작하는 수열 $A$에 대하여 다음의 쿼리 $q$개를 해결해야 합니다.
- 1ドル \ i \ x$: $A_i$의 값을 $x$로 변경합니다. (1ドル \le i,x \le n$)
- 2ドル \ l \ r$: $B$를 수열의 연속 부분 수열 $[A_l,A_{l+1},A_{l+2},\cdots,A_{r-1},A_r]$로 정의할 때, 수열 $B$의 서로 다른 중요한 연속 일치 구간의 개수를 출력합니다. (1ドル \le l \le r \le n$)
어렵지 않은 문제죠? 여러분이 느끼기에도 어렵지 않다면 좋겠습니다.
출력
각 2ドル$번 쿼리에 대해 정답을 한 줄에 하나씩 출력합니다.
W3sicHJvYmxlbV9pZCI6IjMxMjIyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMjE4XHVjNWY0XHVhY2ZjIFx1YzViNFx1YjgzNVx1YzljMCBcdWM1NGFcdWM3NDAgXHVjZmZjXHViOWFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjMzFcdWM5MDAgXHVjNjI4XHViNzdjXHVjNzc4IFx1YzgwMFx1YzljMFx1YzVkMFx1YjI5NCBcdWI5Y2VcdWM3NDAgJnF1b3Q7XHVjMjE4XHVjNWY0XHVhY2ZjIFx1Y2ZmY1x1YjlhYyZxdW90OyBcdWJiMzhcdWM4MWNcdWFjMDAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVhZGY4XHVjOTExIFx1YjMwMFx1YjJlNFx1YzIxOFx1YjI5NCBEaWFtb25kIFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWQyZjBcdWM1YjRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YWUzMFx1YzVkMCwgXHVkNzUwXHVjOTg4XHViODVjXHViMjk0IFx1YzViOFx1YzgyMFx1YWMwMFx1YjI5NCBcdWM1YjRcdWI4MzVcdWM5YzAgXHVjNTRhXHVjNzQwICZxdW90O1x1YzIxOFx1YzVmNFx1YWNmYyBcdWNmZmNcdWI5YWMmcXVvdDsgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YWNhMFx1YjJlNFx1YWNlMCBcdWIyZTRcdWM5ZDBcdWQ1NThcdWM2MDBcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWM4YyBcdWQwYzRcdWMwZGRcdWQ1NWMgXHViYjM4XHVjODFjXHVhYzAwIFx1Yzc3NFx1YWM4M1x1Yzc4NVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMjE4XHVjNWY0XHVjNzU4IFx1YzVmMFx1YzE4ZCBcdWJkODBcdWJkODQgXHVjMjE4XHVjNWY0ICRbYV9sLGFfe2wrMX0sYV97bCsyfSxcXGNkb3RzLGFfe3ItMX0sYV9yXSRcdWM1ZDBcdWMxMWMgXHViYWE4XHViNGUwIFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWMxMWNcdWI4NWMgXHVjNzdjXHVjZTU4XHVkNTYwIFx1YjU0YywgXHVjNzc0XHViN2VjXHVkNTVjIFx1YWQ2Y1x1YWMwNCAkW2wscl0kXHVjNzQ0IFx1YzIxOFx1YzVmNCAkYSRcdWM3NTggPHN0cm9uZz5cdWM1ZjBcdWMxOGQgXHVjNzdjXHVjZTU4IFx1YWQ2Y1x1YWMwNDxcL3N0cm9uZz5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTY5XHViMmM4XHViMmU0LiBcdWI2MTBcdWQ1NWMsIFx1YzIxOFx1YzVmNCAkYSRcdWM3NTggXHVjNWI0XHViNWE0IFx1YzVmMFx1YzE4ZCBcdWM3N2NcdWNlNTggXHVhZDZjXHVhYzA0XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWM1YjRcdWI1YTQgJGEkXHVjNzU4IFx1YzVmMFx1YzE4ZCBcdWM3N2NcdWNlNTggXHVhZDZjXHVhYzA0XHVjNWQwXHViM2M0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0XHViYTc0IFx1Yzc3NFx1Yjk3YyBcdWMyMThcdWM1ZjQgJGEkXHVjNzU4IDxzdHJvbmc+XHVjOTExXHVjNjk0XHVkNTVjIFx1YzVmMFx1YzE4ZCBcdWM3N2NcdWNlNTggXHVhZDZjXHVhYzA0PFwvc3Ryb25nPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjlcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc0MCBcdWM3NzhcdWIzNzFcdWMyYTRcdWFjMDAgJDEkXHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQgJEEkXHVjNWQwIFx1YjMwMFx1ZDU1OFx1YzVlYyBcdWIyZTRcdWM3NGNcdWM3NTggXHVjZmZjXHViOWFjICRxJFx1YWMxY1x1Yjk3YyBcdWQ1NzRcdWFjYjBcdWQ1NzRcdWM1N2MgXHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxIFxcIGkgXFwgeCQ6ICRBX2kkXHVjNzU4IFx1YWMxMlx1Yzc0NCAkeCRcdWI4NWMgXHViY2MwXHVhY2JkXHVkNTY5XHViMmM4XHViMmU0LiAoJDEgXFxsZSBpLHggXFxsZSBuJCk8XC9saT5cclxuXHQ8bGk+JDIgXFwgbCBcXCByJDogJEIkXHViOTdjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM1ZjBcdWMxOGQgXHViZDgwXHViZDg0IFx1YzIxOFx1YzVmNCAkW0FfbCxBX3tsKzF9LEFfe2wrMn0sXFxjZG90cyxBX3tyLTF9LEFfcl0kXHViODVjIFx1YzgxNVx1Yzc1OFx1ZDU2MCBcdWI1NGMsIFx1YzIxOFx1YzVmNCAkQiRcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM5MTFcdWM2OTRcdWQ1NWMgXHVjNWYwXHVjMThkIFx1Yzc3Y1x1Y2U1OCBcdWFkNmNcdWFjMDRcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC4gKCQxIFxcbGUgbCBcXGxlIHIgXFxsZSBuJCk8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM1YjRcdWI4MzVcdWM5YzAgXHVjNTRhXHVjNzQwIFx1YmIzOFx1YzgxY1x1YzhlMD8gXHVjNWVjXHViN2VjXHViZDg0XHVjNzc0IFx1YjI5MFx1YjA3Y1x1YWUzMFx1YzVkMFx1YjNjNCBcdWM1YjRcdWI4MzVcdWM5YzAgXHVjNTRhXHViMmU0XHViYTc0IFx1Yzg4Ylx1YWNhMFx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzQgJG4kXHVhY2ZjIFx1Y2ZmY1x1YjlhY1x1Yzc1OCBcdWFjMWNcdWMyMTggJHEkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAoJDEgXFxsZSBuLHEgXFxsZSAyXFx0aW1lcyAxMF41JCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjMjE4XHVjNWY0ICRBJFx1Yzc1OCBcdWM2ZDBcdWMxOGMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX24kXHVjNzc0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWJkODRcdWI5YWNcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWQxXHViMmM4XHViMmU0LiAoJDEgXFxsZSBBX2kgXFxsZSBuJCk8XC9wPlxyXG5cclxuPHA+XHVhZGY4XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBcdWNkMWQgJHEkXHVhYzFjXHVjNzU4IFx1Y2ZmY1x1YjlhY1x1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1YWMwMSBcdWNmZmNcdWI5YWNcdWIyOTQgXHVjOWMwXHViYjM4XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4ODVcdWI5NThcdWM3NTggXHVjZmZjXHViOWFjIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjVcdWM1ZDBcdWMxMWMgXHViOWM4XHVjOWMwXHViOWM5IFx1Y2ZmY1x1YjlhY1x1YjI5NCAkMiRcdWJjODggXHVjZmZjXHViOWFjXHVjNzg0XHVjNzc0IFx1YmNmNFx1YzdhNVx1YjQyOVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgJDIkXHViYzg4IFx1Y2ZmY1x1YjlhY1x1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjODE1XHViMmY1XHVjNzQ0IFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzMTIyMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNlcXVlbmNlIGFuZCBOb3QgRGlmZmljdWx0IFF1ZXJpZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkJhZWtqb29uIE9ubGluZSBKdWRnZSBoYXMgbWFueSB0YXNrcyB0aXRsZWQgJnF1b3Q7U2VxdWVuY2UgYW5kIFF1ZXJpZXMmcXVvdDsuIEFzIGEgbWFqb3JpdHkgb2YgdGhlbSBhcmUgcmF0ZWQgRGlhbW9uZCB0aWVyIG9yIGhpZ2hlciwgQ2hyb21hdGUgZGVjaWRlZCB0byBzZXQgYSAmcXVvdDtTZXF1ZW5jZSBhbmQgUXVlcmllcyZxdW90OyZuYnNwO3Rhc2sgd2hpY2ggaXMgbm90IHNvIGRpZmZpY3VsdC4gVGhhdCBpcyBob3cgdGhpcyB0YXNrIHdhcyBtYWRlLjxcL3A+XHJcblxyXG48cD5JZiBhbGwgZWxlbWVudHMgYXJlIGVxdWFsIHRvIGVhY2ggb3RoZXIgaW4gc29tZSBjb250aWd1b3VzIHN1YnNlcXVlbmNlICRbYV9sLGFfe2wrMX0sYV97bCsyfSxcXGNkb3RzLGFfe3ItMX0sYV9yXSQsIHdlIGNhbGwgdGhlIGludGVydmFsICRbbCxyXSQgYSA8c3Ryb25nPmNvbnRpZ3VvdXMgZXF1YWwgaW50ZXJ2YWw8XC9zdHJvbmc+Jm5ic3A7b2YgJGEkLiBBbHNvLCBpZiBzb21lIGNvbnRpZ3VvdXMgZXF1YWwgaW50ZXJ2YWwgb2YgJGEkIGlzIG5vdCBlbnRpcmVseSBjb250YWluZWQgaW4gYW55IG90aGVyIGNvbnRpZ3VvdXMgZXF1YWwgaW50ZXJ2YWwgb2YgJGEkLCB3ZSBjYWxsIGl0IGFuIDxzdHJvbmc+aW1wb3J0YW50IGNvbnRpZ3VvdXMgZXF1YWwgaW50ZXJ2YWw8XC9zdHJvbmc+Jm5ic3A7b2YgJGEkLjxcL3A+XHJcblxyXG48cD5Zb3UgbXVzdCBzb2x2ZSAkcSQgcXVlcmllcyBvZiB0aGUgZm9sbG93aW5nIGtpbmRzIG9uIGEgJDEkLWluZGV4ZWQgc2VxdWVuY2UgJEEkLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPiQxIFxcIGkgXFwgeCQ6IENoYW5nZSB0aGUgdmFsdWUgb2YgJEFfaSQgdG8gJHgkLiAoJDEgXFxsZSBpLHggXFxsZSBuJCk8XC9saT5cclxuXHQ8bGk+JDIgXFwgbCBcXCByJDogRGVmaW5lICRCJCBhcyB0aGUgY29udGlndW91cyBzdWJzZXF1ZW5jZSAkW0FfbCxBX3tsKzF9LEFfe2wrMn0sXFxjZG90cyxBX3tyLTF9LEFfcl0kLiBQbGVhc2Ugb3V0cHV0IHRoZSBudW1iZXIgb2YgZGlmZmVyZW50IGltcG9ydGFudCBjb250aWd1b3VzIGVxdWFsIGludGVydmFscyBvZiAkQiQuICgkMSBcXGxlIGwgXFxsZSByIFxcbGUgbiQpPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm90IHNvIGRpZmZpY3VsdCwgcmlnaHQ/IEkgaG9wZSB5b3UgdGhvdWdodCBzbyB0b28uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgZmlyc3QgbGluZSwgdHdvIGludGVnZXJzICRuJCBhbmQgJHEkICZtZGFzaDsgdGhlIGxlbmd0aCBvZiB0aGUgc2VxdWVuY2UgYW5kIHRoZSBudW1iZXIgb2YgcXVlcmllcyAmbWRhc2g7IGFyZSBnaXZlbi4gKCQxIFxcbGUgbixxIFxcbGUgMlxcdGltZXMgMTBeNSQpPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IGxpbmUgY29udGFpbnMgJEFfMSwgQV8yLCBcXGNkb3RzLCBBX24kLCB0aGUgZWxlbWVudHMgb2YgdGhlIHNlcXVlbmNlICRBJC4gKCQxIFxcbGUgQV9pIFxcbGUgbiQpPFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgJHEkIGxpbmVzIGNvbnRhaW4gb25lIHF1ZXJ5IGZvciBlYWNoIGxpbmUuIEVhY2ggcXVlcnkgaXMgb2Ygb25lIG9mIHRoZSB0eXBlcyBleHBsYWluZWQgaW4gdGhlIHN0YXRlbWVudC48XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IGZvciBldmVyeSBpbnB1dCwgdGhlIGxhc3QgcXVlcnkgaXMgb2YgdHlwZSAkMiQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggcXVlcnkgb2YgdHlwZSAkMiQsIG91dHB1dCB0aGUgYW5zd2VyIG9uIGEgc2VwYXJhdGUgbGluZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d