RT,和题解区第一个题解造了一堆 n=q=105 的随机数据对拍,没发现什么问题。设定块长 =3 对着样例调试也没测出什么问题。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double lf;
#define rep(i, f, t) for (int i = (f), ed##i = (t); i <= ed##i; ++i)
#define re(i, t) rep (i, 1, t)
#define per(i, t, f) for (int i = (t), ed##i = (f); i >= ed##i; --i)
#define ste(i, f, t, s) for (int i = (f), ed##i = (t); i <= ed##i; i += s)
#define each(i, x) for (auto &&i : (x))
#define nxt(i, f, g) for (int i = g.h[f]; i; i = g.e[i].n)
#define dbg(x) (cerr << "(dbg) " << #x " = " << (x) << '\n')
#define umod(x) ((x) >= mo && ((x) -= mo))
#define dmod(x) ((x) < 0 && ((x) += mo))
#define up(x, y) (((x) < (y)) && ((x) = (y)))
#define down(x, y) (((x) > (y)) && ((x) = (y)))
#define y1 y1__
#define fio(x) (freopen(x ".in", "r", stdin), freopen(x ".out", "w", stdout))
// clang-format off
namespace FastIO {
const int SZ=(1<<21)+1;
struct I {
char ibuf[SZ],*iS,*iT,c;int f,_eof;FILE*fi;
I(FILE*f):fi(f){}
inline char Gc(){return iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SZ,fi),(iS==iT?EOF:*iS++)):*iS++;}
inline ll operator()(){ll x;operator()(x);return x;}
inline I&operator()(char&x){x=Gc();return*this;}
inline I&operator()(char*s){for(c=Gc();c<32||c>126||c==' ';)c=Gc();for(;c>31&&c<127&&c!=' '&&c!='\n'&&c!='\r';++s,c=Gc())*s=c;*s=0;return*this;}
template<class T>inline I&operator()(T&x){_eof=0;for(f=1,c=Gc();(c<'0'||c>'9')&&!_eof;c=Gc()){if(c=='-')f=-1;_eof|=c==EOF;}for(x=0;c<='9'&&c>='0'&&!_eof;c=Gc())x=x*10+(c&15),_eof|=c==EOF;x*=f;return*this;}
template<class T>I&operator()(T*x,const int&n,const int&st=1){rep(i,st,n){operator()(x[i]);}return*this;}
} in(stdin);
struct O {
char obuf[SZ],*oS=obuf,*oT=oS+SZ-1,qu[55];int f,qr;FILE*fi;
O(FILE*f):fi(f){}
~O(){Flush();}
inline void Flush(){fwrite(obuf,1,oS-obuf,fi),oS=obuf;}
inline O&operator()(char x){*oS++=x;if(oS==oT)Flush();return*this;}
inline O&operator()(char*s){int len=strlen(s);for(f=0;f<len;++f)operator()(s[f]);return*this;}
inline O&operator()(const char*s){return operator()((char*)s);}
template<class T>inline O&operator()(T x){if(!x)operator()('0');if(x<0)operator()('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)operator()(qu[qr--]);return*this;}
template<class T>O&operator()(T*x,const int&n,const char&ed=' ',const int&st=1){rep(i,st,n)operator()(x[i])(ed);return*this;}
} out(stdout);
}
using FastIO::in;using FastIO::out;
template<class K,class V>ostream&operator<<(ostream&s,const pair<K,V>&p){s<<'<'<<p.first<<", "<<p.second<<'>';return s;}
template<class T,class=typename T::value_type,class=typename enable_if<!is_same<T,string>::value>::type>ostream&operator<<(ostream&s,const T&v){s<<'[';each(x,v)s<<x<<", ";if(!v.empty())s<<"\b\b";s<<']';return s;}
template<class T>T Abs(const T&a){return a>0?a:-a;}
ll Pow(ll a,ll b,const ll&m){ll res=1;a%=m;while(b>0){if(b&1)res=res*a%m;a=a*a%m,b>>=1;}return res;}
ll Gcd(ll a,ll b){ll t;while(b!=0)t=a%b,a=b,b=t;return a;}
ll C(ll n,ll m){if(m>n)return 0;ll a=1;re(i,m)a*=(n-i+1),a/=i;return a;}
ll C(ll n,ll m,ll p){if(m>n)return 0;ll x=1;re(i,m){ll a=(n+i-m)%p,b=i%p;x=x*(a*Pow(b,p-2,p)%p)%p;}return x;}
// clang-format on
constexpr int N = 1e5 + 9;
constexpr int B = 333;
int n, a[N], cnt[B][N], bl[N], lbl[N], rbl[N], sz;
vector<int> use[B];
deque<int> dq[B];
void Up(int x) {
auto b = bl[x];
each (y, use[b])
cnt[b][y] = 0;
use[b].clear();
each (y, dq[b]) {
++cnt[b][y];
if (cnt[b][y] == 1) use[b].push_back(y);
}
}
void Init() {
// sz = 3;
sz = max(3, (int)sqrt(n));
re (i, n)
bl[i] = (i - 1) / sz + 1, lbl[i] = (bl[i] - 1) * sz + 1, rbl[i] = min(n, bl[i] * sz);
ste(x, 1, n, sz) {
rep (i, lbl[x], rbl[x])
dq[bl[x]].push_back(a[i]);
Up(x);
}
}
void Mov(int l, int r) {
if (bl[l] == bl[r]) {
int b = bl[l];
rotate(dq[b].begin() + l - lbl[l], dq[b].begin() + r - lbl[l], dq[b].begin() + r + 1 - lbl[l]);
Up(l);
return;
}
dq[bl[l]].insert(dq[bl[l]].begin() + l - lbl[l], dq[bl[r]][r - lbl[r]]);
dq[bl[r]].erase(dq[bl[r]].begin() + r - lbl[r]);
Up(l);
rep (b, bl[l] + 1, bl[r]) {
int t = dq[b - 1].back();
dq[b].push_front(t);
++cnt[b][t];
if (cnt[b][t] == 1) use[b].push_back(t);
dq[b - 1].pop_back();
--cnt[b - 1][t];
}
Up(r);
}
int Ask(int l, int r, int k) {
int res = 0;
if (bl[l] == bl[r]) {
int b = bl[l];
rep (i, l, r)
if (dq[b][i - lbl[l]] == k) ++res;
return res;
}
res += Ask(l, rbl[l], k);
rep (b, bl[l] + 1, bl[r] - 1)
res += cnt[b][k];
res += Ask(lbl[r], r, k);
return res;
}
signed main() {
in(n)(a, n);
Init();
int lastans = 0;
re (_, in()) {
int op = in(), l = (in() + lastans - 1) % n + 1, r = (in() + lastans - 1) % n + 1;
// int op = in(), l = in(), r = in();
if (l > r) swap(l, r);
// cerr << op << ' ' << l << ' ' << r << '\n';
if (op == 1)
Mov(l, r);
else {
int k = (in() + lastans - 1) % n + 1;
lastans = Ask(l, r, k);
out(lastans)('\n');
}
// re (b, bl[n]) {
// each (x, dq[b])
// cerr << x << ' ';
// cerr << "| ";
// }
// cerr << "\n--------\n";
// re (b, bl[n]) {
// each (x, use[b])
// if (cnt[b][x]) cerr << "(" << x << ", " << cnt[b][x] << ") ";
// cerr << "| ";
// }
// cerr << "\n--------\n";
}
return 0;
}