CDOJ 数据结构专题题解

ACM专题笔记

A题

• 模板题，我最大和最小写的线段树，求和写了树状数组。一开始不注意maxn少写了一个0 RE了下
• 做了区间只有一个数的特判，然后在群里试图hack数据的时候被提醒题目区间L<R(逃
• 反正只是多写了一个没有用的判断

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 4000010
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
LL int MAX[maxn];LL int MIN[maxn];
LL int val[50000+10];
LL int ans1=-0x7fffffff,ans2=0x7fffffff;
LL tree[maxn];LL N,M;
void renew(int x,LL v){
    while(x<=N){
        tree[x]+=v;
        x+=(x&(-x));
    }
    return;
}
LL query_tot(int x){
    LL ans=0;
    while(x){
        ans+=tree[x];
        x-=(x&(-x));
    }
    return ans;
}
void init(int n){
    cin>>N>>M;
    return;
}
void build(int P,int rt,int l,int r){
    if(l==r){
        MAX[rt]=val[l];
        MIN[rt]=val[l];
        return;
    }
    if(mid>=P)
        build(P,lson);
    if(mid<P)
        build(P,rson);
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
    MIN[rt]=min(MIN[rt<<1],MIN[rt<<1|1]);
    return;
}
void query(int rt,int l,int r,int L,int R){
    //L,R is what we want.
    if (L<=l&&r<=R){
        ans1=max(ans1,MAX[rt]);
        ans2=min(ans2,MIN[rt]);
        return;
    }
    if(L<=mid){
        query(lson,L,R);
    }
    if(R>mid){
        query(rson,L,R);
    }
}
int main(){
    cin>>N>>M;
    int kase,P,left,right;LL x;
    while(M--){
        scanf("%d",&kase);
        switch(kase){
        case 0:
            scanf("%d%lld",&P,&x);
            x=x-val[P];
            renew(P,x);
            val[P]+=x;
            build(P,1,1,N);
            break;
        case 1:
            scanf("%d%d",&left,&right);
            query(1,1,N,left,right);
            LL ans=query_tot(right)-query_tot(left-1);
            if(left==right){
                printf("0\n");
            }else{
                //cout<<ans<<ans1<<ans2<<endl;
                printf("%lld\n",ans-ans1-ans2);
            }
            ans1=-0x7fffffff,ans2=0x7fffffff;
            cout<<ans2<<endl;
            break;
        }
    }
}

B题

• 还是模板题，不过这道题加了区间增加，要写lazy数组。
• 简单地说就是传到能用的地方就可以停了。要用了再往下传。
• 第一天发题的时候一看是裸的模板就把之前写过的复制过去交了然后吃惊竟然WA了。之后被傅大爷私聊说数据有锅，于是睡觉（醒来发现抢到了一血）

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define maxn 1<<22
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
LL num[maxn];
int N,M;
LL lazy[maxn];
inline LL read_LL()
{
    LL k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        k=k*10+ch-'0';
        ch=getchar();
    }
    return k*f;
}
inline int read_int()
{
    int k=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        k=k*10+ch-'0';
        ch=getchar();
    }
    return k*f;
}
void renew(LL x,int wh,int rt,int l,int r){
    if(l==r){
        num[rt]+=x;
        return;
    }
    if(mid<wh){
        num[rt]+=x;
        renew(x,wh,rson);
    }else{
        num[rt]+=x;
        renew(x,wh,lson);
    }
    return;
}
LL pushdown(LL k,int L,int R,int rt,int l,int r){
    if(L<=l&&r<=R){
        lazy[rt]+=k;
        return k*(r-l+1);
    }
    LL ans=0;
    if(mid<R)
        ans+=pushdown(k,L,R,rson);
    if(mid>=L)
        ans+=pushdown(k,L,R,lson);
    num[rt]+=ans;
    return ans;
}
LL query(int L,int R,int rt,int l,int r){
    if(lazy[rt]){
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        num[rt]+=lazy[rt]*(r-l+1);
        lazy[rt]=0;
    }
    if(L<=l&&r<=R){
        return num[rt];
    }
    LL ans=0;
    //cout << L << R << rt << l << r << endl;
    if(mid<R)
        ans+=query(L,R,rson);
    if(mid>=L)
        ans+=query(L,R,lson);
    return ans;
}
void init(){
    cin>>N>>M;LL k;
    for(int i=1;i<=N;i++){
        k=read_LL();
        renew(k,i,1,1,N);
    }
    return;
}
void test(){
    for(int i=1;i<2*N;i++){
        cout<<num[i]<<' ';
    }
    cout<<endl;
    for(int i=1;i<2*N;i++){
        cout<<lazy[i]<<' ';
    }
    cout<<endl;
    return;
}
int main(){
    //init();
    int kase;int x,y;LL k;
    //test();
    cin>>N>>M;
    while(M--){
        kase=read_int();
        switch(kase){
            case 0:
                x=read_int();y=read_int();k=read_LL();
                pushdown(k,x,y,1,1,N);
                //test();
                break;
            default:
                x=read_int();y=read_int();k=read_LL();
                LL res=query(x,y,1,1,N);
                //test();
                printf("%lld\n",res);
                break;
        }
    }
    return 0;
}

C题

• 看了傅大爷的题解才终于会做。（傅爷这么强，而且还有女票，为什么这么优秀啊）思想是对于重复出现的数字，如果靠前的那个被包括在本次查询区间内，那么靠后的那个一定也在区间内，所以只需要考虑最后一个出现的位置。于是我们查询完之后进行单点更新即可。
• 题目要求 $b_{0}=1$ ，因此我们初始化的时候从第二个位置到最后一个位置初始化-1就行了。第一位不用搞。

#include <bits/stdc++.h>
using namespace std;
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson (rt<<1|1),mid+1,r
const int maxn=1e6;
int lstTree[4*maxn];
int ans=0;
void renew(int P,int val,int rt,int l,int r){
    if(l==r){
        lstTree[rt]=val;
        return;
    }
    if(P<=mid){
        renew(P,val,lson);
    }else{
        renew(P,val,rson);
    }
    lstTree[rt]=min(lstTree[rt<<1],lstTree[rt<<1|1]);
    return;
}
void query(int val,int rt,int l,int r){
    if(l==r){
        ans=l;
        return;
    }
    if(lstTree[rt<<1]<val){
        query(val,lson);
    }else{
        query(val,rson);
    }
    return;
}
int main(){
    int N;int c;
    cin>>N;
    for(int i=2;i<=N;i++){
        renew(i,-1,1,1,N);
    }
    for(int i=1;i<=N;i++){
        scanf("%d",&c);
        query(i-c,1,1,N);
        printf("%d",ans);
        if(i!=N)printf(" ");
        renew(ans,i,1,1,N);
    }
    return 0;
} 

E题

• 竟然忘了set内部是有序的…看题的时候第一反应是怎么搞带有删除中间值操作的最小堆最大堆。想了半天不会写（ORZ果然是蒟蒻）
• 思路就是用一个map和一个set 乱搞。 map用来查询现在这个游戏的价格，set用来存储游戏并排序。

#include <bits/stdc++.h>
using namespace std;
map<string,int> M;
set<pair<int,string> >S;
int N;
void insert(string x,int y){
    if(M.find(x)==M.end()){
        M.insert(pair<string,int>(x,y));
        S.insert(pair<int,string>(y,x));
    }
    return;
}
void erase(string ss){
    if(M.find(ss)==M.end()){
        return;
    }
    int num=M[ss];
    S.erase(pair<int,string>(num,ss));
    M.erase(ss);
    return;
}
void change(string ss,int x){
    if(M.find(ss)==M.end()){
        return;
    }
    int num=M[ss];
    S.erase(pair<int,string>(num,ss));
    S.insert(pair<int,string>(x,ss));
    M[ss]=x;
    return;
}
void output(int opt){
    if(S.size()==0){
        return;
    }
    if(opt==1){
        set<pair<int,string> >::iterator it=S.begin();
        cout<<it->second<<endl;
    }else{
        set<pair<int,string> >::iterator it=S.end();
        it--;
        cout<<it->second<<endl;
    }
    return;
}
int main(){
    cin>>N;int opt;
    while(N--){
        cin>>opt;
        string x;int y;
        switch(opt){
        case 1:cin>>x>>y;   insert(x,y);break;
        case 2:cin>>x;      erase(x);   break;
        case 3:cin>>x>>y;   change(x,y);break;
        case 4:cin>>y;      output(y);  break;
        }
    }
    return 0;
}

G题

队列搞一搞就行。题目显然是先进先出，然后删除操作是删除队首的。所以就可以用队列搞出来。
“袁姐姐最漂亮！”

#include <bits/stdc++.h>
using namespace std;
#define LL long long
struct node{
    int id;
    int start_T;
    int last;
};
int N;deque<node>Q;int size;
int main(){
    cin>>N;int opt;LL t;node X;int a,b;
    for(int i=0;i<N;i++){
        scanf("%d%lld",&opt,&t);
        switch(opt){
        case 1:
            scanf("%d%d",&a,&b);
            X.id=a;X.start_T=b;X.last=t;
            Q.push_back(X);
            size++;
            break;
        case 2:
            while(size){
                X=Q.front();
                if(t<X.start_T+X.last){
                    break;
                }else{
                    size--;
                    Q.pop_front();
                }
            }
            if(size){
                Q.pop_front();
                size--;
            }
            break;
        case 3:
            while(size){
                X=Q.front();
                if(t<X.start_T+X.last){
                    break;
                }else{
                    Q.pop_front();
                    size--;
                }
            }
            if(size){
                printf("%d\n",X.id);
            }else{
                printf("-1\n");
            }
            break;
        }
    }
    return 0;
}

I题

• 带计数功能的并查集，其实就是合并的时候把两个集合的元素个数加起来就行了。
• 因此在merge函数里面加上Num[x]=Num[x]+Num[y];这一条即可。

#include <bits/stdc++.h>
using namespace std;
int Dad[100000+10];
int Num[100000+10]; 
int N,M;
int find(int i){
    int x=i;
    while(x!=Dad[x]){
        x=Dad[x];
    }
    while(i!=x){
        Dad[i]=x;
        i=Dad[i];
    }
    return i;
}
void merge(int a,int b){
    int x=find(a);
    int y=find(b);
    Num[x]=Num[x]+Num[y];
    Dad[y]=x;
    return;
}
void init(){
    cin>>N>>M;int v1,v2;
    for(int i=0;i<=N;i++){
        Dad[i]=i;Num[i]=1;
    }
    for(int i=0;i<M;i++){
        scanf("%d%d",&v1,&v2);
        if(find(v1)!=find(v2))
            merge(v1,v2);
    }
    return;
}
void query(){
    int Q;cin>>Q;int v;
    while(Q--){
        scanf("%d",&v);
        int x=find(v);
        printf("%d\n",Num[x]);
    }
    return;
}
int main(){
    init();
    query();
    return 0;
}

J题

• 类似于食物链一题。当然题解写的是关系并查集，然而我还是习惯写补集法。
• 一倍存自身，一倍存下一个，一倍存上一个
• 同类合并的时候在三个集合中分别合并
• 不同类合并的时候 A下一个是B / B上一个是A / B的上一个是A的下一个 三次合并即可
• 这种方法可以用来解决多个元素成环的关系型问题。

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
int Dad[maxn*3];int N,K;
void init(){
    cin>>N>>K;
    for(int i=1;i<=3*N;i++){
        Dad[i]=i;
    }
    return;
}
int find(int x){
    int i=x;
    while(Dad[i]!=i){
        i=Dad[i];
    }
    while(x!=i){
        Dad[x]=i;
        x=Dad[x];
    }
    return i;
}
void merge(int x,int y){
    int m=find(x);
    int n=find(y);
    Dad[n]=m;
    return;
}
void judge(){
    int kase,x,y;int num=0;
    while(K--){
        scanf("%d%d%d",&kase,&x,&y);
        if(x>N||y>N){
            printf("%d",num+1);
            break;
        }
        switch(kase){
        case 1:
            if(find(N+x)==find(y)||find(N+y)==find(x)){
                printf("%d",num+1);
                return;
            }else{
                merge(x,y);
                merge(N+x,N+y);
                merge(2*N+x,2*N+y); 
            }
            break; 
        case 2:
            if(find(x)==find(y)){
                printf("%d",num+1);
                return;
            }else{
                if(find(N+x)==find(y)){
                    printf("%d",num+1);
                    return;
                }else{
                    merge(N+y,x);
                    merge(2*N+x,y);
                    merge(y+2*N,x+N);
                    break;
                }
            }
        }
        num=(num+1)%3;
    }
    printf("-1");
    return;
}
int main(){
    init();
    judge();
    return 0;
} 

K题

• 第一道吃瓜题 本质是两种西瓜构成一个环。所以我仍然使用建立补集法做了。很好做。
• 值得注意的是2/3的判断应该如何进行，首先通过find(x)==find(y)判断完是否是同类之后，应该使用find(x+N)==find(y)和find(y+N)==find(x)两边各判断一次是否是不同类别西瓜，都找不到的情况下才是3。

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000100 
int Dad[maxn*2];
bool vis[maxn];
int N,M;
int find(int x){
    int i=x;
    while(x!=Dad[x]){
        x=Dad[x];
    }
    while(i!=x){
        Dad[i]=x;
        i=Dad[i];
    }
    return i;
}
void merge(int x,int y){
    int m=find(x);
    int n=find(y);
    Dad[m]=n;
    return;
}
void query(){
    string s;int v1,v2,kase;
    while(M--){
        cin>>s;
        if(s=="Q"){
            scanf("%d%d",&v1,&v2);
            if(find(v1)==find(v2)){
                printf("1\n");
            }else{
                if(find(N+v1)==find(v2)||find(N+v2)==find(v1)){
                    printf("2\n");
                }else{
                    printf("3\n");
                }
            }
        }else{
            scanf("%d%d%d",&v1,&v2,&kase);
            vis[v1]=true;vis[v2]=true;
            switch(kase){
            case 1:
                merge(v1,v2);
                merge(v1+N,v2+N);
                break;
            case 2:
                merge(v1+N,v2);
                merge(v2+N,v1);
                break;
            }
        }
    }
    return;
}
void init(){
    cin>>N>>M;
    for(int i=1;i<=2*N;i++){
        Dad[i]=i;
    }
    return;
}
int main(){
    init();
    query();
    return 0;
}

L题

• 第二道吃瓜题，我把相同和不同的分别做了处理，不同的存下来，相同的进行合并。每次查询的时候先看是不是同类，然后再搜索一遍现在的不同集合里有没有现在查询的这两个西瓜。这里要注意的点是存在集合里的是初始的的输入值，但查询的时候应该找它的祖先进行查询而不是直接查询。另外是也需要两边分别查询。

#include <bits/stdc++.h>
using namespace std;
int Dad[100000+10];
int N,M;
pair<int,int> num[200000+10];
int size;
int find(int i){
    int x=i;
    while(Dad[i]!=i){
        i=Dad[i];
    } 
    while(x!=i){
        Dad[x]=i;
        x=Dad[x];
    }
    return i;
}
void merge(int x,int y){
    int m=find(x);
    int n=find(y);
    Dad[m]=n;
    return;
}
void init(){
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        Dad[i]=i;
    }
    return;
}
int main(){
    init();string ss;int v1,v2,opt;
    for(int j=0;j<M;j++){
        //cout<<j<<endl;
        cin>>ss;
        if(ss=="A"){
            scanf("%d%d%d",&v1,&v2,&opt);
            if(opt==1){
                merge(v1,v2);
            }else{
                num[size].first=v1;num[size].second=v2;
                size++;
            }
        }else{
            scanf("%d%d",&v1,&v2);
            if(find(v1)==find(v2)){
                printf("1\n");
            }else{
                int flag=0;
                for(int i=0;i<size;i++){
                    int x=find(num[i].first);
                    int y=find(num[i].second);
                    if(x==find(v1)&&y==find(v2)){
                        printf("2\n");
                        flag=1;
                        break;
                    }
                    if(y==find(v1)&&x==find(v2)){
                        printf("2\n");
                        flag=1;
                        break;
                    }
                }
                if(!flag){
                    printf("3\n");
                }
            }
        }
    }
    return 0;
}

M题

• 我的分块写法会TLE不得不照着网上的模板改了一发…去洛谷交了一次，发现我平时写的板的运行速度比网上的标答要慢大概3倍左右QAQ。

本质上是支持四个操作:

• 整块查询、块内查询

• 整块更新、块内更新

  1. 整块查询可以使用二分法查询
  2. 块内查询直接暴力更新
  3. 整块更新直接打上tag标记即可
  4. 块内更新直接暴力更新

#include <bits/stdc++.h> 
using namespace std;
int N,block;
int val[100005],bl[100005],atag[100005];
set<int>st[105];
void add(int a,int b,int c){
    for(int i=a;i<=min(bl[a]*block,b);i++){
        st[bl[a]].erase(val[i]);
        val[i]+=c;
        st[bl[a]].insert(val[i]);
    }
    if(bl[a]!=bl[b]){
        for(int i=(bl[b]-1)*block+1;i<=b;i++){
            st[bl[b]].erase(val[i]);
            val[i]+=c;
            st[bl[b]].insert(val[i]);
        }
    }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        atag[i]+=c;
}
int query(int a,int b,int c){
    int ans=-1;
    for(int i=a;i<=min(bl[a]*block,b);i++){
        int value=val[i]+atag[bl[a]];
        if(value<c)ans=max(value,ans);
    }
    if(bl[a]!=bl[b])        
        for(int i=(bl[b]-1)*block+1;i<=b;i++){
            int value=val[i]+atag[bl[b]];
            if(value<c)ans=max(value,ans);
        }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
    {
        int x=c-atag[i];
        set<int>::iterator it=st[i].lower_bound(x);
        if(it==st[i].begin())continue;
        --it;
        ans=max(ans,*it+atag[i]);
    }
    return ans;
}
int main(){
    scanf("%d",&N);block=1000;
    for(int i=1;i<=N;i++)
        scanf("%d",&val[i]);
    for(int i=1;i<=N;i++){
        bl[i]=(i-1)/block+1;
        st[bl[i]].insert(val[i]);
    }
    for(int i=1;i<=N;i++){
        int f,a,b,c;
        scanf("%d%d%d%d",&f,&a,&b,&c);
        if(f==0)add(a,b,c);
        if(f==1)printf("%d\n",query(a,b,c));
    }
    return 0;
}

N题

• 因为数据范围保证了实际上某个数字开方几次之后就会变成0或者1，这样继续开方后就不再变化，因此给它打上标记表示已经不能再开方了。如果整块都是不能再开方的数据这块就没必要开方了。

#include<bits/stdc++.h>
using namespace std;
int N,block;
int bl[50005];
int val[50005],sum[50005],flag[50005];
void solve_sqrt(int x){
    if(flag[x])
        return;
    flag[x]=1;sum[x]=0;
    for(int i=(x-1)*block+1;i<=x*block;i++){
        val[i]=sqrt(val[i]);
        sum[x]+=val[i];
        if(val[i]>1)
            flag[x]=0;
    }
}
void add(int a,int b,int c){
    for(int i=a;i<=min(bl[a]*block,b);i++){
        sum[bl[a]]-=val[i];
        val[i]=sqrt(val[i]);
        sum[bl[a]]+=val[i];
    }
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*block+1;i<=b;i++){
            sum[bl[b]]-=val[i];
            val[i]=sqrt(val[i]);
            sum[bl[b]]+=val[i];
        }
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        solve_sqrt(i);
}
int query(int a,int b){
    int ans=0;
    for(int i=a;i<=min(bl[a]*block,b);i++)
        ans+=val[i];
    if(bl[a]!=bl[b])
        for(int i=(bl[b]-1)*block+1;i<=b;i++)
            ans+=val[i];
    for(int i=bl[a]+1;i<=bl[b]-1;i++)
        ans+=sum[i];
    return ans;
}
int main(){
    cin>>N;
    block=sqrt(N);
    for(int i=1;i<=N;i++)
        scanf("%d",&val[i]);
    for(int i=1;i<=N;i++){
        bl[i]=(i-1)/block+1;
        sum[bl[i]]+=val[i];
    }
    for(int i=1;i<=N;i++){
        int f,a,b,c;
        scanf("%d%d%d%d",&f,&a,&b,&c);
        if(f==0)
            add(a,b,c);
        if(f==1)
            printf("%d\n",query(a,b));
    }
    return 0;
}

Q题

区间更新，单点查询。

• 我写了树状数组的更新
• （虽然我看到了分块做法有加分的Hint，但是在下的分块写的不熟练）

#include <bits/stdc++.h>
using namespace std;
#define maxn 50010
#define LL long long
LL Tree[maxn];
int N;
void renew(int pos,LL val){
    while(pos<=N){
        Tree[pos]+=val;
        pos+=(pos&(-pos));
    }
    return;
}
LL query(int pos){
    LL ans=0;
    while(pos){
        ans+=Tree[pos];
        pos-=(pos&(-pos));
    }
    return ans;
}
void init(){
    scanf("%d",&N);LL val,lst=0;
    for(int i=1;i<=N;i++){
        scanf("%lld",&val);
        val-=lst;
        lst+=val;
        renew(i,val);
    }
    return;
}
int main(){
    init();int opt,l,r;LL c;
    for(int i=1;i<=N;i++){
        scanf("%d%d%d%lld",&opt,&l,&r,&c);
        switch(opt){
        case 0:
            renew(l,c);
            renew(r+1,-c);
            break;
        case 1:
            printf("%lld\n",query(r));
            break;
        }
    }
    return 0;
}

R题

• 对于操作一，是区间增加，可以用树状数组搞定。方法是在增加的区间左端点+1，在增加的区间右端点的右侧一位-1
• 对于操作二，对某个数的倍数都+1。我分别处理大于根号N和小于根号N的数据了。原因是小于根号N的要更新超过根号N次太慢，所以存起来要用了再用，大于的就直接更新掉。
• 对于操作三，先求出操作一和二的和，然后让士兵按照需要走几步走几步。这里考虑到这个图中必定存在环，所以在最开始的初始化过程中进行一波模拟找环，然后士兵一旦走到环上就直接除以环上的城市个数，剩下的步数再直接模拟。

代码运行时间：148ms

#include <bits/stdc++.h>
using namespace std;
const int maxn=200000;
int Tree[maxn+10];
int Mod[1000];int N,M,S,Q;
string city;string soldier;
int Huan[30];int vis[30];
void test(){
    for(int i=0;i<N;i++){
        cout<<vis[i]<<" "<<Huan[i]<<endl;
    }
    return;
}
void renew(int x,int val){
    while(x<=M){
        Tree[x]+=val;
        x+=(x&(-x));
    }
    return;
}
int query(int x){
    int val=0;
    while(x>0){
        val+=Tree[x];
        x-=(x&(-x));
    }
    return val;
}
void init(){
    cin>>N>>M>>city>>soldier;S=sqrt(M);
    for(int i=0;i<N;i++){
        if(vis[i]){
            continue;
        }
        int pos=i;int num=0;
        while(vis[pos]==0){
            vis[pos]=1;
            Huan[pos]=num;
            pos=city[pos]-'A';
            num++;
        }
        int j=i;
        while(j!=pos){
            vis[j]=-1;
            Huan[j]=0;
            j=city[j]-'A';
        }
        num=num-Huan[pos];
        while(vis[pos]==1){
            Huan[pos]=num;
            vis[pos]=2;
            pos=city[pos]-'A';
        }
    }
    return;
}
void multi(int x){
    if(x<=S){
        Mod[x]++;
    }else{
        for(int i=x;i<=M;i+=x){
            soldier[i-1]=city[soldier[i-1]-'A'];
        }
    }
    return;
}
void find(int x){
    int add=query(x);int num=min(S,x);
    if(x&1){
        for(int i=1;i<=num;i+=2){
            if(!(x%i)){
                add+=Mod[i];
            }
        }
    }else{
        for(int i=1;i<=num;i++){
            if(!(x%i)){
                add+=Mod[i];
            }
        }
    }
    int now=soldier[x-1]-'A';
    while(vis[now]==-1){
        if(add==0){
            printf("%c\n",now+'A');
            return;
        }else{
            now=city[now]-'A';
            add--;
        }
    }
    add=add%Huan[now];
    while(add){
        now=city[now]-'A';
        add--;
    }
    printf("%c\n",now+'A');
    return;
}
int main(){
    init();cin>>Q;int opt,l,r;
    while(Q--){
        scanf("%d",&opt);
        switch(opt){
        case 1:scanf("%d%d",&l,&r);renew(l,1);renew(r+1,-1);break;
        case 2:scanf("%d",&r);multi(r);break;
        case 3:scanf("%d",&r);find(r);break;
        }
    }
}