Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
1

Задача на подмножества

04.03.2018, 17:48. Просмотров 857. Ответов 4

Задан массив A из n целых чисел. Существуют операции двух видов:

1.Поменять местами A[l] и A[r].
2.Определить, является ли подмассив A[l, ... r] отсортированным в неубывающем порядке.
(1 ≤ n ≤ 300 000, 1 ≤ q ≤ 200 000)
Задача - ответить на запросы второго типа

Подскажите, пожалуйста, каким методом решать, если простой перебор слетает по времени?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2018, 17:48
Ответы с готовыми решениями:

Задача о сумме подмножества. Псевдокод в код С++
Доброго времени суток. Пожалуйста, помогите в решении следующей проблемы: необходимо данный...

Задача про подмножества. Кто шарит объясните
Задание во вложении.

Задача, сгенерировать все k-элементные подмножества множества
Нужна помощь с задачей, нужно решить с циклами или как то по другом, но не каких рекурсий тд. тп,...

Подмножества
Как зделать чтоб выводилось на екран только подмножества множества <=sqrt(n), где n - ето мощность...

Подмножества
Добрый день! Подскажите пожалуйста насчет подмножеств. Если к примеру у нас X=1, 2, 3, 4, 5;, Y=1,...

4
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
05.03.2018, 13:09 2
Лучший ответ Сообщение было отмечено Chvick как решение

Решение

Цитата Сообщение от Chvick Посмотреть сообщение
каким методом решать
Дерево отрезков.


Вершину дерева нужно определить так, чтобы можно было складывать (комбинировать) две вершины:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public struct SegmentNode
{
    public bool Result;
    public int Left;
    public int Right;
    public bool HasValue;
    
    public SegmentNode(int value)
    {
        Result = true;
        Left = value;
        Right = value;
        HasValue = true;
    }
    
    public static SegmentNode operator+(SegmentNode x, SegmentNode y)
    {
        if(!x.HasValue) return y;
        if(!y.HasValue) return x;
        return new SegmentNode
        {
            Result = x.Result && y.Result && x.Right <= y.Left,
            Left = x.Left,
            Right = y.Right,
            HasValue = true,
        };
    }
}



Стандартное дерево отрезков:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class SegmentTree
{
    public SegmentTree(int[] a) 
    {
        last = a.Length - 1;
        tree = new SegmentNode[4 * a.Length];   
        Build(a, 1, 0, last);
    }
    
    public bool Request(int l, int r)
    {
        return Request(1, 0, last, l, r).Result; 
    }
    
    public void Update(int pos, int newValue)
    {
        Update(1, 0, last, pos, newValue);
    }
    
    int last;
    SegmentNode[] tree;
 
    void Build(int[] a, int v, int tl, int tr)
    {
        if (tl == tr)
        {
            tree[v] = new SegmentNode(a[tl]);
            return;
        }
        
        int tm = (tl + tr) / 2;
        Build(a, v * 2, tl, tm);
        Build(a, v * 2 + 1, tm + 1, tr);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
    
    SegmentNode Request(int v, int tl, int tr, int l, int r)
    {
        if (l > r)
            return new SegmentNode();
            
        if (l == tl && r == tr)
            return tree[v];
            
        int tm = (tl + tr) / 2;
        return Request(v * 2, tl, tm, l, Math.Min(r, tm)) + Request(v * 2 + 1, tm + 1, tr, Math.Max(l, tm + 1), r);
    }
 
    void Update(int v, int tl, int tr, int pos, int new_val)
    {
        if (tl == tr)
        {
            tree[v] = new SegmentNode(new_val);
            return;
        }
        
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            Update(v * 2, tl, tm, pos, new_val);
        else
            Update(v * 2 + 1, tm + 1, tr, pos, new_val);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
}

Программа для тестирования:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
void Main()
{
    Test1();
}
 
void Test1()
{
    var rnd = new Random();
    int n = 100;
    int k = 5;
    int[] a = Enumerable.Repeat(rnd, n).Select(x => x.Next(-k * n, k * n + 1)).ToArray();
    //Console.WriteLine(string.Join(", ", a));
    var st = new SegmentTree(a);
    CheckAll(a, st);
    
    // random updates
    for(int i = 0; i < n/2; i++)
    {
        int j = rnd.Next(0, n);
        int val = rnd.Next(-k * n, k * n + 1);
        a[j] = val;
        //Console.WriteLine($"Update {i}: a[{j}] = {val};");
        st.Update(j, val);
        CheckAll(a, st);
    }
 
    // check all requests
    Console.WriteLine("OK");
}
 
void CheckAll(int[] a, SegmentTree st)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i; j < a.Length; j++)
        {
            var res = st.Request(i, j);
            var res2 = Check(a, i, j);
            if (res != res2)
            {
                Console.WriteLine(string.Join(", ", a));
                //st.t.Dump();
                throw new ApplicationException($"{res} != {res2} for [{i}, {j}]");
            }
        }
}
 
bool Check(int[] a, int l, int r)
{
    for (int i = l + 1; i <= r; i++)
    {
        if(a[i] < a[i-1])
            return false;
    }
    return true;
}
1
Chvick
1 / 1 / 3
Регистрация: 02.03.2018
Сообщений: 25
05.03.2018, 17:56  [ТС] 3
По причине возникновения вопросов по условию задачи, уточняю:

Задан массив,
на вход подаются запросы двух типов: (1, l, r) или (2, l, r);
1 - нужно поменять местами a[l] и a[r]
2 - вывести "Да" или "Нет" в зависимости от того, является ли отрезок [l, r] неубывающей последовательностью или нет.

Входные данные:
n и q (1 ≤ n ≤ 300 000, 1 ≤ q ≤ 200 000) - длина массива и количество запросов,
Вторая строка содержит n целых чисел - элементы массива (1 ≤ Ai ≤ 10^9)
Каждая из следующих q строк содержит один запрос. Первым числом в строке идет тип запроса - 1 или 2. Далее следуют
целые числа l и r (1 ≤ l ≤ r ≤ n).

Пример:

Ввод:
3 3
1 2 3
2 1 3
1 2 3
2 1 3

Вывод:
Да
Нет

Добавлено через 1 минуту
Shamil1, благодарю
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
06.03.2018, 08:23 4
Т.е. суть проблемы в том, что нужно определить является ли заданный отрезок отсортированным за время меньшее чем требуется для поочередного сравнения всех соседних элементов на отрезке, т.е. меньше чем за время (N-1) где N - длинна отрезка ?
0
Shamil1
Модератор
2257 / 1540 / 351
Регистрация: 26.03.2015
Сообщений: 5,494
06.03.2018, 09:13 5
Цитата Сообщение от wingblack Посмотреть сообщение
Т.е. суть проблемы в том, что нужно определить является ли заданный отрезок отсортированным за время меньшее чем требуется для поочередного сравнения всех соседних элементов на отрезке, т.е. меньше чем за время (N-1) где N - длинна отрезка ?
Да.
0
06.03.2018, 09:13
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.03.2018, 09:13

подмножества
Задано натуральное число n, определить и вывести на экран (по одному разу) все подмножества...

Подмножества множества {0,....,n-1}
Сгенерировать все подмножества данного N-элементного множества {0,....,n-1}. Решение: Заведем...

подмножества и множества
Разработать алгоритм генерации всех подмножеств n-элемента множества Помогите решить ее!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru