给你 n 个数, m 次询问, Ks 为区间内 s 的数目, 求区间 [L,R] 之间所有 Ks*Ks*s 的和. 1<=n,m<=200000.1<=s<=10^6
- #include <iostream>
- #include <cstdio>
- #include <sstream>
- #include <cstring>
- #include <map>
- #include <set>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #define MOD 2018
- #define LL long long
- #define ULL unsigned long long
- #define Pair pair<int, int>
- #define mem(a, b) memset(a, b, sizeof(a))
- #define _ ios_base::sync_with_stdio(0),cin.tie(0)
- //freopen("1.txt", "r", stdin);
- using namespace std;
- const int maxn = 200050, INF = 0x7fffffff;
- int n, m, pos[maxn], s[maxn*10], c[maxn];
- LL ans;
- struct node
- {
- int l, r, id;
- LL res;
- }Node[maxn];
- bool cmp(node a, node b)
- {
- return pos[a.l] == pos[b.l] ? (a.r <b.r) : (a.l < b.l);
- }
- bool cmp_id(node a, node b)
- {
- return a.id < b.id;
- }
- void add(LL x)
- {
- s[c[x]]++;
- ans += c[x]*(s[c[x]]*s[c[x]] - (s[c[x]]-1)*(s[c[x]]-1));
- }
- void del(LL x)
- {
- s[c[x]]--;
- ans -= c[x]*((s[c[x]]+1)*(s[c[x]]+1) - (s[c[x]])*(s[c[x]]));
- }
- int main()
- {
- ans = 0;
- scanf("%d%d", &n, &m);
- for(int i=1; i<=n; i++)
- scanf("%d", &c[i]);
- int block = sqrt(n);
- for(int i=1; i<=n; i++)
- pos[i] = (i-1)/block + 1;
- for(int i=1; i<=m; i++)
- {
- scanf("%d%d", &Node[i].l, &Node[i].r);
- Node[i].id = i;
- }
- sort(Node+1, Node+1+m, cmp);
- for(int i=1, l=1, r=0; i<=m; i++)
- {
- for(; r < Node[i].r; r++)
- add(r+1);
- for(; r> Node[i].r; r--)
- del(r);
- for(; l <Node[i].l; l++)
- del(l);
- for(; l> Node[i].l; l--)
- add(l-1);
- Node[i].res = ans;
- }
- sort(Node+1, Node+1+m, cmp_id);
- for(int i=1; i<=m; i++)
- printf("%I64d\n", Node[i].res);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2694675.html