%ad大神的脑洞，这题是强制在线版的HH的项链
所以可以考虑树套树，和主席树之类的做法
对于每个点，可以将这个点的颜色上一次出现的位置插入到主席树里，对于每一个 l ~ r 的询问， l 到 r 之间有多少颜色上一次出现的位置在0 到 l-1 内就是答案
1 #define MAXN 500010UL 2 #include <cstdio> 3 #include <algorithm> 4 5 using namespace std; 6 7 int n, m, Rt[MAXN], num, ans, lt[MAXN]; 8 9 struct Seg { 10 int ls, rs, val; 11 }bn[MAXN*20]; 12 13 void Insert(int lrt, int &rt, int l, int r, int pos) { 14 rt = ++ num; 15 bn[rt] = bn[lrt]; 16 if(l==r) { 17 ++ bn[rt].val; 18 return; 19 } 20 int mid = (l+r)>>1; 21 if(pos<=mid) Insert(bn[lrt].ls, bn[rt].ls, l, mid, pos); 22 else Insert(bn[lrt].rs, bn[rt].rs, mid+1, r, pos); 23 bn[rt].val = bn[bn[rt].ls].val+bn[bn[rt].rs].val; 24 return; 25 } 26 27 void Find(int lrt, int rt, int l, int r, int ls, int rs) { 28 if(bn[rt].val-bn[lrt].val<=0) return; 29 if(ls<=l&&rs>=r) { 30 ans += bn[rt].val-bn[lrt].val; 31 return; 32 } 33 int mid = (l+r)>>1; 34 if(ls<=mid) Find(bn[lrt].ls, bn[rt].ls, l, mid, ls, rs); 35 if(rs>mid) Find(bn[lrt].rs, bn[rt].rs, mid+1, r, ls, rs); 36 return; 37 } 38 39 void In(int &x) { 40 x = 0; 41 char tmp = getchar(); 42 while(tmp<'0'||tmp>'9') tmp = getchar(); 43 while(tmp>='0'&&tmp<='9') x = x*10+tmp-'0', tmp = getchar(); 44 return; 45 } 46 47 int main() { 48 freopen("color_seq.in", "r", stdin); 49 freopen("color_seq.out", "w", stdout); 50 In(n), In(m); 51 for(int i = 1, x ; i <= n ; ++ i) { 52 In(x); 53 Insert(Rt[i-1], Rt[i], 0, n, lt[x]); 54 lt[x] = i; 55 } 56 for(int i = 1, l, r ; i <= m ; ++ i) { 57 In(l), In(r); 58 l = (l+ans)%n+1, r = (r+ans)%n+1; 59 if(l>r) swap(l, r); 60 ans = 0, Find(Rt[l-1], Rt[r], 0, n, 0, l-1); 61 printf("%d\n", ans); 62 } 63 return 0; 64 }