题解：AT_jsc2019_final_h Distinct Integers

Purslane · 2025-05-05 22:11:41 · 题解

Solution

线段树单侧递归板子题。

先考虑如果 q=1，怎么做到线性。

对于每个位置，记 lst_p 为上一个和 a_p 相同的值出现的位置，记其前缀最大值数组 LST_p = \max_{i \le p} lst_i。

则 \sum_{p=1}^n p -LST_p 就是答案。正确性是显然的。

发现原题等价于：给定 lst 数组，进行单点修改，或者查询 \sum_{i=l}^r \max\{p,\max_{l \le j \le i}lst_j\}。

看到前缀最大值这种东西，考虑“单侧递归线段树”（套用不了 after god 了 /ll）。

发现和楼房重建简直一模一样，直接维护即可。

怎么有人写线段树不 build 的，你省选就是因为这个调了一年啊啊啊啊。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
int n,q,a[MAXN],lst[MAXN];
set<int> st[MAXN];
#define lson (k<<1)
#define rson (k<<1|1)
#define mid (l+r>>1)
int mx[MAXN<<2];
ll sum[MAXN<<2];
inline ll calc(int k,int l,int r,int p) {
    if(l==r) return max(p,lst[l]);
    if(p>mx[k]) return 1ll*p*(r-l+1);
    if(p>mx[lson]) return 1ll*p*(mid-l+1)+calc(rson,mid+1,r,p);
    return sum[k]-sum[lson]+calc(lson,l,mid,p);
}
void push_up(int k,int l,int r) {return mx[k]=max(mx[lson],mx[rson]),sum[k]=sum[lson]+calc(rson,mid+1,r,mx[lson]),void();}
void build(int k,int l,int r) {
    if(l==r) return mx[k]=sum[k]=lst[l],void();
    build(lson,l,mid),build(rson,mid+1,r);
    return push_up(k,l,r),void();
}
int MX;ll ANS;
void query(int k,int l,int r,int x,int y) {
    if(x<=l&&r<=y) return ANS+=calc(k,l,r,MX),MX=max(MX,mx[k]),void();
    if(x<=mid) query(lson,l,mid,x,y);
    if(y>mid) query(rson,mid+1,r,x,y);
    return ;
}
void modify(int k,int l,int r,int pos,int v) {
    if(l==r) return mx[k]=lst[l]=sum[k]=v,void();
    if(pos<=mid) modify(lson,l,mid,pos,v);
    else modify(rson,mid+1,r,pos,v);
    return push_up(k,l,r),void();
}
int calc_lst(int pos) {
    auto it=st[a[pos]].find(pos);
    if(it==st[a[pos]].begin()) return 0;
    return *(--it); 
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    ffor(i,1,n) cin>>a[i],st[a[i]].insert(i);
    ffor(i,0,n-1) {int lid=0;for(auto id:st[i]) lst[id]=lid,lid=id;}
    build(1,1,n);
    ffor(i,1,q) {
        int op,x,y;
        cin>>op>>x>>y;
        if(op==0) {
            vector<int> cg;
            x++,cg.push_back(x);
            auto it=st[a[x]].find(x);
            if(it!=--st[a[x]].end()) cg.push_back(*(++it));
            st[a[x]].erase(x),a[x]=y,st[a[x]].insert(x);
            it=st[a[x]].find(x);
            if(it!=--st[a[x]].end()) cg.push_back(*(++it));
            for(auto id:cg) modify(1,1,n,id,calc_lst(id));
        }
        else {
            x++,MX=x-1,ANS=0;
            query(1,1,n,x,y);
            cout<<1ll*(x+y)*(y-x+1)/2-ANS<<'\n';
        }
    }
    return 0;
}