题解

一次询问不是只求前缀中有几种类别，而是把前缀内每个非空区间的不同类别数加起来．记询问答案为 $F(x)$．同一种类别在一个区间里出现多次，也只贡献一次，这是统计时需要处理的重复．

以下用 $V=2\times10^5$ 表示类别编号上界．

算法 0：枚举区间

对于一次询问，枚举左端点 $l$，从 $l$ 向右扫描到 $x$，用出现标记维护当前不同类别数．每增加一个右端点，把当前不同类别数累加到答案．每个区间恰好枚举一次，直接符合定义．替换操作直接改数组．

时间复杂度为 $O(qn^2+V)$，空间复杂度为 $O(n+V)$．出现标记可以用时间戳清空，避免每换一个左端点就清空整个值域．

预期通过子任务 1，获得 10 分．

算法 1：每次询问线性扫描

先考虑当前数组不变时，如何一次求出所有前缀的答案．设 $pre_i$ 是 $i$ 前面最后一个与 $a_i$ 同类的位置；不存在则为 $0$．

记 $H_i$ 为所有以 $i$ 为右端点的区间的丰富度之和．把以 $i-1$ 为右端点的区间都延长一位，再加入单点区间 $[i,i]$．对于左端点 $l\le pre_i$ 的区间，类别 $a_i$ 已经出现，不会增加丰富度；对于 $pre_i<l\le i$ 的区间，这个类别是新出现的．后一种共有 $i-pre_i$ 个，因此

$$H_i=H_{i-1}+i-pre_i,\qquad F(i)=F(i-1)+H_i.$$

从左向右扫描时，用每种类别最后出现的位置即可求出 $pre_i$．每次询问都重新扫描前 $x$ 项，时间复杂度为 $O(nq+V)$，空间复杂度为 $O(n+V)$．同样可以用时间戳避免每次清空长度为 $V$ 的数组．

预期通过子任务 1、2，获得 25 分．

算法 2：没有替换

子任务 3 中数组始终不变．用上一节的递推一次算出 $F(1),F(2),\ldots,F(n)$，之后每次询问直接查表．

时间复杂度为 $O(n+q+V)$，空间复杂度为 $O(n+V)$．预期通过子任务 3，获得 15 分．如果与前两节的程序按输入条件分别处理，可以获得 40 分．

算法 3：询问始终覆盖整个序列

为了处理替换，改为统计每个位置的贡献．对于区间 $[l,r]$ 内的一种类别，只把它计在该类别在区间内第一次出现的位置上．这样每个类别恰好被计一次．

位置 $i$ 能代表它所在的类别，当且仅当

$$pre_i<l\le i\le r\le x.$$

当 $i\le x$ 时，左端点有 $i-pre_i$ 种选择，右端点有 $x-i+1$ 种选择．因此

$$F(x)=\sum_{i=1}^{x}(i-pre_i)(x-i+1).$$

子任务 4 中 $x$ 固定为 $n$，每个位置的贡献就是 $(i-pre_i)(n-i+1)$．可以用一个变量维护全部贡献之和．

将位置 $p$ 从旧类别中移走，会使旧类别中 $p$ 的后一个出现位置的前驱改变；将 $p$ 放入新类别，会使新类别中 $p$ 的后一个出现位置的前驱改变．此外，$p$ 自己的前驱也会改变．其他位置的前驱都不变．

为每种类别维护一个存储出现位置的有序集合，就能找到这些前驱、后继．每次替换只需去掉受影响位置的旧贡献，再加入新贡献．缺少后继时不做对应修改；替换成原类别时直接跳过．

初始化时间 $O(n\log n+V)$，每次替换 $O(\log n)$，每次询问 $O(1)$，总时间 $O((n+q)\log n+V)$，空间 $O(n+V)$．

预期通过子任务 4，获得 20 分．这条路径已经解决了“修改只影响少量前驱”的主要问题，还没有处理任意前缀询问．

算法 4：同类展品连成一段

在特殊性质 A 下，一个区间中的不同类别数，等于其中同类连续段的数量．从区间左端开始，先计一段；之后每遇到一次相邻类别不同，就多出一段．没有这种性质时，同一类别可能隔开再次出现，这个等式就不成立．

令 $b_j=[a_j\ne a_{j+1}]$，其中 $1\le j<n$．前缀 $[1,x]$ 有 $x(x+1)/2$ 个非空区间，每个先贡献 $1$．对于分界 $j<x$，包含其左右两个位置的区间恰好满足 $l\le j$、$r\ge j+1$，共有 $j(x-j)$ 个．所以

$$F(x)=\frac{x(x+1)}2+\sum_{j=1}^{x-1}b_jj(x-j) =\frac{x(x+1)}2+x\sum_{j=1}^{x-1}b_jj-\sum_{j=1}^{x-1}b_jj^2.$$

用两棵树状数组维护 $b_jj$ 和 $b_jj^2$ 的前缀和．替换位置 $p$ 只可能改变分界 $p-1$ 和 $p$，不需要维护每种类别的有序集合．题目保证替换后仍满足性质，不需要自行检查输入是否合法．

时间复杂度为 $O((n+q)\log n)$，空间复杂度为 $O(n)$．

预期通过子任务 5，获得 15 分．这一性质把“前驱”简化为“是否与紧邻位置相同”，可以先完成贡献公式和树状数组部分．

算法 5：完整做法

回到一般情况，把算法 3 的公式按与 $x$ 有关的部分展开：

$$F(x)=(x+1)\sum_{i=1}^{x}(i-pre_i)-\sum_{i=1}^{x}i(i-pre_i).$$

令 $d_i=i-pre_i$．两棵树状数组分别维护 $d_i$ 和 $i d_i$，询问时求两次前缀和即可．替换时仍用算法 3 的有序集合，最多修改三个位置的 $pre_i$；每改变一个 $pre_i$，就把 $d_i$ 的变化量以及乘上 $i$ 后的变化量加入两棵树状数组．

实现中的顺序是：

1. 找到旧类别的后继，把它的前驱改为 $p$ 原来的前驱，然后删除旧集合中的 $p$．
2. 在新类别集合中找到 $p$ 应插入的位置，得到新的前驱和后继．把新后继的前驱改为 $p$．
3. 更新 $p$ 自己的前驱，插入新集合，并修改 $a_p$．

旧类别与新类别不同，所以两边的后继不会是同一个位置．对于未受影响的位置，前面最近的同类位置不变；对受影响的位置，以上步骤恢复了正确的前驱．由此，每次操作后树状数组维护的始终是真实的 $d_i$ 与 $id_i$．结合每个区间内每种类别由其第一次出现位置唯一代表的计数证明，询问公式得到的就是所求答案．

初始化及所有操作总时间为 $O((n+q)\log n+V)$，空间为 $O(n+V)$．全部有序集合总共只存 $n$ 个位置，不是 $nV$ 个．

当所有类别不同且 $x=n$ 时，答案最大，为所有区间长度之和 $n(n+1)(n+2)/6$．所有贡献、乘法以及答案都需要使用 long long．

预期通过所有子任务，获得 100 分．

参考代码

#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
using ll = long long;
const int V = 200000;
struct BIT {
    int n;
    vector<ll> t;
    BIT(int n): n(n), t(n+1) {}
    void add(int p,ll v) { for (;p<=n;p+=p&-p) t[p]+=v; }
    ll sum(int p) { ll s=0; for (;p;p-=p&-p) s+=t[p]; return s; }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q; cin>>n>>q;
    vector<int> a(n+1),pre(n+1),last(V+1);
    vector<set<int>> pos(V+1);
    BIT b1(n),b2(n);
    auto change = [&](int p,int previous) {
        ll delta=pre[p]-previous;
        b1.add(p,delta); b2.add(p,delta*p);
        pre[p]=previous;
    };
    for (int i=1;i<=n;i++) {
        cin>>a[i]; pre[i]=last[a[i]]; last[a[i]]=i;
        pos[a[i]].insert(i);
        ll d=i-pre[i]; b1.add(i,d); b2.add(i,d*i);
    }
    while (q--) {
        int op,p; cin>>op>>p;
        if (op==2) {
            ll ans=(p+1LL)*b1.sum(p)-b2.sum(p);
            cout<<ans<<'\n'; continue;
        }
        int v; cin>>v;
        if (v==a[p]) continue;
        auto &old=pos[a[p]];
        auto it=old.find(p), nxt=next(it);
        if (nxt!=old.end()) change(*nxt,pre[p]);
        old.erase(it);
        auto &now=pos[v];
        it=now.lower_bound(p);
        int previous=it==now.begin()?0:*prev(it);
        if (it!=now.end()) change(*it,p);
        change(p,previous);
        now.insert(p); a[p]=v;
    }
}