Description

Hack 國的居民人人都是 OI 大師，Hometown 得知便趕緊來到 Hack 國學習。可想要進入 Hack 國并不是件容易的事情，首先就必須通過 Hack 國海關小 B 的考驗。小 B 覺得 Hometown 比較菜，于是就扔了一道小水題給 Hometown。
給定一個長度為 n 的數列 a i ，接下來會對這個序列進行 m 次操作。操作類型分為以下兩種：
? 1 l r，表示將區間 [l,r] 輪轉一次，具體來說，a l ,a l+1 ,a l+2 ,··· ,a r?1 ,a r 經過一次輪轉之后，會變為 a r ,a l ,a l+1 ,··· ,a r?1 ；
? 2 l r k，詢問區間 [l,r] 內 a i = k 的個數。
可惜 Hometown 還是不會做，他只能期待你能解決這個問題了。

Input

從文件queue.in中讀入數據。
第一行兩個整數 n,m，表示序列的長度與操作的次數。
第二行 n 個整數 a i ，表示這個序列。
接下來的 m 行，每行先是一個整數 opt 表示操作的類型。對于 opt = 1 的操作，接下來兩個整數 l,r 表示將區間 [l,r] 輪轉；對于 opt = 2 的操作，接下來三個整數 l,r,k 表示求區間 [l,r] 內等于 k 的值的個數。

Output

輸出到文件queue.out中。
對于每個 2 操作，一行一個整數，表示這次詢問的答案。

Sample Input

7 6
1 2 2 3 2 1 3
2 3 6 2
1 1 6
2 2 4 1
1 3 6
2 6 7 3
2 3 5 2

Sample 2

見選手目錄下的queue/queue2.in與queue/queue2.ans。
該組樣例的數據范圍同第 2 個測試點。

Sample 3

見選手目錄下的queue/queue3.in與queue/queue3.ans。
該組樣例的數據范圍同第 13 個測試點。

Sample Output

2
1
2
3

Explanation

對于第一次詢問，區間 [3,6] 中一共出現了 2 次 2。
隨后進行修改，修改之后序列變為 1,1,2,2,3,2,3。
對于第二次詢問，區間 [2,4] 中一共出現了 1 次 1。
隨后再次修改，修改之后序列變為 1,1,2,2,2,3,3。
對于第三次詢問，區間 [6,7] 中一共出現了 2 次 3。
對于第四次詢問，區間 [3,5] 中一共出現了 3 次 2。

Data Constraint

對于 100% 的數據，滿足 0 ≤ n,m ≤ 10^5 ,1 ≤ a i ≤ n,1 ≤ l i ≤ r i ≤ n。除此之外，對于每個數據點，還滿足以下限制。

Solution

• 這題我的方法是分塊（也可以用 splay+權值線段樹）。

• 用類似塊狀鏈表的方法，所有數用一個雙向鏈表連起來。

• 并且每 $\sqrt{n}$ 個數分成一塊，每塊記錄開頭指針和結尾指針。

• 之后每一塊開一個桶存每個數出現的次數。

• 詢問的話整塊直接在桶中讀取，散塊直接掃。

• 如果是翻轉的話呢，就把 $a[r]$ 對應的指針剪下來，并將其插到 $a[l]$ 對應的指針前。

• 中途順帶修改每個塊的信息即可。

• 查詢和修改的復雜度均為 $O(\sqrt{n})$ 。

• 總時間復雜度 $O(n\sqrt{n})$ 。

• 要注意下細節和特殊情況，比如說 $n=0$ 、$l,r$ 相同或在同一塊內……

Code

#include<cstdio> #include<cmath> #include<cctype> using namespace std; const int N=1e5+5; int siz,tot; int a[N],t[318][N],lt[N],nex[N]; int id[N],st[N],en[N],pl[N],pr[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int main() {freopen("queue.in","r",stdin);freopen("queue.out","w",stdout);int n=read(),m=read();if(!n) return 0;siz=sqrt(n);for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) nex[i]=i+1,lt[i]=i-1;int sum=0;while(sum<n){tot++;pl[tot]=st[tot]=sum+1;for(int i=1;i<=siz && sum<n;i++){sum++;t[tot][a[sum]]++;id[sum]=tot;}pr[tot]=en[tot]=sum;}while(m--){int op=read(),l=read(),r=read();if(op==1){if(l==r) continue;int ll=(l-1)/siz+1,rr=(r-1)/siz+1;int posr=pr[rr]==r?en[rr]:0;if(!posr){posr=st[rr];for(int i=pl[rr];i<r;i++) posr=nex[posr];}int posl=pl[ll]==l?st[ll]:0;if(!posl){posl=en[ll];for(int i=pr[ll];i>l;i--) posl=lt[posl];}t[id[posr]][a[posr]]--;nex[lt[posr]]=nex[posr];lt[nex[posr]]=lt[posr];if(en[rr]==posr) en[rr]=lt[posr];int pos=posr;bool pd=false;while(id[posl]^id[pos]){pos=st[id[pos]];st[id[pos]]=lt[pos];pos=lt[pos];if(pos==posl){en[id[pos]]=posr;id[posr]=id[posl];t[id[pos]][a[pos]]--;id[pos]++;t[id[pos]][a[pos]]++;pd=true;break;}en[id[pos]]=lt[pos];t[id[pos]][a[pos]]--;id[pos]++;t[id[pos]][a[pos]]++;pos=lt[pos];}if(st[ll]==posl) st[ll]=posr;if(!pd) id[posr]=id[posl];nex[lt[posl]]=posr;lt[posr]=lt[posl];nex[posr]=posl;lt[posl]=posr;t[id[posr]][a[posr]]++;}else{int k=read(),ans=0;int ll=(l-1)/siz+1,rr=(r-1)/siz+1;if(ll==rr){int pos=en[ll];for(int i=pr[ll];i>r;i--) pos=lt[pos];for(int i=r;i>=l;i--){if(a[pos]==k) ans++;pos=lt[pos];}write(ans),putchar('\n');continue;}if(pl[ll]^l){int pos=en[ll];for(int i=pr[ll];i>=l;i--){if(a[pos]==k) ans++;pos=lt[pos];}ll++;}if(pr[rr]^r){int pos=st[rr];for(int i=pl[rr];i<=r;i++){if(a[pos]==k) ans++;pos=nex[pos];}rr--;}for(int i=ll;i<=rr;i++) ans+=t[i][k];write(ans),putchar('\n');}}return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5924. 【NOIP2018模拟10.23】Queue的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。