上周讲的，补一发。
模版题
我们发现如果一段区间的不同数的个数等于区间长度，那么这个区间中的数就互不相同。
这就是莫队的模版了。
莫队算法
对于这道题目如果我们知道 [l,r] 那么就能 O(1) 求出 [l-1,r]，[l,r-1]，[l+1,r]，[l,r+1] 。
这样大概就是莫队思想了，但是我们发现，最坏情况下复杂度仍为 O(n^2) 。
这里求要用到分块的思想了，我们将 l 按块排序，快相同就按 r 排序，这样复杂度就是 n\sqrt{n} 。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,block,a[N],ans[N],vis[N],l[N],r[N],L=1,R,cnt;
struct node
{
int l,r,id;
}c[N];
bool cmp(node x,node y)
{
if(pos[x.l]/block==pos[y.l]/block) return x.r<y.r;
return pos[x.l]/block<pos[y.l]/block;//按块排序
}
void del(int x)
{
vis[a[x]]--;
if(/*这个数没了*/) cnt--;
}
void add(int x)
{
vis[a[x]]++;
if(/*新多了一个数*/) cnt++;
}
int main()
{
cin>>n>>q;
block=;//确定块的大小
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=q;++i)
{
cin>>c[i].l>>c[i].r;
c[i].id=i;
l[i]=c[i].l;
r[i]=c[i].r;
}
//按块排序
for(int i=1;i<=q;++i)
{
while(L<c[i].l) del(L++);
while(L>c[i].l) add(--L);
while(R<c[i].r) add(++R);
while(R>c[i].r) del(R--);
//从上一个点推到这一个点
//记录答案
}
for(int i=1;i<=q;++i)
if(/*如果不同的数等于区间长度*/) cout<<"Yes\n";
else cout<<"No\n";
return 0;
}
上面代码漏掉了好多，如果看不懂可以看看洛谷题解。
还是一道模版题
我们发现这道题目有了修改。
带修莫队
其实很简单就多一个时间维度，不过复杂度变成了 O(n^{\frac{5}{3} }) 。
和之前不同的是这里的块取 n^{\frac{2}{3}} 最合适。
不过这里要先走区间，再走时间，相信我们的 @陶荣杰1 深有体会。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q,block,qq_sum,qr_sum,a[N],ans[N],vis[N],L=1,R,T,cnt;
struct Replace
{
int l,r;
}qr[N];
struct Query
{
int l,r,id,t;
}qq[N];
bool cmp(Query x,Query y)
{
//排序，自己写
}
//del和add自己写
void upd(int x,int t)
{
if(qq[x].l<=qr[t].l&&qr[t].l<=qq[x].r)
{
del(a[qr[t].l]);
add(qr[t].r);
//修改就是减一个，加一个
}
swap(a[qr[t].l],qr[t].r);//因为变过以后下一次要相反
}
int main()
{
cin>>n>>q;
block=pow(n,0.66666666666);//确定块的大小
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=q;++i)
{
char op;
int l,r;
cin>>op>>l>>r;
if(op=='Q')
{
qq_sum++;
qq[qq_sum].id=qq_sum;
qq[qq_sum].l=l;
qq[qq_sum].r=r;
qq[qq_sum].t=qr_sum;
}
else
{
qr_sum++;
qr[qr_sum].l=l;
qr[qr_sum].r=r;
}
}
sort(qq+1,qq+1+qq_sum,cmp);//按块排序
for(int i=1;i<=qq_sum;++i)
{
//这和上面差不多就是从上一个点推到这一个点
/*记录自己填*/
}
for(int i=1;i<=qq_sum;++i) cout<<ans[i]<<"\n";
return 0;
}