P1903

本文主要是介绍P1903，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：https://www.luogu.org/problemnew/show/P1903

分析：主席可以做，也可以用动态（带修改）莫队，模板题。

参考博客：https://www.cnblogs.com/zwfymqz/p/7154145.html

https://blog.csdn.net/wu_tongtong/article/details/77924765

注意：对于n和m同级的题目，块的大小为时复杂度为，可以证明，此处略去。如果修改次数少，所以块的大小为更快。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,m;
int c[N];
struct node1{int l,r,x,id;
};
node1 q[N];
struct node2{int x,y;
};
node2 ch[N];
int totq=0,totch=0,unit,ans[N],tot=0,sum[N];int cmp(const node1 &a,const node1 &b)
{if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;else if (a.r/unit!=b.r/unit) return a.r/unit<b.r/unit;else return a.x<b.x;
}void update(int wz,int z)
{if (z==-1) {sum[c[wz]]--;if (!sum[c[wz]]) tot--;}else{sum[c[wz]]++;if (sum[c[wz]]==1) tot++;}
}void change(int bh,int z,int l,int r)
{if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,-1);   //删除从前的影响swap(c[ch[bh].x],ch[bh].y);if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,1);   //添加影响
}void solve()
{int l=1,r=0,now=0;for (int i=1;i<=m;i++){while (r<q[i].r) update(r+1,1),r++;while (r>q[i].r) update(r,-1),r--;while (l>q[i].l) update(l-1,1),l--;while (l<q[i].l) update(l,-1),l++;while (now<q[i].x) change(now+1,1,l,r),now++;while (now>q[i].x) change(now,-1,l,r),now--;ans[q[i].id]=tot;}
}int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d",&c[i]);for (int i=1;i<=m;i++){char s[2];int x,y;scanf("%s%d%d",&s,&x,&y);if (s[0]=='Q'){totq++;q[totq].l=x; q[totq].r=y;q[totq].x=totch;q[totq].id=totq;}else{totch++;ch[totch].x=x;ch[totch].y=y;}}unit=(int)pow(n,0.666666);sort(q+1,q+1+totq,cmp);solve();for (int i=1;i<=totq;i++) printf("%d\n",ans[i]);return 0;
}

 

这篇关于P1903的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---