Interesting Problem ! any better solution other than O(q*{n^2})

1

Interesting Task
can anyone help me out with this? any better solution other than O(q*{n^2})

2

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

#define int long long int
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define testCases int t;cin>>t;while(t–)
#define mod 1000000007
#define br “\n”

void solve()
{
int n,q; cin>>n>>q;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int count=0;
for(int i=0;i<q;i++)
{ count=0;
int x,y; cin>>x>>y;
vector v;
for(int j=x-1;j<=y-1;j++)
{
v.push_back(a[j]);

    }
    
    for(int l=0;l<((y-x)+1);l++)
    {
        for(int m=l+1;m<((y-x)+1);m++)
        {
            if(v[l]>v[m]) count++;
        }
    }
    cout<<count<<endl;

}

}

int32_t main()
{
fastIO
// testCases
solve();
}

// 5,2 3,3 3,3 2,3

3

This is not an optimized Solution.

4

It’s pretty easy to solve it you know how to solve this problem for one query in \mathcal{O}(N \log N) time , just process the queries offline after sorting them with ending indices of each range. Do let me know if you couldn’t figure it out.

5

You wud have to use MO’s Algo for this, You can process initial query in O(NlogN) time because its just counting number of inversions, u can refer gfg for the nlogn algo for counting it.

6

Here’s an O((n + m) sqrt n log n)-time algorithm. That’s probably not good enough to pass, but something seems not quite right here – the usual programming contest tricks don’t work. (O((n + m) sqrt n) might be achievable with more care.)

Divide the input array into sqrt n subarrays of length sqrt n, called blocks. Using an incremental algorithm for counting inversions, for each pair consisting of a block and a prefix of the array, compute the number of inversions where the first element comes from the former and the second element comes from the latter. (O(n sqrt n log n)) Do the same for prefix-block pairs.

For each input range, decompose it into the union of some blocks (blocked elements) and less than 2 sqrt n elements (unblocked elements). Using the precomputed results and inclusion-exclusion, find the number of inversions in the range where at least one element is blocked. (O(sqrt n)) Compute and add to this quantity the number of inversions in the range involving two unblocked elements. (O(sqrt n log n))

7

For one query sort the array and update the index of smaller value then through the range query we can get the no .of smallest element right to index “i” but how to do for “q” queries ??