PROBLEM LINK:
Setter: Kasra Mazaheri
Tester: Arshia Soltani
Editorialist: Kasra Mazaheri
DIFFICULTY:
Easy
PREREQUISITES:
Observation, Bit Manipulation
PROBLEM:
Define XPR(N) to be a pair (A,B) such that :

1 \le A \le B \le N

A \oplus B = N

The value of A is minimized.
If there is no valid pair for a number N, then XPR(N) = (1,1).
Define function F(N) to be the value of B in XPR(N). Function G(L,R) is then defined as \sum\limits_{i = L}^R {F(i)}. Calulate G(L, R) for Q queries.
QUICK EXPLANATION
 A and B should not have any common bits set.
 If N = 2^K for some 0 \le K, then XPR(N) = (1,1). Otherwise A = 2^{lb(N)} and B = N \oplus A where lb(N) is the lowest bit of N.
 G(L,R) can be rewritten as G(1,R)  G(1,L1).
 We can find the opposite summation, the values of A, much easier.
 Half of the numbers in [1, R] have lb(i) = 0. Half of the rest have lb(i) = 1. Half of the rest have lb(i) = 2 and so on.
EXPLANATION
It can be proven that A should have at least one common set bit with N. Otherwise B would be N  A and since 1 \le A, weâ€™ll have N < B. It can be further proved that A and B will not have any common set bits since if they had a common bit, we couldâ€™ve set it to zero in both of them, the value of A \oplus B would still equal N but the value of A decreases which is contradictory with the fact of it being minimal. Itâ€™s then easy to see that if N = 2^K there can be no valid pair and so XPR(N) = (1,1). Otherwise we can always pick A =2^{lb(N)}. This will always be the optimal answer since A should have at least one common bit with N.
We can rewrite G(L, R) as G(1, R)  G(1, L  1) in order to simplify our calculations.
For now weâ€™ll consider F(N) = 0 for all N = 2^K. Define F'(N) as the value of A in XPR(N). As a result of above observations, F(N) = N  F'(N). We can then define G'(R) as \sum\limits_{i = 1}^R {F'(i)}. As a result, G(1,R) = \frac{R \times (R+1)}{2}  G'(R). Now we only need to calculate G'(R).
So for each number from 1 to R we have to sum up the value of their lowest bit. This can be handled in the following way :
 There are \lceil{\frac{R}{2}}\rceil odd numbers that have their lb = 1.
 The even numbers contribute G'(\lfloor{\frac{R}{2}}\rfloor) \times 2 in total. This is because theyâ€™re the same as the numbers in [1,\lfloor{\frac{R}{2}}\rfloor], only multiplied by two. So the value of their lowest bit is also multiplied by two.
We can finally subtract the number of numbers in [1,R] that are equal to some 2^K. This will automatically handle the cases where F(N) = 1.
TIME COMPLEXITY
The time complexity is O(log(N)) per test case.
SOLUTIONS:
Setter's Solution
// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll Get(ll n)
{
ll tot = n * (n + 1) / 2;
for (ll b = 1; n; n >>= 1, b <<= 1)
tot = (n + 1) / 2 * b, tot ;
return (tot);
}
int main()
{
int q;
scanf("%d", &q);
for (; q; q )
{
int l, r;
scanf("%d%d", &l, &r);
printf("%lld\n", Get(r)  Get(l  1));
}
return 0;
}
Tester's Solution
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);}
#define ll long long
#define pb push_back
#define ld long double
#define mp make_pair
#define F first
#define S second
#define pii pair<ll,ll>
using namespace :: std;
//=======================================================================//
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=1;
bool is_neg=false;
while(true){
char g=getchar();
if(g==''){
assert(fi==1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g'0';
if(cnt==0){
fi=g'0';
}
cnt++;
assert(fi!=0  cnt==1);
assert(fi!=0  is_neg==false);
assert(!(cnt>19  ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
//=======================================================================//
const ll maxn=1e4+500;
ll get(ll n){
if(n==0){
return 0;
}
ll ans=(n+1)/2;
ans+=get(n/2)*2;
return(ans);
}
ll bit(ll n){
if(n==0){
return 0;
}
return bit(n/2)+1;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll q;
//cin>>q;
q=readIntLn(1,1e5);
while(q){
ll l,r;
//cin>>l>>r;
l=readIntSp(1,1e18);
r=readIntLn(l,1e18);
ll ans=(rl+1)*(r+l)/2;
ans=get(r)get(l1);
ans=bit(r)bit(l1);
cout<<ans<<endl;
}
}
Feel free to share your approach. As usual, suggestions are warmly welcomed.