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.

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("%d\n", 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("%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;
}