【CF86D】Powerful array

2023-10-07 15:58

文章标签 array powerful cf86d

本文主要是介绍【CF86D】Powerful array，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

莫队裸题
每次加入一个a[i]，ans=ans-k(a[i])^2*a[i]+(k(a[i])+1)^2*a[i]，去掉一个a[i]同理，都能在O(1)的时间里完成转移。我做的时候把这个式子化开来了，用的位运算。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 2000005
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
struct query{int l,r,id;} q[N];
int block_pos[N],sum[N*10],c[N];
ll res[N];
int n,m,i,block,l,r,p;
ll ans,k;
bool cmp(const query &a,const query &b)
{if (block_pos[a.l] == block_pos[b.l]) return a.r < b.r;return a.l < b.l;
}
ll sqr(ll x) {return x*x;}
void update1(int p)
{ans += (sum[c[p]]<<1|1) * c[p];sum[c[p]]++;
}
void update2(int p)
{ans -= ((sum[c[p]]<<1)-1) * c[p];sum[c[p]]--;
}
inline int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int main()
{scanf("%d%d",&n,&m);fo(i,1,n) scanf("%d",&c[i]);fo(i,1,m) scanf("%d%d",&q[i].l,&q[i].r);fo(i,1,m) q[i].id = i;block = sqrt(n);fo(i,1,n) block_pos[i] = (i - 1) / block + 1;sort(q+1,q+m+1,cmp);l = 1; r = 0;fo(i,1,m){while (r < q[i].r) {update1(r+1); r++;}while (r > q[i].r) {update2(r); r--;}while (l < q[i].l) {update2(l); l++;}while (l > q[i].l) {update1(l-1); l--;}res[q[i].id] = ans;}fo(i,1,m) printf("%I64d\n",res[i]);return 0;   
}