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 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

【SAS Says】基础篇:开发数据

特别说明:本节【SAS Says】基础篇:开发数据,用的是数说君学习《The little SAS book》时的中文笔记,我们认为这是打基础的最好选择。 转载...

3516
来自专栏李智的专栏

pandas多表操作,groupby,时间操作

使用场景:有两张表left和right,一般要求它们的表格结构一致,数据量也一致,使用right的数据去填补left的数据缺漏 如果在同一位置left与ri...

1501
来自专栏Java成神之路

Java_util_02_Java判断字符串是中文还是英文

做微信开发,使用百度翻译API时,需要指定译文的语种。这就需要我们判断待翻译内容是中文还是英文,若是中文,则翻译成英文,若是英文则翻译成中文。

1235
来自专栏机器学习入门

POJ 刷题系列:3094. Quicksum

POJ 刷题系列:3094. Quicksum 传送门:POJ 3094. Quicksum 题意: 给定一个字符串S,且A = 1, B = 2…. 空格 ...

19010
来自专栏数据结构与算法

3149 爱改名的小融 2

3149 爱改名的小融 2 时间限制: 2 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description W...

3635
来自专栏小樱的经验随笔

51 Nod 1005 大数加法【Java大数乱搞,python大数乱搞】

1005 大数加法 基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题 给出2个大整数A,B,计算A+B的结果。 Input 第1行:...

3849
来自专栏水击三千

SQL Server 2008 geometry 数据类型

摘自SQL Server 2008帮助 平面空间数据类型 geometry 是作为 SQL Server 中的公共语言进行时 (CLR) 数据类型实现的。此类型...

2616
来自专栏乐百川的学习频道

Python学习笔记 异常处理

Python和很多其他语言一样,支持异常处理。我们可以使用try-catch类似的形式捕获异常,处理异常,或者抛出异常。Python的异常命名惯例和Java语言...

2015
来自专栏小樱的经验随笔

Codeforces 791B Bear and Friendship Condition(DFS,有向图)

B. Bear and Friendship Condition time limit per test:1 second memory limit per t...

3609
来自专栏Danny的专栏

设计模式奠基石——UML关系转化为代码

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/huyuyang6688/article/...

2043

扫码关注云+社区

领取腾讯云代金券