摘要:带修莫队

luogu1903[国家集训队]数颜色

题面

题目分析

本来是想了个树状数组套主席树的做法,但是感觉十分不好写,于是去学了带修莫队.

其实也就是在莫队转移的时候加上修改的影响,记录每个距离询问最近的修改,如果在进行询问时,进行的修改改多了,那么就撤销修改,如果改少了,就进行修改.

然后块长$n^{\frac{2}{3}}$理论在带修莫队中是最优的,但是这题常数原因开到$n^{\frac{3}{4}}$更优.

然后在排序的时候用三个关键字,分别是左端点所在块,右端点所在块,查询的编号,尽量让编号小查询的靠前处理让修改尽量少.

在执行完修改后,有个很巧妙的操作,将修改的数和原序列上的数进行了交换,这样就可以直接撤销了.

代码

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
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=150010,large=1000010;
lxl n,m,QCnt,CCnt,nowans,now,_l,_r;
lxl a[big],cnt[large],ans[big],block[big];
struct _Query
{
lxl l,r,pre,id;
inline bool operator <(const _Query &another)const
{
// if(l!=another.l)return block[l]<block[another.l];
// if(r!=another.r)return block[r]<block[another.r];
// return pre<another.pre;
if(block[l]==block[another.l])
if(block[r]==block[another.r])return id<another.id;
else return r<another.r;
else return l<another.l;
}
}q[big];
struct _Modify
{
lxl pos,val;
}c[big];
inline lxl read()
{
lxl x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(lxl x){if(++cnt[x]==1)++nowans;}
inline void del(lxl x){if(--cnt[x]==0)--nowans;}
inline void work(lxl x,lxl i)
{
lxl pos=c[x].pos,val=c[x].val;
lxl l_=q[i].l,r_=q[i].r;
if(pos>=l_&&pos<=r_)
{
if(!(cnt[a[pos]]-1))--nowans;--cnt[a[pos]];
if(!cnt[val])++nowans;++cnt[val];
}
std::swap(c[x].val,a[pos]);
}
int main(void)
{
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
n=read(),m=read();
lxl len=pow(n,0.75);
for(R int i(1);i<=n;++i)a[i]=read(),block[i]=(i-1)/len+1;
for(R int i(1);i<=m;++i)
{
char opt;std::cin>>opt;
if(opt=='Q')
{
lxl x=read(),y=read();
q[++QCnt]=(_Query){x,y,CCnt,QCnt};
}
else
{
lxl x=read(),y=read();
c[++CCnt]=(_Modify){x,y};
}
}
std::sort(q+1,q+1+QCnt);
_l=q[1].l,_r=q[1].l-1;
// _l=1,_r=0;
for(R int i(1);i<=QCnt;++i)
{
lxl nl=q[i].l,nr=q[i].r,nid=q[i].id,npre=q[i].pre;
while(_l>nl)add(a[--_l]);
while(_r>nr)del(a[_r--]);
while(_r<nr)add(a[++_r]);
while(_l<nl)del(a[_l++]);
while(now<npre)work(++now,i);
while(now>npre)work(now--,i);
ans[nid]=nowans;
}
for(R int i(1);i<=QCnt;++i)printf("%lld\n",ans[i]);
return 0;
}