CF848C Goodbye Souvenir

Arahc 11.0
  2022-01-04 08:00 2022-01-04 08:00 创建   2023-03-15 14:16:12 2023-03-15 14:16:12 更新      1.8k 字  9 分钟  

题面

简化题意

给定一个长度为 nn 的数组，多组操作，每组操作为修改一个数的值，或者查询区间内所有数的权值和。

一个数的权值为其在区间中第一次和最后一次出现的下标差，相同数字权值只计算一次。

n,q,ai≤105n,q,a_i\leq 10^5

题解

询问和数值大小无关，把填数看成染色。设一段查询区间内，某个颜色出现的位置分别为 i1,i2,i3,⋯ ,imi_1,i_2,i_3,\cdots,i_m。

根据定义，这个颜色产生的贡献是 im−i1i_m-i_1。这就让中间的一堆数没有参与贡献计算，不方便维护，这不好。但是我们发现：

(i2−i1)+(i3−i2)+(i4−i3)+⋯+(im−im−1)=im−i1(i_2-i_1)+(i_3-i_2)+(i_4-i_3)+\cdots+(i_m-i_{m-1})=i_m-i_1

因此对于每一个颜色，设其位于位置 ii，则找到其上一次出现的位置（若不存在，则为 00）preipre_i。题目转化为：给定区间 [l,r][l,r]，求 ∑i−prei\sum i-pre_i，其中 l≤prei<i≤rl\leq pre_i<i\leq r。

我们将一个位置扩展成一个二维平面上的点，设其位置为 ii，则以 ii 为横坐标，preipre_i 为纵坐标。那么符合条件的点就位于左下角为 (l,l)(l,l)，右上角为 (r,r)(r,r) 的矩形内。不妨再给每个点赋予一个权值 i−preii-pre_i，询问就转化为查询矩阵内点权和。就是经典的数点问题了。

需要注意的是单点修改会产生什么影响，设位置 ii 的颜色从 aa 被修改为 bb。从 aa 颜色看，这个点被删除了，随之影响了它右边的第一个颜色为 aa 的点的 prepre 改变了。从 bb 颜色看，新增了一个点，随之影响的也是它右边第一个颜色为 bb 的点的 prepre。

开 nn 个 set 维护每一个颜色的位置，就可以快速查询与修改下标 ii 的前驱后继。数点用 KDTree 维护即可。

还补充一个简单小 Trick，KDTree 写删除的确有些烦人，但是因为我们要查询的是点权和，因此不妨直接在原位置上加一个点，权值为原来的相反数就行了；修改一个点权等价于删除这个点再加一个点。如果怕加入的点过多导致爆炸，就写一个特判，如果两个点位置相同就合并权值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int max_n=600005;
inline int read(){
    int x=0;bool w=0;char c=getchar();
    while(c<'0' || c>'9') w|=c=='-',c=getchar();
    while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return w?-x:x;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10^48);
}
inline bool interv(int mid,int l,int r){
    if(l<=mid && mid<=r) return 1;
    return 0;
}

int n,m,a[max_n],pre[max_n],nxt[max_n];

struct point{
    int x,y,val;
    point(){x=y=val=0;}
    bool operator == (const point &b) const{
        point a=*this;
        return (a.x==b.x && a.y==b.y);
    }
}pos[max_n];
inline point makep(int a,int b,int c){
    point res;
    res.x=a,res.y=b,res.val=c;
    return res;
}
bool cmpt=0;
inline bool cmp(point i,point j){
    if(cmpt) return i.x<j.x;
    return i.y<j.y;
}
int fre[max_n],tp;
struct KD_Tree{
    const double alpha=0.75;
    int root,tot,tmp;
    bool chgr;
    KD_Tree(){root=tot=tmp=0;}
    inline int newnode(){
        int x;
        if(tp) x=fre[tp--];
        else x=++tot;
        return x;
    }
    struct dot{
        point x,l,r;
        int tp,sz,ls,rs;ll sm;
        dot(){tp=sz=ls=rs=sm=0;}
    }a[max_n];
    #define ls(x) (a[x].ls)
    #define rs(x) (a[x].rs)
    inline void pushup(int x){
        a[x].l=a[x].r=a[x].x,a[x].sm=a[x].x.val;
        a[x].sz=a[ls(x)].sz+a[rs(x)].sz+1;
        if(ls(x)){
            a[x].sm+=a[ls(x)].sm;
            a[x].l.x=min(a[x].l.x,a[ls(x)].l.x),a[x].r.x=max(a[x].r.x,a[ls(x)].r.x);
            a[x].l.y=min(a[x].l.y,a[ls(x)].l.y),a[x].r.y=max(a[x].r.y,a[ls(x)].r.y);
        }
        if(rs(x)){
            a[x].sm+=a[rs(x)].sm;
            a[x].l.x=min(a[x].l.x,a[rs(x)].l.x),a[x].r.x=max(a[x].r.x,a[rs(x)].r.x);
            a[x].l.y=min(a[x].l.y,a[rs(x)].l.y),a[x].r.y=max(a[x].r.y,a[rs(x)].r.y);
        }
    }
    inline int build(int l,int r,int t){
        int x=newnode(),mid=(l+r)>>1;
        cmpt=t;
        nth_element(pos+l,pos+mid,pos+r+1,cmp);
        a[x].tp=t,a[x].x=pos[mid],ls(x)=rs(x)=0;
        if(l<=mid-1) ls(x)=build(l,mid-1,t^1);
        if(r>=mid+1) rs(x)=build(mid+1,r,t^1);
        pushup(x);
        return x;
    }
    inline void get(int x){
        if(ls(x)) get(ls(x));
        pos[++tmp]=a[x].x,fre[++tp]=x;
        if(x==root) chgr=1;
        if(rs(x)) get(rs(x));
    }
    inline void rebuild(int &x){
        if(alpha*a[x].sz>max(a[ls(x)].sz,a[rs(x)].sz)) return;
        tmp=0,chgr=0;
        get(x),x=build(1,tmp,0);
        if(chgr) root=x;
    }
    inline void insert(int &x,point pt,int t){
        if(!x){
            x=newnode();
            a[x].sz=1,a[x].x=pt,a[x].tp=t;
            pushup(x);
            return;
        }
        if(pt==a[x].x){ // 小 Trick
            a[x].x.val+=pt.val;
            pushup(x);
            return;
        }
        cmpt=t;
        if(cmp(pt,a[x].x)) insert(ls(x),pt,t^1);
        else insert(rs(x),pt,t^1);
        pushup(x),rebuild(x);
    }
    inline ll ask(int x,point i,point j){
        if(!x || a[x].l.x>j.x || a[x].r.x<i.x || a[x].l.y>j.y || a[x].r.y<i.y) return 0;
        if(a[x].l.x>=i.x && a[x].r.x<=j.x && a[x].l.y>=i.y && a[x].r.y<=j.y)
            return a[x].sm;
        ll res=0;
        if(interv(a[x].x.x,i.x,j.x) && interv(a[x].x.y,i.y,j.y)) res+=a[x].x.val;
        res+=ask(ls(x),i,j)+ask(rs(x),i,j);
        return res;
    }
}kdt;

set<int> st[max_n];
inline int Pre(int x,int col){ // 查询前驱
    auto it=st[col].lower_bound(x);
    --it;
    return *it;
}
inline int Nxt(int x,int col){ // 查询后继
    return *(st[col].upper_bound(x));
}

signed main(){
    n=read(),m=read();
    for(register int i=1;i<=n;++i)
        st[i].insert(0),st[i].insert(n+1);
    for(register int i=1;i<=n;++i){
        a[i]=read(),st[a[i]].insert(i);
        pre[i]=Pre(i,a[i]);
        kdt.insert(kdt.root,makep(i,pre[i],i-pre[i]),0);
    }
    for(register int i=1;i<=n;++i)
        nxt[i]=Nxt(i,a[i]);
    while(m--){
        int op=read();
        if(op==1){
            int i=read(),val=read();
            kdt.insert(kdt.root,makep(i,pre[i],pre[i]-i),0),
            kdt.insert(kdt.root,makep(nxt[i],i,i-nxt[i]),0);
            // 先把原颜色的的点删掉
            st[a[i]].erase(i),st[val].insert(i);
            pre[nxt[i]]=pre[i],nxt[pre[i]]=nxt[i];
            // 修改原颜色的前驱后继关系
            kdt.insert(kdt.root,makep(nxt[i],pre[i],nxt[i]-pre[i]),0);
            // 修改原颜色的点权
            a[i]=val;
            pre[i]=Pre(i,a[i]),nxt[i]=Nxt(i,a[i]);
            // 更新这个点前驱后继关系
            kdt.insert(kdt.root,makep(nxt[i],pre[nxt[i]],pre[nxt[i]]-nxt[i]),0);
            nxt[pre[i]]=pre[nxt[i]]=i;
            kdt.insert(kdt.root,makep(i,pre[i],i-pre[i]),0),
            kdt.insert(kdt.root,makep(nxt[i],i,nxt[i]-i),0);
            // 更新新颜色前驱后继关系和权值
        }
        if(op==2){
            int l=read(),r=read();
            write(kdt.ask(kdt.root,makep(l,l,0),makep(r,r,0))),putchar('\n');
        }
    }
    return 0;
}
  • 标题: CF848C Goodbye Souvenir
  • 作者: Arahc
  • 创建于 : 2022-01-04 08:00:00
  • 更新于 : 2023-03-15 14:16:12
  • 链接: https://arahc.github.io/2022/01/04/【题解】CF848C-Goodbye-Souvenir/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
CF848C Goodbye Souvenir
  1. 题面
  2. 题解
  3. 代码