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

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →