莫队：O( $n\sqrt{n}$ )

算法：算法核心是分块与排序。分块是将数组分成大小为 $\sqrt{n}$ 的几块，然后对左端点所在块的编号进行排序，如果相等则按照右端点进行排序。

大佬博客：https://www.cnblogs.com/WAMonster/p/10118934.html

题目：https://www.luogu.com.cn/problem/P2709

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define ll long long
#define inf 0x3f3f3f3f
const int mod = 1e9+7;
const int msize = 50005;
using namespace std;

ll cnt[msize],ans[msize],sum;
int a[msize],l,r,m,n,k,block;
struct node{
    int l,r,xb;
    friend bool operator < (node a,node b){
        if(a.l / block == b.l / block) return a.r < b.r;
        return a.l / block < b.l / block;
    }
}q[50005];

void add(int t)
{
    ll temp = cnt[a[t]];
    cnt[a[t]]++;
    sum += cnt[a[t]] * cnt[a[t]] - temp * temp;
}

void del(int t)
{
    ll temp = cnt[a[t]];
    cnt[a[t]]--;
    sum += cnt[a[t]] * cnt[a[t]] - temp * temp;
}

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    block = sqrt(n);
    sum = 0;
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    for(int i = 1; i <= m; i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].xb = i;
    }
    l = 1,r = 0;
    sort(q + 1,q + m + 1);
    for(int i = 1; i <= m; i++){
        while(l < q[i].l) del(l++);
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(r > q[i].r) del(r--);
        ans[q[i].xb] = sum;
    }
    for(int i = 1; i <= m; i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}

分块

题单：https://loj.ac/problems/search?keyword=%E5%88%86%E5%9D%97

用来解决用线段树和树状数组难以实现的题。

算法实现：

一：建立块

1）将数组分成大小为 $\sqrt{n}$ 的几块，算出每一块的左端点的下标l[i]与右端点下标r[i]。

2）算出每个下标所属块存在数组belong中。

二：区间加法 [L,R]

1）利用belong数组找到L，R所属块bl，br。

2）如果相等说明这个区间在同一块里面，那我们直接对区间[L,R]里面的每个数加上c

3）如果不等，那我们对区间[L,r[bl]],[l[br,R]里面的每个数加上c,然后对(bl,br)的每个块进行整体加c，即add[i] += c。

三：单点查值 r

直接查找a[r] + add[belong[r]]即可.

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#define LL long long
#define inf 0x3f3f3f3f
const int mod = 1e9+7;
const int msize = 50005;
using namespace std;

int a[msize],belong[msize],l[msize],r[msize],add[msize],n;
void build()
{
    int block = sqrt(n);
    int m = n / block;
    if(n % block) m++;
    for(int i = 1; i <= m; i++) l[i] = (i - 1) * block + 1,r[i] = i * block;
    r[m] = n;
    for(int i = 1; i <= n; i++){
        belong[i] = (i - 1) / block + 1;
    }
}

void Add(int L,int R,int c)
{
    int bl,br;
    bl = belong[L];
    br = belong[R];
    if(bl == br){
        for(int i = L; i <= R; i++){
            a[i] += c;
        }
        return;
    }
    for(int i = L; i <= r[bl]; i++) a[i] += c;
    for(int i = l[br]; i <= R; i++) a[i] += c;
    for(int i = bl+1; i < br; i++) add[i] += c;
}

int main()
{
	int opt,l,r,c;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
    build();
    for(int i = 1; i <= n; i++){
        cin >> opt >> l >> r >> c;
        if(opt == 1){
            cout << a[r] + add[belong[r]] << endl;
        }
        else{
            Add(l,r,c);
        }
    }
	return 0;
}

莫队/分块

莫队：O()

分块

全站热榜

莫队：O( $n\sqrt{n}$ )