CF86D Powerful array

CF86D Powerful array

題意：給出一個n個數組成的數列a，有t次詢問，每次詢問為一個[l,r]的區間，求區間内每種數字出現次數的平方×數字的值 的和。 輸入：第一行2個正整數n,t。 接下來一行n個正整數，表示數列a1a_1a1​~ana_nan​的值。 接下來t行，每行兩個正整數l,r，為一次詢問。 輸出：t行，分别為每次詢問的答案。

思路：一眼莫隊

搞清楚維護啥

維護出現次數

相鄰兩次轉移注意先減oldoldvalue再加上newnewval

其它沒啥，就是一個一般的莫隊

#include<bits/stdc++.h>
using namespace std;
const int N=200005;
typedef long long ll;
struct node{
 int l,r;
 int Rk;
 int ans;
};
int n,m;
int col[N];
int b[N];
int u;
int l,r;
ll happen[N*5];
ll ans;
node s[N]; 
ll anw[N];
bool cmp(node x,node y){
 if(b[x.l]==b[y.l]) return x.r<y.r;
 return x.l<y.l;
}
bool kmp(node x,node y){
 return x.Rk<y.Rk;
}
int main(){
 while(~scanf("%d%d",&n,&m)){
  memset(anw,0,sizeof(anw));
  ans=0;
  memset(happen,0,sizeof(happen));
  u=sqrt(n);
  for(int i=1;i<=n;i++) b[i]=(i/u)+1;
  for(int i=1;i<=n;i++) scanf("%d",&col[i]);
  for(int i=1;i<=m;i++) {scanf("%d%d",&s[i].l,&s[i].r);s[i].Rk=i;s[i].ans=0;}
  sort(s+1,s+m+1,cmp);
  for(int i=1;i<=m;i++){
   if(i==1){
    for(int j=s[i].l;j<=s[i].r;j++){
     happen[col[j]]++;
     ans=ans-(happen[col[j]]-1)*(happen[col[j]]-1)*col[j]+happen[col[j]]*happen[col[j]]*col[j];
    }
    l=s[i].l;
    r=s[i].r;
   }
   else{
    while(l<s[i].l){
     l++;
     happen[col[l-1]]--;
     ans=ans-(happen[col[l-1]]+1)*(happen[col[l-1]]+1)*col[l-1]+happen[col[l-1]]*happen[col[l-1]]*col[l-1];
    }
    while(l>s[i].l){
     l--;
     happen[col[l]]++;
     ans=ans-(happen[col[l]]-1)*(happen[col[l]]-1)*col[l]+happen[col[l]]*happen[col[l]]*col[l];
    }
    while(r<s[i].r){
     r++;
     happen[col[r]]++;
     ans=ans-(happen[col[r]]-1)*(happen[col[r]]-1)*col[r]+happen[col[r]]*happen[col[r]]*col[r];
    }
    while(r>s[i].r){
     r--;
     happen[col[r+1]]--;
     ans=ans-(happen[col[r+1]]+1)*(happen[col[r+1]]+1)*col[r+1]+happen[col[r+1]]*happen[col[r+1]]*col[r+1];
    }
   }
   anw[s[i].Rk]=ans;
  }
  sort(s+1,s+m+1,kmp);
  for(int i=1;i<=m;i++){printf("%lld\n",anw[i]);}
 }
  
 return 0;
}