[NOI Online #2 提高组] 游戏

题面

给你一个长度为 \(n\) 的序列 \(\{a_i\}\)，定义 \(f(l,r)\) 为 \([l,r]\) 不同整数的个数，求 $$\sum_{1\le l \le n}\sum_{l\le r\le n}f(l,r)$$

题解

设 $$f(l,r)=\sum_{i=l}^{r} [pre_i<l]$$其中 \(pre_i\) 为 上一次出现 \(a_i\) 的位置。

我们拆括号，考虑每一项的贡献。

对于形如 \([pre_i<l]^2\) 的平方项，对结果产生的贡献是 \(pre_i<l\le i\) 且 \(r\ge i\) 的二元组 \((l,r)\) 的个数，即 \((i-pre_i)\times (n-i+1)\)。

对于形如 \(2[pre_i<l][pre_j<l]\) 的平方项，我们发现 \([pre_i<l]\) 和 \([pre_j<l]\) 是两个独立的条件，所以直接套用上面的式子，对结果产生的贡献是满足 \(i\) 和 \(j\) 的区间的交集。

我们依次考虑 \(a_1,a_2,\cdots,a_n\) 和之前所有数的贡献。

对于 \(pre_j<pre_i\) 的 \(j\)，\(l\) 可选的范围是 \((pre_j,j]\)，\(r\) 可选的范围是 \([i,n]\)，对于 \(pre_j\ge pre_i\) 的 \(j\)，\(l\) 可选的范围是 \((pre_i,j]\)，不难发现是一个 \(\mbox{min}\) 卷积的形式，按照上一场考试第二题的经验，我们可以用树状数组维护。

具体的，求的是 \(\sum_{j<i \land pre_j<pre_i} (j-pre_j)\) 和 \(\sum_{j<i \land pre_j\ge pre_i} (pre_i-j)=(\sum_{j<i\land pre_j\ge pre_i}1)\times pre_i-\sum_{j<i \land pre_j\ge pre_i}j\)，就可以用树状数组搞定了。

但是我们还有一个问题，就是第二种情况中，如果 \(pre_i<j\) ，结果应该是 \(0\)，而不是这个负的东西，所以重新定义 \(j\) 为 \(pre_i\le j<i\) 的所有数，直接按原来的方法算，最后再用前缀和减一下就行了。

#include<bits/stdc++.h>
#define N 1005000
#define ri register int
#define LL long long 
#define mod 1000000007
using namespace std;

inline int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch<‘0‘ || ch>‘9‘) f|=(ch==‘-‘),ch=getchar();
  while (ch>=‘0‘ && ch<=‘9‘) ret*=10,ret+=ch-‘0‘,ch=getchar();
  return f?-ret:ret;
}

int n,a[N],aw[N],ton[N],pre[N];
struct node {
  int x,v;
  bool operator < (const node &rhs) const {
    return x<rhs.x;
  }
} b[N];

int add(int a,int b) {
  a+=b; if (a>=mod) a-=mod;
  return a;
}

int mul(int a,int b) {
  LL c=a; c*=b;
  return (int)(c%mod);
}

struct szsz {
  int t1[N],t2[N],t3[N];
  void insert(int x,int v) {
    int tx=x; x++;
    for (ri i=x;i<=n+1;i+=(i&(-i))) t1[i]++;
    for (ri i=x;i<=n+1;i+=(i&(-i))) t2[i]=add(t2[i],v);
    for (ri i=x;i<=n+1;i+=(i&(-i))) t3[i]=add(t3[i],v-tx);
  }
  int findgeval2(int x) {
    int ret1=0;
    for (ri i=n+1;i;i-=(i&(-i))) ret1=add(ret1,t3[i]);
    int ret2=0;
    for (ri i=x;i;i-=(i&(-i))) ret2=add(ret2,t3[i]);
    return add(ret1,mod-ret2);
  }

  int findlcount(int x) {
    int ret=0;
    for (ri i=x;i;i-=(i&(-i))) ret=add(ret,t1[i]);
    return ret;
  }

  int findlval1(int x) {
    int ret=0;
    for (ri i=x;i;i-=(i&(-i))) ret=add(ret,t2[i]);
    return ret;
  }

  void clear() {
    for (ri i=0;i<=n+1;i++) t1[i]=t2[i]=t3[i]=0;
  }
} t;

int main() {
  n=read();
  for (ri i=1;i<=n;i++) a[i]=read();
  for (ri i=1;i<=n;i++) aw[i]=a[i];
  sort(aw+1,aw+n+1);
  int nw=unique(aw+1,aw+n+1)-aw-1;
  for (ri i=1;i<=n;i++) a[i]=lower_bound(aw+1,aw+nw+1,a[i])-aw;
  for (ri i=1;i<=n;i++) {
    pre[i]=ton[a[i]];
    ton[a[i]]=i;
  }
  int ret=0;
  for (ri i=1;i<=n;i++) {
    int a3=t.findgeval2(pre[i]);
    int a1=t.findlcount(pre[i]),a2=t.findlval1(pre[i]);
    ret=add(ret,mul(2,mul(a3,n-i+1)));
    ret=add(ret,mul(2,mul(add(a2,mod-mul(pre[i],a1)),n-i+1)));
    t.insert(pre[i],i);
  }
  t.clear();
  for (ri i=1;i<=n;i++) b[i]=(node){pre[i],i};
  sort(b+1,b+n+1);
  for (ri i=1,j=1;i<=n;i++) {
    while (j<=b[i].x) t.insert(pre[j],j),j++;
    int a1=t.findlcount(pre[b[i].v]),a2=t.findlval1(pre[b[i].v]);
    ret=add(ret,mod-mul(mul(2,add(a2,mod-mul(pre[b[i].v],a1))),n-b[i].v+1));
  }
  for (ri i=1;i<=n;i++) ret=add(ret,mul(i-pre[i],n-i+1));
  cout<<ret<<endl;
  return 0;
}

[NOI Online #2 提高组] 游戏

原文：https://www.cnblogs.com/shxnb666/p/12812928.html