# 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 :

```                            ```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.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 {
getCountsForTests();
printResults();
}

throws Exception {
StringBuilder builder = new StringBuilder(100000);
String aux = "";
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;
}```
```

## 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):

## 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.

## 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

## 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

## 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