{"id":2304,"date":"2017-02-03T21:01:43","date_gmt":"2017-02-03T17:31:43","guid":{"rendered":"https:\/\/blog.quera.ir\/?p=1280"},"modified":"2017-02-03T21:01:43","modified_gmt":"2017-02-03T17:31:43","slug":"%d8%b1%d8%a7%d9%87-%d8%ad%d9%84-%d9%87%d8%a7%db%8c-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%d8%b4%d9%85%d8%a7%d8%b1%d9%87-15-quera","status":"publish","type":"post","link":"https:\/\/quera.org\/blog\/%d8%b1%d8%a7%d9%87-%d8%ad%d9%84-%d9%87%d8%a7%db%8c-%d9%85%d8%b3%d8%a7%d8%a8%d9%82%d9%87-%d8%b4%d9%85%d8%a7%d8%b1%d9%87-15-quera\/","title":{"rendered":"\u0631\u0627\u0647 \u062d\u0644 \u0647\u0627\u06cc \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 15 Quera"},"content":{"rendered":"

\u0645\u0633\u0627\u0628\u0642\u0647 \u062a\u0645\u0627\u0645 \u0634\u062f!<\/p>\n

\u0627\u0645\u06cc\u062f\u0648\u0627\u0631\u06cc\u0645 \u0627\u0632 \u0633\u0648\u0627\u0644\u0627 \u062e\u0648\u0634\u062a\u0648\u0646 \u0627\u0648\u0645\u062f\u0647 \u0628\u0627\u0634\u0647 \ud83d\ude09<\/p>\n

\u0631\u0627\u0647 \u062d\u0644 \u0633\u0648\u0627\u0644\u0627\u062a \u062f\u0631 \u0627\u062f\u0627\u0645\u0647 \u0645\u0637\u0644\u0628<\/p>\n

<\/p>\n

\u0645\u0628\u0646\u0627\u06cc \u0634\u0648\u0646\u0632\u062f\u0647<\/strong><\/a><\/p>\n

\u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u060c \u0627\u0648\u0644\u06cc\u0646 \u0631\u0642\u0645 (\u0627\u0632 \u0633\u0645\u062a \u0631\u0627\u0633\u062a) \u063a\u06cc\u0631\u0650 F \u0639\u062f\u062f \u0631\u0648 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645 \u060c \u0627\u06cc\u0646 \u0631\u0642\u0645 \u06cc\u06a9\u06cc \u0632\u06cc\u0627\u062f \u0645\u06cc\u0634\u0647 \u060c \u0627\u0631\u0642\u0627\u0645 \u0633\u0645\u062a \u0631\u0627\u0633\u062a \u0627\u06cc\u0646 \u0631\u0642\u0645(\u06a9\u0647 \u0645\u0646\u0637\u0642\u0627 \u0647\u0645\u06af\u06cc F \u0628\u0648\u062f\u0647 \u0627\u0646\u062f) \u060c \u0635\u0641\u0631 \u0645\u06cc \u0634\u0648\u0646\u062f \u0648 \u0628\u0642\u06cc\u0647 \u0631\u0634\u062a\u0647 \u0628\u06cc \u062a\u063a\u06cc\u06cc\u0631 \u0645\u06cc \u0645\u0627\u0646\u062f .
\n\u062a\u0646\u0647\u0627 \u0628\u0627\u06cc\u062f \u062d\u0627\u0644\u062a\u06cc \u06a9\u0647 \u06a9\u0644 \u0631\u0634\u062a\u0647 F \u0628\u0627\u0634\u062f \u0647\u0645 \u062c\u062f\u0627 \u0628\u0631\u0631\u0633\u06cc \u0634\u0648\u062f .<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc : O(n)<\/span><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

C++ Code By Navick<\/a><\/p>\n

\u062d\u0631\u06a9\u062a \u0631\u0648\u06cc \u0638\u0631\u0648\u0641<\/strong><\/a><\/p>\n

\u062f\u0631 \u0627\u0646\u062a\u0647\u0627 \u0642\u0631\u0627\u0631 \u0627\u0633\u062a \u0645\u06cc\u0627\u0646\u06af\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631 \u0622\u0628 \u0633\u0647 \u0638\u0631\u0641 \u062f\u0631 \u0647\u0631 \u0638\u0631\u0641 \u0642\u0631\u0627\u0631 \u06af\u06cc\u0631\u062f .
\n\u0633\u0647 \u062d\u0627\u0644\u062a \u0645\u062a\u0635\u0648\u0631 \u0627\u0633\u062a .
\n1) \u0647\u0631 \u0633\u0647 \u0638\u0631\u0641 \u0645\u0642\u062f\u0627\u0631 \u06cc\u06a9\u0633\u0627\u0646\u06cc \u0622\u0628 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u0646\u062f \u06a9\u0647 \u0628\u0647 \u0648\u0636\u0648\u062d \u067e\u0627\u0633\u062e \u0635\u0641\u0631 \u0627\u0633\u062a .
\n2)\u06cc\u06a9\u06cc \u0627\u0632 \u0638\u0631\u0648\u0641 \u0645\u0642\u062f\u0627\u0631 \u0645\u06cc\u0627\u0646\u06af\u06cc\u0646 \u0633\u0647 \u0638\u0631\u0641 \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u062f \u060c \u0628\u062f\u06cc\u0647\u06cc \u0627\u0633\u062a \u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u06cc\u06a9 \u0627\u0633\u062a \u0686\u0631\u0627 \u06a9\u0647 \u0628\u0627 \u0628\u0631\u0627\u0628\u0631 \u06a9\u0631\u062f\u0646 \u0645\u0642\u062f\u0627\u0631 \u062f\u0648 \u0638\u0631\u0641 \u062f\u06cc\u06af\u0631 \u060c \u0647\u0631 \u0633\u0647 \u06cc\u06a9\u0633\u0627\u0646 \u0645\u06cc \u0634\u0648\u0646\u062f .
\n3)\u0647\u06cc\u0686 \u06cc\u06a9 \u0627\u0632 \u062d\u0627\u0644\u0627\u062a \u0628\u0627\u0644\u0627 \u0646\u0628\u0627\u0634\u062f \u060c \u06a9\u0647 \u062f\u0631 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u062c\u0648\u0627\u0628 2 \u0627\u0633\u062a (\u0642\u0637\u0639\u0627 \u0646\u0645\u06cc \u062a\u0648\u0627\u0646\u062f \u067e\u0627\u0633\u062e \u0635\u0641\u0631 \u06cc\u0627 \u06cc\u06a9 \u0628\u0627\u0634\u062f)
\n\u0627\u06a9\u0646\u0648\u0646 \u06a9\u0627\u0641\u06cc \u0627\u0633\u062a \u060c \u0631\u0648\u0634\u06cc \u0627\u0631\u0627\u0626\u0647 \u062f\u0647\u06cc\u0645 \u06a9\u0647 \u0628\u0627 \u062f\u0648 \u062d\u0631\u06a9\u062a \u0634\u0631\u0627\u06cc\u0637 \u0628\u0631\u0642\u0631\u0627\u0631 \u0634\u0648\u062f : \u0627\u0628\u062a\u062f\u0627 \u062f\u0648 \u0638\u0631\u0641 \u0628\u0627 \u0645\u0642\u062f\u0627\u0631 \u0622\u0628 \u0628\u06cc\u0634\u062a\u0631 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc\u06af\u06cc\u0631\u06cc\u0645 \u0648 \u06cc\u06a9\u06cc \u0631\u0627 \u0645\u06cc\u0627\u0646\u06af\u06cc\u0646 \u0645\u06cc \u06a9\u0646\u06cc\u0645 \u060c\u0633\u067e\u0633 \u0627\u06cc\u0646 \u0638\u0631\u0641 \u0631\u0627 \u06a9\u0646\u0627\u0631 \u06af\u0630\u0627\u0634\u062a\u0647 \u0648 \u062f\u0648 \u0638\u0631\u0641 \u062f\u06cc\u06af\u0631 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u06af\u0631\u0641\u062a\u0647 \u0648 \u0622\u0646 \u0647\u0627 \u0631\u0627 \u0646\u06cc\u0632 \u0628\u0627\u0647\u0645 \u0628\u0631\u0627\u0628\u0631 \u0645\u06cc \u06a9\u0646\u06cc\u0645 .<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc : O(1)<\/span><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

C++ Code By Navick<\/a><\/p>\n

\u0627\u06a9\u0628\u0631\u062c\u0648\u062c\u0647<\/strong><\/a><\/p>\n

\u0627\u0632 \u0631\u0627\u0633 \u06cc\u06a9 \u062f\u0631 \u062f\u0631\u062e\u062a dfs<\/span> \u0645\u06cc \u0632\u0646\u06cc\u0645 .
\n\u0645\u0642\u062f\u0627\u0631 dp[i]<\/span> \u0631\u0648 \u0628\u0631\u0627\u0628\u0631 \u062c\u0648\u0627\u0628 \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u06cc \u0632\u06cc\u0631\u062f\u0631\u062e\u062a \u0631\u0627\u0633 i<\/span> \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f \u060c \u0628\u0646\u0627\u0628\u0631 \u0627\u06cc\u0646 \u062a\u0639\u0631\u06cc\u0641 \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u0628\u0631 dp[1]<\/span> \u0645\u06cc \u0628\u0627\u0634\u062f .
\n\u0645\u06cc \u062e\u0648\u0627\u0647\u06cc\u0645 \u0645\u0642\u062f\u0627\u0631 dp[i]<\/span> \u060c \u0631\u0627 \u0645\u062d\u0627\u0633\u0628\u0647 \u06a9\u0646\u06cc\u0645 .
\n\u062d\u0627\u0644\u0627\u062a \u0632\u06cc\u0631 \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0645\u06cc\u06af\u06cc\u0631\u06cc\u0645 .
\n1)\u0631\u0627\u0633 i<\/span> \u062e\u0648\u062f \u062f\u0631 \u0645\u062c\u0645\u0648\u0639\u0647 \u0628\u0627\u0634\u062f : \u062f\u0631 \u0627\u06cc\u0646 \u0635\u0648\u0631\u062a \u0647\u06cc\u0686 \u0631\u0627\u0633 \u062f\u06cc\u06af\u0631\u06cc \u0646\u0645\u06cc \u062a\u0648\u0627\u0646\u06cc\u0645 \u0627\u0646\u062a\u062e\u0627\u0628 \u06a9\u0646\u06cc\u0645 (\u062f\u0642\u06cc\u0642\u0627 \u06cc\u06a9 \u062d\u0627\u0644\u062a)
\n2)\u0631\u0627\u0633 i<\/span> \u062f\u0631 \u0645\u062c\u0645\u0648\u0639\u0647 \u0646\u0628\u0627\u0634\u062f : \u0627\u06a9\u0646\u0648\u0646 \u0632\u06cc\u0631 \u062f\u0631\u062e\u062a \u0647\u0627\u06cc \u0628\u0686\u0647 \u0647\u0627\u06cc \u0631\u0627\u0633 i<\/span> \u060c \u06a9\u0644\u0627 \u062a\u0627\u062b\u06cc\u0631\u06cc \u0628\u0631 \u0631\u0648\u06cc \u06cc\u06a9\u062f\u06cc\u06af\u0631 \u0646\u062f\u0627\u0631\u0646\u062f \u060c \u067e\u0633 \u062f\u0631 \u0627\u06cc\u0646 \u062d\u0627\u0644\u062a \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u0628\u0631 \u0636\u0631\u0628 dp[j]<\/span> \u0647\u0627\u0633\u062a \u06a9\u0647 j<\/span> \u0628\u0686\u0647 i<\/span> \u0628\u0627\u0634\u062f .
\n\u067e\u0633 \u0627\u06cc\u0646 \u0645\u0642\u062f\u0627\u0631 \u0628\u0631\u0627\u062d\u062a\u06cc \u0645\u062d\u0627\u0633\u0628\u0647 \u0645\u06cc \u0634\u0648\u062f .<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc : O(n)<\/span><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

C++ Code By Navick<\/a><\/p>\n

\u062f\u0631\u062e\u062a \u06a9\u0633\u0631\u0627<\/a>
\n<\/strong><\/p>\n

\u06a9\u0633\u0631 \\frac {a} {b} <\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u067e\u062f\u0631 \u0627\u0648 \u06cc\u06a9\u06cc \u0627\u0632 \u06a9\u0633\u0631 \u0647\u0627\u06cc \u0632\u06cc\u0631 \u0645\u06cc\u062a\u0648\u0627\u0646\u062f \u0628\u0627\u0634\u062f:<\/p>\n \\frac {a-b} {b} , \\frac {a} {b-a} <\/span>\n

\u06a9\u0647 \u0628\u0633\u062a\u0647 \u0628\u0647 \u0627\u06cc\u0646 \u06a9\u0647 \u06a9\u062f\u0627\u0645 \u06cc\u06a9\u06cc \u0627\u0632 a<\/span> \u0648 b<\/span> \u0628\u0632\u0631\u06af\u062a\u0631 \u0627\u0633\u062a \u06cc\u06a9\u06cc \u0645\u0646\u0641\u06cc \u0648 \u062f\u06cc\u06af\u0631\u06cc \u0645\u062b\u0628\u062a \u0645\u06cc\u200c\u0634\u0648\u062f. \u067e\u0633 \u06cc\u06a9\u062a\u0627 \u062a\u0639\u06cc\u06cc\u0646 \u0645\u06cc\u200c\u0634\u0648\u062f.<\/p>\n

\u062d\u0627\u0644 \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f b \\le a<\/span> \u0628\u0627\u0634\u062f. \u062a\u0627 \u0648\u0642\u062a\u06cc \u06a9\u0647 b \\le a<\/span> \u0628\u0645\u0627\u0646\u062f a<\/span> \u0645\u0646\u0647\u0627\u06cc b<\/span> \u0645\u06cc\u0634\u0648\u062f.<\/p>\n

\u067e\u0633 \u0627\u0632 \u06a9\u0633\u0631 \\frac {a} {b} <\/span> \u0628\u0647 \u06a9\u0633\u0631 \\frac {a \\mod b} {b} <\/span> \u0645\u06cc\u0631\u0633\u06cc\u0645.<\/p>\n

\u0628\u0627 \u0628\u0631\u0631\u0633\u06cc \u0647\u0631 \u062f\u0648 \u062d\u0627\u0644\u062a \u0628\u0647 \u0627\u06cc\u0646 \u0646\u062a\u06cc\u062c\u0647 \u0645\u06cc\u200c\u0631\u0633\u06cc\u0645 \u06a9\u0647 \u0627\u0632 \u06a9\u0633\u0631 \\frac {a} {b} <\/span> \u0628\u0647 \u06a9\u0633\u0631 \\frac {a \\mod b} {b \\mod a} <\/span> \u0628\u0627 \u0637\u06cc \u06a9\u0631\u062f\u0646 max( \\frac{a}{b} , \\frac{b}{a})<\/span>\u00a0\u06cc\u0627\u0644 \u0645\u06cc\u0631\u0633\u06cc\u0645.<\/p>\n

\u0627\u0646\u0642\u062f\u0631 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc\u062f\u0647\u06cc\u0645 \u062a\u0627 a=b<\/span>\u00a0\u0628\u0634\u0648\u062f \u06a9\u0647 \u00a0\u0628\u0647 \u0631\u0627\u0633 \u0631\u06cc\u0634\u0647 \u0631\u0633\u06cc\u062f\u0647 \u0627\u06cc\u0645.<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc: O(Q\\times(\\log{p_{i}}+\\log{q_{i}}))<\/span><\/p>\n

C++ Code By AmSen<\/a><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

\u062f\u0646\u0628\u0627\u0644\u0647 \u0648\u0644\u0627\u06cc\u06cc<\/strong><\/a><\/p>\n

\u0645\u06cc\u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u0639\u062f\u062f \u0627\u0648\u0644 \u062f\u0646\u0628\u0627\u0644\u0647 \u0628\u0627\u06cc\u062f \u0646\u0627\u0635\u0641\u0631 \u0628\u0627\u0634\u062f. \u062d\u0627\u0644 \u0641\u0631\u0636 \u06a9\u0646\u06cc\u0645 \u062a\u0639\u062f\u0627\u062f \u0627\u0639\u062f\u0627\u062f \u0645\u062b\u0628\u062a \u0622\u0631\u0627\u06cc\u0647 \u0628\u062c\u0632 \u0639\u062f\u062f \u0627\u0648\u0644 p<\/span> \u0628\u0627\u0634\u062f\u060c \u0645\u06cc\u062f\u0627\u0646\u06cc\u0645 \u06a9\u0647 \u062c\u0645\u0639 \u0627\u0639\u062f\u0627\u062f \u0622\u0631\u0627\u06cc\u0647 \u0628\u062c\u0632 \u0639\u062f\u062f \u0627\u0648\u0644 \u0628\u0631\u0627\u0628\u0631 \u0628\u0647 p+1<\/span> \u0627\u0633\u062a\u060c \u067e\u0633 \u0628\u062c\u0632 \u0639\u062f\u062f \u0627\u0648\u0644\u060c \u062f\u0631 \u0628\u0642\u06cc\u0647 \u0627\u0639\u062f\u0627\u062f \u06cc\u06a9 \u0639\u062f\u062f 2 \u062f\u0627\u0631\u06cc\u0645 \u0648 \u0628\u0642\u06cc\u0647 \u0627\u0639\u062f\u0627\u062f \u0645\u062b\u0628\u062a 1 \u0627\u0646\u062f. \u0647\u0645\u0686\u0646\u06cc\u0646 p\\leq3<\/span> \u0632\u06cc\u0631\u0627 \u0627\u06af\u0631 p>3<\/span> \u0628\u0627\u0634\u062f \u0622\u0646\u06af\u0627\u0647 \u0639\u062f\u062f 1\u060c \u0633\u0647 \u0628\u0627\u0631 \u062a\u06a9\u0631\u0627\u0631 \u0634\u062f\u0647 \u06a9\u0647 \u0646\u062a\u06cc\u062c\u0647 \u0645\u06cc\u062f\u0647\u062f a_{1}<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 3 \u0627\u0633\u062a \u06a9\u0647 \u062e\u0644\u0627\u0641 \u0641\u0631\u0636 \u0627\u0633\u062a.<\/p>\n

\u062d\u0627\u0644 \u0631\u0648\u06cc p<\/span> \u062d\u0627\u0644\u062a \u0628\u0646\u062f\u06cc \u0645\u06cc\u06a9\u0646\u06cc\u0645.<\/p>\n

\u0628\u0647 \u0627\u0632\u0627\u06cc p=1<\/span> \u062a\u0646\u0647\u0627 \u062d\u0627\u0644\u062a \u0631\u0634\u062a\u0647\u200c\u06cc 2,0,2,0<\/span> \u0627\u0633\u062a.<\/p>\n

\u0628\u0647 \u0627\u0632\u0627\u06cc p=2<\/span> \u0647\u0645 \u0631\u0634\u062a\u0647\u200c\u0647\u0627 1,2,1,0<\/span> \u0648\u00a02,1,2,0,0<\/span> \u0627\u0646\u062f.<\/p>\n

\u0628\u0647 \u0627\u0632\u0627\u06cc p=3<\/span> \u0631\u0634\u062a\u0647 \u0628\u0647 \u0635\u0648\u0631\u062a X,2,1,0,0,...,0,1,0,0,0<\/span> \u0627\u0633\u062a \u06a9\u0647 \u062a\u0639\u062f\u0627\u062f \u0635\u0641\u0631 \u0647\u0627\u06cc \u0628\u06cc\u0646 \u062f\u0648 \u0639\u062f\u062f 1\u060c \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 X-3<\/span> \u0627\u0633\u062a.<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc : O(n)<\/span><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

\u062a\u0627\u0628\u0639<\/strong><\/a><\/p>\n

\u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f a_{i}<\/span> \u0627\u0631\u062a\u0641\u0627\u0639 \u0633\u0627\u062e\u062a\u0645\u0627\u0646 i<\/span>\u00a0\u0628\u0627\u0634\u062f.<\/p>\n

f(l,r)<\/span> \u0628\u0631\u0627\u0628\u0631 \u0628\u0627 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0646\u0631 \u0628\u06cc\u0646 \u0633\u0627\u062e\u062a\u0645\u0627\u0646 \u0647\u0627\u06cc l<\/span> \u062a\u0627 r<\/span> \u0645\u06cc\u0634\u0648\u062f.<\/p>\n

\u062d\u0627\u0644 \u0639\u062f\u062f a_{i}<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0627\u06cc\u0646 \u0639\u062f\u062f \u062f\u0631 \u0628\u0627\u0632\u0647 [L,R]<\/span> \u0645\u06cc\u0646\u06cc\u0645\u0645 \u0628\u0627\u0634\u062f. \u0637\u0648\u0644 \u0645\u0627\u06a9\u0633\u0645\u06cc\u0645 \u0628\u0646\u0631\u06cc \u06a9\u0647 \u0627\u0631\u062a\u0641\u0627\u0639\u0634 a_{i}<\/span> \u0628\u0627\u0634\u062f \u0628\u0631\u0627\u0628\u0631 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0627\u0634\u062a\u0631\u0627\u06a9 [l_{i},r_{i}]<\/span> \u0647\u0627 \u0628\u0627 [L,R]<\/span> \u0627\u0633\u062a. \u06a9\u0647 \u0628\u0627 O(n\\log^2{n})<\/span> \u0628\u0647 \u062f\u0633\u062a \u0645\u06cc \u0622\u06cc\u062f.<\/p>\n

\u0628\u0631\u0627\u06cc \u062d\u0644 \u0633\u0648\u0627\u0644 \u0628\u0627 O(n\\log{n})<\/span> \u0627\u0628\u062a\u062f\u0627 \u0628\u0627\u06cc\u062f \u0628\u06cc\u0646 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u06a9\u0647 l_{i}\\le L<\/span> \u0647\u0633\u062a \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 r_{i}<\/span> \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u0641\u0631\u0636 \u06a9\u0646\u06cc\u062f \u0627\u06cc\u0646 \u0639\u062f\u062f x<\/span> \u0628\u0627\u0634\u062f. \u062a\u0645\u0627\u0645 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u06a9\u0647 r_{i}<\/span> \u0622\u0646\u200c\u0647\u0627 \u062f\u0631 \u0628\u0627\u0632\u0647 (x,R]<\/span> \u0647\u0633\u062a\u00a0l_{i}<\/span> \u0622\u0646\u200c\u0647\u0627 \u0628\u0632\u0631\u06af\u062a\u0631\u0645\u0633\u0627\u0648\u06cc L<\/span> \u0627\u0633\u062a.<\/p>\n

\u0628\u0631\u0627\u06cc \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f\u0646 x<\/span> \u0645\u06cc\u062a\u0648\u0627\u0646 \u0628\u0627 \u067e\u0627\u0631\u0634\u06cc\u0627\u0644 \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0628\u0627 O(1)<\/span> \u0628\u0647 \u062f\u0633\u062a \u0622\u0648\u0631\u062f \u0648 \u0628\u0631\u0627\u06cc \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0637\u0648\u0644\u0647 \u0628\u0642\u06cc\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627 \u0645\u06cc\u062a\u0648\u0627\u0646 \u0628\u0627 \u0633\u06af\u0645\u0646\u062a \u060c \u0645\u0627\u06a9\u0633\u06cc\u0645\u0645 \u0637\u0648\u0644\u0647 \u0628\u0627\u0632\u0647 \u0647\u0627\u06cc\u06cc \u06a9\u0647 r_{i}<\/span> \u0627\u0634\u0627\u0646 \u0628\u06cc\u0646 (x,R]<\/span> \u0647\u0633\u062a \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u0648 \u062f\u0631 \u06a9\u0644 \u0628\u0627 O(n\\log{n})<\/span> \u062d\u0644 \u0645\u06cc\u200c\u0634\u0648\u062f.<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc:\u200c\u00a0O(n\\log{n})<\/span><\/p>\n

C++ Code By AmSen<\/a><\/p>\n

\u0639\u062f\u062f \u0628\u0648\u06af\u0646\u062f\u0648\u06cc \u0631\u0634\u062a\u0647\u200c\u06cc \u062e\u0641\u0646<\/strong><\/a><\/p>\n

\u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0647\u0627 \u0631\u0627 \u0630\u062e\u06cc\u0631\u0647 \u06a9\u0631\u062f\u0647 \u0648 \u0622\u0646\u0647\u0627 \u0631\u0627 \u0622\u0641\u0644\u0627\u06cc\u0646 \u062c\u0648\u0627\u0628 \u0645\u06cc\u062f\u0647\u06cc\u0645.<\/p>\n

\u062a\u0627\u0628\u0639\u00a0solve(xl,xr)<\/span> \u0631\u0627 \u0645\u06cc\u0633\u0627\u0632\u06cc\u0645 \u0648 mid<\/span> \u0631\u0627 \\frac {xl+xr} {2}<\/span> \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u06a9\u0646\u06cc\u0645. \u062a\u0627\u0628\u0639 solve(xl,xr)<\/span> \u06a9\u0647 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0647\u0627\u06cc\u06cc \u06a9\u0647\u00a0l<\/span> \u0622\u0646\u0647\u0627 \u0627\u0632 mid<\/span> \u06a9\u0645\u062a\u0631\u060c \u0648 r<\/span> \u0622\u0646\u0647\u0627 \u0627\u0632 mid<\/span> \u0628\u06cc\u0634\u062a\u0631\u0645\u0633\u0627\u0648\u06cc \u0627\u0633\u062a \u0631\u0627 \u062c\u0648\u0627\u0628 \u0645\u06cc\u062f\u0647\u062f \u0648 \u0633\u067e\u0633 solve(xl,mid)<\/span> \u0648 solve(mid,xr)<\/span> \u0631\u0627 \u0635\u062f\u0627 \u0645\u06cc\u0632\u0646\u062f.<\/p>\n

\u0628\u0631\u0627\u06cc \u062c\u0648\u0627\u0628 \u062f\u0627\u062f\u0646 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u0647\u0627 \u0628\u0631\u0627\u06cc \u0628\u0627\u0632\u0647\u200c\u06cc [mid,xr)<\/span> \u0628\u0647 \u0627\u0632\u0627\u06cc \u062a\u0645\u0627\u0645 prefix \u0647\u0627\u06cc\u0634 OR \u0631\u0634\u062a\u0647 \u0647\u0627\u0631\u0627 \u062f\u0631 bitset<\/span> \u0630\u062e\u06cc\u0631\u0647 \u0645\u06cc\u06a9\u0646\u06cc\u0645 \u0648 \u0647\u0645\u0686\u0646\u06cc\u0646 \u0628\u0631\u0627\u06cc \u0628\u0627\u0632\u0647\u200c\u06cc [xl,mid)<\/span> \u0647\u0645 \u0628\u0647 \u0627\u0632\u0627\u06cc \u062a\u0645\u0627\u0645 suffix \u0647\u0627\u06cc\u0634 \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0631\u0627 \u0627\u0646\u062c\u0627\u0645 \u0645\u06cc\u062f\u0647\u06cc\u0645.<\/p>\n

\u062d\u0627\u0644 \u0647\u0631 \u062f\u0631\u062e\u0648\u0627\u0633\u062a \u06a9\u0647 \u062e\u0627\u0635\u06cc\u062a\u06cc \u06a9\u0647 \u062f\u0631 \u0627\u0628\u062a\u062f\u0627 \u06af\u0641\u062a\u06cc\u0645 \u0631\u0627 \u062f\u0627\u0634\u062a \u0631\u0627 \u0645\u06cc\u062a\u0648\u0627\u0646 \u0628\u0627 OR \u06af\u0631\u0641\u062a\u0646 \u062f\u0648\u062a\u0627 \u0627\u0632 bitset<\/span> \u0647\u0627 \u062c\u0648\u0627\u0628 \u062f\u0627\u062f.<\/p>\n

\u067e\u06cc\u0686\u06cc\u062f\u06af\u06cc : O(qlgn+qk\/32+nklgn\/32) <\/span><\/p>\n

C++ Code By Sa1378<\/a><\/p>\n

C++ Code By Navick<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

\u0645\u0633\u0627\u0628\u0642\u0647 \u062a\u0645\u0627\u0645 \u0634\u062f! \u0627\u0645\u06cc\u062f\u0648\u0627\u0631\u06cc\u0645 \u0627\u0632 \u0633\u0648\u0627\u0644\u0627 \u062e\u0648\u0634\u062a\u0648\u0646 \u0627\u0648\u0645\u062f\u0647 \u0628\u0627\u0634\u0647 \ud83d\ude09 \u0631\u0627\u0647 \u062d\u0644 \u0633\u0648\u0627\u0644\u0627\u062a \u062f\u0631 \u0627\u062f\u0627\u0645\u0647 \u0645\u0637\u0644\u0628<\/p>\n","protected":false},"author":6,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46,50,141],"tags":[],"class_list":["post-2304","post","type-post","status-publish","format-standard","hentry","category-developer","category-quera-developer","category-contests-and-events"],"_links":{"self":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/comments?post=2304"}],"version-history":[{"count":0,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/posts\/2304\/revisions"}],"wp:attachment":[{"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/media?parent=2304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/categories?post=2304"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/quera.org\/blog\/wp-json\/wp\/v2\/tags?post=2304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}