HackerRank Beautiful Segments problem solution

In this HackerRank Beautiful Segments problem solution, you are given an array consisting of N integers. we need to find and print the lines where the line contains the number of beautiful segments for the query.

HackerRank Beautiful Segments problem solution

Problem solution in 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();
  }

}

Problem solution in 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("%dn", answer[i]);
    }
    //cout << f_size << endl;
    //cout << (clock() - h) / CLOCKS_PER_SEC << "sec" << endl;
    return 0;
}

Problem solution in 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("%lldn",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;
}