====== Algorithm Speedup ======
‎
متغیر ‎$n$‎ تایی ‎$x = (x_1,x_2,\cdots,x_n)$‎ و متغیر ‎$m$‎ تایی ‎$y=(y_1,y_2,\cdots,y_m)$‎ به شما داده شده است‎.

‎
می‌دانیم تابع ‎$F$‎ به صورت زیر تعریف شده است:
‎
$$ Boolean F(x,y):$$

$$ if W(x) \neq W(y) then return 0; $$

$$ ‎else if |W(x)| = |W(y)| = 1 then return 1; $$

$$ ‎else return F(p(x)‎, ‎p(y)) \wedge F(s(x)‎, ‎s(y));$$
که:
‎‎
  *  $W(x)$‎ برابر است با مجموعه عناصر ‎$x$‎
  *  $p(x)$‎ برابر است با بزرگ‌ترین پیشوند ‎$x$‎ که ‎$W(x) \neq W(p(x))$‎
  *  $s(x)$‎ برابر است با بزرگ‌ترین پسوند ‎$x$‎ که ‎$W(x) \neq W(s(x))$‎
  *  $\wedge$‎ علامت ‎and‎ منطقی است و ‎$|Z|$‎ برابر تعداد عناصر ‎$Z$‎ است.
   
‎
به طور مثال اگر ‎$x = (2‎, ‎3‎, ‎7‎, ‎2‎, ‎7‎, ‎4‎, ‎7‎, ‎2‎, ‎4)$‎ باشد ، ‎$W(x) = \{2‎, ‎3‎, ‎4‎, ‎7\}$‎ ، ‎$p(x) = (2‎, ‎3‎, ‎7‎, ‎2‎, ‎7)$‎ و ‎$s(x) = (7‎, ‎2‎, ‎7‎, ‎4‎, ‎7‎, ‎2‎, ‎4)$.

‎
به شما متغیر های ‎$x$‎ و ‎$y$‎ داده شده است ، شما باید ‎$F(x,y)$‎ را به‌دست آورید‎.
‎
‎
===== ورودی =====
  * در سطر اول ورودی ‎$1 \leq t \leq 13$‎ نشان‌دهنده تعداد تست‌ها آمده است‎.
  * سطر اول هر تست دو عدد ‎$1 \leq n,m \leq 10^5$‎ آمده است.
  * در سطر بعدی ‎$n$‎ عدد ‎$x_1$‎ تا ‎$x_n$‎ آمده است‎.
  * در سطر سوم هر تست ‎$m$‎ عدد ‎$y_1$‎ تا ‎$y_m$‎ آمده است‎.
  * مقادیر ‎$x_i$‎ ها و ‎$y_i$‎ ها بین ‎1‎ و ‎$100$‎ است.
===== خروجی =====

به ازای هر تست ‎$F(x,y)$‎ مربوط به آن تست را چاپ کنید‎.

===== محدودیت‌ها =====

  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

‎
===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|‎2‎ \\ 4 5 \\ ‎3 1 2 1 \\ ‎1 3 1 2 1 \\ 7 7‎ \\ ‎1 1 2 1 2 1 3‎ \\ ‎1 1 2 1 3 1 3|‎0 \\ ‎1|

</WRAP>


<پاسخ>
‎
می‌توان نشان داد که شرط این که تابع ‎$f$‎ مقدار ‎true برگرداند برقرار بودن هر دو گزاره زیر است:
‎
‎
  * ‎ اگر ‎$start(x)$‎ برابر با لیستی از ‎$x_i$‎ هایی باشد که هیچ ‎$x_{j < i}$‎ برابر با ‎$x_i$‎ وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در ‎$x$‎ است باشد ، ‎$start(x)$‎ باید با ‎$start(y)$‎ برابر باشد.
  * ‎ اگر ‎$end(x)$‎ برابر با لیستی از ‎$x_i$‎ هایی باشد که هیچ ‎$x_{j > i}$‎ برابر با ‎$x_i$‎ وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در ‎$x$‎ است باشد ، ‎$end(x)$‎ باید با ‎$end(y)$‎ برابر باشد.

بدیهی است که اگر ‎$|w(x)|$‎ برابر با ‎$1$‎ باشد، شرط لازم و کافی برای این که تابع ‎$f$‎ مقدار ‎true‎ برگرداند، دو شرط بالاست‎.

‎
حال اگر ‎$|w(x)| \geq 2$‎ باشد ، تنها در صورتی تابع ‎$f$‎ مقدار ‎true برمی‌گرداند که هر دو شرط برای ‎$s(x),s(y)$‎ و ‎$p(x),p(y)$‎ برقرار باشد که در این صورت هر دو شرط برای ‎$x,y$‎ نیز برقرار است‎.

‎
پس کافیست دو لیست ‎$start$‎ و ‎$end$‎ را برای ‎$x$‎ و ‎$y$‎ تولید کنیم و آن‌ها را با هم مقایسه کنیم و در صورتی پاسخ مثبت چاپ کنیم که هر دو برابر بودند‎.‎


**پيچيدگي**


دو لیست ‎$start$‎ و ‎$end$‎ را می‌توان با پیچیدگی زمانی ‎$o(n \times \log n)$‎ برای ‎$x$‎ و ‎$y$‎ ساخت و مقایسه آن‌ها در زمان ‎$o(n)$‎ امکان‌پذیر است. پس پیچیدگی الگوریتم برابر است با ‎$o(n \log n)$‎.
</پاسخ>

  * [[سوال ۷۲|سوال بعد]]
  * [[سوال ۷۰|سوال قبل]]