全員に毎回(同率を考慮した)順位をつけ、それらの和を求めて出力といった行為を繰り返していては実行時間制限に間に合いません。
また、毎回個人の順位を求めるのも大変なので、できれば回避したいです。なにか良い言い換えはないでしょうか？

同率の性質を観察します。

• \(1,2\) 位が同率なら双方が \(1\) 位として扱われる。このとき、求めるべき値は同率がない時に比べて \(1\) 減る。

• \(1,2,3\) 位が同率なら全員が \(1\) 位として扱われる。このとき、求めるべき値は同率がない時に比べて \(3\) 減る。

• \(1,2,3,4\) 位が同率なら全員が \(1\) 位として扱われる。このとき、求めるべき値は同率がない時に比べて \(6\) 減る。

• \(\dots\)

• つまり、 \(k\) 人が同率であれば、そのことによって求める値が \(\frac{k(k-1)}{2}\) 減る。

(これだけでも以降の解法で解くには十分ですが、) 更に以下のように言い換えることができます。

• \(k\) 人が同率であれば、そのことによって求める値が「 \(k\) 人から相異なる \(2\) 人をペアにする方法の数」だけ減る。

座標・評価ポイントに対して適切な座標圧縮を使うと、問題は以下のものに帰着されます。

• 座標圧縮 (座圧)
• 座標圧縮の解説（1次元から2次元の圧縮まで）

左から \(L\) 番目の人から左から \(R\) 番目の人に着目する。
このとき、着目した人の中で同じ評価ポイントを持つ \(2\) 人組の個数を \(p\) とする。
\(\frac{(R-L+2)(R-L+1)}{2} - p\) を求めよ。

この問題は Mo’s algorithm を利用して解くことができます。

• Mo’s algorithm(クエリ平方分割)の話
• Mo’s algorithm
• Mo’s algorithm とその上位互換の話

Mo’s algorithm 自体の解説は記事に譲ります。

区間を伸ばす際は以下の手順を行えばよいです。

• \(k\) 人目を追加するとする。
• 答えに「区間内の \(V_k\) の数」を追加する。
• 「区間内の \(V_k\) の数」に \(1\) 加算する。

区間を縮める際はこの操作を逆順に行えばよいです。

時間計算量は \(O(N \sqrt{Q})\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

const int bsize=317;

typedef struct{
  int st;
  int fi;
  int id;
}query;

bool qcomp(const query &a,const query &b){
  int ast=a.st;
  int afi=a.fi;
  int bst=b.st;
  int bfi=b.fi;
  ast/=bsize;bst/=bsize;
  if(ast<bst){return true;}
  if(ast>bst){return false;}
  if((ast&1)==0){
    if(afi<bfi){return true;}
    if(afi>bfi){return false;}
  }
  else{
    if(afi<bfi){return false;}
    if(afi>bfi){return true;}
  }
  return (a.id<b.id);
}

vector<int> col;
vector<int> bk;
long long res=0;
int st,fi;

void mo_add(int id){
  res+=bk[col[id]];
  bk[col[id]]++;
}

void mo_rem(int id){
  bk[col[id]]--;
  res-=bk[col[id]];
}

long long mo_query(int tst,int tfi){
  if(!(fi<tst)){
    while(st<tst){mo_rem(st);st++;}
    while(tst<st){st--;mo_add(st);}
  }
  while(fi<tfi){fi++;mo_add(fi);}
  while(tfi<fi){mo_rem(fi);fi--;}

  while(st<tst){mo_rem(st);st++;}
  while(tst<st){st--;mo_add(st);}
  return res;
}

long long f(long long x){
  return ((x+1)*x)/2;
}

int main(){
  int N,Q;
  cin >> N >> Q;
  vector<int> X(N),V(N);
  map<int,int> xmp,vmp;
  for(int i=0;i<N;i++){
    cin >> X[i] >> V[i];
    xmp[X[i]]=0;
    vmp[V[i]]=0;
  }
  xmp[2e9]=0;

  int xn=0,vn=0;
  for(auto &nx : xmp){
    nx.second=xn; xn++;
  }
  for(auto &nx : vmp){
    nx.second=vn; vn++;
  }

  col.resize(N);
  for(int i=0;i<N;i++){
    col[xmp[X[i]]]=vmp[V[i]];
  }

  vector<long long> res(Q,0);
  vector<query> qv;
  for(int i=0;i<Q;i++){
    int L,R;
    cin >> L >> R;
    query cq;
    cq.st=(*xmp.lower_bound(L)).second;
    cq.fi=(*xmp.lower_bound(R+1)).second;
    cq.fi--;
    if(cq.st>cq.fi){continue;}
    res[i]=f(cq.fi-cq.st+1);
    cq.id=i;
    qv.push_back(cq);
  }

  bk.resize(vn);
  for(auto &nx : bk){nx=0;}

  st=0; fi=0; mo_add(0);
  sort(qv.begin(),qv.end(),qcomp);

  for(auto &nx : qv){
    res[nx.id]-=mo_query(nx.st,nx.fi);
  }
  for(auto &nx : res){
    cout << nx << "\n";
  }
  return 0;
}