Steven_MengのBlog

传送门

首先,假设你会了不带修改的莫队(不会出门右拐百度)

我们来想一想莫队如何支持修改,我们把查询和修改操作离线下来,如图,将查询标为蓝色,将修改标为红色。

假设我们要查询六号查询的答案,考虑哪些修改会影响答案,肯定是在六号之前的修改,且这些修改的下标$ind$在六号查询的区间$[l,r]$之内,如图中$2$,$4$号修改,要把这些修改全部做完,才能得到正确的结果。

所以,我们在每个查询中除了$l,r,id$,还要记录一个$last$,代表最近的修改位置,查询时,我们要把$last$前面的修改全部做完,如代码。

1
2
3
struct Query{
int l,r,id,last;//last为最近的修改位置
}q[MAXN];

同时记录每个修改操作,只用记录修改的下标$ind$和修改的值$val$即可。

1
2
3
struct Update{
int ind,val;//把ind修改成val
}u[MAXN];

为了做带修莫队,我们记录一个指针$p$ ,代表我们把$[1,p]$的修改操作全部做完了,做莫队的时候,除了常规的莫队操作,还要有下面两行:

1
2
while (p<q[i].last) Upd(++p,i);
while (p>q[i].last) Upd(p--,i);

如果操作做少了,那么我们调用$Upd(++p,i)$,多做一次操作,如果操作做少了,我们调用$Upd(p—,i)$,撤销一次操作。

那么这个撤销怎么弄呢?

很容易想到的是,我们在每个$Update$结构体里面再多存一个$flag$,代表当前是增加操作还是撤销操作,如果是撤销操作,那么我们删除$u[p].val$,加入$num[u[p].ind]$,每次操作后,$flag$取反,即撤销操作变成加入操作,加入操作变成撤销操作。

但是呢,这样代码量不但增加,常数也增多了,这道题你可能$TLE$,考虑有没有更加简洁优美的方法替代$flag$。

有!

我们每次操作之后,将$num[u[p].ind]$和$u[p].val$对调,我们再撤销回去的时候,就相当于将$u[p].val$改成$num[u[p].ind]$,非常巧妙。

实现如下,注意只有修改的下标在现在查询范围之内才会对答案造成影响:

1
2
3
4
5
6
inline void Upd(int p,int i){
if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
Del(num[u[p].ind]),Add(u[p].val);//修改,先删去原有的,再加进val
}
swap(num[u[p].ind],u[p].val);
}

注意要加$sort$,(虽然我不加$sort$也卡过)

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int 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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Query{
int l,r,id,last;//last为最近的修改位置
}q[MAXN];
struct Update{
int ind,val;//把ind修改成val
}u[MAXN];
int pos[MAXN],num[MAXN];
inline bool operator < (const Query &x,const Query &y){
if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];
return x.last<y.last;
}
int cntq,cntu;
inline char gc(){
char ch=getchar();
while (ch!='Q'&&ch!='R') ch=getchar();
return ch;
}
int ans,Ans[MAXN];
static int cnt[MAXN];
#define Add(x) (++cnt[x]==1)?++ans:0
#define Del(x) (--cnt[x]==0)?--ans:0
inline void Upd(int p,int i){
if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
Del(num[u[p].ind]),Add(u[p].val);//修改,先删去原有的,再加进val
}
swap(num[u[p].ind],u[p].val);
}
inline void Print(register int x){
if (x>=10ll) Print(x/10ll);
putchar(x%10ll+48ll);
}
inline void print(register int x,const char ch){
if (x<0){x=-x,putchar('-');}
if (x==0){putchar('0');putchar(ch);return ;}
Print(x);putchar(ch);
}
int main(){
int n=read(),m=read();
const int Size=pow(n,(double)0.666666666);
for (register int i=1;i<=n;++i){
num[i]=read();
}
for (register int i=1;i<=m;++i){
char opr=gc();
if (opr=='Q') q[++cntq]=Query{read(),read(),cntq,cntu};
else u[++cntu]=Update{read(),read()};
}
for (register int i=1;i<=n;++i){
pos[i]=(i-1)/Size+1;
}
sort(q+1,q+1+cntq);
register int l=1,r=0;
register int p=0;//修改的操作
for (register int i=1;i<=m;++i){
while (l<q[i].l) Del(num[l++]);
while (l>q[i].l) Add(num[--l]);
while (r<q[i].r) Add(num[++r]);
while (r>q[i].r) Del(num[r--]);
while (p<q[i].last) Upd(++p,i);
while (p>q[i].last) Upd(p--,i);
Ans[q[i].id]=ans;
}
for (register int i=1;i<=cntq;++i){
print(Ans[i],'\n');
}
}

 评论