@[LHTCFLS](/user/436107) 可以。
by FastFourierTransform @ 2023-08-23 08:55:16
@[LHTCFLS](/user/436107) 可以套bitset
by 寒烟冷浅暮殇 @ 2023-08-23 08:55:53
带修区间 rank
by cyffff @ 2023-08-23 08:59:51
@[This_is_FFT](/user/806728) 为啥我还是T了3个点？
by Creeper_l @ 2023-08-23 10:28:36
```cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n,m,a[MAXN],len,pre[MAXN],id[MAXN],p[MAXN],num;
int lid[MAXN],rid[MAXN],pos[MAXN],x,y;
char op[3];
inline bool cmp(int x,int y){return x < y;}
inline void Init()
{
for(register int i = 1;i <= n;i++) pre[i] = id[a[i]],id[a[i]] = i;
memcpy(p,pre,sizeof pre);
for(register int i = 1;i <= num;i++)
{
lid[i] = len * (i - 1) + 1,rid[i] = min(n,len * i);
for(int j = lid[i];j <= rid[i];j++) pos[j] = i;
sort(pre + lid[i],pre + rid[i] + 1,cmp);
}
}
inline int Query(int l,int r)
{
int ans = 0;
if(pos[l] == pos[r])
{
for(register int i = l;i <= r;i++) if(p[i] < l) ans++;
return ans;
}
for(register int i = l;i <= rid[pos[l]];i++) if(p[i] < l) ans++;
for(register int i = lid[pos[r]];i <= r;i++) if(p[i] < l) ans++;
for(register int i = pos[l] + 1;i < pos[r];i++) ans += (lower_bound(pre + lid[i],pre + rid[i] + 1,l) - (pre + lid[i]));
return ans;
}
inline void Add(int x,int color)
{
int last = p[x];
for(register int i = x + 1;i <= n;i++)
if(a[i] == a[x])
{
p[i] = last;
int idx = lower_bound(pre + lid[pos[i]],pre + rid[pos[i]] + 1,x) - pre;
pre[idx] = last;
sort(pre + lid[pos[i]],pre + rid[pos[i]] + 1,cmp);
break;
}
a[0] = color;
for(register int i = x - 1;i >= 0;i--)
if(a[i] == color)
{
p[x] = i;
int idx = lower_bound(pre + lid[pos[x]],pre + rid[pos[x]] + 1,last) - pre;
pre[idx] = i;
sort(pre + lid[pos[x]],pre + rid[pos[x]] + 1,cmp);
break;
}
for(register int i = x + 1;i <= n;i++)
if(a[i] == color)
{
int idx = lower_bound(pre + lid[pos[i]],pre + rid[pos[i]] + 1,p[i]) - pre;
p[i] = x;
pre[idx] = x;
sort(pre + lid[pos[i]],pre + rid[pos[i]] + 1,cmp);
break;
}
a[x] = color;
}
signed main()
{
scanf("%d%d",&n,&m);
len = sqrt((double)n);num = ceil(1.0 * n / len);
for(register int i = 1;i <= n;i++) scanf("%d",&a[i]);
Init();
for(register int i = 1;i <= m;i++)
{
scanf("%s%d%d",&op,&x,&y);
if(op[0] == 'Q') printf("%d\n",Query(x,y));
if(op[0] == 'R') Add(x,y);
}
return 0;
}
```
by Creeper_l @ 2023-08-23 10:29:57
可能是用了sort...
by Creeper_l @ 2023-08-23 10:39:21
@[LHTCFLS](/user/436107) 你这个做法带了个log啊，卡卡常试下呢？
by FastFourierTransform @ 2023-08-23 10:44:59
或者写大力合并bitset的做法……？
by FastFourierTransform @ 2023-08-23 10:45:29
好像分块被卡了？我用`bitset`寄了一半的点
by SuperChao @ 2023-09-08 20:14:32