zcmimi's blog
查看原题

点击跳转

官方:

对于一段区间l~r,其中一个数x对答案的贡献为(2x-l-r)次。

因此我们只要求出所有数对答案的贡献并累加起来即可。

将2x-l-r分为两部分,一部分为求2x的和,即为x左边与x右边相同的数的对数。

另一部分为l+r,将其拆开来,并记录前缀和,对于一个数a[i],我们需要维护的是Σk,Σs[i-1],Σs[i-1]*i,以及a[i]出现的次数就可以了。

这里我们可以在枚举的同时,记录这些信息,并更新答案,就可以了。

复杂度为线性O(n)。

更加详细:

https://www.cnblogs.com/zkGaia/p/6108204.html

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define ll long long 
#define db double
#define uint unsigned int
#define N 3000100
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define swap(T, a, b) ({T ttt = a; a = b; b = ttt;})
int n, lrk[N], rrk[N], pre[N], next[N], pos[N];
uint a[N], decA[N], decB[N], f[N], g[N], Ans = 0;
void G(uint &w) {
   w = 0; char c = getchar();
   while (c > '9' || c < '0') c = getchar();
   while (c >= '0' && c <= '9') { w = w * 10 + c - '0'; c = getchar(); }
}
uint Mult(uint a, uint b){
   uint s = 0; 
   while(b){
      if (b & 1) s += a;
      a += a; b >>= 1;
   }
   return s;
}
int main(){
   scanf("%d", &n);
   for (int i = 1; i <= n; i++)
      G(a[i]);
   memset(pos, 0, sizeof(pos));
   for (int i = 1; i <= n; i++){
      pre[i] = pos[a[i]]; pos[a[i]] = i;
      lrk[i] = lrk[pre[i]] + 1;
      decA[i] = decA[pre[i]] + pre[i];
   }
   memset(pos, 0, sizeof(pos)); 
   for (int i = n; i >= 1; i--){
      next[i] = pos[a[i]]; pos[a[i]] = i;
      rrk[i] = rrk[next[i]] + 1;
      decB[i] = decB[next[i]] + next[i]; 
   }
   for (int i = 1; i <= n; i++){
      if (rrk[i] == 1){
         next[i] = i+n; pre[i+n] = i;
         lrk[next[i]] = lrk[i] + 1; 
         decA[i+n] = decA[i] + i;
      }
      if (lrk[i] == 1){
         pre[i] = i+n*2; next[i+n*2] = i;
         rrk[pre[i]] = rrk[i] + 1; 
         decB[i+n*2] = decB[i] + i;
      }
   }
   for (int i = 1; i <= n; i++)
      f[i] = f[i-1] + i*rrk[i] - decA[next[i-1]];
   for (int i = n; i >= 1; i--)
      g[i] = g[i+1] + i*lrk[i] - decB[pre[i+1]];
   for (int i = 1; i <= n; i++)
      f[i] = f[i] + g[i] - i*2; 
   memset(g, 0, sizeof(g));
   memset(decA, 0, sizeof(decA));
   for (int i = 1; i <= n; i++){
      decA[i] = decA[pre[i]] + (pre[i] >= 1 && pre[i] <= n);
      if (rrk[i] == 1) decA[i+n] = decA[i] + 1;
   }
   for (int i = 1; i <= n; i++){
      g[i] = g[i-1] + rrk[i] - decA[next[i-1]];
      f[i] = Mult(g[i] - 1, i) * 2 - f[i];
      Ans += Mult(f[i], a[i]); 
   }
   std::cout << Ans << std::endl; 
}
51nod 1712 区间求和
comment评论
Search
search