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

Castle on the Grid

You are given a square grid with some cells open (.) and some blocked (X). Your playing piece can move along any row or column until it reaches the edge of the grid or a blocked cell. Given a grid, a start and a goal, determine the minmum number of moves to get to the goal. Function Description Complete the minimumMoves function in the editor. minimumMoves has the following parameter(s):

View Solution →

Down to Zero II

You are given Q queries. Each query consists of a single number N. You can perform any of the 2 operations N on in each move: 1: If we take 2 integers a and b where , N = a * b , then we can change N = max( a, b ) 2: Decrease the value of N by 1. Determine the minimum number of moves required to reduce the value of N to 0. Input Format The first line contains the integer Q.

View Solution →

Truck Tour

Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0 to (N-1) (both inclusive). You have two pieces of information corresponding to each of the petrol pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no petr

View Solution →

Queries with Fixed Length

Consider an -integer sequence, . We perform a query on by using an integer, , to calculate the result of the following expression: In other words, if we let , then you need to calculate . Given and queries, return a list of answers to each query. Example The first query uses all of the subarrays of length : . The maxima of the subarrays are . The minimum of these is . The secon

View Solution →

QHEAP1

This question is designed to help you get a better understanding of basic heap operations. You will be given queries of types: " 1 v " - Add an element to the heap. " 2 v " - Delete the element from the heap. "3" - Print the minimum of all the elements in the heap. NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct element

View Solution →

Jesse and Cookies

Jesse loves cookies. He wants the sweetness of all his cookies to be greater than value K. To do this, Jesse repeatedly mixes two cookies with the least sweetness. He creates a special combined cookie with: sweetness Least sweet cookie 2nd least sweet cookie). He repeats this procedure until all the cookies in his collection have a sweetness > = K. You are given Jesse's cookies. Print t

View Solution →