# CodeForces D.Powerful array(Div.1)

#### D. Powerful array

```import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class CF522A {

final static int N = (int)200001;
static long nowAns = 0;//当前答案
static int n,m,k,block;
static int[] cnt = new int[N];//每个数出现的次数
static long[] ans = new long[N];//记录每个答案
static int[] arr = new int[N];//数组
static Query[] q = new Query[N];//询问

public static class cmp implements Comparator<Query> {
public int compare(Query x,Query y) {
if(x.l / block == y.l / block)
return x.r - y.r;
return x.l / block - y.l / block;
}
}

public static void remove(int x) {
nowAns -= cnt[arr[x]] * cnt[arr[x]] * arr[x];
cnt[arr[x]]--;
nowAns += cnt[arr[x]] * cnt[arr[x]] * arr[x];
}

public static void add(int x) {
nowAns -= cnt[arr[x]] * cnt[arr[x]] * arr[x];
cnt[arr[x]]++;
nowAns += cnt[arr[x]] * cnt[arr[x]] * arr[x];
}

public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
int l = 0,r = -1;
n = cin.nextInt();//数组长度
m = cin.nextInt();//询问次数
block = (int) Math.sqrt(n);//每块的大小
for(int i = 0;i < n;i++) arr[i] = cin.nextInt();

for(int i = 0;i < m;i++) {
int tmp_l = cin.nextInt();
int tmp_r = cin.nextInt();
q[i] = new Query(tmp_l - 1,tmp_r - 1,i);//减1是为了将询问转换为下标
}
Arrays.sort(q,0,m,new cmp());//sort是左闭右开的区间
for(int i = 0;i < m;i++) {
while(l < q[i].l) remove(l++);//移出数字
while(r > q[i].r) remove(r--);//移出数字
ans[q[i].id] = nowAns;
}
for(int i = 0;i < m;i++) System.out.println(ans[i]);
}
}
class Query {
int l,r,id;
long a,b;
Query(int L,int R,int id) {
this.l = L;
this.r = R;
this.id = id;
}
}```
```#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;
const int N = 200010;
struct node {
int l, r, id;
} g[N];
int n, m, unit;
int num[N], a[N], b[N], c[N];
ll tmp, res[N];
bool cmp(node a, node b) {
if(a.l / unit != b.l / unit)
return a.l / unit < b.l / unit;
return a.r < b.r;
}
tmp -= (ll)num[a[i]] * num[a[i]] * c[i];
num[a[i]]++;
tmp += (ll)num[a[i]] * num[a[i]] * c[i];
}
void del(int i) {
tmp -= (ll)num[a[i]] * num[a[i]] * c[i];
num[a[i]]--;
tmp += (ll)num[a[i]] * num[a[i]] * c[i];
}
void solve() {
unit = (int)sqrt(1.0 * n);
sort(g + 1, g + 1 + m, cmp);
int l = 1, r = 0;
tmp = 0;
for(int i = 1; i <= m; i++) {
while(r > g[i].r) del(r--);
while(l < g[i].l) del(l++);
res[g[i].id] = tmp;
}
for(int i = 1; i <= m; i++) printf("%I64d\n", res[i]);
}
int main() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = c[i] = a[i];
}
sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; i++)
a[i] = lower_bound(b+1, b+1+n, a[i]) - b;
for(int i = 1; i <= m; i++)
scanf("%d%d", &g[i].l, &g[i].r), g[i].id = i;
solve();
return 0;
}```

0 条评论

• ### BFPRT算法

首先将原数组分成5个一组，每组内进行排序，组间不排序，然后将每组的中位数取出再次进行上述操作，直到最后只能分成一组了，然后取出中位数，将这个中位数当作标尺进行...

• ### ECJTUACM16 Winter vacation training #5 题解&源码

A-------------------------------------------------------------------------------...

• ### Codeforces Round #186 (Div. 2)A、B、C、D、E

Ilya得到了一个礼物，可以在删掉银行账户最后和倒数第二位的数字（账户有可能是负的），也可以不做任何处理。

• ### View的工作原理

View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure，layout，draw三个过程将view绘制出来。m...

• ### 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

小L 最近沉迷于塞尔达传说：荒野之息（The Legend of Zelda: Breath of The Wild）无法自拔，他尤其喜欢游戏中的迷你挑战。