专栏首页mathorCodeForces D.Powerful array(Div.1)

CodeForces D.Powerful array(Div.1)

D. Powerful array

 大意是是说,问区间[L,R]内的的一个值,这个值是arr[x]出现次数cnt[arr[x]]^2^*arr[x]  这道题Java版的莫队怎么都tle,实在是没办法了,用c过的,就改一下莫队的remove和add函数即可

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;
    }
}
#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode215.数组中的第K个最大元素

    mathor
  • 搜索(4)

    mathor
  • BFPRT算法

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

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

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

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

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

    xindoo
  • 图论--LCA--树上倍增法(在线)

    风骨散人Chiam
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • View的工作原理

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

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

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

    attack
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack

扫码关注云+社区

领取腾讯云代金券