CodeForces-86D Powerful array
题意: 给定一个区间计算power值, power[l, r] = sigma(sum[pi]*sum[pi]*pi).
分析: 莫队来做, 对于add操作, 要累加的值为(sum[a[x]]*2 + 1)*a[x], del操作减去就行. 这个规律很好发现. 这道题卡常, 乘法用位操作替代. 输出一定要I64d, 否则TLE.
代码:
#include <bits/stdc++.h>using namespace std;const int MAXN = 2e5 + 10;
const int MAXM = 1e6 + 10;
struct Query
{int l, r, id;
} Q[MAXN];int L = 1, R = 0;
long long Ans = 0;
long long ans[MAXN];
int flag[MAXM], pos[MAXN], a[MAXN];
int n, m;
bool cmp(Query x, Query y)
{if (pos[x.l] == pos[y.l]){return x.r < y.r;}else{return pos[x.l] < pos[y.l];}
}
inline int read()
{int x = 0;char ch = getchar();while (ch < '0' || ch > '9')ch = getchar();while (ch <= '9' && ch >= '0'){x = x * 10 + ch - '0';ch = getchar();}return x;
}inline void add(int x)
{Ans += (((long long)(flag[a[x]]) << 1) + 1) * a[x];flag[a[x]]++;return;
}inline void del(int x)
{flag[a[x]]--;Ans -= (((long long)(flag[a[x]]) << 1) + 1) * a[x];return;
}
int main()
{// cin.sync_with_stdio(false);// cin.tie(0);//scanf("%d%d", &n, &m);//cin >> n >> m;n = read();m = read();int unit = sqrt(1.0 * n);for (int i = 1; i <= n; i++){//cin >> a[i];a[i] = read();pos[i] = i / unit + 1;}for (int i = 1; i <= m; i++){Q[i].l = read();Q[i].r = read();Q[i].id = i;}sort(Q + 1, Q + m + 1, cmp);for (int i = 1; i <= m; i++){if (Q[i].l == Q[i].r){ans[Q[i].id] = 1l * a[Q[i].l];continue;}while (L < Q[i].l){del(L++);//L++;}while (L > Q[i].l){//L--;add(--L);}while (R < Q[i].r){//R++;add(++R);}while (R > Q[i].r){del(R--);//R--;}ans[Q[i].id] = Ans;}for (int i = 1; i <= m; i++){printf("%I64d\n", ans[i]);// cout << ans[i] << endl;}return 0;
}