题解 P7527 【[USACO21OPEN] United Cows of Farmer John G】

· · 题解

题目传送门

题目大意：

求区间 [l,r] 的数的种类。

对于以i为开头的方案数，只要保证让结尾不等于这段区间的数字，也即让结尾是该数字靠前出现的位置。

代码实现

可以从 n 到 1 枚举开头。

不断更新靠前的位置。

更改：

定义数组 tree 表示种类数，当有一个新元素加入时，现将上一个位置上的种类数 -1，然后再让新加入的位置种类数 +1。

（一开始的位置可以设置成 n+1 ）

查询：

先前位置的前一个元素的种类数。

时间复杂度： \mathcal{O}_{nlogn}

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack> 
#define lowbit(x) x & -x;
#define int long long 
#define N 400010
using namespace std;
int re() {
    int p=0; char i=getchar();
    while(i<'0'||i>'9') i=getchar();
    while(i>='0'&&i<='9')   p=p*10+i-'0',i=getchar();
    return p;
}
int n,ans;
int a[N],f[N];
int tree[N];
int ask(int x) {
    int sum=0;
    while(x>0) {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}
void add(int x,int k)
{
    while(x<=2*n) {
        tree[x]+=k;
        x+=lowbit(x);
    }   
}
signed main()
{
    n=re();
    for(int i=1;i<=n;i++) {
        a[i]=re();
        f[i]=n+1;
    }
    for(int i=n;i>=1;i--)
    {
        ans+=ask(f[a[i]]-1);
        add(f[a[i]],-1);
        f[a[i]]=i;
        add(f[a[i]],1);
    }
    cout<<ans<<endl;
}

如有不妥，请不要吝啬您的评论。

qwq

双倍经验

三倍经验