# HackerEarth A special sequence problem solution

In this HackerEarth A special sequence problem solution An array A contains integers with the following constraints:
1. A contains elements in sorted order.
2. Integer i occurs i x floor(sqrt(i)) + ceil(i/2) times in the array.
3. All elements are greater than or equal to 1.
You are given Q queries of type:

L R: Find the number of distinct values present in subarray A[L...R].

## HackerEarth A special sequence problem solution.

#include<bits/stdc++.h>
#define ll long double
using namespace std;
vector<long long>p;

signed main(){
long long sum = 0;
p.push_back(0);
for(ll i = 1 ; i <= 500000 ; i++){
long long val = i*floor(sqrt(i)) + ceil(i/2);
p.push_back(val);
}

int sz = p.size();

for(int i = 1 ; i < sz ; i++){
p[i] += p[i-1];
}

int q;
cin >> q;
assert(1 <= q and q <= 100000);
while(q--){
long long l, r;
cin >> l >> r;
assert(1 <= l and l <= r and r <= 10000000000000);
int s = 0;
int e = sz - 1;
int ans1 = -1;
while(s <= e){
int m = (s + e)/2;
if(p[m] < l){
ans1 = m;
s = m + 1;
}
else{
e = m - 1;
}
}

ans1++;

s = 0;
e = sz - 1;
int ans2 = -1;
while(s <= e){
int m = (s + e)/2;
if(p[m] < r){
ans2 = m;
s = m + 1;
}
else{
e = m - 1;
}
}
ans2++;

cout << (ans2 - ans1 + 1) << endl;
}
}

### Second solution

from bisect import bisect_left
from math import sqrt

import os
import sys
from io import BytesIO, IOBase

_str = str
str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

BUFSIZE = 8192

class FastIO(IOBase):
newlines = 0

def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None

while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0

while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1

def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))

input = lambda: sys.stdin.readline().rstrip("\r\n")

a = [2]
while a[-1] < 1e13:
i = len(a) + 1
a += [a[-1] + i * int(sqrt(i)) + (i + 1) // 2]
q = int(input())
while q > 0:
q -= 1
l, r = map(int, input().split())
print(bisect_left(a, r) - bisect_left(a, l) + 1)