CodeForces D.Powerful array(Div.1)

D. Powerful array展开目录

题解展开目录

大意是是说，问区间 [L,R] 内的的一个值，这个值是 arr [x] 出现次数 $cnt [arr [x]]^2*arr [x]$

这道题 Java 版的莫队怎么都 tle，实在是没办法了，用 c 过的，就改一下莫队的 remove 和 add 函数即可

代码展开目录

Java展开目录

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(l > q[i].l) add(--l);//加入数字
            while(r < q[i].r) add(++r);//加入数字
            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;
    }
}

C++展开目录

#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;
}
void add(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 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) add(++r);
        while(r > g[i].r) del(r--);
        while(l < g[i].l) del(l++);
        while(l > g[i].l) add(--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;
}