#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> a(n);
                vector<int> b(n);

                for (int i = 0; i < n; i++) cin >> a[i];
                for (int i = 0; i < n; i++) cin >> b[i];

                vector<int> ord(n);
                iota(ord.begin(), ord.end(), 0);
                sort(ord.begin(), ord.end(), [&](int x, int y) {
                        if (b[x] == b[y]) return a[x] > a[y];
                        return b[x] == 1;
                });

                int ans = a[0] * b[0];
                int suma = 0, sumb = 0;

                for (int i = 0; i < n; i++) {
                        suma += a[ord[i]];
                        sumb += b[ord[i]];

                        ans = max(ans, suma * sumb);
                        ans = max(ans, a[i] * b[i]);
                }

                cout << ans << '\n';
        }

        return 0;
}

Consider greedy algorithm.

When all $$$b_i(1 \leq i \leq n)=-1$$$,obviously,the answer is $$$-min(a_i)$$$.

Otherwise,we choose all tuples which's $$$b_i=1$$$ firstly.Then choose tuples in descending order of $$$a_i$$$ value which's $$$b_i=-1$$$.The answer is the maximum in this process.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n;
                cin >> n;

                vector<int> ca(2 * n);
                vector<int> cb(2 * n);

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        ca[x] += 1;
                }

                for (int i = 0; i < n; i++) {
                        int x;
                        cin >> x;
                        --x;

                        cb[x] += 1;
                }

                bool ok = 1;

                for (int i = 0; i < 2 * n; i++) {
                        if (ca[i] + cb[i] > n) {
                                ok = 0;
                        }
                }

                cout << (ok ? "YES" : "NO") << '\n';
        }
        
        return 0;
}

Note $$$k$$$ is the number with the highest sum of occurrences in $$$s$$$ and $$$t$$$.The answer is "YES" iff $$$occurrences(k) \leq n$$$.

If $$$occurrences(k) > n$$$,it means the total of numbers that are not $$$k$$$ is less than $$$n$$$.Obviously the answer is "NO".

Otherwise,we can use Mathematical induction to prove that there is a solution:

• 1.For two empty sets $$$s$$$,$$$t$$$,$$$occurrences(k) \leq n$$$ holds;

• 2.Assume for two empty sets $$$s$$$,$$$t$$$ if size $$$n$$$,$$$occurrences(k) \leq n$$$ holds.We do remove a $$$k$$$ from one set and remove a number which is not $$$k$$$ from another set.After that,the size becomes $$$n-1$$$,and $$$occurrences(k) \leq n-1$$$ holds.

#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
*/
using namespace std;
#define fastio  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define pb push_back
#define PI acos(-1)
#define pii pair<int,int>
#define endl "\n"
#define all(a) a.begin(),a.end()
#define len(s) (int)s.size()
#define F first
#define S second
const int mod=1e9+7;
int dp[20001][101][101];
int a[101];
const int add=10000;
const int L=-10000;
const int R=10000;
int f(int sum,int l,int r)
{
	//count number of non-empty subsequence of subarray [l,r] 
	//with adding=sum
	if( !(sum>=L and sum<=R))
		return 0;
	
	if(l==r)
	{

		if(sum==a[l])
			return 1;
		return 0;
	}
	if(dp[sum+add][l][r]!=-1)
		return dp[sum+add][l][r];
	int ans1=f(sum,l,r-1);
	int ans2=f(sum,l+1,r);
	int rem=0;
	if(l+1<=r-1)
		rem=f(sum,l+1,r-1);
	int ans3=0;
	if(l+1<=r-1)
		ans3=f(sum-a[l]-a[r],l+1,r-1)+(sum==(a[l]+a[r]));
	else
		ans3=(sum==(a[l]+a[r]));
	
	return dp[sum+add][l][r]=(((ans1+ans2)%mod-rem+mod)%mod+ans3)%mod;
}
void solve()
{
	int n,x;
	cin>>n>>x;
	memset(dp,-1,sizeof(dp));
	for(int i=1;i<=n;i++)
		cin>>a[i];
	if(n<3)
	{
		cout<<0;
		return ;
	}
	else
	{
		sort(a+1,a+n+1);
		for(int i=1;i<=n;i++)
			a[i]-=x;
		int ans=0;
	
		for(int i=1;i<=n;i++)
		{
			for(int j=i+2;j<=n;j++)
			{
				ans+=f(0,i+1,j-1);
				ans%=mod;
			}
		}
		cout<<ans;
	}
}
signed main()
{
fastio
int TestCases=1;
//cin>>TestCases;
while(TestCases--)
{
solve();
cout<<endl;
}
}

Firstly,we substract all $$$a_i$$$ by $$$x$$$.Then the problem is equivent to count the number of subsequences which's sum is $$$0$$$.

Consider sort the array and do DP.Note $$$dp_{l,r,s}$$$ as the number of subsequences with $$$a_l$$$ as the head, $$$a_r$$$ as the tail, and $$$s$$$ as the sum.

For $$$dp_{l,r,0}(2\leq l \leq r \leq n-1)$$$,it's contribution is $$$dp_{l,r,0}*(l-1)*(n-r)$$$.

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        vector<int> fac(2222222);

        fac[0] = 1;
        for (int i = 1; i <= 2000000; i++) {
                fac[i] = (fac[i - 1] * i) % MOD;
        }

        auto binpow = [&](int x, int y) {
                int res = 1;

                while (y > 0) {
                        if (y & 1) (res *= x) %= MOD;

                        (x *= x) %= MOD;
                        y >>= 1;
                }

                return res;
        };

        vector<int> inv(2222222);

        inv[2000000] = binpow(fac[2000000], MOD - 2);
        for (int i = 1999999; i >= 0; i--) {
                inv[i] = (inv[i + 1] * (i + 1)) % MOD;
        }

        auto comb = [&](int n, int r) {
                if (n < r) {
                        cout << "hi\n";
                        exit(0);
                }
                return fac[n] * inv[r] % MOD * inv[n - r] % MOD;
        };

        int t;
        cin >> t;

        while (t --> 0) {
                int n, m;
                cin >> n >> m;
                // general case: a1 + a2 + a3 + .. + an = m -> C(m - 1, n - 1)
                int ans = comb(m - 1, n - 1);

                if (n - 1 <= m - (m + 1) / 2) {
                        ans -= n * comb(m - (m + 1) / 2 - 1 + 1, n - 1 - 1 + 1);
                }

                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        
        return 0;
}

As we all know,the sum of the two sides of a triangle is greater than the third side.Similarly,we can infer condition $$$3$$$ is equviant to $$$max(a_i)< \lceil m/2 \rceil$$$.

What's the number of arrays satisfying the following condition?

• 1.All $$$a_i$$$ are positive integers;

• 2.$$$\Sigma a_i=m$$$.

The answer is $$$C^{m-1}_{n-1}$$$.It's a classic problem.

$$$C^i_j+C^{i-1}_j+...+C^j_j=C^{i+1}_{j+1}$$$.

We find it's easier to calculate bad arrays.When $$$max(a_i)=\lceil m/2 \rceil,\lceil m/2 \rceil+1,...$$$,$$$a$$$ is a bad array.

The total of bad array is $$$n*(C^{m-\lceil m/2 \rceil}_{n-2}+C^{m- \lceil m/2 \rceil-1}_{n-2}+...)=n*C^{\lfloor m/2 \rfloor}_{n-1}$$$.

The final answer is $$$C^{m-1}_{n-1}-n*C^{\lfloor m/2 \rfloor}_{n-1}$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int INFF = 1e18;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int t;
        cin >> t;

        while (t --> 0) {
                int n, m, s;
                cin >> n >> m >> s;

                set<pair<int, int>> st;
                st.insert({s, 0});

                for (int i = 0; i < m; i++) {
                        int l, r;
                        cin >> l >> r;

                        vector<pair<int, int>> del;
                        int mnl = INFF, mnr = INFF;
                        for (auto it = st.lower_bound({l, 0}); it != st.end(); it++) {
                                if (it->fi > r) break;

                                if (l - 1 >= 1) {
                                        mnl = min(mnl, it->se + it->fi - l + 1);
                                }

                                if (r + 1 <= n) {
                                        mnr = min(mnr, it->se + r + 1 - it->fi);
                                }

                                del.push_back(*it);
                        }
                        
                        for (auto p : del) st.erase(p);

                        auto it = st.lower_bound({l - 1, 0});
                        if (it != st.end() && it->fi == l - 1) {
                                mnl = min(mnl, it->se);
                                st.erase(it);
                        }

                        auto it2 = st.lower_bound({r + 1, 0});
                        if (it2 != st.end() && it2->fi == r + 1) {
                                mnr = min(mnr, it2->se);
                                st.erase(it2);
                        }

                        if (l - 1 >= 1) {
                                st.insert({l - 1, mnl});
                        }

                        if (r + 1 <= n) {
                                st.insert({r + 1, mnr});
                        }
                }

                int ans = INFF;

                for (auto [pos, cost] : st) {
                        ans = min(ans, cost);
                }

                cout << ans << '\n';
        }
        
        return 0;
}

The original idea of this problem is using segment tree, hence the $$$n \leq 2\cdot 10^5$$$ constraint. However, this problem can be solved easier by using std::set.

For this problem, we can do DP to solve the problem.

Define $$$dp_i$$$ after the $$$j$$$-th attack as minimum energy needed to avoid the first $$$j$$$ attacks and we ended up at tile $$$i$$$. If we try updating all $$$n$$$ indices for each attack (by doing $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ for all $$$1 \leq j \leq n$$$), that will cost $$$O(n)$$$ transition, which means the complexity will be $$$O(n^2m)$$$ per test case. Since it's too slow, we need some observation.

\textbf{Observation.} For the $$$k$$$-th attack, we only need to update two DP indices each attack and it's optimal to do $$$dp_i=\min (dp_i,dp_j+|dp_j-dp_i|)$$$ where $$$i=l_k-1$$$ or $$$i=r_k+1$$$ (if those two indices actually exist inside the range $$$[1,n]$$$) and $$$l_k \leq j \leq r_k$$$

\textbf{Proof.} Assume that everytime the boss attacks, it is sometimes optimal for us to move if we didn't stand inside the incoming lazer previously. So, assume at some point, we went to the right $$$y$$$ tiles as the "optimal" route. Then, there are three cases for the next attack:

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(x > y)$$$. In this case, the current optimal is not the same as the previous optimal, since we could've just not move in previous turn and then move to the left by $$$x-y$$$ tiles.

• The current optimal route involves going to the left by $$$x$$$ tiles $$$(0 < x \leq y)$$$. In this case, the current optimal is also not the same as the previous optimal, since we could've just not move in previous turn and then move to the right by $$$y-x$$$ tiles.

• The current optimal route involves going to the right by $$$x$$$ tiles $$$(x \geq 0)$$$. In this case, there is an alternative solution, where we could've just not move in previous turn and then move to the right by $$$x+y$$$ tiles. It'll result with the same energy spent.

\end{enumerate}

So, it is optimal to do nothing if we don't stand inside the lazer.

If we do stand inside the lazer (assume it's the $$$j$$$-th lazer), it is optimal to go to either $$$l_j-1$$$ or $$$r_j+1$$$, since with the same idea as above, one of these tiles are either the most optimal solution, or one of the most optimal solution (think of it like a waterfall :]).

Now, with this in mind, we can implement this in $$$O(n\sum_{i=1}^n (r_i-li))$$$ per test case. Since it's still too slow, we can optimize it again. Notice that for each attack, we're only interested from the updates that actually give paths, not the one getting blocked by the lazer. So, we will try to implement this using C++ std::set. First, create the set $$$route$$$ which stores all previously updated $$$dp$$$ indices that \textbf{give paths} (since we update the tiles that will get hit by the lazer for each attack to $$$INF$$$ again after updating $$$dp{li-1}$$$ and $$$dp{r_i+1}$$$). Set $$$dp_i=INF$$$ for all $$$1 \leq i \leq n,i \neq s$$$, $$$dp_s=0$$$, and . Then, do the following for the j-th attack:

• Find all the element $$$k$$$ in $$$route$$$ such that $$$l_j \leq k \leq rj$$$.

• For each of the element satisfying the constraint above, update $$$dp{lj-1}$$$ to $$$\min(dp{l_j-1},dp_k+k-lj+1)$$$ and $$$dp{rj+1}$$$ to $$$\min(dp{r_j+1},dp_k+r_j+1-k)$$$

• Set all $$$dp_k$$$ to $$$INF$$$, remove all elements satisfying the constraint above, and then add $$$l_j-1$$$ and $$$r_j+1$$$ to $$$route$$$

The time complexity of this would be $$$O(m\log m)$$$ with $$$O(n)$$$ initializer and $$$O(n)$$$ finding optimal of each $$$dp$$$ index for each test case.

To optimize this even further, notice that after all the $$$m$$$ attacks, every index outside the $$$route$$$ would have the value of $$$INF$$$, so we only need to check the minimum from all $$$dp$$$ with indices inside $$$route$$$ (which is $$$O(m)$$$) and only to reset those indices as well for the next test case (which is also $$$O(m)$$$).

Once again, beware of the fact that $$$l_i-1$$$ or $$$r_i+1$$$ might be out of the arena range.

Time complexity: $$$O(m\log m)$$$

Bonus: Solve the problem if $$$n \leq 10^9$$$

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second

using namespace std;

const int MOD = 1e9 + 7;

int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        vector<bool> ok(22222, 0);

        auto conv = [&](int x) {
                int res = 0;

                while (x > 0) {
                        int y = x % 10;

                        res += y * y;
                        x /= 10;
                }

                return res;
        };

        for (int i = 1; i <= 16200; i++) {
                int x = i;

                set<int> vis;
                
                while (!vis.count(x)) {
                        vis.insert(x);

                        int y = conv(x);
                        if (x == y) {
                                ok[i] = 1;
                        }
                        x = y;
                }
        }
        
        vector<vector<int>> dp(222, vector<int>(22222)); // digit - sum
        dp[0][0] = 1;

        for (int i = 1; i <= 200; i++) {
                for (int j = 0; j < 20000; j++) {
                        for (int k = 0; k <= 9; k++) {
                                dp[i][j + k * k] += dp[i - 1][j];
                                dp[i][j + k * k] %= MOD;
                        }
                }
        }

        int t;
        cin >> t;

        while (t --> 0) {
                string l, r;
                cin >> l >> r;

                auto calc = [&](string s, bool on) {
                        int res = 0;
                        int n = (int)s.length();
                        int cur = 0;

                        for (int i = 0; i < n; i++) {
                                for (int j = 0; j < s[i] - '0'; j++) {
                                        for (int k = cur + j * j; k <= 16200; k++) {
                                                res += ok[k] * dp[n - i - 1][k - (cur + j * j)];
                                                res %= MOD;
                                        }
                                }
                                cur += (s[i] - '0') * (s[i] - '0');
                        }

                        if (ok[cur] && on) res += 1;

                        return res;
                };
                
                int ans = calc(r, 1) - calc(l, 0);
                ans %= MOD;
                ans += MOD;
                ans %= MOD;

                cout << ans << '\n';
        }
        return 0;
}

Notice that the biggest number we can obtain after exactly one operation is $$$81 \cdot 200 = 16200$$$.

We can solve the problem with digit DP (or DFS with memorization). Let $$$AN$$$ be the number of happy numbers less than or equal to $$$N$$$. Our answer would then be $$$A{ri} - A{l_i - 1}$$$.

Now we are interested in calculating $$$AN$$$ for some integer $$$N$$$. We do a DFS from the leftmost digit to the rightmost digit. Let $$$f{i, j}$$$ denote the number of happy numbers, less than or equal to $$$N$$$, with the sum of the first $$$i$$$ digits squared equal to $$$j$$$. We can do a DFS from left to right, taking note of whether the current digit sequence is exactly the same as $$$N$$$'s first digits; if not so, we can memorize the answer with $$$f_{i, j}$$$ (to avoid repeated calculations).

It is not hard to see that we are expected to reach every state once, and we can re-use $$$f$$$ over all test cases. Thus, the time complexity is $$$O(DS)$$$, where $$$D \leq 201$$$ is the number of digits and $$$S \leq 16200$$$ is the digit-squared sum.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")

#define int long long
const int bk=500;
namespace sumadd {
   int tag[bk],pb[bk],pre[bk][bk];
   void addib(int l,int r,int id,int v) {
      for(int i=0,x=0;i<=bk-1;++i){if(l<=i&&i<=r)x+=v;x+=tag[id];pre[id][i]+=x;}
      tag[id]=0;
   }
   void add(int l,int r,int v) {
      if(l/bk==r/bk) {
         addib(l%bk,r%bk,l/bk,v);
         for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
         return;
      }
      if(l%bk!=0) {addib(l%bk,bk-1,l/bk,v);l+=bk-l%bk;}
      if(r%bk!=bk-1) {addib(0,r%bk,r/bk,v);r-=r%bk+1;}
      while(l<=r) {tag[l/bk]+=v;l+=bk;}
      for(int i=0;i<=bk-1;++i) pb[i]=(i==0?0:pb[i-1])+pre[i][bk-1]+tag[i]*bk;
   }
   int sum(int l,int r) {
      if(l/bk==r/bk) {
         return (r-l+1)*tag[l/bk]+pre[l/bk][r%bk]-(l%bk==0?0:pre[l/bk][l%bk-1]);
      }
      int sum=0;
      if(l%bk!=0) {sum+=tag[l/bk]*(bk-l%bk)+pre[l/bk][bk-1]-(l%bk==0?0:pre[l/bk][l%bk-1]);l+=bk-l%bk;}
      if(r%bk!=bk-1) {sum+=tag[r/bk]*(r%bk+1)+pre[r/bk][r%bk];r-=r%bk+1;}
      sum+=pb[r/bk]-(l==0?0:pb[l/bk-1]);
      return sum;
   }
   void cln() {
      for(int i=0;i<bk;++i) {
         tag[i]=pb[i]=0;
         for(int j=0;j<bk;++j)
            pre[i][j]=0;
      }
   }
}
pair<int,int> ivl[bk][bk];
array<int,4> qry[bk*bk];
int cnt[bk*bk],ans[bk*bk],flag[bk*bk];
vector<int> lp={0};
void Delta() {
   int n,m,q;
   cin >> n >> m >> q;
   for(int i=1,l,r;i<=m;++i) {
      cin >> l >> r;
      ivl[i/bk][i%bk]={l,r};
      lp.push_back(lp.end()[-1]+r-l+1);
   }
   cerr << endl;
   lp.push_back(2147483647);
   for(int i=1,o,l,r,v;i<=q;++i) {
      cin >> o >> l >> r;
      if(o==1) {cin >> v;qry[i]={1,l,r,v};sumadd::add(l,r,v);}
      else {
         auto il=lower_bound(lp.begin(),lp.end(),l-1),ir=prev(lower_bound(lp.begin(),lp.end(),r+1));
         qry[i]={2,il-lp.begin()+1,ir-lp.begin(),0};
         if(qry[i][1]==qry[i][2]+2) {
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            l-=*prev(il);r-=*prev(il);
            ans[i]=sumadd::sum(t.first+l-1,t.first+r-1);
            flag[i]=true;
            continue;
         }
         if(qry[i][1]==qry[i][2]+1) {
            ans[i]=sumadd::sum(ivl[qry[i][2]/bk][qry[i][2]%bk].first+l-*prev(il)-1,ivl[qry[i][2]/bk][qry[i][2]%bk].second);
            ans[i]+=sumadd::sum(ivl[qry[i][1]/bk][qry[i][1]%bk].first,ivl[qry[i][1]/bk][qry[i][1]%bk].first+r-*ir-1);
            flag[i]=true;
            continue;
         }
         if(il!=lp.begin()) {
            int p=qry[i][1]-1;l=*il-l+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.second+1-l,t.second);
         }
         if(next(ir)!=lp.end()) {
            r-=*ir;
            int p=qry[i][2]+1;
            auto t=ivl[p/bk][p%bk];
            ans[i]+=sumadd::sum(t.first,t.first+r-1);
         }
         if(flag[i]) ans[i]=-ans[i];
      }
   }
   sumadd::cln();
   for(int k=0;k<bk;++k) {
      int sum=0;
      for(int i=0;i<bk;++i) {
         auto t=ivl[k][i];
         if(t==pair<int,int>{0,0}) continue;
         cnt[t.first]++;
         cnt[t.second+1]--;
      }
      for(int j=1;j<=2;++j)
         for(int i=1;i<=n;++i)
            cnt[i]+=cnt[i-1];
      for(int i=1;i<=q;++i)
         if(qry[i][0]==1) {
            sum+=qry[i][3]*(cnt[qry[i][2]]-(qry[i][1]==0?0:cnt[qry[i][1]-1]));
         }
         else
            if(!flag[i]&&qry[i][1]<=k*bk&&k*bk+bk-1<=qry[i][2]) ans[i]+=sum;
      for(int i=1;i<=n;++i) cnt[i]=0;
   }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==1)
         sumadd::add(qry[i][1],qry[i][2],qry[i][3]);
      else {
         if(flag[i]) continue;
         int l=qry[i][1],r=qry[i][2];
         if(l>r) continue;
         if(l/bk==r/bk&&l%bk!=0&&r%bk!=bk-1) {
            for(int j=l;j<=r;++j) {
               auto t=ivl[j/bk][j%bk];
               ans[i]+=sumadd::sum(t.first,t.second);
            }
            continue;
         }
         while(l%bk!=0)    {auto t=ivl[l/bk][l%bk];ans[i]+=sumadd::sum(t.first,t.second);l++;}
         while(r%bk!=bk-1) {auto t=ivl[r/bk][r%bk];ans[i]+=sumadd::sum(t.first,t.second);r--;}
      }
   for(int i=1;i<=q;++i)
      if(qry[i][0]==2)
         cout << ans[i] << ' ';
   cout << endl;
}
signed main() {
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   Delta();
}

Consider SQRT decomp for $$$[l_i,r_i]$$$, putting each $$$sqrt(n)$$$ of $$$[l_i,r_i]$$$ into a block, and maintaining the sum of the group, and the number of occurrences in the block in each original array $$$a_i$$$.

Enumerate all blocks, and if a query completely contains an sqrt, then +=sum is added to the result of the query.

If we add, then sum+= the number of times the number * added value. (This can be done with two times perfix sums)

For queries that are not complete blocks, consider direct brute force maintenance of the A-array and query, it has $$$n^{1.5}$$$ query operations and n modification operations, so we can use a partitioned data structure to do $$$O(1)$$$ queries, $$$O(n^{0.5})$$$ modifications.

So, the total complexity is $$$O(n^{1.5})$$$.