Solution
【题目传送门】。
设 \(f_{l,r}\) 表示 \([l,r]\) 区间的答案，\(i\) 右边第一个与其数字相同的位置为 \(nxt_i\)。考虑 \(l\) 是否会被消掉，有：
\[f_{l,r}=
\begin{cases}
f_{l+1,r}+1,\ \ \ \ \ \ \ \ nxt_l>r\\
f_{nxt_l+1,r},\ \ \ \ \ \ \ \ \ \ \ nxt_l\le r
\end{cases}
\]
其中 \(f_{i+1,i}=0\)。
会发现 \(f_{l,r}\) 由 \(f_{l+1}\) 的某一段和 \(f_{nxt_l+1}\) 的某一段拼接而成。因为强制在线，用主席树维护。
具体的区间加用标记永久化来维护。
复杂度 \(\mathcal{O}(n\log n)\)。
Code
#include<bits/stdc++.h>
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
#define ll long long
#define db double
#define pb push_back
#define eb emplace_back
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define lb(x) ((x)&(-x))
using namespace std;
const int N=3e5+20,M=1e5+20;
const ll INF=1ll<<60,mod=998244353;
namespace H_H{int n,m,a[N],nxt[N],pos[N];int rt[N],tot;struct Tree{int ls,rs,pre;#define ls(p) t[p].ls#define rs(p) t[p].rs#define pre(p) t[p].pre}t[N<<8];inline int cpynode(int p){t[++tot]=t[p];return tot;}void update(int &p,int L,int R,int l,int r,int d,bool flag){if(flag) p=cpynode(p);else if(!p) p=++tot;if(l<=L && R<=r) return pre(p)+=d,void();int mid=(L+R)>>1;if(l<=mid) update(ls(p),L,mid,l,r,d,flag);if(mid<r) update(rs(p),mid+1,R,l,r,d,flag);}void cpy(int &rt1,int rt2,int L,int R,int l,int r,int Tot){if(l<=L && R<=r){rt1=cpynode(rt2);pre(rt1)+=Tot;return ;}rt1=cpynode(rt1);int mid=(L+R)>>1;if(l<=mid) cpy(ls(rt1),ls(rt2),L,mid,l,r,Tot-pre(rt1)+pre(rt2));if(mid<r) cpy(rs(rt1),rs(rt2),mid+1,R,l,r,Tot-pre(rt1)+pre(rt2));}int query(int p,int L,int R,int x){if(L==R) return pre(p);int mid=(L+R)>>1;if(x<=mid) return query(ls(p),L,mid,x)+pre(p);else return query(rs(p),mid+1,R,x)+pre(p);}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=n;i;i--){nxt[i]=pos[a[i]];pos[a[i]]=i;}update(rt[n],1,n,n,n,1,1);if(n^1) update(rt[n],1,n,n-1,n-1,0,1);for(int i=n-1;i;i--){rt[i]=rt[i+1];update(rt[i],1,n,i,n,1,1);if(i^1) update(rt[i],1,n,i-1,i-1,0,1);if(nxt[i] && nxt[i]+1<=n) cpy(rt[i],rt[nxt[i]+1],1,n,nxt[i],n,0);else if(nxt[i]==n) update(rt[i],1,n,n,n,-query(rt[i],1,n,n),1);}int ans=0;for(int i=1,l,r;i<=m;i++){cin>>l>>r;l^=ans,r^=ans;cout<<(ans=query(rt[l],1,n,r))<<"\n";}return 0;}
}
int main(){IOS;H_H::main();return 0;
}