Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/beautiful-segments/problem?isFullScreen=true
In this HackerRank in Data Structures -
You are given an array, A, consisting of N integers.
A segment, [l,r] is beautiful if and only if the bitwise AND of all numbers in A with indices in the inclusive range of [l,r] is not greater than X . In other words, segment [l,r] is beautiful if (Ai ^ Al+1 ^ .... ^ Ar) <= X. You must answer Q queries. Each query, Qj consists of 3 integers: Lj,Rj and Xj . The answer for each Qj is the number of beautiful segments [l,r] such that Lj <= 1 <= r <= Rj and X = Xj
Input Format
The first line contains two space-separated integers, N (the number of integers in A ) and Q (the number of queries).
The second line contains N space-separated integers, where the i**th integer denotes the i**th element of array A.
Each line j of the Q subsequent lines contains 3 space-separated integers, Lj,Rj and Xj respectively, describing query Qj.
Output Format
Print Q lines, where the j**th line contains the number of beautiful segments for query Qj.
Sample Input
5 3
1 2 7 3 4
1 5 3
2 4 6
3 5 2
Sample Output
13
5
2
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#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;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <utility>
#include <memory.h>
#include <iterator>
#include <iomanip>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int mod = (int)1e9 + 7;
const long long longMod = (long long)1e9 + 7LL;
const int N = 40500;
const int Q = 100500;
const int MAX_LOG = 18;
char mem[300000000];
int used_mem = 0;
void * operator new(size_t sz) {
void * res = mem + used_mem;
used_mem += sz;
return res;
}
void operator delete (void * p) {}
struct Event {
int x, y, tin, num;
Event () {};
Event (int x, int y, int tin, int num) : x(x), y(y), tin(tin), num(num) {};
bool operator < (const Event &e) const {
if (tin != e.tin) {
return tin > e.tin;
}
return num < e.num;
}
};
int modRand = (1 << 16);
struct node {
node * left, * right;
int key, prior;
int cnt;
int sum_val;
int sum_cnt;
node () {
left = right = NULL;
key = prior = sum_cnt = sum_val = 0;
}
node (node * left, node * right) {
this -> left = left;
this -> right = right;
key = prior = sum_cnt = sum_val = 0;
}
node (int key) {
cnt = 1;
left = right = NULL;
this -> key = key;
this -> sum_val = key;
this -> sum_cnt = 1;
prior = (((rand() % modRand) << 15) + rand() % modRand);
}
};
void add(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
if (x < 0) {
x += mod;
}
}
int get_cnt(node * ver) {
if (!ver) {
return 0;
}
return ver -> sum_cnt;
}
int get_sum(node * ver) {
if (!ver) {
return 0;
}
return ver -> sum_val;
}
void update_cnt(node * ver) {
if (!ver) return;
ver -> sum_cnt = ver -> cnt + get_cnt(ver -> left) + get_cnt(ver -> right);
}
void update_sum(node * ver) {
if (!ver) return;
ver -> sum_val = ver -> key * ver -> cnt;
add(ver -> sum_val, get_sum(ver -> left));
add(ver -> sum_val, get_sum(ver -> right));
}
void split(node * ver, node * &left, node * &right, int key) {
if (!ver) {
left = right = NULL;
return;
}
if (ver -> key < = key) {
split(ver -> right, ver -> right, right, key);
left = ver;
} else {
split(ver -> left, left, ver -> left, key);
right = ver;
}
update_cnt(left);
update_cnt(right);
update_sum(left);
update_sum(right);
}
void merge(node * &ver, node * left, node * right) {
if (!left || !right) {
ver = left;
if (!ver) {
ver = right;
}
update_sum(ver);
update_cnt(ver);
return;
}
if (left -> prior > right -> prior) {
merge(left -> right, left -> right, right);
ver = left;
} else {
merge(right -> left, left, right -> left);
ver = right;
}
update_sum(ver);
update_cnt(ver);
}
node * contains(node * ver, int key) {
if (!ver) return NULL;
if (ver -> key == key) return ver;
if (key > ver -> key) {
return contains(ver -> right, key);
} else {
return contains(ver -> left, key);
}
}
void fix(node * ver, int key) {
if (!ver) return;
if (ver -> key == key) {
update_cnt(ver);
update_sum(ver);
}
if (key > ver -> key) {
fix(ver -> right, key);
update_sum(ver);
update_cnt(ver);
} else {
fix(ver -> left, key);
update_cnt(ver);
update_sum(ver);
}
}
void insert(node * &ver, node * what) {
if (!ver) {
ver = what;
return;
}
if (what -> prior > ver -> prior) {
split(ver, what -> left, what -> right, what -> key);
ver = what;
update_sum(ver);
update_cnt(ver);
return;
}
if (what -> key > ver -> key) {
insert(ver -> right, what);
} else {
insert(ver -> left, what);
}
update_sum(ver);
update_cnt(ver);
}
int n, q;
int a[N];
int T[N];
int numOfNode[N];
int parent[4 * N];
int two[22];
int answer[Q];
int f_size = 0;
int psum[MAX_LOG][N];
node * tree[4 * N];
vector < pair<int, int> > have[N];
void build(int ver, int l, int r) {
parent[ver] = (ver / 2);
if (l == r) {
numOfNode[l] = ver;
return;
}
int mid = (l + r) >> 1;
build(ver + ver, l, mid);
build(ver + ver + 1, mid + 1, r);
}
node * temp;
pair < int, int> CCC;
void setValue(int pos, int val) {
int ver = numOfNode[pos];
while (ver > 0) {
temp = contains(tree[ver], val);
if (temp == NULL) {
insert(tree[ver], new node(val));
} else {
add(temp -> sum_val, val);
temp -> sum_cnt++;
temp -> cnt++;
fix(tree[ver], val);
}
ver = parent[ver];
}
}
void deleteValue(int pos, int val) {
int ver = numOfNode[pos];
while (ver > 0) {
temp = contains(tree[ver], val);
if (temp == NULL) {
puts("FAIL");
exit(228);
} else {
add(temp -> sum_val, -val);
temp -> sum_cnt--;
temp -> cnt--;
fix(tree[ver], val);
}
ver = parent[ver];
}
}
pair < int, int> make_go(int pos, int le, int ch) {
int ri, mid, its;
ri = n;
while (le < ri) {
mid = (le + ri) >> 1;
its = 0;
for (int i = 0; i < = 17; i++) {
if (psum[i][mid] - psum[i][pos - 1] == mid - pos + 1) {
its += two[i];
}
}
if (its == ch) {
le = mid + 1;
} else {
ri = mid;
}
}
le = min(le, n);
its = 0;
for (int i = 0; i < = 17; i++) {
if (psum[i][le] - psum[i][pos - 1] == le - pos + 1) {
its += two[i];
}
}
if (its == ch) {
return mp(n + 1, 0);
} else {
return mp(le, its);
}
}
int L, R;
node * t1, * t2;
void go(int ver, int l, int r, int pl, int pr) {
if (pl > pr) return;
if (l == pl && r == pr) {
split(tree[ver], t1, t2, R);
CCC.F += t1 -> sum_cnt;
add(CCC.S, t1 -> sum_val);
merge(tree[ver], t1, t2);
return;
}
int mid = (l + r) >> 1;
go(ver + ver, l, mid, pl, min(pr, mid));
go(ver + ver + 1, mid + 1, r, max(pl, mid + 1), pr);
}
void make_query(int l, int r) {
L = l;
R = r;
go(1, 1, n, l, r);
}
int main() {
//freopen("input.txt","r",stdin);
//freopen("o1","w",stdout);
//double h = clock();
scanf("%d%d", &n, &q);
for (int i = 0; i < 17; i++) {
psum[i][0] = 0;
two[i] = (1 << i);
}
for (int i = 1; i < = n; i++) {
scanf("%d", &a[i]);
for (int j = 0; j < = 17; j++) {
psum[j][i] = psum[j][i - 1];
if ((a[i] & (1 << j)) != 0) {
++psum[j][i];
}
}
}
build(1, 1, n);
pair < int, int> now, then;
for (int i = 1; i < = n; i++) {
now = mp(i, a[i]);
have[i].pb(mp(i, a[i]));
while (true) {
then = make_go(i, now.F, now.S);
have[i].pb(mp(then.F, then.S));
if (then.F == n + 1) {
break;
}
now = then;
}
}
pair < int, pair<int, int> > data;
priority_queue< pair<int, pair<int, int> > > pq;
int e_size = 0;
int le, ri, val;
vector < Event> events;
for (int i = 1; i < = q; i++) {
scanf("%d%d%d", &le, &ri, &val);
events.pb(Event(le, ri, val, i));
}
for (int i = 1; i < = n; i++) {
T[i] = i;
setValue(i, i);
pq.push(mp(a[i], mp(0, i)));
}
sort(events.begin(), events.end());
for (int i = 0; i < q; i++) {
val = events[i].tin;
while (true) {
data = pq.top();
if (data.F < = val) {
break;
}
pq.pop();
le = have[data.S.S][data.S.F].F;
deleteValue(data.S.S, T[data.S.S]);
while (true) {
data.S.F++;
if (have[data.S.S][data.S.F].S < = val) {
data.F = have[data.S.S][data.S.F].S;
break;
} else continue;
}
le = have[data.S.S][data.S.F].F;
T[data.S.S] = le;
setValue(data.S.S, T[data.S.S]);
pq.push(data);
}
val = events[i].num;
CCC = mp(0, 0);
make_query(events[i].x, events[i].y);
answer[val] = ((CCC.F * (events[i].y + 1) - CCC.S));
}
for (int i = 1; i < = q; i++) {
printf("%d\n", answer[i]);
}
//cout << f_size << endl;
//cout << (clock() - h) / CLOCKS_PER_SEC << "sec" << endl;
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
static class Segment {
int left;
int right;
int limit;
int count = 0;
public Segment(int left, int right, int limit) {
this.left = left;
this.right = right;
this.limit = limit;
}
}
static class Struct implements Comparable < Struct> {
int key;
int dat;
int count;
public Struct(int key, int dat, int count) {
this.key = key;
this.dat = dat;
this.count = count;
}
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[][] biggerKeys;
int columnBlocks;
Struct[] sortedKeys;
int index;
public Counter(int colNum, Struct[] sortedKeys) {
this.columnBlocks = ((int) (Math.log(colNum) / Math.log(2))) + 1;
this.biggerKeys = new int[colNum][this.columnBlocks];
this.sortedKeys = sortedKeys;
this.index = 0;
}
public void countDownTo(int limit) {
while (sortedKeys[index].key > limit) {
updateCount(sortedKeys[index].count, sortedKeys[index].dat);
index++;
}
}
public void updateCount(int countOfKey, int rowIdx) {
for (int row = 0; row < columnBlocks; row++) {
biggerKeys[rowIdx][row] += countOfKey;
rowIdx /= 2;
}
}
public int getBiggersKeysToColumn(int rowIdx) {
int biggers = 0;
int row = 0;
while (rowIdx > 0) {
if (rowIdx % 2 != 0) {
biggers += biggerKeys[rowIdx - 1][row];
}
rowIdx /= 2;
row++;
}
return biggers;
}
}
static final int MINUS_KEY = -1;
static final int MAX_ROW = 19;
static class CompactMatrix {
int[][] keys, counts;
int numOfKeys;
private CompactMatrix(int[][] keys, int[][] counts, int n) {
this.keys = keys;
this.counts = counts;
this.numOfKeys = n;
}
public Struct[] getSortedKeys() {
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++;
}
}
sortedKeys[numOfKeys] = new Struct(MINUS_KEY, -1, -1);
Arrays.sort(sortedKeys);
return sortedKeys;
}
public Counter createCounter() {
return new Counter(keys.length, getSortedKeys());
}
public int getKeyUsingLeft(int left, int right) {
int maxRow = right - left;
int idx = left;
int rowInMatrix = 0;
int row = counts[idx][rowInMatrix] - 1;
while (row < maxRow) {
rowInMatrix++;
row += counts[idx][rowInMatrix];
}
return keys[idx][rowInMatrix];
}
}
public static CompactMatrix createLeft(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;
Arrays.fill(keys[idx], 1, MAX_ROW, MINUS_KEY);
}
int numOfKeys = n;
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++;
keys[idx][row] = nextValue;
counts[idx][row] = counts[preIdx][preRow];
numOfKeys++;
}
preRow++;
} while (keys[preIdx][preRow] != -1);
}
return new CompactMatrix(keys, counts, numOfKeys);
}
public static CompactMatrix createRight(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;
Arrays.fill(keys[idx], 1, MAX_ROW, MINUS_KEY);
}
int numOfKeys = n;
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++;
keys[idx][row] = nextValue;
counts[idx][row] = counts[preIdx][preRow];
numOfKeys++;
}
preRow++;
} while (keys[preIdx][preRow] != -1);
}
return new CompactMatrix(keys, counts, numOfKeys);
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int q = Integer.parseInt(st.nextToken());
int[] a = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int item = Integer.parseInt(st.nextToken());
a[i] = item;
}
boolean b = st.countTokens() > 1;
Segment[] segments = new Segment[q];
Struct[] sortedLimits = new Struct[q];
for (int i = 0; i < q; i++) {
if (!b) {
st = new StringTokenizer(br.readLine());
}
b = false;
int l = Integer.parseInt(st.nextToken()) - 1;
int r = Integer.parseInt(st.nextToken()) - 1;
int x = Integer.parseInt(st.nextToken());
segments[i] = new Segment(l, r, x);
sortedLimits[i] = new Struct(x, i);
}
Arrays.sort(sortedLimits);
CompactMatrix leftMatrix = createLeft(n, a);
CompactMatrix rightMatrix = createRight(n, a);
Counter leftCounter = leftMatrix.createCounter();
Counter rightCounter = rightMatrix.createCounter();
for (int i = 0; i < q; i++) {
int segId = sortedLimits[i].dat;
int limit = segments[segId].limit;
int left = segments[segId].left;
int right = segments[segId].right;
int minKey = leftMatrix.getKeyUsingLeft(left, right);
if (minKey < = limit) {
leftCounter.countDownTo(limit);
rightCounter.countDownTo(limit);
int biggers = rightCounter.getBiggersKeysToColumn(right + 1)
- leftCounter.getBiggersKeysToColumn(left);
int len = right - left + 1;
segments[segId].count = len * (len + 1) / 2 - biggers;
}
}
for (int i = 0; i < q; i++) {
bw.append(segments[i].count + "\n");
}
bw.newLine();
bw.close();
br.close();
}
}