find the groups in which you and your crush are placed .

use ceil function .

As You want that you and your crush will be in same group , find out Group number for both $$$G_a$$$ = ceil(a/x) (group number where you are placed) , $$$G_b$$$ = ceil(b/x) (group number where your crush is placed) . there are total of n diffrent value of x(group size) which is equiprobable. Hence Probability = P/Q . P = Number of group size's in which $$$G_a == G_b$$$ , Q = n .

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

#define int long long
#define pb push_back
#define ppb pop_back
#define MOD 998244353

const int N=1e5;

int binexp(int a, int b) {
    int res = 1;
    while (b > 0) {
        if(b&1)
        res = ((res%MOD)*(a%MOD))%MOD;
        a = ((a%MOD)*(a%MOD))%MOD;
        b >>= 1;
    }
    return res;
}

void solve(){
    int n;
    string a,b;
    cin >> n >> a >> b;
    int an = stoi(a.substr(7,3));
    int bn = stoi(b.substr(7,3));
    int ans = 0;
    for(int i=1;i<=n;i++){
        if((an-1)/i == (bn-1)/i){
            ans++;
        }
    }
    
    ans *= binexp(n,MOD-2);
    ans %= MOD;

    cout << ans << endl;

}

int32_t main()
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifndef ONLINE_JUDGE
    freopen("test0.in", "r", stdin);
    freopen("test0.out", "w", stdout);
#endif

    int t = 1;
    cin >> t;
    while (t--)
        solve();
        
    return 0;
}

Pbds

Let Array $$$B$$$ store indices of an element x in the array.
For two indices i and j where i < j, if A[i..j] is good, then (j-i+1)/(A[j]-A[i]+1)>=K/1000.
1000*j-A[j]>=1000*i-A[i]+K-1
For each index we can find the number of indices which make a good subarray by using pbds or segment tree.

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define int long long
#define ll __int128
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<long double,int>, null_type,
      less<pair<long double,int>>, rb_tree_tag,
      tree_order_statistics_node_update>
      Pbds;


const char nl = '\n';
bitset<1000010> iscomp;
int highest[1000010];
void sieve()
{
    for (int i = 2; i < 1000010; i++)
    {
        if (!iscomp[i])
        {
            highest[i]=i;
            for (int j = i * i; j < 1000010; j += i)
            {
                highest[j]=i;
                iscomp[j] = 1;
            }
        }
    }
}
int n,k;
void yes() { cout << "Yes" << endl; }
void no() { cout << "No" << endl; }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
void solve(int testcase)
{
    cin>>n>>k;
    vector<int>a(n);
    for(int &it:a)cin>>it;
    map<int,vector<int>>m;
    for(int i=0;i<n;i++){
        m[a[i]].push_back(i);
    }
    long double K=k;
    for(auto &it:m){
        cout<<it.first<<' ';
        if(it.second.size()==1){
            cout<<0<<endl;continue;
        }
        Pbds s;
        s.insert({K-1000-K*it.second[0],0});
        int ans=0;
        for(int i=1;i<it.second.size();i++){
            int p=s.order_of_key({i*1000-K*it.second[i],INT_MAX});
            ans+=p;
            s.insert({K-1000-K*it.second[i]+i*1000,i});
        }
        cout<<ans<<' ';
        cout<<endl;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //sieve();
    int t = 1;
    //cin >> t;
    for (int p = 1; p <= t; p++)
    {
        solve(p);
    }
}

Is there any benefit of taking a subarray which contains more than 2 occurence of val?

Let us prove that the answer is an subarray which contains only two occurence of val, where the first and last element are val.
Firstly, any subarray which does not contain val as first/last element is not optimal as this subarray can be trimmed to such a state which improves the ratio.
Let $$$a$$$ be the smallest distance between any two occurrence of val in the array. The answer for this subarray is 2/(a+2).
It is easy to see that adding any occurence at a distance >$$$a$$$ can never give better answer.
Now it is needed to prove that adding more occurence at distance $$$a$$$ also does not improve the answer.
Let us add y occurence of val at a distance $$$a$$$.
The new ratio is (2 + y ) / (y*a + y + 2).
If this ratio is better, (2 + y ) / (y*a + y + 2 + a) > 2 / a+2
2*a + y*a + 2*y + 4 > 2*y*a + 2y + 4 + 2*a
0 > y*a
0 > y
By contradiction, it is shown that we must not add any more occurrences.

//Author Solution
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
 ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
map<int,set<int>>m;
map<int,set<pair<int,int>>>track;
int a[n+1];
for(int i=0;i<n;i++)
{
    int x;
    cin>>x;
    a[i]=x;
    m[x].insert(i);
}
for(auto &it:m)
{
    int temp=-1;
    for(auto &trav:it.second)
    {
        if(temp==-1)
        temp=trav;
        else
        {
            track[it.first].insert({trav-temp,temp});
            temp=trav;
        }
    }
}
int q;
cin>>q;
while(q--)
{
    int check;
    cin>>check;
    if(check==1)
    {
        int x;
        cin>>x;
        if(track[x].empty())
        {
            cout<<-1<<'\n';
            continue;
        }
        auto it=*track[x].begin();
        cout<<it.second<<" "<<it.second+it.first<<endl;
    }
    else
    {
        int indx,y;
        cin>>indx>>y;
        int temp=a[indx];
        auto it=m[temp].find(indx);
        int left=-1,right=-1;
        if(it!=m[temp].begin())
        {
            auto it1=it;
            it1--;
            left=(*it1);
            track[temp].erase(track[temp].find({((*it)-(*it1)),(*it1)}));
        }
        auto it1=it;
        it1++;
        if(it1!=m[temp].end())
        {
            right=(*it1);
            track[temp].erase(track[temp].find({((*it1)-(*it)),(*it)}));
              
        }
        if(left!=-1&&right!=-1)
        {
            track[temp].insert({right-left,left});
        }
        m[temp].erase(it);
        m[y].insert(indx);
        
        it=m[y].find(indx);
        left=-1,right=-1;
        if(it!=m[y].begin())
        {
            auto it1=it;
            it1--;
            track[y].insert({((*it)-(*it1)),(*it1)});
            left=(*it1);
        }
        it1=it;
        it1++;
        if(it1!=m[y].end())
        {
              track[y].insert({((*it1)-(*it)),(*it)});
              right=(*it1);
        }
        a[indx]=y;
        if(left!=-1&&right!=-1)
        {
            track[y].erase(track[y].find({right-left,left}));
        }
    }
}
 return 0;
}

//Another solution
#include<bits/stdc++.h>
using namespace std;
vector<int>a;
unordered_map<int,set<int>>m1;
unordered_map<int,multiset<pair<int,pair<int,int>>>>m2;
void query1(int value){
    if(m2.count(value)==0){
        cout<<-1<<endl;return;
    }
    cout<<m2[value].begin()->second.first<<' '<<m2[value].begin()->second.second<<endl;
}
 
void query2(int x,int y){
    auto it=m1[a[x]].find(x);auto it1=it,it2=it;
    if(it1!=m1[a[x]].begin()){
        it1--;
        m2[a[x]].erase({*it-*it1,{*it1,*it}});
    }
    if(it2!=(--m1[a[x]].end())){
        it2++;
        m2[a[x]].erase({*it2-*it,{*it,*it2}});
    }
    if(it2!=it&&it1!=it)
    {
        m2[a[x]].insert({*it2-*it1,{*it1,*it2}});
    }
    m1[a[x]].erase(it);
    if(m1[a[x]].size()==0)m1.erase(a[x]);
    if(m2[a[x]].size()==0)m2.erase(a[x]);
    a[x]=y;
    m1[y].insert(x);
    it=m1[y].find(x);it1=it,it2=it;
    if(it1!=m1[y].begin()){
        it1--;
        m2[a[x]].insert({*it-*it1,{*it1,*it}});
    }
    if(it2!=(--m1[y].end())){
        it2++;
        m2[a[x]].insert({*it2-*it,{*it,*it2}});
    }
     if(it2!=it&&it1!=it)
    {
        m2[a[x]].erase({*it2-*it1,{*it1,*it2}});
    }
    
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    a.resize(n);
    for(int &it:a)cin>>it;
    for(int i=0;i<n;i++){
        m1[a[i]].insert(i);
    }
    for(auto &it:m1){
        multiset<pair<int,pair<int,int>>>&itr=m2[it.first];
        vector<int>temp(it.second.begin(),it.second.end());
        for(int i=0;i+1<temp.size();i++){
            itr.insert({temp[i+1]-temp[i],{temp[i],temp[i+1]}});
        }
    }
    int q;cin>>q;
    for(int i=0;i<q;i++){
        int type;cin>>type;
        if(type==1){
            int x;cin>>x;
            query1(x);
        }else{
            int x,y;cin>>x>>y;
            query2(x,y);
        }
    }
}

Try doing something with the lowest common ancestor of $$$i$$$ and $$$i + 1$$$.

Prefix sums on tree?

Since we have to answer the problem offline, let's try to do something similar to difference arrays.

First root the tree on an arbitrary vertex — say $$$1$$$.

Say the lowest common ancestor of $$$i$$$ and $$$i + 1$$$ be $$$LCA$$$. We will add $$$1$$$ to $$$score[parent_i]$$$ and $$$score[i + 1]$$$, and subtract $$$1$$$ from $$$score[LCA]$$$ and $$$score[parent_{LCA}]$$$. A Now if we add up scores going from bottom to top, we will get the number of times each vertex is visited.

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

#define int long long

// LCA code source - usaco.guide
int depth[200010];
int up[200010][20];
int score[200010];
vector<int> adj[200010];

void dfs(int v) {
    for(int i = 1; i < 20; i++) { up[v][i] = up[up[v][i - 1]][i - 1]; }
    for (int x : adj[v]) {
        if (x != up[v][0]) {
            depth[x] = depth[up[x][0] = v] + 1;
            dfs(x);
        }
    }
}

int jump(int x, int d) {
    for(int i = 0; i < 20; i++) {
        if ((d >> i) & 1) x = up[x][i];
    }
    return x;
}

int LCA(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);

    a = jump(a, depth[a] - depth[b]);
    if (a == b) return a;

    for(int i = 19; i >= 0; i--) {
        int aT = up[a][i], bT = up[b][i];
        if (aT != bT) a = aT, b = bT;
    }

    return up[a][0];
}

void clear(int n) {
    for(int i = 0; i < n; i++) {
        score[i] = 0;
        depth[i] = 0;
        adj[i].clear();
        for(int j = 0; j < 20; j++) 
            up[i][j] = 0;
    }   
}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--) {
        int n; cin >> n;
        clear(n + 5);

        for(int i = 0; i < n - 1; i++) {
            int a, b; cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        dfs(1);

        for(int i = 1; i < n; i++) {
            int par = LCA(i, i + 1);
            score[up[i][0]]++, score[i + 1]++;
            score[par]--, score[up[par][0]]--;
        }
        
        vector<pair<int,int>> vp;
        for(int i = 2; i <= n; i++) {
            vp.push_back({-depth[i], i});
        }
        sort(vp.begin(), vp.end());

        for(int i = 0; i < vp.size(); i++) {
            score[up[vp[i].second][0]] += score[vp[i].second];
        }

        score[1]++; // initial stand
        for(int i = 1; i <= n; i++) cout << score[i] << " ";
        cout << "\n";
    }
    return 0;
}