大意是是说,问区间[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; }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句