Beautiful Segments


Problem Statement :


You are given an array, , consisting of  integers.

A segment, , is beautiful if and only if the bitwise AND of all numbers in  with indices in the inclusive range of  is not greater than . In other words, segment  is beautiful if .

You must answer  queries. Each query, , consists of  integers: , , and . The answer for each  is the number of beautiful segments  such that  and .

Input Format

The first line contains two space-separated integers,  (the number of integers in ) and  (the number of queries).

The second line contains  space-separated integers, where the  integer denotes the  element of array .

Each line  of the  subsequent lines contains  space-separated integers, , , and , respectively, describing query .


Output Format

Print Q lines, where the jth  line contains the number of beautiful segments for query Qj.


Solution :



title-img 


                            Solution in C :

In   C++  :









#include "iostream"
#include "algorithm"
#include "vector"
#include "set"
#include "map"
#include "cstring"
#include "string"
#include "vector"
#include "cassert"
#include "queue"
#include "cstdio"
#include "cstdlib"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 40000 + 5;
const int LOG = 16;
const int Q = 1e5 + 5;
const int K = 200 + 5;
const int T = N / K + 5;
const int MAX = 200000;

int n, q;
int a[N], ql[LOG][N], qr[LOG][N];
int fen[MAX];
int L[Q], R[Q], X[Q], ans[Q];
vector < int > qu[T];

int fl(int x, int y, int k) {
    if(a[x] <= k)
        return y - x + 1;
    int res = a[x];
    x++;
    for(int i = LOG - 1; i >= 0; i--) {
        if((res & qr[i][x]) > k) {
            res &= qr[i][x];
            x += 1 << i;
        }
    }
    return max(0, y - x + 1);
}

void up(int x, int y, int k) {
    x += 5;
    y += 5;
    for(; x < MAX; x += x & -x)
        fen[x] += k;
    for(y++; y < MAX; y += y & -y)
        fen[y] -= k;
}

int get(int x) {
    x += 5;
    int res = 0;
    for(; x; x -= x & -x)
        res += fen[x];
    return res;
}

void f(int to, int x) {
    int last = 150000, cur = a[x];
    while(x >= to) {
        int lx = x + 1;
        cur &= a[x];
        x--;
        if(cur == 0)
            x = 0;
        else
        for(int i = LOG - 1; i >= 0; i--) {
            if((cur & ql[i][x]) == cur) {
                x -= 1 << i;
            }
        }
        x++;
        x = max(x, to);
        int len = lx - x;
        up(cur, last - 1, len);
        //doSmth();
        x--;
    }
}

int main() {
    
    scanf("%d %d", &n, &q);
    
    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        ql[0][i] = qr[0][i] = a[i];
    }
    
    for(int i = 1; i < LOG; i++) {
        for(int j = 1; j + (1 << i) - 1 <= n; j++) {
            qr[i][j] = qr[i - 1][j] & qr[i - 1][j + (1 << i - 1)];
        }
        for(int j = n; j - (1 << i) + 1 >= 1; j--) {
            ql[i][j] = ql[i - 1][j] & ql[i - 1][j - (1 << i - 1)];
        }
    }
    
    for(int i = 1; i <= q; i++) {
        scanf("%d %d %d", L + i, R + i, X + i);
        qu[(L[i] - 1) / K].push_back(i);
    }
    
    for(int it = 0; it < T; it++) {
        if(qu[it].empty())
            continue;
        sort(qu[it].begin(), qu[it].end(), [&](int x, int y) {
            return R[x] < R[y];
        });
        memset(fen, 0, sizeof(fen));
        int last = min(n, (it + 1) * K);
        int Rb = last, res = 0;
        for(auto id : qu[it]) {
            int x = L[id];
            int y = R[id];
            int k = X[id];
            for(int i = Rb + 1; i <= y; i++) {
                f(last + 1, i);
                Rb = i;
            }
            ans[id] = get(k);
            for(int i = x; i <= last and i <= y; i++) {
                ans[id] += fl(i, y, k);
            }
        }
    }
    
    for(int i = 1; i <= q; i++) {
        printf("%d\n", ans[i]);
    }
    
    return 0;
    
}








In  Java :







import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.BufferedOutputStream;
import java.util.Arrays;

public class Solution {

static int N, Q;
static int[] A;
static Test[] Tests;

public static void main(String[] args) throws Exception {
readDataAndTestsFromInput();
getCountsForTests();
printResults();
}

private static void readDataAndTestsFromInput() 

throws Exception {
StringBuilder builder = new StringBuilder(100000);
String aux = "";
BufferedReader reader = new BufferedReader(
    new InputStreamReader(System.in));
while ((aux = reader.readLine()) != null) {
builder.append(aux).append(" ");
}

String[] data = builder.toString().split(" ");
int idx = 0;
N = Integer.parseInt(data[idx++]);
Q = Integer.parseInt(data[idx++]);

A = new int[N];
for (int i = 0; i < N; i++) {
A[i] = Integer.parseInt(data[idx++]);
}

Tests = new Test[Q];
for (int i = 0; i < Q; i++) {
Tests[i] = new Test(Integer.parseInt(data[idx++]) - 1,
    Integer.parseInt(data[idx++]) - 1,
    Integer.parseInt(data[idx++]));
}
}

public static void printResults() {
StringBuilder sb = new StringBuilder(400000);
for (int i = 0; i < Q; i++) {
sb.append(Tests[i].count).append("\n");
}
System.out.print(sb.toString());
}

static class Test {
int left, right, limit;
int count;

public Test(int l, int r, int lim) {
this.left = l;
this.right = r;
this.limit = lim;
this.count = 0;
}
}

static class CompactMatrix {
static final int MINUS_KEY = -1;
static final int MAX_ROW = 19;

int[][] keys, counts;
int numOfKeys;

private CompactMatrix(int[][] keys, int[][] counts, int n) {
this.keys = keys;
this.counts = counts;
this.numOfKeys = n;
}

public static CompactMatrix CreateLeftMatrixOfANDFrom(
    int N, int[] A) {
int[][] keys = new int[N][MAX_ROW];
int[][] counts = new int[N][MAX_ROW];
for (int idx = 0; idx < N; idx++) {
keys[idx][0] = A[idx];
counts[idx][0] = 1;
}
int numOfKeys = N;

for (int idx = 0; idx < N; idx++) {
for (int row = 1; row < MAX_ROW; row++) {
keys[idx][row] = MINUS_KEY;
}
}

for (int idx = N - 2; idx >= 0; idx--) {
int preIdx = idx + 1;
int preRow = 0;
int row = 0;
do {
int nextValue = keys[idx][0] & keys[preIdx][preRow];
if (nextValue == keys[idx][row]) {
counts[idx][row] += counts[preIdx][preRow];
} else {
row += 1;
keys[idx][row] = nextValue;
counts[idx][row] = counts[preIdx][preRow];
numOfKeys += 1;
}
preRow += 1;
} while (keys[preIdx][preRow] != -1);
}
return new CompactMatrix(keys, counts, numOfKeys);
}

public static CompactMatrix CreateRightMatrixOfANDFrom(int N, 
int[] A) {
int[][] keys = new int[N][MAX_ROW];
int[][] counts = new int[N][MAX_ROW];
for (int idx = 0; idx < N; idx++) {
keys[idx][0] = A[idx];
counts[idx][0] = 1;
}
int numOfKeys = N;

for (int idx = 0; idx < N; idx++) {
for (int row = 1; row < MAX_ROW; row++) {
keys[idx][row] = MINUS_KEY;
}
}

for (int idx = 1; idx < N; idx++) {
int preIdx = idx - 1;
int preRow = 0;
int row = 0;
do {
int nextValue = keys[idx][0] & keys[preIdx][preRow];
if (nextValue == keys[idx][row]) {
counts[idx][row] += counts[preIdx][preRow];
} else {
row += 1;
keys[idx][row] = nextValue;
counts[idx][row] = counts[preIdx][preRow];
numOfKeys += 1;
}
preRow += 1;
} while (keys[preIdx][preRow] != -1);
}
return new CompactMatrix(keys, counts, numOfKeys);
}

public Struct[] getSortedKeysWithCount() {
Struct[] sortedKeys = new Struct[numOfKeys + 1];
int i = 0;
int colNum = keys.length;
for (int idx = 0; idx < colNum; idx++) {
int row = 0;
while (keys[idx][row] != MINUS_KEY) {
sortedKeys[i++] = new Struct(keys[idx][row],
 idx, counts[idx][row]);
row += 1;
}
}
// Insert a last smallest element to stop loop later
sortedKeys[numOfKeys] = new Struct(MINUS_KEY, -1, -1);

Arrays.sort(sortedKeys);
return sortedKeys;
}

public Counter newCounter() {
return new Counter(keys.length, getSortedKeysWithCount());
}

public int getKeyUsingLeftMatrixOf(int left, int right) {
int maxRow = right - left;
int idx = left;
int rowInMatrix = 0;
int row = counts[idx][rowInMatrix] - 1;
while (row < maxRow) {
rowInMatrix += 1;
row += counts[idx][rowInMatrix];
}
return keys[idx][rowInMatrix];
}
}

static class Struct implements Comparable<Struct> {
int key, dat, count;

public Struct(int v, int d, int c) {
this.key = v;
this.dat = d;
this.count = c;
}

public Struct(int v, int d) {
this(v, d, 0);
}

@Override
public int compareTo(Struct s) {
if (this.key < s.key) {
return 1;
}
if (this.key > s.key) {
return -1;
}
if (this.dat < s.dat) {
return 1;
}
if (this.dat > s.dat) {
return -1;
}
return 0;
}
}

static class Counter {
int[][] countsOfBiggerKeys;
int numOfColumnBlocks;
Struct[] sortedKeys;
int keyIdx;

public Counter(int colNum, Struct[] sortedKeys) {
this.numOfColumnBlocks = ( (int) (
    Math.log(colNum) / Math.log(2)) ) + 1;
this.countsOfBiggerKeys = 
new int[colNum][this.numOfColumnBlocks];
this.sortedKeys = sortedKeys;
this.keyIdx = 0;
}

public void countDownTo(int limit) {
while (sortedKeys[keyIdx].key > limit) { 
                          
updateCountWith(sortedKeys[keyIdx].count, 
sortedKeys[keyIdx].dat);
keyIdx += 1;
}
}

public void updateCountWith(int countOfKey,
 int rowIdx) {
for (int row=0; row < numOfColumnBlocks; row++) {
countsOfBiggerKeys[rowIdx][row] += countOfKey;
rowIdx /= 2;
}
}

public int getCountOfBiggerKeysToColumn(int rowIdx) {
int countOfBigger = 0;
int row = 0;
while (rowIdx > 0) {
if (rowIdx % 2 != 0) {
countOfBigger += countsOfBiggerKeys[rowIdx-1][row];
}
rowIdx /= 2;
row += 1;
}
return countOfBigger;
}
}

private static void getCountsForTests() {

CompactMatrix leftMatrix =
 CompactMatrix.CreateLeftMatrixOfANDFrom(N, A);
CompactMatrix rightMatrix = 
CompactMatrix.CreateRightMatrixOfANDFrom(N, A);
Counter leftCounter = leftMatrix.newCounter();
Counter rightCounter = rightMatrix.newCounter();

Struct[] sortedLimits = getSortedTestsByLimit();
for (int i = 0; i < Q; i++) {
int testId = sortedLimits[i].dat;
int limit = Tests[testId].limit;
int left = Tests[testId].left;
int right = Tests[testId].right;
int minKey = leftMatrix.getKeyUsingLeftMatrixOf(left, right);
if (minKey <= limit) { 
leftCounter.countDownTo(limit);
rightCounter.countDownTo(limit);

int countOfBigger = 
rightCounter.getCountOfBiggerKeysToColumn(right + 1);
countOfBigger -= 
leftCounter.getCountOfBiggerKeysToColumn(left);

int len = right - left + 1;
Tests[testId].count = len * (len + 1) / 2 - countOfBigger;
} 
}
}

private static Struct[] getSortedTestsByLimit() {
Struct[] sortedLimits = new Struct[Q];
for (int testId = 0; testId < Q; testId++) {
sortedLimits[testId] = new Struct(Tests[testId].limit, testId);
}
Arrays.sort(sortedLimits);
return sortedLimits;
}

}









In    C   :








#include <stdio.h>
#include <stdlib.h>
typedef struct _ct_node {
  int size;
  int priority;
  int value;
  int max;
  long long sum;
  struct _ct_node *left, *right;
} ct_node;
void query(int v, int tl, int tr, int l, int r, int *c, long long *s);
void insert(int v, int tl, int tr, int x, int y);
void remove2(int v, int tl, int tr, int x, int y);
int max(int x, int y);
int sizeOf(ct_node *root);
int maxOf(ct_node *root);
long long sumOf(ct_node *root);
void recalc(ct_node *root);
ct_node *merge(ct_node *L, ct_node *R);
void split(int x, ct_node **L, ct_node **R, ct_node *root, int f);
void query1(ct_node *root, int r, int *c, long long *s);
ct_node *remove1(ct_node *root, int x);
ct_node *insert1(ct_node *root, int x);
void solve(int base, int i, int j, int idx1, int idx2);
int range_and(int i, int j);
void sort_a2(int *a, int *b, int size);
void merge2(int *a, int *left_a, int *right_a, int *b, int *left_b,
            int *right_b, int left_size, int right_size);
int a[40000], b[40000][17], c[40000][17], len[40000], L[100000], R[100000],
    X[100000], M[40000][16], two[40000], A[800000], B[800000], C[800000],
    idx1[800000], idx2[100000];
long long ans[100000];
ct_node *t[160000];

int main() {
  int N, Q, t, size, count, i, j;
  long long sum;
  scanf("%d%d", &N, &Q);
  for (i = 0; i < N; i++)
    scanf("%d", a + i);
  for (i = 0; i < Q; i++) {
    scanf("%d%d%d", L + i, R + i, X + i);
    L[i]--;
    R[i]--;
    idx2[i] = i;
  }
  for (two[0] = 0, i = j = 1; i < N; i++)
    if (i + 1 > j * 2) {
      two[i] = two[i - 1] + 1;
      j *= 2;
    } else
      two[i] = two[i - 1];
  for (i = 0; i < N; i++)
    M[i][0] = a[i];
  for (j = 1; 1 << j <= N; j++)
    for (i = 0; i + (1 << j) - 1 < N; i++)
      M[i][j] = (M[i][j - 1] & M[i + (1 << (j - 1))][j - 1]);
  for (i = 0; i < N; i++) {
    b[i][0] = i;
    c[i][0] = a[i];
    len[i] = 1;
    t = range_and(i, N - 1);
    while (t != c[i][len[i] - 1]) {
      solve(i, b[i][len[i] - 1], N - 1, i, len[i]);
      len[i]++;
    }
  }
  for (i = 0; i < N; i++)
    a[i] = -1;
  for (i = size = 0; i < N; i++)
    for (j = 0; j < len[i]; j++) {
      idx1[size] = size;
      A[size] = i;
      B[size] = b[i][j];
      C[size++] = c[i][j];
    }
  sort_a2(C, idx1, size);
  sort_a2(X, idx2, Q);
  for (i = j = 0; i < Q; i++) {
    for (; j < size && C[j] <= X[i]; j++) {
      if (a[A[idx1[j]]] != -1)
        remove2(1, 0, N - 1, A[idx1[j]], a[A[idx1[j]]]);
      a[A[idx1[j]]] = B[idx1[j]];
      insert(1, 0, N - 1, A[idx1[j]], B[idx1[j]]);
    }
    query(1, 0, N - 1, L[idx2[i]], R[idx2[i]], &count, &sum);
    ans[idx2[i]] = count * (long long)(R[idx2[i]] + 1) - sum;
  }
  for (i = 0; i < Q; i++)
    printf("%lld\n", ans[i]);
  return 0;
}
void query(int v, int tl, int tr, int l, int r, int *c, long long *s) {
  int tm, c1, c2;
  long long s1, s2;
  if (tl > r || tr < l) {
    *c = *s = 0;
    return;
  }
  if (tl >= l && tr <= r) {
    query1(t[v], r, c, s);
    return;
  }
  tm = (tl + tr) / 2;
  query(2 * v, tl, tm, l, r, &c1, &s1);
  query(2 * v + 1, tm + 1, tr, l, r, &c2, &s2);
  *c = c1 + c2;
  *s = s1 + s2;
  return;
}
void insert(int v, int tl, int tr, int x, int y) {
  int tm;
  if (x >= tl && x <= tr)
    t[v] = insert1(t[v], y);
  if (tl != tr) {
    tm = (tl + tr) / 2;
    if (x <= tm)
      insert(2 * v, tl, tm, x, y);
    else
      insert(2 * v + 1, tm + 1, tr, x, y);
  }
  return;
}
void remove2(int v, int tl, int tr, int x, int y) {
  int tm;
  if (x >= tl && x <= tr)
    t[v] = remove1(t[v], y);
  if (tl != tr) {
    tm = (tl + tr) / 2;
    if (x <= tm)
      remove2(2 * v, tl, tm, x, y);
    else
      remove2(2 * v + 1, tm + 1, tr, x, y);
  }
  return;
}
int max(int x, int y) { return (x > y) ? x : y; }
int sizeOf(ct_node *root) { return (root) ? root->size : 0; }
int maxOf(ct_node *root) { return (root) ? root->max : 0; }
long long sumOf(ct_node *root) { return (root) ? root->sum : 0; }
void recalc(ct_node *root) {
  root->size = sizeOf(root->left) + sizeOf(root->right) + 1;
  root->max = max(maxOf(root->right), root->value);
  root->sum = sumOf(root->left) + sumOf(root->right) + root->value;
  return;
}
ct_node *merge(ct_node *L, ct_node *R) {
  if (!L)
    return R;
  if (!R)
    return L;
  if (L->priority > R->priority) {
    L->right = merge(L->right, R);
    recalc(L);
    return L;
  }
  R->left = merge(L, R->left);
  recalc(R);
  return R;
}
void split(int x, ct_node **L, ct_node **R, ct_node *root, int f) {
  if (!root) {
    *L = *R = NULL;
    return;
  }
  int curIndex;
  if (f)
    curIndex = root->value;
  else
    curIndex = sizeOf(root->left);
  ct_node *t;
  if (curIndex <= x) {
    if (f)
      split(x, &t, R, root->right, f);
    else
      split(x - curIndex - 1, &t, R, root->right, f);
    root->right = t;
    recalc(root);
    *L = root;
  } else {
    split(x, L, &t, root->left, f);
    root->left = t;
    recalc(root);
    *R = root;
  }
  return;
}
void query1(ct_node *root, int r, int *c, long long *s) {
  if (!root) {
    *c = *s = 0;
    return;
  }
  if (maxOf(root) <= r) {
    *c = sizeOf(root);
    *s = sumOf(root);
    return;
  }
  if (root->value > r) {
    query1(root->left, r, c, s);
    return;
  }
  query1(root->right, r, c, s);
  *c += sizeOf(root->left) + 1;
  *s += sumOf(root->left) + root->value;
  return;
}
ct_node *remove1(ct_node *root, int x) {
  ct_node *t1, *t2, *t3;
  split(x - 1, &t1, &t2, root, 1);
  split(0, &t2, &t3, t2, 0);
  return merge(t1, t3);
}
ct_node *insert1(ct_node *root, int x) {
  ct_node *t1, *t2, *t3;
  t2 = (ct_node *)malloc(sizeof(ct_node));
  t2->size = 1;
  t2->priority = rand();
  t2->value = t2->max = t2->sum = x;
  t2->left = t2->right = NULL;
  split(x - 1, &t1, &t3, root, 1);
  return merge(t1, merge(t2, t3));
}
void solve(int base, int i, int j, int idx1, int idx2) {
  int m, l, h, t;
  l = i;
  h = j;
  t = range_and(base, i);
  while (l < h) {
    m = (l + h) / 2;
    if (range_and(base, m) == t)
      l = m + 1;
    else
      h = m;
  }
  if (range_and(base, l) == t) {
    b[idx1][idx2] = l + 1;
    c[idx1][idx2] = range_and(base, l + 1);
  } else {
    b[idx1][idx2] = l;
    c[idx1][idx2] = range_and(base, l);
  }
  return;
}
int range_and(int i, int j) {
  return (M[i][two[j - i]] & M[j + 1 - (1 << two[j - i])][two[j - i]]);
}
void sort_a2(int *a, int *b, int size) {
  if (size < 2)
    return;
  int m = (size + 1) / 2, i;
  int *left_a, *left_b, *right_a, *right_b;
  left_a = (int *)malloc(m * sizeof(int));
  right_a = (int *)malloc((size - m) * sizeof(int));
  left_b = (int *)malloc(m * sizeof(int));
  right_b = (int *)malloc((size - m) * sizeof(int));
  for (i = 0; i < m; i++) {
    left_a[i] = a[i];
    left_b[i] = b[i];
  }
  for (i = 0; i < size - m; i++) {
    right_a[i] = a[i + m];
    right_b[i] = b[i + m];
  }
  sort_a2(left_a, left_b, m);
  sort_a2(right_a, right_b, size - m);
  merge2(a, left_a, right_a, b, left_b, right_b, m, size - m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int *a, int *left_a, int *right_a, int *b, int *left_b,
            int *right_b, int left_size, int right_size) {
  int i = 0, j = 0;
  while (i < left_size || j < right_size) {
    if (i == left_size) {
      a[i + j] = right_a[j];
      b[i + j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i + j] = left_a[i];
      b[i + j] = left_b[i];
      i++;
    } else if (left_a[i] <= right_a[j]) {
      a[i + j] = left_a[i];
      b[i + j] = left_b[i];
      i++;
    } else {
      a[i + j] = right_a[j];
      b[i + j] = right_b[j];
      j++;
    }
  }
  return;
}








View More Similar Problems

Lazy White Falcon

White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi

View Solution →

Ticket to Ride

Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o

View Solution →

Heavy Light White Falcon

Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim

View Solution →

Number Game on a Tree

Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy

View Solution →

Heavy Light 2 White Falcon

White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr

View Solution →

Library Query

A giant library has just been inaugurated this week. It can be modeled as a sequence of N consecutive shelves with each shelf having some number of books. Now, being the geek that you are, you thought of the following two queries which can be performed on these shelves. Change the number of books in one of the shelves. Obtain the number of books on the shelf having the kth rank within the ra

View Solution →