有时间就加一点吧....
Tarjan
namespace Tarjan{
int col[N],num[N],dfn[N],low[N],cnt,colornum,val[N];
bool ins[N];
stack<int>s;
vector<int>g[N];
vector<int>e[N];
int a[N];
inline void tarjan(int u){
dfn[u]=low[u]=++cnt;
s.push(u);ins[u]=1;
for(auto v:g[u]){
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
int t;
colornum++;
do{
t=s.top();s.pop();
col[t]=colornum;
num[colornum]++;
val[colornum]+=a[t];
ins[t]=0;
}while(t!=u);
}
}
}using namespace Tarjan;
树链剖分求LCA
code
struct treelca{
int siz[N],son[N],fa[N],dep[N],top[N];
inline void dfs1(int u,int from){
siz[u]=1;son[u]=0;
dep[u]=dep[from]+1;
for(auto v:g[u]){
if(v==from) continue;
fa[v]=u;dfs1(v,u);
if(siz[v]>siz[son[u]])son[u]=v;
siz[u]+=siz[v];
}
}
inline void dfs2(int u,int tp){
top[u]=tp;
if(son[u]!=0) dfs2(son[u],tp);
for(auto v:g[u]){
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]>dep[top[y]])x=fa[top[x]];
else y=fa[top[y]];
}
return dep[x]<dep[y]?x:y;
}
}T;
矩阵快速幂
code
struct mat{
int a[15][15];
mat(){memset(a,0,sizeof a);}
inline mat operator*(const mat& rhs)const {
mat res;
up(i,1,2){
up(j,1,2){
up(k,1,2){
res.a[i][j]=(res.a[i][j]+a[i][k]*rhs.a[k][j])%p;
}
}
}
return res;
}
};
inline mat ksm(mat rhs,int k){
mat base;
up(i,1,2)base.a[i][i]=1;
while(k){
if(k&1)base=base*rhs;
rhs=rhs*rhs;
k>>=1;
}
return base;
}
FHQTreap
code
struct FHQTreap{
int cnt=0,root=0;
struct node{
int ls,rs;
int key,pri;
int siz;
}tr[N];
int ans;
inline void build(int x){
cnt++;
tr[cnt].siz=1;
tr[cnt].ls=tr[cnt].rs=0;
tr[cnt].key=x;
tr[cnt].pri=rand();
}
inline void push_up(int k){
tr[k].siz=tr[tr[k].ls].siz+tr[tr[k].rs].siz+1;
}
inline void split(int u,int x,int &l,int &r){
if(u==0){l=r=0;return;}
if(tr[u].key<=x){
l=u;
split(tr[u].rs,x,tr[u].rs,r);
}
else{
r=u;
split(tr[u].ls,x,l,tr[u].ls);
}
push_up(u);
}
inline int merge(int l,int r){
if(l==0||r==0)return l+r;
if(tr[l].pri>tr[r].pri){
tr[l].rs=merge(tr[l].rs,r);
push_up(l);
return l;
}
else{
tr[r].ls=merge(l,tr[r].ls);
push_up(r);
return r;
}
}
inline void insert(int x){
int l,r;
split(root,x,l,r);
build(x);
root=merge(merge(l,cnt),r);
}
inline void del(int x){
int l,r,p;
split(root,x,l,r);
split(l,x-1,l,p);
p=merge(tr[p].ls,tr[p].rs);
root=merge(merge(l,p),r);
}
inline void getrank(int x){
int l,r;
split(root,x-1,l,r);
int last=tr[l].siz+1;
root=merge(l,r);
}
inline int kth(int u,int k){
if(k==tr[tr[u].ls].siz+1)return u;
if(k<=tr[tr[u].ls].siz)return kth(tr[u].ls,k);
else return kth(tr[u].rs,k-tr[tr[u].ls].siz-1);
}
inline int getpre(int x){
int l,r;
split(root,x-1,l,r);
int last=tr[kth(l,tr[l].siz)].key;
root=merge(l,r);
return last;
}
inline int getpre1(int x){
int l,r;
split(root,x,l,r);
int last=tr[kth(l,tr[l].siz)].key;
root=merge(l,r);
return last;
}
inline int getnxt(int x){
int l,r;
split(root,x,l,r);
int last=tr[kth(r,1)].key;
root=merge(l,r);
return last;
}
inline int size(){
return tr[root].siz;
}
inline int getans(int x){
int a=getpre1(x),b=getnxt(x);
if(x-a>b-x)return b;
else return a;
}
}
文艺平衡树
int n,m;
int a[N];
struct FHQTreap{
struct node{
int ls,rs;
int val,key;
int siz,tag;
}tr[N];
int rt=0,cnt=0;
inline void push_up(int k){
tr[k].siz=tr[tr[k].ls].siz+tr[tr[k].rs].siz+1;
}
inline int nd(int x){
cnt++;
tr[cnt].val=x;
tr[cnt].key=rng();
tr[cnt].siz=1;
return cnt;
}
inline void push_down(int k){
if(tr[k].tag){
tr[tr[k].ls].tag^=1;
tr[tr[k].rs].tag^=1;
swap(tr[k].ls,tr[k].rs);
tr[k].tag=0;
}
}
inline void split(int u,int x,int &L,int &R){
if(!u)return L=R=0,void();
push_down(u);
if(tr[tr[u].ls].siz>=x)R=u,split(tr[u].ls,x,L,tr[u].ls);
else L=u,split(tr[u].rs,x-tr[tr[u].ls].siz-1,tr[u].rs,R);
push_up(u);
}
inline int merge(int L,int R){
if(!L||!R)return L|R;
push_down(L);
push_down(R);
if(tr[L].key>tr[R].key){
tr[L].rs=merge(tr[L].rs,R);
push_up(L);
return L;
}
else{
tr[R].ls=merge(L,tr[R].ls);
push_up(R);
return R;
}
}
inline void insert(int x){
rt=merge(rt,nd(x));
}
inline void rev(int l,int r){
int x,y,z;
split(rt,r,x,z);
split(x,l-1,x,y);
tr[y].tag^=1;
rt=merge(x,merge(y,z));
}
inline void print(int x){
if(!x)return;
push_down(x),
print(tr[x].ls);
cout<<tr[x].val<<" ";
print(tr[x].rs);
}
}T;
signed main(){
n=read();m=read();
up(i,1,n)T.insert(i);
int l,r;
up(i,1,m){
l=read();r=read();
T.rev(l,r);
}
T.print(T.rt);
return 0;
}
线段树
code
struct SegmentTree{
struct node{
int l,r,maxl;
}tr[N<<2];
inline void push_up(int k){
tr[k].maxl=max(tr[lc].maxl,tr[rc].maxl);
}
inline void build(int k,int l,int r,int arr[]){
tr[k].l=l;tr[k].r=r;
if(l==r){
tr[k].maxl=arr[l];
return;
}
int mid=(l+r)>>1;
build(lc,l,mid,arr);
build(rc,mid+1,r,arr);
push_up(k);
}
inline int ask(int k,int l,int r){
if(tr[k].l>=l&&tr[k].r<=r){
return tr[k].maxl;
}
int mid=(tr[k].l+tr[k].r)>>1,res=-inf;
if(mid>=l)res=max(res,ask(lc,l,r));
if(mid<r)res=max(res,ask(rc,l,r));
return res;
}
};
ST表
code
struct ST{
int dp[N][20],pos[N][20];
inline void build(int l,int r,int arr[]){
up(i,l,r)dp[i-l+1][0]=arr[i];
up(i,l,r)pos[i][0]=i;
int res=0;
for(int j=1;(1<<j)<=r-l+1;j++){
for(int i=l;i+(1<<j)-1<=r;i++){
int x=pos[i-l+1][j-1],y=pos[i-l+1+(1<<(j-1))][j-1];
dp[i-l+1][j]=max(dp[i-l+1][j-1],dp[i-l+1+(1<<(j-1))][j-1]);
pos[i-l+1][j]=arr[x]>arr[y]?x:y;
}
}
}
inline int ask(int l,int r){
int k=log2(r-l+1);
return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
inline int askpos(int l,int r,int arr[]){
int k=log2(r-l+1);
int x=pos[l][k],y=pos[r-(1<<k)+1][k];
return arr[x]>arr[y]?x:y;
}
}T;
并查集
namespace DSU{
int fa[N], siz[N];
void init(int n) {
for(int i = 1; i <=n; i++) fa[i] = i, siz[i] = 1;
}
int find(int x) {
return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
int fx = find(x), fy = find(y);
if(siz[fx] > siz[fy]) swap(fx, fy);
fa[fx] = fy; siz[fy] += siz[fx];
}
}using namespace DSU;
快读快出
namespace IO{
inline int read(){
char c=getchar();int x=0,fh=0;
while(c<'0'||c>'9'){fh|=c=='-';c=getchar();}
while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return fh?-x:x;
}
inline void wt(int x){
if(x<0){x=-x;putchar('-');}
if(x>9)wt(x/10);
putchar((x%10)^48);
}
inline void write(int x,bool op){
wt(x);
putchar(op?'\n':' ');
}
}using namespace IO;
AC自动机
int tr[N][26],cnt,ed[N],fail[N];
inline void insert(char s[]){
int len=strlen(s+1),p=0;
up(i,1,len){
int ch=s[i]-'a';
if(!tr[p][ch])tr[p][ch]=++cnt;
p=tr[p][ch];
}
ed[p]++;
}
queue<int>q;
inline void getfail(){
up(i,0,25)if(tr[0][i])q.push(tr[0][i]);
while(q.size()){
int u=q.front();q.pop();
up(i,0,25){
int v=tr[u][i];
if(v){
fail[v]=tr[fail[u]][i];
q.push(v);
}
else tr[u][i]=tr[fail[u]][i];
}
}
}
inline int ask(char s[]){
int len=strlen(s+1),p=0,ans=0;
up(i,1,len){
int ch=s[i]-'a';
p=tr[p][ch];
for(int v=p;v&&ed[v]!=-1;v=fail[v])ans+=ed[v],ed[v]=-1;
}
return ans;
}
}T;
kmp
string a,b;
int _next[500500];
inline void getnext(string p){
memset(_next,0,sizeof _next);
for(int i=1;i<p.size();i++){
int j=_next[i];
while(j&&p[i]!=p[j])j=_next[j];
if(p[i]==p[j])_next[i+1]=j+1;
else _next[i+1]=0;
}
}
inline void kmp(string s,string p){
int j=0,res=0,last=-1;
for(int i=0;i<s.size();i++){
while(j&&s[i]!=p[j])j=_next[j];
if(s[i]==p[j])j++;
if(j==p.size()&&i-last>=p.size()){
res++;
last=i;
}
}
printf("%d\n",res);
}
Dinic
struct Dinic{
struct edge{
int u,v,cap,flow;
};
vector<edge>edges;
vector<int>g[N];
int cur[N],d[N];
bool vis[N];
inline void add(int u,int v,int cap){
edges.push_back({u,v,cap,0});
edges.push_back({v,u,0,0});
int t=edges.size();
g[u].push_back(t-2);
g[v].push_back(t-1);
}
inline bool bfs(int s,int t){
memset(vis,0,sizeof vis);
queue<int>q;
q.push(s);
d[s]=0;vis[s]=1;
while(q.size()){
int u=q.front();q.pop();
for(auto i:g[u]){
auto e=edges[i];
if(!vis[e.v]&&e.cap>e.flow){
vis[e.v]=1;
d[e.v]=d[u]+1;
q.push(e.v);
}
}
}
return vis[t];
}
inline int dfs(int u,int a,int t){
if(u==t||a==0)return a;
int flow=0,f;
for(int &i=cur[u];i<g[u].size();i++){
auto& e=edges[g[u][i]];
if(d[u]+1==d[e.v]&&(f=dfs(e.v,min(a,e.cap-e.flow),t))>0){
e.flow+=f;
edges[g[u][i]^1].flow-=f;
flow+=f;
a-=f;
if(a==0)break;
}
}
return flow;
}
inline int maxflow(int s,int t){
int flow=0;
while(bfs(s,t)){
memset(cur,0,sizeof cur);
flow+=dfs(s,inf,t);
}
return flow;
}
}E;
struct Dinic{
struct edge{
int u,v,cap,flow,w;
};
vector<edge>edges;
vector<int>g[N];
inline void add(int u,int v,int cap,int w){
edges.push_back({u,v,cap,0,w});
edges.push_back({v,u,0,0,-w});
int t=edges.size();
g[u].push_back(t-2);
g[v].push_back(t-1);
}
bool vis[N];
int dis[N],cur[N];
queue<int>q;
inline bool spfa(int s,int t){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
dis[s]=0;vis[s]=1;
q.push(s);
while(q.size()){
int u=q.front();q.pop();
vis[u]=0;
for(auto i:g[u]){
auto [_,v,cap,flow,w]=edges[i];
if(dis[v]>dis[u]+w&&cap>flow){
dis[v]=dis[u]+w;
if(!vis[v]){
vis[v]=1;
q.push(v);
if(dis[q.front()]>dis[q.back()])swap(q.front(),q.back());
}
}
}
}
return dis[t]<inf;
}
inline int dfs(int u,int a,int t){
if(u==t||a==0)return a;
vis[u]=1;
int flow=0;
for(int &i=cur[u];i<g[u].size();i++){
auto &e=edges[g[u][i]];
if(!vis[e.v]&&dis[e.v]==dis[u]+e.w&&e.cap>e.flow){
int res=dfs(e.v,min(a,e.cap-e.flow),t);
flow+=res;
e.flow+=res;
edges[g[u][i]^1].flow-=res;
a-=res;
if(a==0)break;
}
}
vis[u]=0;
return flow;
}
inline pii mincostmaxflow(int s,int t){
int res,flow=0,cost=0;
while (spfa(s,t)) {
memset(cur, 0, sizeof(cur));
while ((res=dfs(s,inf,t)))flow += res,cost += res * dis[t];
}
return {flow,cost};
}
}E;
EK
struct EK{
struct edge{
int u,v,cap,flow;
};
vector<edge>edges;
vector<int>g[N];
int a[N],p[N];
inline void add(int u,int v,int cap){
edges.push_back({u,v,cap,0});
edges.push_back({v,u,0,0});
int t=edges.size();
g[u].push_back(t-2);
g[v].push_back(t-1);
}
inline int maxflow(int s,int t){
int flow=0;
for(;;){
up(i,1,n)a[i]=0;
queue<int>q;
q.push(s);
a[s]=inf;
while(q.size()){
int u=q.front();q.pop();
for(auto i:g[u]){
auto e=edges[i];
if(!a[e.v]&&e.cap>e.flow){
p[e.v]=i;
a[e.v]=min(a[u],e.cap-e.flow);
q.push(e.v);
}
}
if(a[t])break;
}
if(!a[t])break;
for(int u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
}E;
struct EK{
struct edge{
int u,v,cap,flow,cost;
};
vector<edge>edges;
vector<int>g[N];
int a[N],p[N];
int vis[N];
int dis[N];
inline void add(int u,int v,int cap,int cost){
edges.push_back({u,v,cap,0,cost});
edges.push_back({v,u,0,0,-cost});
int t=edges.size();
g[u].push_back(t-2);
g[v].push_back(t-1);
}
inline int maxflow(int s,int t){
int flow=0;
for(;;){
up(i,1,n)a[i]=0;
queue<int>q;
q.push(s);
a[s]=inf;
while(q.size()){
int u=q.front();q.pop();
for(auto i:g[u]){
auto e=edges[i];
if(!a[e.v]&&e.cap>e.flow){
p[e.v]=i;
a[e.v]=min(a[u],e.cap-e.flow);
q.push(e.v);
}
}
if(a[t])break;
}
if(!a[t])break;
for(int u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
flow+=a[t];
}
return flow;
}
inline bool spfa(int s,int t,int &flow,int &cost){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
memset(a,0,sizeof a);
dis[s]=0;vis[s]=1;
p[s]=0;a[s]=inf;
queue<int>q;
q.push(s);
while(q.size()){
int u=q.front();q.pop();
vis[u]=0;
for(auto i:g[u]){
auto e=edges[i];
if(e.cap>e.flow&&dis[e.v]>dis[u]+e.cost){
dis[e.v]=dis[u]+e.cost;
p[e.v]=i;
a[e.v]=min(a[u],e.cap-e.flow);
if(!vis[e.v]){
q.push(e.v);
vis[e.v]=1;
}
}
}
}
if(dis[t]>=inf)return 0;
flow+=a[t];
cost+=dis[t]*a[t];
for(int u=t;u!=s;u=edges[p[u]].u){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
}
return 1;
}
inline int mincostmaxflow(int s,int t,int& cost){
int flow=0;
cost=0;
while(spfa(s,t,flow,cost));
return flow;
}
}E;
lucas
inline int ksm(int a,int b){
int res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int inv[N],fac[N];
inline void init(){
inv[0]=fac[0]=1;
up(i,1,mod+10){
fac[i]=fac[i-1]*i%mod;
inv[i]=ksm(fac[i],mod-2);
}
}
inline int C(int n,int m){
if(n<m) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
inline int lucas(int n,int m){
if(m==0) return 1;
return (C(n%mod,m%mod)*lucas(n/mod,m/mod))%mod;
}
Z函数
int n,m;
char a[N],b[N];
int z[N],p[N];
signed main() {
scanf("%s",a+1);
scanf("%s",b+1);
int lenb=strlen(b+1);
z[1]=lenb;
for(int i=2,l=0,r=0;i<=lenb;i++) {
z[i]=i>r?0:min(z[i-l+1],r-i+1);
while(b[1+z[i]]==b[i+z[i]])z[i]++;
if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}
int lena=strlen(a+1);
for(int i=1,l=0,r=0;i<=lena;i++){
p[i]=i>r?0:min(z[i-l+1],r-i+1);
while(p[i]<lenb&&b[1+p[i]]==a[i+p[i]])p[i]++;
if(i+p[i]-1>r)l=i,r=i+p[i]-1;
}
int ans=0;
up(i,1,lenb)ans^=i*(z[i]+1);
cout<<ans<<endl;
ans=0;
up(i,1,lena)ans^=i*(p[i]+1);
cout<<ans<<endl;
return 0;
}
失配书
inline void failtree(){
dn(i,n,1){
siz[i]++;
if(nxt[i])siz[nxt[i]]+=siz[i];
if(siz[i]>=siz[son[nxt[i]]])son[nxt[i]]=i;
}
up(i,1,n){
dep[i]=dep[nxt[i]]+1;
if(son[nxt[i]]!= i)top[i] = i;
else top[i]=top[nxt[i]];
fa[i]=nxt[i];
}
}
bool vis[N];
signed main(){
scanf("%s",s+1);
n=strlen(s+1);
getnxt();
T.failtree();
int q=read();
int l,r;
while(q--){
l=nxt[read()];r=nxt[read()];
write(T.lca(l,r),1);
}
return 0;
}
高斯消元
namespace gauss{
ldb a[500][500];
int n;
inline void work(){
for(int r=1,c=1;c<=n;c++,r++){
int t=r;
up(i,r+1,n){
if(fabs(a[i][c])>fabs(a[t][c]))t=i;
}
up(i,c,n+1)swap(a[t][i],a[r][i]);
if(!a[c][c]){
puts("No Solution");
exit(0);
}
dn(i,n+1,c)a[r][i]/=a[r][c];
up(i,r+1,n){
dn(j,n+1,c){
a[i][j]-=a[i][c]*a[r][j];
}
}
}
dn(i,n,2){
dn(j,i-1,1){
a[j][n+1]-=a[i][n+1]*a[j][i];
a[j][i]=0;
}
}
}
inline void print(){
up(i,1,n){
printf("%.3Lf ",a[i][n+1]);
}
}
}using namespace gauss;
线性基
namespace Linear_basis{
int p[100],cnt,flag0=0;
inline void insert(int x){
if(x==0)flag0=1;
dn(i,62,0){
if(x&(1ll<<i)){
if(!p[i]){
p[i]=x;
cnt++;
return;
}
else x^=p[i];
}
}
}
inline bool ask(int x){
dn(i,62,0){
if(x&(1ll<<i)){
x^=p[i];
}
}
return x==0;
}
inline int askmax(int x) {
int ans=x;
dn(i,62,0)if((ans^p[i])>ans)ans^=p[i];
return ans;
}
inline int askmin(int x){
int ans=x;
dn(i,62,0)if(ans>(p[i]^ans))ans^=p[i];
return ans;
}
}using namespace Linear_basis;
点分治
int n,m;
vector<pii>g[N];
int lim;
bool del[N];
inline int getsiz(int u,int from){
if(del[u])return 0;
int res=1;
for(auto [v,w]:g[u]){
if(v==from)continue;
res+=getsiz(v,u);
}
return res;
}
inline int getwc(int u,int from,int tot,int&wc){
if(del[u])return 0;
int sum=1,maxl=0;
for(auto [v,w]:g[u]){
if(v==from)continue;
int t=getwc(v,u,tot,wc);
maxl=max(maxl,t);
sum+=t;
}
maxl=max(maxl,tot-sum);
if(maxl<=tot/2)wc=u;
return sum;
}
inline void dfs(int u,int from,int dis,vector<int>&q){
if(del[u])return;
q.push_back(dis);
for(auto [v,w]:g[u]){
if(v==from)continue;
dfs(v,u,dis+w,q);
}
}
inline int get(vector<int>&a){
sort(a.begin(),a.end());
int res=0,len=a.size();
for(int i=len-1,j=-1;i>=0;i--){
while(j+1<i&&a[j+1]+a[i]<=lim)j++;
j=min(j,i-1);
res+=j+1;
}
return res;
}
inline int clac(int u){
if(del[u])return 0;
int res=0;
getwc(u,0,getsiz(u,0),u);
del[u]=1;
vector<int>p;
for(auto [v,w]:g[u]){
if(del[v])continue;
vector<int>q;
dfs(v,u,w,q);
res-=get(q);
for(auto x:q){
p.push_back(x);
if(x<=lim)res++;
}
}
res+=get(p);
for(auto [v,w]:g[u])res+=clac(v);
return res;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
int u,v,w;
up(i,1,n-1){
cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
cin>>lim;
cout<<clac(1)<<endl;
return 0;
}
李超线段树
int n,last;
struct line{
ldb k,b;
}p[N];
int cnt;
inline void add(int x0, int y0, int x1, int y1) {
cnt++;
if(x0==x1)p[cnt].k=0,p[cnt].b=max(y0, y1);
else p[cnt].k=1.0*(y1-y0)/(x1-x0),p[cnt].b=y0-p[cnt].k*x0;
}
int s[N];
inline ldb calc(int id,int d) { return p[id].b+p[id].k*d;}
inline int cmp(ldb x,ldb y) {
if(x-y>eps)return 1;
if(y-x>eps)return -1;
return 0;
}
inline void change(int k,int l,int r,int u){
int &v=s[k],mid=(l+r)>>1;
int bmid=cmp(calc(u,mid),calc(v,mid));
if(bmid==1||(!bmid&&u<v))swap(u,v);
int bl=cmp(calc(u,l),calc(v,l)),br=cmp(calc(u,r),calc(v,r));
if(bl==1||(!bl&&u<v))change(lc,l,mid,u);
if(br==1||(!br&&u<v))change(rc,mid+1,r,u);
}
inline void insert(int k,int tl,int tr,int l,int r,int u){
if(l<=tl&&tr<=r) {
change(k,tl,tr,u);
return;
}
int mid=(tl+tr)>>1;
if(l<=mid)insert(lc,tl,mid,l,r,u);
if(mid<r)insert(rc,mid+1,tr,l,r,u);
}
inline pdi pmax(pdi x,pdi y){
if(cmp(x.fi,y.fi)==-1)return y;
else if(cmp(x.fi,y.fi)==1)return x;
return x.se<y.se?x:y;
}
inline pdi ask(int k,int l,int r,int d){
if (r<d||d<l)return {0,0};
int mid=(l+r)>>1;
db res=calc(s[k],d);
if(l==r)return{res,s[k]};
return pmax({res,s[k]},pmax(ask(lc,l,mid,d),ask(rc,mid+1,r,d)));
}
signed main(){
n=read();
int op,k,x0,y0,x1,y1;
up(i,1,n){
op=read();
if(op==1){
x0=(read()+last-1+mod1)%mod1+1;
y0=(read()+last-1+mod2)%mod2+1;
x1=(read()+last-1+mod1)%mod1+1;
y1=(read()+last-1+mod2)%mod2+1;
if (x0>x1)swap(x0,x1),swap(y0,y1);
add(x0,y0,x1,y1);
insert(1,1,mod1,x0,x1,cnt);
}
else {
k=read();
k=(k+last-1+mod1)%mod1+1;
last=ask(1,1,mod1,k).second;
cout<<(last)<<endl;
}
}
return 0;
}