[ABC293G] Triple Index 题解

· · 题解

本题需要使用莫队思想。

考虑加入一个数会对答案造成什么影响：

记 x 在目前扫描的区间中出现了 c_x 次，再加入一个 x，因为可以从原来的 c_x（这里 c_x 指还未加入新的 x 时的 x 的数量）中选择 2 个和 x 组成一个三元组，所以能形成的三元组数量应该增加 \dfrac{c_x(c_x-1)}{2}，而后 c_x\leftarrow c_x+1。删除也是类似的思想。

然后就是莫队板子了，先把所有询问离线下来，可以使用奇偶性排序优化。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef tuple<int,int,int> tpi;
int t,c[200001];
void add(int p){
  if(++c[p]==3)t++;
  if(c[p]==4)t+=3;
  if(c[p]>4)t+=(c[p]-1)*(c[p]-2)>>1;
} // 加入一个数
void del(int p){
  if(--c[p]==2)t--;
  if(c[p]==3)t-=3;
  if(c[p]>3)t-=c[p]*(c[p]-1)>>1;
} // 删除一个数
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q,L=0,R=-1,sq; cin>>n>>q; sq=sqrt(n);
  vector<int> a(n),s(q);
  vector<tpi> w(q);
  for(auto &i:a)cin>>i;
  for(int i=0;i<q;i++)
    cin>>get<0>(w[i])>>get<1>(w[i]),get<2>(w[i])=i;
  sort(w.begin(),w.end(),[&](tpi x,tpi y){
    if(get<0>(x)/sq!=get<0>(y)/sq)return get<0>(x)<get<0>(y);
    return get<0>(x)/sq&1?get<1>(x)<get<1>(y):get<1>(x)>get<1>(y);
    }); // 奇偶性排序
  for(auto &[l,r,x]:w){
    l--,r--;
    while(L<l)del(a[L++]);
    while(L>l)add(a[--L]);
    while(R<r)add(a[++R]);
    while(R>r)del(a[R--]);
    s[x]=t;
  } // L 和 R 扫描
  for(int i:s)cout<<i<<endl;
  return 0;
}