正題

題目鏈接:https://www.luogu.com.cn/problem/P4867

---

題目大意

一個序列要求支持詢問一個區(qū)間$[l,r]$內(nèi)在$[a,b]$之間有多少種不同的權(quán)值。

---

解題思路

首先我們需要莫隊，考慮用什么數(shù)據(jù)結(jié)構(gòu)，如果我們使用線段樹，那么復(fù)雜度將是$O(m\sqrt{n}\log n)$的，但是我們發(fā)現(xiàn)我們的修改次數(shù)雖然多，但是詢問最多只有$m$次，那么我們考慮提升詢問的時間復(fù)雜度降低修改的復(fù)雜度。

改為用分塊來，這樣詢問時是$O(\sqrt{n})$的但是修改時就是$O(1)$的，所以時間復(fù)雜度為$O(n\sqrt{n})$的

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+10; struct node{int l,r,a,b,id; }q[N*10]; int n,m,T,a[N],val[N],pos[N],ans[N*10]; int L[500],R[500],Val[500]; bool cmp(node x,node y){if(x.l/T==y.l/T)return x.r<y.r;return x.l<y.l; } void Add(int x) {val[x]++;Val[pos[x]]+=(val[x]==1);} void Del(int x) {val[x]--;Val[pos[x]]-=(val[x]==0);} int Query(int l,int r){int x=pos[l],y=pos[r],ans=0;if(x==y){for(int i=l;i<=r;i++)ans+=(val[i]>0);return ans;}for(int i=x+1;i<y;i++)ans+=Val[i];for(int i=l;i<=R[x];i++)ans+=(val[i]>0);for(int i=L[y];i<=r;i++)ans+=(val[i]>0);return ans; } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);T=sqrt(n);for(int i=1;i<=T;i++)L[i]=R[i-1]+1,R[i]=i*T;if(n!=T*T)L[++T]=R[T-1]+1,R[T]=n;for(int i=1;i<=T;i++)for(int j=L[i];j<=R[i];j++)pos[j]=i;for(int i=1;i<=m;i++){scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);q[i].id=i;}sort(q+1,q+1+m,cmp);int l=1,r=0;for(int i=1;i<=m;i++){while(r<q[i].r)Add(a[++r]);while(l>q[i].l)Add(a[--l]);while(r>q[i].r)Del(a[r--]);while(l<q[i].l)Del(a[l++]);ans[q[i].id]=Query(q[i].a,q[i].b);}for(int i=1;i<=m;i++)printf("%d\n",ans[i]); }

總結(jié)

以上是生活随笔為你收集整理的P4867-Gty的二逼妹子序列【平衡结合,莫队,分块】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。