\u062a\u0648\u0636\u06cc\u062d \u0631\u0627\u0647 \u062d\u0644 \u0647\u0627\u06cc \u0645\u0633\u0627\u0628\u0642\u0647 \u0634\u0645\u0627\u0631\u0647 \u06cc\u06a9 Quera \u0628\u0647 \u0647\u0645\u0631\u0627\u0647 \u06a9\u062f\u0647\u0627\u06cc \u0635\u062d\u06cc\u062d \u0631\u0627 \u062f\u0631 \u0627\u062f\u0627\u0645\u0647 \u0645\u0637\u0644\u0628 \u0645\u06cc\u200c\u0628\u06cc\u0646\u06cc\u062f. \u062f\u0631 \u0635\u0648\u0631\u062a\u06cc \u06a9\u0647 \u0627\u0634\u062a\u0628\u0627\u0647\u06cc \u0645\u0634\u0627\u0647\u062f\u0647 \u06a9\u0631\u062f\u06cc\u062f \u062f\u0631 \u0628\u062e\u0634 \u0646\u0638\u0631\u0627\u062a \u0628\u0627 \u0645\u0627 \u062f\u0631 \u0645\u06cc\u0627\u0646 \u0628\u06af\u0630\u0627\u0631\u06cc\u062f.<\/p>\n
<\/p>\n
\u0628\u0631\u0627\u06cc \u062d\u0644 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u06a9\u0627\u0641\u06cc\u0633\u062a \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631 \u0627\u0633\u0645 \u062f\u0627\u062f\u0647\u200c\u0634\u062f\u0647\u060c \u062a\u0639\u062f\u0627\u062f \u062d\u0631\u0648\u0641 \u0645\u062a\u0645\u0627\u06cc\u0632\u0634 \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645. \u0645\u06cc\u062a\u0648\u0627\u0646\u06cc\u0645 \u0628\u0631\u0627\u06cc \u0647\u0631 \u06a9\u0644\u0645\u0647 w \u0648 \u062d\u0631\u0641 c\u060c \u062a\u0639\u062f\u0627\u062f \u062a\u06a9\u0631\u0627\u0631 c \u062f\u0631 w \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u06cc\u0645 \u0648 \u062a\u0639\u062f\u0627\u062f \u062d\u0631\u0648\u0641 \u0645\u062a\u0645\u0627\u06cc\u0632 w \u0631\u0627 \u0628\u0631\u0627\u0628\u0631 \u062a\u0639\u062f\u0627\u062f \u062d\u0631\u0641\u200c\u0647\u0627\u06cc \u0628\u0627 \u062d\u062f\u0627\u0642\u0644 \u06f1 \u062a\u06a9\u0631\u0627\u0631 \u0642\u0631\u0627\u0631 \u062f\u0647\u06cc\u0645.<\/p>\n
\u06a9\u062f<\/a><\/p>\n \u0628\u0627 \u062a\u0648\u062c\u0647 \u0628\u0647 \u0634\u0631\u0627\u06cc\u0637 \u06af\u0641\u062a\u0647\u200c\u0634\u062f\u0647 \u062f\u0631 \u0635\u0648\u0631\u062a \u0633\u0648\u0627\u0644\u060c \u0645\u062a\u0648\u062c\u0647 \u0645\u06cc\u0634\u0648\u06cc\u0645 \u06a9\u0647 \u0628\u0647 \u0627\u0632\u0627\u06cc \u0647\u0631\u06cc\u06a9 \u0627\u0632 \u062d\u0631\u0648\u0641 L, F, T, D \u062f\u0631 \u06a9\u0644\u0645\u0647\u200c\u06cc \u06af\u0641\u062a\u0647 \u0634\u062f\u0647\u060c \u06f2 \u062d\u0627\u0644\u062a \u0628\u0631\u0627\u06cc \u06a9\u0644\u0645\u0647\u200c\u06cc \u0645\u062f\u0646\u0638\u0631 \u06a9\u0631\u06cc\u0645 \u0648\u062c\u0648\u062f\u200c \u062f\u0627\u0631\u062f\u061b\u00a0\u0628\u0631\u0627\u06cc T\u00a0\u0645\u0645\u06a9\u0646 \u0627\u0633\u062a \u0645\u062f\u0646\u0638\u0631\u0634 K \u06cc\u0627 T \u0628\u0627\u0634\u062f\u060c \u0628\u0631\u0627\u06cc D \u062d\u0631\u0648\u0641 D \u06cc\u0627 G\u060c \u0628\u0631\u0627\u06cc L \u062d\u0631\u0648\u0641 L \u06cc\u0627 R \u0648 \u0628\u0631\u0627\u06cc F \u062d\u0631\u0648\u0641 F \u06cc\u0627 R. \u067e\u0633 \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u0628\u0631 \u062f\u0648 \u0628\u0647 \u062a\u0648\u0627\u0646 \u062a\u0639\u062f\u0627\u062f \u062d\u0631\u0648\u0641 \u0645\u0628\u0647\u0645 \u062f\u0631 \u06a9\u0644\u0645\u0647 \u0627\u0633\u062a.<\/p>\n \u06a9\u062f<\/a><\/p>\n \u0628\u0647 \u0627\u0632\u0627\u06cc \u0639\u062f\u062f x<\/span>\u060c \u062a\u0639\u062f\u0627\u062f \u0645\u0638\u0646\u0648\u0646\u06cc\u0646\u06cc \u06a9\u0647 \u062f\u0631 \u0644\u062d\u0638\u0647\u200c\u06cc x<\/span> \u062f\u0631 \u067e\u0627\u0631\u06a9 \u062d\u0636\u0648\u0631 \u062f\u0627\u0634\u062a\u0646\u062f \u0631\u0627 f(x)<\/span> \u0645\u06cc\u0646\u0627\u0645\u06cc\u0645 \u06a9\u0647 \u062f\u0631 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u200c\u06cc O(n)<\/span> \u0642\u0627\u0628\u0644 \u0645\u062d\u0627\u0633\u0628\u0647 \u0627\u0633\u062a. \u0627\u06cc\u0646 \u0645\u0633\u0626\u0644\u0647 \u0645\u0642\u062f\u0627\u0631 \u06a9\u0645\u06cc\u0646\u0647 \u0648 \u0628\u06cc\u0634\u06cc\u0646\u0647\u200c\u06cc f(x)<\/span> \u0628\u0647 \u0627\u0632\u0627\u06cc L \\le x \\le R<\/span> \u0631\u0627 \u0627\u0632 \u0645\u0627 \u0645\u06cc\u062e\u0648\u0627\u0647\u062f.<\/p>\n \u0646\u0645\u0648\u062f\u0627\u0631 \u062a\u0627\u0628\u0639 f<\/span> \u0627\u0632 L<\/span> \u062a\u0627 R<\/span> \u0631\u0627 \u062f\u0631 \u0646\u0638\u0631 \u0628\u06af\u06cc\u0631\u06cc\u062f. \u0645\u0642\u062f\u0627\u0631\u00a0\u0627\u06cc\u0646 \u062a\u0627\u0628\u0639\u00a0\u062a\u0646\u0647\u0627 \u062f\u0631\u00a0\u0646\u0642\u0627\u0637\u06cc\u00a0\u062a\u063a\u06cc\u06cc\u0631 \u0645\u06cc\u06a9\u0646\u062f \u06a9\u0647 \u06cc\u0627 \u0628\u0631\u0627\u0628\u0631 r_i<\/span> \u06cc\u0627 \u0628\u0631\u0627\u0628\u0631 l_i<\/span> \u0628\u0647 \u0627\u0632\u0627\u06cc \u06cc\u06a9 \u0645\u0638\u0646\u0648\u0646 \u0647\u0633\u062a\u0646\u062f \u0648 \u062f\u0631 \u0628\u06cc\u0646 \u0622\u0646\u200c\u0647\u0627 \u0645\u0642\u062f\u0627\u0631 \u062b\u0627\u0628\u062a\u06cc \u062f\u0627\u0631\u062f\u061b \u067e\u0633 \u0645\u0642\u062f\u0627\u0631\u00a0\u06a9\u0645\u06cc\u0646\u0647 \u06cc\u0627 \u0628\u06cc\u0634\u06cc\u0646\u0647\u200c\u06cc \u0627\u06cc\u0646 \u062a\u0627\u0628\u0639 \u062f\u0631 \u06cc\u06a9\u06cc \u0627\u0632 \u0646\u0642\u0627\u0637\u00a0l_i, r_i, L, R, r_i + \\epsilon, l_i - \\epsilon<\/span> (\u0628\u0647 \u0627\u0632\u0627\u06cc\u00a0\\epsilon<\/span> \u0628\u0631\u0627\u0628\u0631 \u06cc\u06a9 \u0639\u062f\u062f \u0628\u0633\u06cc\u0627\u0631 \u06a9\u0648\u0686\u06a9) \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 \u062a\u0639\u062f\u0627\u062f \u0627\u06cc\u0646 \u0646\u0642\u0627\u0637\u00a0O(n)<\/span> \u0627\u0633\u062a. \u06a9\u0627\u0641\u06cc\u0633\u062a \u0645\u0642\u062f\u0627\u0631 f<\/span> \u0631\u0627 \u062f\u0631 \u0627\u06cc\u0646 \u0646\u0642\u0627\u0637 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f\u0647 \u0648 \u06a9\u0645\u06cc\u0646\u0647 \u0648 \u0628\u06cc\u0634\u06cc\u0646\u0647 \u0645\u0642\u062f\u0627\u0631 \u0628\u062f\u0633\u062a \u0622\u0645\u062f\u0647 \u0631\u0627 \u062e\u0631\u0648\u062c\u06cc \u062f\u0647\u06cc\u0645. \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc \u0627\u06cc\u0646 \u0631\u0627\u0647 \u062d\u0644 O(n^2)<\/span> \u0627\u0633\u062a. \u0645\u06cc\u062a\u0648\u0627\u0646 \u0627\u06cc\u0646 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627 \u0631\u0627 \u0628\u0647 O(n\\log n)<\/span> \u06a9\u0627\u0647\u0634 \u062f\u0627\u062f\u061b \u0627\u0645\u0627 \u0628\u0631\u0627\u06cc\u00a0\u0645\u062d\u062f\u0648\u062f\u06cc\u062a\u200c\u0647\u0627\u06cc \u0633\u0648\u0627\u0644 \u0646\u06cc\u0627\u0632\u06cc \u0628\u0647 \u0627\u06cc\u0646\u06a9\u0627\u0631 \u0646\u06cc\u0633\u062a.<\/p>\n \u0627\u06cc\u0646 \u06a9\u062f<\/a>\u00a0\u0628\u0627 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc\u00a0O(n\\log n)<\/span> \u0648 \u0627\u06cc\u0646 \u06a9\u062f<\/a> \u0628\u0627 \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc\u00a0O(n^2)<\/span> \u0628\u0647 \u062a\u0631\u062a\u06cc\u0628 \u062a\u0648\u0633\u0637 \u0627\u06cc\u0645\u0627\u0646 \u063a\u0644\u0627\u0645\u06cc \u0648 \u0627\u0645\u06cc\u0631\u0645\u062d\u0645\u062f \u0642\u0627\u0633\u0645\u06cc \u0647\u0646\u06af\u0627\u0645\u00a0\u0645\u0633\u0627\u0628\u0642\u0647 \u0646\u0648\u0634\u062a\u0647\u200c\u0634\u062f\u0646\u062f.<\/p>\n \u062f\u0631 \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u06af\u0631\u0627\u0641\u06cc\u00a0n<\/span> \u0631\u0627\u0633\u06cc \u0628\u0647 \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u062f\u0627\u0631\u06cc\u0645 \u0648 \u0645\u06cc\u062e\u0648\u0627\u0647\u06cc\u0645 \u06cc\u06a9 \u0645\u0633\u06cc\u0631 \u0647\u0645\u06cc\u0644\u062a\u0648\u0646\u06cc \u0645\u0633\u0637\u062d \u0627\u0632 \u0622\u0646 \u067e\u06cc\u062f\u0627 \u06a9\u0646\u06cc\u0645. (\u06cc\u0639\u0646\u06cc \u0645\u0633\u06cc\u0631\u06cc \u06a9\u0647 \u0627\u0632 \u0647\u0645\u0647 \u0631\u0626\u0648\u0633 \u0628\u06af\u0630\u0631\u062f \u0648 \u0647\u06cc\u0686 \u062f\u0648 \u06cc\u0627\u0644\u0634 \u0628\u0627\u0647\u0645 \u062a\u0642\u0627\u0637\u0639 \u0646\u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u0646\u062f.)<\/p>\n \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646 \u06cc\u06a9 \u0645\u0633\u06cc\u0631 \u0647\u0645\u06cc\u0644\u062a\u0648\u0646\u06cc \u0648 \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646 \u06cc\u06a9 \u0632\u06cc\u0631\u06af\u0631\u0627\u0641 \u0628\u0632\u0631\u06af \u0645\u0633\u0637\u062d \u062f\u0631 \u06cc\u06a9 \u06af\u0631\u0627\u0641\u060c \u0647\u0631\u062f\u0648 \u062f\u0631 \u062f\u0633\u062a\u0647 \u0645\u0633\u0627\u0626\u0644 \u0633\u062e\u062a (NP-Hard) \u0647\u0633\u062a\u0646\u062f \u0648 \u0647\u0646\u0648\u0632 \u0631\u0627\u0647\u200c\u062d\u0644\u06cc \u0686\u0646\u062f\u062c\u0645\u0644\u0647\u200c\u0627\u06cc \u0628\u0631\u0627\u06cc \u0622\u0646\u0627\u0646 \u067e\u06cc\u062f\u0627 \u0646\u0634\u062f\u0647 \u0627\u0633\u062a. \u0627\u0645\u0627 \u0634\u0631\u0637 \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0628\u0648\u062f\u0646 \u062a\u0627\u062b\u06cc\u0631 \u0628\u0647\u200c\u0633\u0632\u0627\u06cc\u06cc \u0631\u0648\u06cc \u0633\u0648\u0627\u0644 \u062f\u0627\u0631\u062f.<\/p>\n \u0646\u06a9\u062a\u0647 \u0627\u0635\u0644\u06cc \u0627\u06cc\u0646\u06a9\u0647 \u0631\u0626\u0648\u0633 \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0686\u06cc\u062f\u0647 \u0634\u062f\u0647\u200c\u0627\u0646\u062f \u0627\u06cc\u0646 \u0627\u0633\u062a \u06a9\u0647 \u0645\u06cc\u062a\u0648\u0627\u0646 \u062b\u0627\u0628\u062a \u06a9\u0631\u062f \u06a9\u0647 \u0631\u0626\u0648\u0633 \u0647\u0631 \u067e\u06cc\u0634\u0648\u0646\u062f\u06cc \u0627\u0632 \u06cc\u06a9 \u0645\u0633\u06cc\u0631 \u0647\u0645\u06cc\u0644\u062a\u0648\u0646\u06cc \u0645\u0633\u0637\u062d\u060c \u062f\u0631 \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0628\u0635\u0648\u0631\u062a \u0628\u0627\u0632\u0647\u200c\u0627\u06cc \u067e\u0634\u062a \u0633\u0631\u200c \u0647\u0645 \u0622\u0645\u062f\u0647\u200c\u0627\u0646\u062f. \u06cc\u0639\u0646\u06cc \u06a9\u0645\u0627\u0646\u06cc \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0648\u062c\u0648\u062f \u062f\u0627\u0631\u062f \u06a9\u0647 \u062a\u0646\u0647\u0627 \u0634\u0627\u0645\u0644 \u0627\u06cc\u0646 \u0631\u0627\u0633\u200c\u0647\u0627\u00a0\u0645\u06cc\u0634\u0648\u062f.<\/p>\n \u0628\u0631\u0627\u06cc \u0627\u062b\u0628\u0627\u062a \u0627\u06cc\u0646 \u0644\u0645 \u0627\u0632 \u0627\u0633\u062a\u0642\u0631\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0645\u06cc\u06a9\u0646\u06cc\u0645. \u0641\u0631\u0636 \u0627\u0633\u062a\u0642\u0631\u0627 \u0631\u0627 \u0642\u0648\u06cc \u0645\u06cc\u06a9\u0646\u06cc\u0645: i<\/span> \u0631\u0627\u0633\u200c \u0627\u0628\u062a\u062f\u0627\u06cc\u06cc \u0645\u0633\u06cc\u0631 \u0647\u0645\u06cc\u0644\u062a\u0648\u0646\u06cc \u0645\u0633\u0637\u062d\u00a0\u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0628\u0635\u0648\u0631\u062a \u0628\u0627\u0632\u0647\u200c\u0627\u06cc \u067e\u0634\u062a \u0633\u0631 \u0647\u0645 \u0642\u0631\u0627\u0631 \u062f\u0627\u0631\u0646\u062f \u06a9\u0647 i<\/span>\u0645\u06cc\u0646 \u0631\u0627\u0633\u00a0\u0627\u06cc\u0646 \u0645\u0633\u06cc\u0631 \u06cc\u06a9\u06cc \u0627\u0632 \u062f\u0648 \u0631\u0627\u0633 \u0627\u0646\u062a\u0647\u0627\u06cc\u06cc \u0622\u0646 \u0628\u0627\u0632\u0647 \u0627\u0633\u062a. \u0627\u06cc\u0646 \u0641\u0631\u0636 \u0628\u0631\u0627\u06cc \u067e\u06cc\u0634\u0648\u0646\u062f \u062a\u06a9 \u0631\u0627\u0633\u06cc \u0645\u0633\u06cc\u0631\u00a0\u0628\u0631\u0642\u0631\u0627\u0631 \u0627\u0633\u062a. \u0628\u0627 \u0641\u0631\u0636 \u0628\u0631\u0642\u0631\u0627\u0631\u06cc \u0628\u0631\u0627\u06cc \u067e\u06cc\u0634\u0648\u0646\u062f\u00a0i<\/span> \u0631\u0627\u0633\u06cc \u06a9\u0647 i < n<\/span>\u060c \u0645\u06cc\u062e\u0648\u0627\u0647\u06cc\u0645 \u062b\u0627\u0628\u062a \u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0644\u0645 \u06af\u0641\u062a\u0647 \u0634\u062f\u0647 \u0628\u0631\u0627\u06cc \u067e\u06cc\u0634\u0648\u0646\u062f\u00a0i+1<\/span> \u0631\u0627\u0633\u06cc \u0646\u06cc\u0632 \u0628\u0631\u0642\u0631\u0627\u0631 \u0627\u0633\u062a. \u0628\u062f\u0648\u0646 \u06a9\u0627\u0647\u0634 \u0641\u0631\u0636 \u0645\u0633\u0626\u0644\u0647\u060c \u0641\u0631\u0636 \u0645\u06cc\u06a9\u0646\u06cc\u0645\u00a0i<\/span> \u0631\u0627\u0633 \u0627\u0648\u0644 \u0645\u0633\u06cc\u0631 \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0631\u0648\u06cc \u06a9\u0645\u0627\u0646 \u0628\u06cc\u0646 \u0631\u0627\u0633\u00a01<\/span> \u0648 \u0631\u0627\u0633\u00a0i<\/span> \u0628\u0635\u0648\u0631\u062a \u0633\u0627\u0639\u062a\u06af\u0631\u062f \u0622\u0645\u062f\u0647 \u0627\u0646\u062f \u0648 \u0634\u0645\u0627\u0631\u0647\u200c\u06cc i<\/span>\u0645\u06cc\u0646 \u0631\u0627\u0633 \u0645\u0633\u06cc\u0631 \u0628\u0631\u0627\u0628\u0631 i<\/span> \u0627\u0633\u062a. \u06cc\u0627\u0644 \u0628\u0639\u062f\u06cc \u062f\u0631 \u0645\u0633\u06cc\u0631\u060c \u06a9\u0645\u0627\u0646 \u0633\u0627\u0639\u062a\u06af\u0631\u062f\u00a0i<\/span> \u062a\u0627\u00a0n<\/span> \u0631\u0627 \u062f\u0648\u0628\u062e\u0634 \u0645\u062c\u0632\u0627 \u0645\u06cc\u06a9\u0646\u062f \u0648 \u0627\u062f\u0627\u0645\u0647\u200c\u06cc \u0645\u0633\u06cc\u0631 \u062f\u0631 \u062a\u0646\u0647\u0627 \u06cc\u06a9\u06cc \u0627\u0632 \u0622\u0646\u200c\u0647\u0627 \u0645\u06cc\u0633\u0631 \u062e\u0648\u0627\u0647\u062f \u0628\u0648\u062f\u061b \u0648\u06af\u0631\u0646\u0647 \u0645\u0633\u06cc\u0631 \u0627\u0646\u062a\u062e\u0627\u0628 \u0634\u062f\u0647 \u0645\u0633\u0637\u062d \u0628\u0627\u0642\u06cc \u0646\u0645\u06cc\u0645\u0627\u0646\u062f. \u067e\u0633 \u0686\u0648\u0646 \u0645\u0633\u06cc\u0631 \u0647\u0645\u06cc\u0644\u062a\u0648\u0646\u06cc \u0627\u0633\u062a \u06cc\u06a9\u06cc \u0627\u0632 \u0627\u06cc\u0646 \u062f\u0648\u0628\u062e\u0634 \u0628\u0627\u06cc\u062f \u062a\u0647\u06cc \u0628\u0627\u0634\u062f \u067e\u0633 \u0631\u0627\u0633 \u0628\u0639\u062f\u06cc \u0645\u0633\u06cc\u0631 \u06cc\u0627 \u0631\u0627\u0633 \u0634\u0645\u0627\u0631\u0647\u00a0n<\/span> \u0627\u0633\u062a \u0648 \u06cc\u0627 \u0631\u0627\u0633 \u0634\u0645\u0627\u0631\u0647\u00a0i+1<\/span> \u06a9\u0647 \u062f\u0631 \u0647\u0631\u200c \u062f\u0648 \u062d\u0627\u0644\u062a \u0641\u0631\u0636 \u0645\u0633\u0626\u0644\u0647 \u0628\u0631\u0627\u06cc\u00a0i+1<\/span> \u0631\u0627\u0633 \u0627\u0648\u0644 \u0646\u06cc\u0632 \u0628\u0631\u0642\u0631\u0627\u0631 \u062e\u0648\u0627\u0647\u062f \u0645\u0627\u0646\u062f.\u00a0\\blacksquare<\/span><\/p>\n \u0628\u0631\u0627\u06cc \u062d\u0644 \u0645\u0633\u0626\u0644\u0647 \u0627\u0632 \u0628\u0631\u0646\u0627\u0645\u0647\u200c\u0646\u0648\u06cc\u0633\u06cc \u067e\u0648\u06cc\u0627 \u0627\u0633\u062a\u0641\u0627\u062f\u0647 \u0645\u06cc\u06a9\u0646\u06cc\u0645.\u00a0dp_{i, j, dir}<\/span> \u0631\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u06a9\u0646\u06cc\u0645: \u0627\u06af\u0631 \u0645\u06cc\u062a\u0648\u0627\u0646 \u0645\u0633\u06cc\u0631\u06cc \u062f\u0631 \u06af\u0631\u0627\u0641 \u06cc\u0627\u0641\u062a \u06a9\u0647 \u0631\u0626\u0648\u0633 \u0622\u0646 \u0631\u0627\u0633\u200c\u0647\u0627\u06cc \u06a9\u0645\u0627\u0646\u00a0i<\/span> \u062a\u0627\u00a0j<\/span> \u062f\u0631 \u062c\u0647\u062a dir<\/span> (\u0633\u0627\u0639\u062a\u06af\u0631\u062f \u06cc\u0627 \u067e\u0627\u062f\u0633\u0627\u0639\u062a\u06af\u0631\u062f) \u062f\u0648\u0631 \u062f\u0627\u06cc\u0631\u0647 \u0628\u0627\u0634\u0646\u062f \u0648 \u0631\u0627\u0633 \u0627\u0646\u062a\u0647\u0627\u06cc\u06cc \u0622\u0646\u00a0j<\/span> \u0628\u0627\u0634\u062f\u060c \u0645\u0642\u062f\u0627\u0631\u00a0dp_{i, j, dir}<\/span> \u0628\u0631\u0627\u0628\u0631 true<\/span> \u0627\u0633\u062a \u0648\u06af\u0631\u0646\u0647 false<\/span>. \u0645\u06cc\u062a\u0648\u0627\u0646 \u0645\u0634\u0627\u0628\u0647 \u0627\u062b\u0628\u0627\u062a \u0644\u0645 \u06af\u0641\u062a\u0647 \u0634\u062f\u0647\u060c \u0645\u0642\u0627\u062f\u06cc\u0631 \u0627\u06cc\u0646 \u0622\u0631\u0627\u06cc\u0647 \u0631\u0627 \u0628\u062f\u0633\u062a \u0622\u0648\u0631\u062f. \u0632\u0645\u0627\u0646 \u0627\u062c\u0631\u0627\u06cc \u0627\u06cc\u0646 \u0631\u0627\u0647\u200c\u062d\u0644\u00a0O(n^2)<\/span> \u0627\u0633\u062a.<\/p>\n \u06a9\u062f<\/a>\u00a0\u0627\u06cc\u0646 \u0631\u0627\u0647\u200c\u062d\u0644 \u06a9\u0647 \u062a\u0648\u0633\u0637 \u0645\u062d\u0645\u062f\u200c\u0647\u0627\u062f\u06cc \u062d\u062c\u062a \u0647\u0646\u06af\u0627\u0645 \u0645\u0633\u0627\u0628\u0642\u0647 \u0646\u0648\u0634\u062a\u0647\u200c\u0634\u062f\u0647 \u0627\u0633\u062a.<\/p>\n \u062f\u0631 \u0639\u0644\u0648\u0645 \u06a9\u0627\u0645\u067e\u06cc\u0648\u062a\u0631\u060c \u06a9\u0644\u0627\u0633\u06cc \u0627\u0632 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u200c\u0647\u0627 \u062a\u0639\u0631\u06cc\u0641 \u0645\u06cc\u0634\u0648\u062f \u0628\u0646\u0627\u0645 one-pass algorithms. \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u200c\u0647\u0627 \u0628\u0631\u0627\u06cc \u062d\u0644 \u0645\u0633\u0627\u0626\u0644\u06cc \u0628\u06a9\u0627\u0631 \u0645\u06cc\u0631\u0648\u0646\u062f \u06a9\u0647 \u062f\u0631 \u0622\u0646\u200c\u0647\u0627 \u0627\u0646\u062f\u0627\u0632\u0647\u200c\u06cc \u0648\u0631\u0648\u062f\u06cc \u0628\u0633\u06cc\u0627\u0631 \u0628\u0632\u0631\u06af \u0627\u0633\u062a\u060c \u0628\u0637\u0648\u0631\u06cc \u06a9\u0647 \u0645\u0639\u0645\u0648\u0644\u0627\u064b \u0646\u0645\u06cc\u062a\u0648\u0627\u0646 \u0648\u0631\u0648\u062f\u06cc \u0631\u0627 \u0646\u06af\u0647 \u062f\u0627\u0634\u062a \u0648 \u0628\u0627\u06cc\u062f \u0628\u0627 \u06cc\u06a9\u0628\u0627\u0631 \u062e\u0648\u0627\u0646\u062f\u0646 \u0648\u0631\u0648\u062f\u06cc\u060c \u067e\u0627\u0633\u062e \u0645\u0633\u0626\u0644\u0647 \u0631\u0627 \u06cc\u0627\u0641\u062a. \u062f\u0631 \u0633\u0648\u0627\u0644 \u062f\u0648\u0631\u06af\u06cc\u0631\u06cc \u0628\u0627\u06cc\u062f \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u06cc one-pass \u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0647\u200c\u06cc \u0645\u0633\u0627\u062d\u062a \u06cc\u06a9 \u0634\u06a9\u0644 \u0637\u0631\u0627\u062d\u06cc \u0645\u06cc\u06a9\u0631\u062f\u06cc\u062f. \u062f\u0631 \u062d\u0627\u0644\u062a \u06a9\u0644\u06cc \u0627\u06cc\u0646 \u06a9\u0627\u0631 \u0645\u0645\u06a9\u0646 \u0646\u06cc\u0633\u062a \u0627\u0645\u0627 \u0634\u06a9\u0644 \u062e\u0627\u0635 \u0648\u0631\u0648\u062f\u06cc \u0627\u06cc\u0646 \u0633\u0648\u0627\u0644 \u0627\u0631\u0627\u0626\u0647\u200c\u06cc \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 one-pass \u0631\u0627 \u0645\u0645\u06a9\u0646 \u06a9\u0631\u062f\u0647 \u0627\u0633\u062a.<\/p>\n \u0627\u0628\u062a\u062f\u0627 \u0641\u0631\u0636 \u0645\u06cc\u06a9\u0646\u06cc\u0645 \u06a9\u0647 \u0634\u06a9\u0644 \u0631\u0627 \u0645\u06cc\u062a\u0648\u0627\u0646\u06cc\u0645 \u0646\u06af\u0647\u062f\u0627\u0631\u06cc\u0645. “\u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0628\u0646\u062f \u06a9\u0641\u0634” \u06cc\u0627 “\u0642\u0627\u0639\u062f\u0647\u200c\u06cc \u0645\u0633\u0627\u062d\u062a \u06af\u0627\u0648\u0633”\u060c \u0631\u0648\u0634 \u0645\u0639\u0645\u0648\u0644 \u0628\u0631\u0627\u06cc \u0645\u062d\u0627\u0633\u0628\u0647\u200c\u06cc \u0645\u0633\u0627\u062d\u062a \u06cc\u06a9 \u0634\u06a9\u0644 \u0628\u0633\u062a\u0647 \u0648 \u0628\u062f\u0648\u0646 \u0633\u0648\u0631\u0627\u062e\u00a0\u0627\u0633\u062a. \u062a\u0648\u0636\u06cc\u062d\u0627\u062a \u0628\u06cc\u0634\u062a\u0631 \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645 \u0631\u0627 \u0645\u06cc\u062a\u0648\u0627\u0646\u06cc\u062f \u062f\u0631 \u0627\u06cc\u0646\u062c\u0627<\/a>\u00a0\u0628\u062e\u0648\u0627\u0646\u06cc\u062f. \u0628\u0627 \u062f\u0642\u062a \u0628\u0647 \u0627\u06cc\u0646 \u0627\u0644\u06af\u0648\u0631\u06cc\u062a\u0645\u060c \u0645\u06cc\u0628\u06cc\u0646\u06cc\u0645 \u06a9\u0647 \u0644\u0632\u0648\u0645\u06cc \u0646\u062f\u0627\u0631\u062f \u06a9\u0647 \u0645\u0627 \u06a9\u0644 \u0634\u06a9\u0644 \u0631\u0627 \u062f\u0627\u0634\u062a\u0647 \u0628\u0627\u0634\u06cc\u0645 \u0648 \u0627\u06af\u0631\u00a0\u062e\u0637\u200c\u0647\u0627\u06cc \u062f\u0648\u0631 \u0634\u06a9\u0644 \u0631\u0627 \u0628\u0647 \u062a\u0631\u062a\u06cc\u0628 \u0633\u0627\u0639\u062a\u06af\u0631\u062f \u0628\u06cc\u0627\u0628\u06cc\u0645\u060c \u0628\u0631\u0627\u062d\u062a\u06cc \u0645\u06cc\u062a\u0648\u0627\u0646 \u062d\u0627\u0641\u0638\u0647 \u0631\u0627\u0647 \u062d\u0644 \u0631\u0627 \u0628\u0647\u00a0O(1)<\/span> \u06a9\u0627\u0647\u0634 \u062f\u0627\u062f. \u06cc\u0627\u0641\u062a\u0646 \u062f\u0648\u0631\u06af\u06cc\u0631\u06cc \u062e\u0637\u06cc \u0634\u06a9\u0644 \u0646\u06cc\u0632 \u0628\u0648\u0633\u06cc\u0644\u0647\u200c\u06cc \u062f\u0648\u0631\u06af\u06cc\u0631\u06cc \u062a\u0648\u0635\u06cc\u0641 \u0634\u062f\u0647 \u062f\u0631 \u0633\u0648\u0627\u0644 \u0628\u0635\u0648\u0631\u062a one-pass \u0627\u0645\u06a9\u0627\u0646\u200c\u067e\u0630\u06cc\u0631 \u0627\u0633\u062a. \u062f\u0642\u062a \u06a9\u0646\u06cc\u062f \u06a9\u0647 \u06a9\u062f \u067e\u06cc\u062f\u0627 \u06a9\u0631\u062f\u0646 \u062f\u0648\u0631\u06af\u06cc\u0631\u06cc \u062e\u0637\u06cc \u0634\u0627\u0645\u0644\u00a0\u062c\u0632\u06cc\u06cc\u0627\u062a \u0628\u0633\u06cc\u0627\u0631\u06cc \u0627\u0633\u062a.<\/p>\n\n
\u0644\u06a9\u0646\u062a<\/b><\/a><\/h3>\n<\/li>\n<\/ul>\n
\n
\u062c\u0646\u0627\u06cc\u062a<\/strong><\/a><\/h3>\n<\/li>\n<\/ul>\n
\n
\u06af\u0631\u062f\u0647\u0645\u0627\u06cc\u06cc<\/a><\/h3>\n<\/li>\n<\/ul>\n
\n
\u062f\u0648\u0631\u06af\u06cc\u0631\u06cc<\/a><\/h3>\n<\/li>\n<\/ul>\n