P5268 题解（暴力莫队）

jiarenmen · 2024-10-17 16:00:15 · 题解

本题普通莫队就可以过，借鉴带修莫队的思路，把本题想成四个维度，然后把块长调成 n^{\frac{3}{4}} 能达到理论最优复杂度 O(n^{\frac{7}{4}}) 。

考虑暴力开两个莫队，贡献好计算，用乘法分配律拆开即可，在加上数据类型优化（开 unsigned short），甚至无需卡常，约是时限的 \frac{1}{2} 。

这是我的测评记录

代码直观：

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
#define int unsigned short
#define N 500005
int mp1[N],mp2[N],n,m,sq,b[N];
struct que{
  int a,b,c,d,id;
  bool operator<(const que cmp)const{
    if(a/sq!=cmp.a/sq)return a<cmp.a;
    if(b/sq!=cmp.b/sq)return b<cmp.b;
    if(c/sq!=cmp.c/sq)return c<cmp.c;
    return d<cmp.d;
  }
}a[N];
long long ans[N],res;
void add1(int x){return mp1[x]++,res+=mp2[x],void();}
void del1(int x){return mp1[x]--,res-=mp2[x],void();}
void add2(int x){return mp2[x]++,res+=mp1[x],void();}
void del2(int x){return mp2[x]--,res-=mp1[x],void();}
signed main(){
  //freopen("1.in","r",stdin);
  //freopen("1.out","w",stdout);
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  cin>>n,sq=pow(n,0.75);
  for(int i=1;i<=n;i++)cin>>b[i];
  cin>>m;
  for(int i=1;i<=m;i++)cin>>a[i].a>>a[i].b>>a[i].c>>a[i].d,a[i].id=i;
  sort(a+1,a+m+1);
  for(int i=1,L,R,l=1,r=0,ll=1,rr=0;i<=m;i++){
    L=a[i].a,R=a[i].b;
    while(r<R)add1(b[++r]);
    while(l>L)add1(b[--l]);
    while(r>R)del1(b[r--]);
    while(l<L)del1(b[l++]);
    L=a[i].c,R=a[i].d;
    while(rr<R)add2(b[++rr]);
    while(ll>L)add2(b[--ll]);
    while(rr>R)del2(b[rr--]);
    while(ll<L)del2(b[ll++]);
    ans[a[i].id]=res;
  }
  for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
  return 0;
}