Biorąc pod uwagę zbiór S dodatnich liczb całkowitych, których elementy nie muszą być odrębne, muszę znaleźć minimalną sumę nieujemną, której nie można uzyskać z żadnego podzbioru danego zbioru.

Przykład:if S = {1, 1, 3, 7}, Możemy dostać0 tak jak(S' = {}), 1 tak jak(S' = {1}), 2 tak jak(S' = {1, 1}), 3 tak jak(S' = {3}), 4 tak jak(S' = {1, 3}), 5 tak jak(S' = {1, 1, 3}), ale nie możemy dostać6.

Teraz dostaliśmy jedenarray A, składający się zN dodatnie liczby całkowite. Oni sąM zapytania, z których każda składa się z dwóch liczb całkowitychLi iRi opisz to zapytanie: musimy znaleźć tę sumę, której nie można uzyskać z tablicyelements ={A[Li], A[Li+1], ..., A[Ri-1], A[Ri]} .

Wiem, że można to znaleźć za pomocą brutalnej siły, która ma być wykonana w O (2 ^ n). Ale biorąc pod uwagę1 ≤ N, M ≤ 100,000.Nie można tego zrobić. Czyli ich skuteczne podejście do tego.