HackerEarth Odd divisors problem solution

In this HackerEarth Odd divisors problem solution you are given a positive integer N.f(N) is the greatest odd divisor of N. Find the sum (f(1) + f(2) + ... + f(N))%M.

HackerEarth Odd divisors problem solution.

#include<bits/stdc++.h>
using namespace std;

int T;
long long N, M;

long long sqr(long long x){
x %= M;
return x * x % M;
}

int main(){

    cin >> T;
    while(T-->0){
        cin >> N >> M;
        long long ans = 0;
        while(N){
            ans = (ans + sqr(N / 2 + N % 2)) % M;
            N /= 2;
        }
        cout << ans << '\n';
    }

    return 0;
}

second solution

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
 
const int maxn = 2e5 + 14;
template<class cmp> struct LS{
    vector<int> v;
    vector<pair<int, int> > his;
    void add(int x){
    int p = lower_bound(v.begin(), v.end(), x, cmp()) - v.begin();
    if(p == v.size()){
        his.push_back({-1, 0});
        v.push_back(x);
    }
    else{
        his.push_back({p, v[p]});
        v[p] = x;
    }
    }
    void swap(LS<cmp> &od){  od.v.swap(v);  }
    void merge(LS<cmp> &od){
    if(od.v.size() > v.size())
        v.swap(od.v);
    for(int i = 0; i < od.v.size(); i++)
        if(cmp()(od.v[i], v[i]))  v[i] = od.v[i];
    }
    void undo(){
    assert(his.size());
    if(his.back().first == -1)
        v.pop_back();
    else
        v[his.back().first] = his.back().second;
    his.pop_back();
    }
};
typedef LS<less<int> > Lis;
int p[maxn];
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }
    Lis ans;
    for(int i = 0; i < n; i++)
        ans.add(p[n - i - 1]);
    cout << ans.v.size() << '\n';
}