莫队/分块
莫队：O(
)
算法：算法核心是分块与排序。分块是将数组分成大小为
的几块，然后对左端点所在块的编号进行排序，如果相等则按照右端点进行排序。
#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;
} 分块
用来解决用线段树和树状数组难以实现的题。
算法实现：
一：建立块
1）将数组分成大小为的几块，算出每一块的左端点的下标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;
}
