Subpermutation Query

2 secs 1024 MB
mugeneloff's icon mugeneloff

想定解1

区間種類数 + 区間max
区間種類数に領域木を使うとすると
O((N+Q)(logN)2)O((N+Q)(logN)^2)

想定解2

hashをxorでとって判定
この解法での提出はこれです.https://mojacoder.app/users/mugeneloff/problems/subpermutation_query/submissions/3c272fa2-4f34-443a-a176-201f1b4e29b0
この解法であれば,余裕で点更新にも耐えます.
O(N+Q)O(N+Q)

https://mugen1337.github.io/procon/tips/CountSubpermutation.cpp
このリンク先で解いている問題から発想を得てもっと簡単なバージョンであるこの問題を作りました.

なにかあったら

連絡ください.
Twitter : @mugen_1337
初めての作問なのでいろいろよくわかりませんでした.
特に,テストケースは弱いですし,何かミスがあるかもしれません.
一応色々チェックしたつもりですが何かあったらごめんなさい