題目鏈接：點擊查看

題目大意：給出一個長度為 n 的序列 a，sum 為數列 a 的前綴異或和，再給出 m 次操作，每次操作分為兩種類型：

1 l r：詢問 sum 在區間 [ l , r ] 內有多少對不重復的數

2 pos：交換 a[ pos ] 和 a[ pos + 1 ] 位置的數

題目分析：參考博客：https://blog.csdn.net/qq_42576687/article/details/98211361

帶修莫隊模板題，存個板子，對于這個題目而言，轉換后的題意如上，因為修改操作對于前綴異或和的影響只有 pos 位置受到影響，其他位置不受影響，所以可以視為單點修改，詢問有多少對不重復的數，正難則反，可以用總數減去區間內有多少對重復的數即可

分塊大小為??，時間復雜度為?

相對于普通莫隊而言，只是在結構體中多了一個變量 t ，代表當前詢問之前有多少次修改，在處理時 while 循環也多了兩重，需要放在端點修改的 while 之后

修改的話需要分類討論一下，如果當前修改的點位于當前詢問的區間內，則需要對區間的貢獻同樣做出修改，否則的話不用處理

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int size,n,m,a[N],sum[N],p[N],qcnt,pcnt;LL cnt[N*10],ans[N];struct query {int l,r,id,t;bool operator<(const query& a)const{if(l/size!=a.l/size)return l<a.l;else if(r/size!=a.r/size)return r<a.r;elsereturn t<a.t;} }q[N];LL add(int pos) {return cnt[sum[pos]]++; }LL del(int pos) {return --cnt[sum[pos]]; }LL modify(int id,int pos) {LL ans=0;bool flag=q[id].l<=p[pos]&&p[pos]<=q[id].r;if(flag)ans-=del(p[pos]);sum[p[pos]]^=a[p[pos]];swap(a[p[pos]],a[p[pos]+1]);sum[p[pos]]^=a[p[pos]];if(flag)ans+=add(p[pos]); return ans; }void solve() {sort(q+1,q+1+qcnt);int l=1,r=0,t=0;LL sum=0;for(int i=1;i<=qcnt;i++){int ql=q[i].l,qr=q[i].r,qt=q[i].t;while(r<qr)sum+=add(++r);while(l>ql)sum+=add(--l);while(r>qr)sum-=del(r--);while(l<ql)sum-=del(l++);while(t<qt)sum+=modify(i,++t);while(t>qt)sum+=modify(i,t--);ans[q[i].id]=1LL*(qr-ql+1)*(qr-ql)/2-sum;} }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){memset(cnt,0,sizeof(cnt));size=(int)pow(n,2.0/3.0);for(int i=1;i<=n;i++){scanf("%d",a+i);sum[i]=sum[i-1]^a[i];}qcnt=0,pcnt=0;while(m--){int op;scanf("%d",&op);if(op==1){int l,r;scanf("%d%d",&l,&r);qcnt++;q[qcnt].l=l-1,q[qcnt].r=r,q[qcnt].t=pcnt,q[qcnt].id=qcnt;}else{int pos;scanf("%d",&pos);p[++pcnt]=pos;}}solve();for(int i=1;i<=qcnt;i++)printf("%lld\n",ans[i]);}return 0; }

?

總結

以上是生活随笔為你收集整理的HDU - 6610 Game(带修莫队)的全部內容，希望文章能夠幫你解決所遇到的問題。

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