并不是HH的项链主要原因是,洛谷的HH项链卡莫队卡的很严重,而我又是初学莫队,所以说就不去挑战了
而且HH的项链树状数组写码量也没太大的区别
对于初始维护首先考虑O(nm)O(nm)的:
对于m次询问,每次我可以维护一个cnt数组,每次修改x的时候就cnt[x]−− or cnt[x]++cnt[x]−− or cnt[x]++ 并且答案每次在cnt修改的时候都维护一下,代码如下

for(int i = 1 ; i <= m ; i ++){
    int res = 0;
    for(int j = l[i] ; j <= r[i] ; j ++){
        int x = a[i];
        res -= cnt[x] * cnt[x];
        cnt[x] ++ or cnt[x] --;
        res += cnt[x] * cnt[x];
    }
    cout << res << endl; 
}

显然,正常情况就是O(nm)O(nm),并不是我们所能接受的
因此我们考虑如果我们通过[l[i],r[i]]−>[l[i+1],r[i+1]][l[i],r[i]]−>[l[i+1],r[i+1]]通过这样的转移,对于一些极端情况依然会优化很多的

int l = 1, r = 0, res = 0; // res要定义到外面,因为两次的res是转移的关系,
for(int i = 1 ; i <= m ; i ++){
    while(l < l[i] or l > l[i]){
        l --;// 和下面的l++只能出现一个
        res -= cnt[a[l]] * cnt[a[[l]];
        cnt[a[l]] ++ or cnt[a[l]] --;
        res += cnt[a[l]] * cnt[a[[l]];
        l ++;// 和上面的l--只能出现一个
    }
    while(r < r[i] or r > r[i]){
        r ++;// 和下面的r--只能出现一个
        res -= cnt[a[r]] * cnt[a[[r]];
        cnt[a[r]] ++ or cnt[a[r]] --;
        res += cnt[a[r]] * cnt[a[[r]];
        r --;// 和上面的r++只能出现一个
    }
    cout << res << endl; 
}
// 本来并不准备在这里放下面的代码的,不过这部分思路就这样
for(int i = 1 ; i <= m ; i ++){
    while(l > l[i]){-- l;res -= c[a[l]] * c[a[l]];c[a[l]] ++;res += c[a[l]] * c[a[l]];}
    while(l < l[i]){res -= c[a[l]] * c[a[l]];c[a[l]] --;res += c[a[l]] * c[a[l]];l ++;}
    while(r > r[i]){res -= c[a[r]] * c[a[r]];c[a[r]] --;res += c[a[r]] * c[a[r]];r --;}
    while(r < r[i]){++ r;res -= c[b[r]] * c[b[r]];c[b[r]] ++;res += c[b[r]] * c[a[r]];}
    cout << res << endl; 
}
//在这里c数组就是cnt数组

这种情况显然在某种数据可以达到最优的情况O(m)O(m)不过最坏情况下的概率更大基本上就是 99.999%99.999%的概率O(nm)O(nm)了吧
我们来分析为什么依然是O(nm)O(nm)的
最坏情况下左端点每次可能移动距离为n右端点移动距离为n,因此m次操作每次都要移动n次,显然复杂度是O(nm)O(nm)的
我们先考虑右端点(左端点也是可以的这段话对称看就好了),如果我们如果按照右端点排序那么结果会就是右端点m次操作总移动次数是n次,也就是说右端点移动的复杂度显然就是O(n+m)O(n+m)的了,但是这时候我们就发现了无论怎么修改左端点都是O(nm)O(nm)的复杂度
不过这种解法显然比上面的解法更优,虽说复杂度都差不多

代码:无

这时候显然可以借助左区间用分块弄,这个就是莫队了
左区间我可以按照分好的块排序,然后每次在同一个块内我再按照右端点排序,
这样左端点最坏的移动次数就是O(mn)O(mn​)了,每次左端点移动最坏是O(mn)O(mn​),最优是O(1)O(1)的,一共会移动,其实复杂度不是O(mn)O(mn​),正确的分析应该是相同的块之间的转移和不同的块之间的转移,同一个块最多移动的复杂度是O(n)O(n​),不同块之间的移动每次复杂度是O([1,n]n)O([1,n​]n​),并且对于∑[1,n]≤n∑[1,n​]≤n​, 因此复杂度是O(nn)O(nn​),
考虑左端点的移动对应的右端点再一个块内的所有右端点的总移动复杂度为O(n)O(n),对应每次不同块之间的总移动复杂度显然就是O(nn)O(nn​)
显然上面是将原数组分为nn​块,每块长度为nn​
代码:

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define eps 1e-9
#define endl '\n'
#define gcd __gcd
#define pi acos(-1)
#define ll long long
#define LL long long
#define IDX(x) x - 'A'
#define idx(x) x - 'a'
#define idz(x) x - '0'
#define ld long double
#define lowebit(x) x&(-x)
#define rint register int
#define Len(x) (int)(x).size()
#define all(s) (s).begin(), (s).end()
using namespace std;
inline int read()
{
    register int x = 0, f = 1, ch = getchar();
    while( !isdigit(ch) ){if(ch == '-') f = -1; ch = getchar();}
    while( isdigit(ch) ){x = x * 10 + ch - '0'; ch = getchar();}
    return x * f;
}
const int maxn = 5e4 + 5;
struct node {int l, r, id, t;}a[maxn];
int b[maxn], c[maxn],ans[maxn];
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // .....................................
    int n = read(), m = read(), k = read(),sn = sqrt(n);
    for(int i = 1 ; i <= n ; i ++) b[i] = read();
    for(int i = 1 ; i <= m ; i ++)
    {
        int l = read(), r = read();
        a[i] = {l, r, i, l / sn};
    }
    sort(a + 1, a + m + 1,[](const node& t, const node& s){if(t.t == s.t) return t.r < s.r;return t.t < s.t;});
    int l = 1, r = 0, res = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        while(l > a[i].l){-- l;res -= c[b[l]] * c[b[l]];c[b[l]] ++;res += c[b[l]] * c[b[l]];}
        while(l < a[i].l){res -= c[b[l]] * c[b[l]];c[b[l]] --;res += c[b[l]] * c[b[l]];l ++;}
        while(r > a[i].r){res -= c[b[r]] * c[b[r]];c[b[r]] --;res += c[b[r]] * c[b[r]];r --;}
        while(r < a[i].r){++ r;res -= c[b[r]] * c[b[r]];c[b[r]] ++;res += c[b[r]] * c[b[r]];}
        ans[a[i].id] = res;
    }
    for(int i = 1 ; i <= m ; i ++) cout << ans[i] << endl;
    // .....................................
    return 0;
}

C++

很容易发现的一个信息就是AC代码的区间维护和暴力转移的区间维护的代码一模一样,除了sort不一样(有 or 没有 or sort方式不一样)