4504. AND & OR & max на отрезке

 

У Василия есть n чисел: x1, x2,..., xn.

Вы должны помочь ему быстро отвечать на запросы двух типов:

AND L R – в этом случае нужно найти маскимальное значение xi1 AND xi2 AND ... AND xik, где {xik} – некоторое непустое подмножество, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.

OR L R – в этом случае вам нужно найти маскимальное значение xi1 OR xi2 OR ... OR xik где {xik} – некоторое непустое подмножество, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.

 

Вход. В первой строке задано число n (1 ≤ n ≤ 105).

В следующей строке задано n чисел xi (0 ≤ xi ≤ 109). После этого задано число m (1 ≤ m ≤ 105) – количество запросов, на которые вам нужно найти ответ. В последующих m сроках заданы сами запросы.

 

Выход. Выведите ответ для каждого запроса в отдельной строке.

 

Пример входа

5

1 2 3 4 5

10

AND 1 5

AND 1 4

AND 1 3

AND 2 4

AND 1 1

OR 1 5

OR 1 1

OR 1 2

OR 1 3

OR 4 5

 

Пример выхода

5

4

3

4

1

7

1

3

3

5

 

 

РЕШЕНИЕ

структуры данных – дерево отрезков

 

Анализ алгоритма

Максимальное значение функции OR на подотрезке [L, R] равно значению OR на всем отрезке. Поэтому ее будем вычилять как функцию на отрезке. В вершине дерева отрезков для нее достаточно хранить одного значения orOp.

Для вычисления максимального значения andOp функции AND на подотрезке [L, R] будем поддерживать значение функции AND на префиксе (prefix), суффиксе (suffix) и на всем отрезке (andSeg). Имеют место соотношения:

prefix[L..R] = max(prefix[L..m], andSeg[L..m] & prefix[m+1.. R])

 suffix[L.. R] = max(suffix[m+1.. R], suffix[L.. m] & andSeg[m+1.. R])

andOp[L..R] = max(andOp[L..m], andOp[m+1.. R], suffix[L..m] & prefix[m+1.. R])

andSeg[L.. R] = andSeg[L..m] & andSeg[m+1.. R]

 

Можно заметить, что максимальное значение функции AND на подотрезке [L, R] равно максимальному числу на всем отрезке [L, R]. Таким образом достатчно реализовать статическое дерево отрезков с реализацией двух операций: OR и максимума.

 

Реализация алгоритма

Объявим структуру дерева отрезков.

.

#define MAX 100010

struct node

{

  int andOp, andSeg, orOp, prefix, suffix;

} SegTree[4*MAX];

 

Слияние двух вершин.

 

node Merge(node &Left, node &Right)

{

  node Res;

  Res.prefix = max(Left.prefix,Left.andSeg & Right.prefix);

  Res.suffix = max(Right.suffix,Right.andSeg & Left.suffix);

  Res.orOp = Left.orOp | Right.orOp;

  Res.andSeg = Left.andSeg & Right.andSeg;

  Res.andOp = max(max(Left.andOp,Right.andOp),Left.suffix & Right.prefix);

  return Res;

}

 

Построение дерева отрезков по массиву а.

 

void build(int *a, int Vertex, int LeftPos, int RightPos)

{

  if (LeftPos == RightPos)

    SegTree[Vertex].orOp = SegTree[Vertex].andOp = SegTree[Vertex].prefix =

    SegTree[Vertex].suffix = a[LeftPos];

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    build (a, 2*Vertex, LeftPos, Middle);

    build (a, 2*Vertex+1, Middle+1, RightPos);

 

    SegTree[Vertex] = Merge(SegTree[2*Vertex], SegTree[2*Vertex+1]);

  }

}

 

Вычисляем ответ на запрос. Функция get возвращает структуру node.

 

struct node get(int Vertex, int LeftPos, int RightPos,

                int Left, int Right, char type)

{

  if ((Left == LeftPos) && (Right == RightPos))

    return SegTree[Vertex];

 

  int Middle = (LeftPos + RightPos) / 2;

  if (Right <= Middle )

    return get(2*Vertex,LeftPos, Middle,Left,Right,type);

  if (Left > Middle)

    return get(2*Vertex+1,Middle+1,RightPos,Left,Right,type);

 

  struct node LeftNode  =

    get(2*Vertex,LeftPos,Middle,Left,Middle,type);

  struct node RightNode =

    get(2*Vertex+1,Middle+1,RightPos,Middle+1,Right,type);

  return Merge(LeftNode, RightNode);

}

 

Основная часть программы. Читаем входной массив чисел.

 

scanf("%d",&n);

for(i = 1; i <= n; i++)

  scanf("%d",&mas[i]);

 

Строим дерево отрезков.

 

build(mas,1,1,n);

 

Последовательно обрабатываем m запросов.

 

scanf("%d",&m);

for(i = 0; i < m; i++)

{

  scanf("%s %d %d",s,&L,&R);

  res = get(1,1,n,L,R,s[0]);

  printf("%d\n",(s[0] == 'A') ? res.andOp : res.orOp);

}

 

Реализация алгоритма – OR и максимум

 

#include <cstdio>

#include <algorithm>

#define MAX 100010

#define INF 2100000000

using namespace std;

 

struct node

{

  int max, orOp;

} SegTree[4*MAX];

 

int mas[MAX];

char s[10];

 

void build(int *a, int Vertex, int LeftPos, int RightPos)

{

  if (LeftPos == RightPos)

    SegTree[Vertex].orOp = SegTree[Vertex].max = a[LeftPos];

  else

  {

    int Middle = (LeftPos + RightPos) / 2;

    build (a, 2*Vertex, LeftPos, Middle);

    build (a, 2*Vertex+1, Middle+1, RightPos);

 

    SegTree[Vertex].orOp = SegTree[2*Vertex].orOp | SegTree[2*Vertex+1].orOp;

    SegTree[Vertex].max =

      max(SegTree[2*Vertex].max, SegTree[2*Vertex+1].max);

  }

}

 

int GetOr(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

  if (Left > Right) return 0;

  if ((Left == LeftPos) && (Right == RightPos))

    return SegTree[Vertex].orOp;

 

  int Middle = (LeftPos + RightPos) / 2;

  return GetOr(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)) |

         GetOr(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

 

int GetMax(int Vertex, int LeftPos, int RightPos, int Left, int Right)

{

  if (Left > Right) return -INF;

  if ((Left == LeftPos) && (Right == RightPos))

    return SegTree[Vertex].max;

 

  int Middle = (LeftPos + RightPos) / 2;

  return max(GetMax(2*Vertex, LeftPos, Middle, Left, min(Right,Middle)),

          GetMax(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right));

}

 

int i, L, R, n, m, res;

 

int main(void)

{

  scanf("%d",&n);

  for(i = 1; i <= n; i++)

    scanf("%d",&mas[i]);

 

  build(mas,1,1,n);

 

  scanf("%d",&m);

  for(i = 0; i < m; i++)

  {

    scanf("%s %d %d",s,&L,&R);

    if (s[0] == 'A')

      res = GetMax(1,1,n,L,R);

    else

      res = GetOr(1,1,n,L,R);

    printf("%d\n",res);

  }

  return 0;

}