Approximate

#include <bits/stdc++.h>

using namespace std;
long long cs[110][101010];
int main(){
  cin.sync_with_stdio(0);
  cin.tie(0);
  
  int n, q; cin >> n >> q;
  int x[101010];
  for(int i = 0; i < n; i++)
    cin >> x[i];
 
  long long s[101010] = {0};
  s[0] = x[0];
  cs[x[0]][0]++;
  for(int i = 1; i < n; i++){
    s[i] = s[i-1]+x[i];
    for(int j = 1; j <= 100; j++)
      cs[j][i] = cs[j][i-1];
    cs[x[i]][i]++;
  }
  while(q--){
      int a, b; cin >> a >> b;
      a--;
      b--;
      long long su = s[b];
      if(a > 0)
	su-=s[a-1];
      double le = (b-a)+1;
      double c = su/le;
      long double ans = 0;
      for(long long i = 1; i <= 100; i++){
	  long long mm = cs[i][b];
	  if(a > 0)
	    mm-=cs[i][a-1];
	  //cout << i << " on " << mm << " delta c " << (i-c)  << endl;
	  ans+=(i-c)*(i-c)*mm;
      }
      ans/=le;
      cout <<setprecision(20);
      cout << ans << endl;
  }
  return 0;
}

Test 1

Verdict: OUTPUT LIMIT EXCEEDED