C++高阶数据结构

#include <bits/stdc++.h>
using namespace std;

#define N 100001

typedef struct node{
    int data[6];
    struct node* last;
}point;

int n, dp[6];
point snow[N];

void init(){
    for(int i=0;i<N;i++) snow[i].last=NULL;
}

bool issame(int* white){
    for(int i=0;i<6;i++){    //这里为了解决同构的问题，我们必须要考虑顺时针和逆时针，在这里我们引入了如下的方法进行优化，值得学习 
        if((dp[0]==white[i] && dp[1]==white[(i+1)%6] && dp[2]==white[(i+2)%6] && 
            dp[3]==white[(i+3)%6] && dp[4]==white[(i+4)%6] && dp[5]==white[(i+5)%6]) ||
            (dp[0]==white[i] && dp[1]==white[(i+5)%6] && dp[2]==white[(i+4)%6] &&
            dp[3]==white[(i+3)%6] && dp[4]==white[(i+2)%6] && dp[5]==white[(i+1)%6]))
            return true;
    }
    return false;
}

bool find(int key){
    point* k=snow[key].last;
    while(k!=NULL){
        if(issame(k->data)) return true;
        k=k->last;
    }
    return false;
}

void insert(int key){
    point* k=new point;
    for(int i=0;i<6;i++) k->data[i]=dp[i];
    k->last=snow[key].last;
    snow[key].last=k;
}
 
int main(){
    bool ok=false;
    init();
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int sum=0;
        for(int j=0;j<6;j++) scanf("%d",&dp[j]),sum+=dp[j];
        sum=sum%N;
        if(find(sum)) ok=true;
        else insert(sum);
    }
    if(ok) printf("Twin snowflakes found.\n");
    else printf("No two snowflakes are alike.\n");
    return 0;
}

int father[MAX];   /* father[x]表示x的父节点*/
int rank[MAX];     /* rank[x]表示x的秩*/

/* 初始化集合*/
void Make_Set(int x){
    father[x] = x;   //根据实际情况指定的父节点可变化
    rank[x] = 0;    //根据实际情况初始化秩也有所变化
}

/* 查找x元素所在的集合,回溯时压缩路径*/
int Find_Set(int x){
    if (x != father[x])
        father[x] = Find_Set(father[x]); //这个回溯时的压缩路径是精华
    return father[x];
}

/* 按秩合并x,y所在的集合。下面的那个if else结构不是绝对的，具体根据情况变化。但是，宗旨是不变的即，按秩合并，实时更新秩。*/
void Union(int x, int y){
    x = Find_Set(x);
    y = Find_Set(y);
    if (x == y) return;
    if (rank[x] > rank[y]) 
        father[y] = x;
    else{
        if (rank[x] == rank[y])
            rank[y]++;
        father[x] = y;
    }
}

#include <bits/stdc++.h>
using namespace std;

const int maxn = 50000+10;

int p[maxn]; //存父节点
int r[maxn];//存与父节点的关系 0 同一类，1被父节点吃，2吃父节点

void set(int n) //初始化{
    for(int x = 1; x <= n; x++){
        p[x] = x; //开始自己是自己的父亲节点
        r[x] = 0;//开始自己就是自己的父亲，每一个点均独立
    }
}

int find(int x) //找父亲节点{
    if(x == p[x]) return x;
    int t = p[x];
    p[x] = find(p[x]);
    r[x] = (r[x]+r[t])%3; //回溯由子节点与父节点的关系和父节点与根节点的关系找子节点与根节点的关系
    return p[x];
}

void Union(int x, int y, int d){
    int fx = find(x);
    int fy = find(y);
    p[fy] = fx; //合并树 注意：被 x 吃，所以以 x 的根为父
    r[fy] = (r[x]-r[y]+3+(d-1))%3; //对应更新与父节点的关系
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    set(n);
 
    int ans = 0;
    int d, x, y;
    while(m--){
        scanf("%d%d%d", &d, &x, &y);
        if(x > n || y > n || (d == 2 && x == y)) ans++; //如果节点编号大于最大编号，或者自己吃自己，说谎
        else if(find(x) == find(y)){ //如果原来有关系，也就是在同一棵树中，那么直接判断是否说谎
            if(d == 1 && r[x] != r[y]) ans++; //如果 x 和 y 不属于同一类
            if(d == 2 && (r[x]+1)%3 != r[y]) ans++; // 如果 x 没有吃 y (注意要对应Uinon(x, y)的情况，否则一路WA到死啊！！！)
        }
        else Union(x, y, d); //如果开始没有关系，则建立关系
    }
    printf("%d\n", ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;
const int MAXN = 3e4 + 10;
LL inv[MAXN];

void init() {
    inv[0] = inv[1] = 1;
    for (int i = 2; i <= 30000; i++)
        inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
}

LL cur, num;
int cnt[MAXN], a[MAXN], p[MAXN];

void add(int pos) {
    ++num; ++cnt[a[pos]];
    cur = cur * num % MOD;
    cur = cur * inv[cnt[a[pos]]] % MOD;
}

void del(int pos) {
    cur = cur * inv[num] % MOD;
    cur = cur * cnt[a[pos]] % MOD;
    cnt[a[pos]]--; num--;
}

struct Query {
    int l, r, id;
    bool operator < (const Query &rhs) const {
        return p[l] == p[rhs.l] ? r < rhs.r : p[l] < p[rhs.l];
    }
} q[MAXN];

LL ans[MAXN];

int main() {
    //freopen("in.txt", "r", stdin);
    init();
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        int block = ceil(sqrt(n));
        for (int i = 1; i <= n; i++) p[i] = (i - 1) / block;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d", &q[i].l, &q[i].r);
            q[i].id = i;
        }
        sort(q + 1, q + 1 + m);
        memset(cnt, 0, sizeof(cnt));
        cur = 0, num = 0;
        add(1);
        cur = 1;
        int l = 1, r = 1;
        for (int i = 1; i <= m; i++) {
            while (r > q[i].r) {
                del(r);
                r--;
            }
            while (r < q[i].r) {
                ++r;
                add(r);
            }
            while (l > q[i].l) {
                --l;
                add(l);
            }
            while (l < q[i].l) {
                del(l);
                l++;
            }
            ans[q[i].id] = cur;
        }
        for (int i = 1; i <= m; i++)
            printf("%I64d\n", ans[i]);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;

int treeNum[MAXN][MAXN];

int lowbit(int x){
    return x&(-x);
}
 
long long getSum(int x , int y){
    long long sum = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i))
        for(int j = y ; j > 0 ; j -= lowbit(j))
            sum += treeNum[i][j];
    return sum;
}
 
void add(int x , int y , int val){
    for(int i = x ; i < MAXN ; i += lowbit(i))
        for(int j = y ; j < MAXN ; j += lowbit(j))
            treeNum[i][j] += val;
}
 
void solve(int m){
    char ch;
    int x , y;
    int x1 , y1 , x2 , y2;
    memset(treeNum , 0 , sizeof(treeNum));
    while(m--){ 
        scanf("%c" , &ch); 
        if(ch == 'C'){
            scanf("%d%d" , &x1 , &y1);
            scanf("%d%d%*c" , &x2 , &y2);
            // update
            add(x1 , y1 , 1);
            add(x2+1 , y1 , -1);
            add(x1 , y2+1 , -1);
            add(x2+1 , y2+1 , 1);
        }
        else{
            scanf("%d%d%*c" , &x , &y);
            int ans = getSum(x , y);
            printf("%d\n" , ans%2);
        }
    }
}
 
int main(){
    int cas;
    int n , m;
    bool isFirst = true;
    scanf("%d" , &cas);
    while(cas){
        scanf("%d%d%*c" , &n , &m); 
        solve(m);
        if(--cas)
            puts("");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define lson i*2,l,m
#define rson i*2+1,m+1,r
const int MAXN=20000+5;  //必须为2W,因为点有1W个,所以扫描线2W个,不同的Y坐标最多有2W个

int cnt[MAXN*4],sum[MAXN*4];
double Y[MAXN];
struct seg{
    double l,r,h;
    int d;
    seg(){}
    seg(double a,double b,double c,int d):l(a),r(b),h(c),d(d){}
    bool operator <(const seg&b)const{
        if(h == b.h) return d<b.d;
        return h<b.h;
    }
}ss[MAXN];
void PushUp(int i){
    sum[i]=max(sum[i*2],sum[i*2+1]) + cnt[i];
}
void update(int ql,int qr,int v,int i,int l,int r){
    if(ql<=l && r<=qr){
        cnt[i]+=v;
        sum[i]+=v;
        return ;
    }
    int m=(l+r)>>1;
    if(ql<=m) update(ql,qr,v,lson);
    if(m<qr) update(ql,qr,v,rson);
    PushUp(i);
}
int main(){
    int n;
    double w,h;
    while(scanf("%d%lf%lf",&n,&w,&h)==3){
        if(n==0){
            printf("0\n");
            continue;
        }
        double x,y;
        int val;
        int cnt_y=0,cnt_ss=0;//记录有多少个Y值和扫描线
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%d",&x,&y,&val);
            ss[cnt_ss++] = seg(y-h/2,y+h/2,x-w/2,val);
            ss[cnt_ss++] = seg(y-h/2,y+h/2,x+w/2,-val);
            Y[cnt_y++] = y-h/2;
            Y[cnt_y++] = y+h/2;
        }
        sort(ss,ss+cnt_ss);
        sort(Y,Y+cnt_y);
        cnt_y = unique(Y,Y+cnt_y)-Y;
        int ans=0;
        memset(cnt,0,sizeof(cnt));
        memset(sum,0,sizeof(sum));
        for(int i=0;i<cnt_ss-1;i++){
            int ql=lower_bound(Y,Y+cnt_y,ss[i].l)-Y;
            int qr=lower_bound(Y,Y+cnt_y,ss[i].r)-Y-1;
            if(ql<=qr) update(ql,qr,ss[i].d,1,0,cnt_y-1);
            ans=max(ans,sum[1]);
        }
        printf("%d\n",ans);
    }
}

#include <bits/stdc++.h>
using namespace std;

#define lc (o<<1)
#define rc ((o<<1)+1)

const int MAXN = 100 + 10;

double y[MAXN<<1];
int cnt;

struct Scanline {
    double x;
    double y1, y2;
    bool is_left;
    bool operator < (const Scanline& e) const {
        return x < e.x;
    }
} scanlines[MAXN<<1];

struct Node {
    int L, R;
    double len;
    int cover;
} nodes[MAXN<<3];

int point_to(double x) {
    return lower_bound(y, y + cnt, x) - y;
}

void build(int o, int L, int R) {
    nodes[o].L = L;
    nodes[o].R = R;
    nodes[o].len = 0;
    nodes[o].cover = 0;
    if(L + 1 == R) return;
    int M = (L + R) >> 1;
    build(lc, L, M);
    build(rc, M, R);
}

void maintain_len(int o) {
    if(nodes[o].cover > 0)
        nodes[o].len = y[nodes[o].R] - y[nodes[o].L];
    else if(nodes[o].L + 1 == nodes[o].R) 
        nodes[o].len = 0;
    else
        nodes[o].len = nodes[lc].len + nodes[rc].len;
}

void my_insert(int o, int ql, int qr) {
    if(ql <= nodes[o].L && nodes[o].R <= qr) {
        nodes[o].cover++;
        maintain_len(o);
        return;
    }
    int M = (nodes[o].L + nodes[o].R) >> 1;
    if(ql < M) my_insert(lc, ql, qr);
    if(qr > M) my_insert(rc, ql, qr);
    maintain_len(o);
}

void my_delete(int o, int ql, int qr) {
    if(ql <= nodes[o].L && nodes[o].R <= qr) {
        nodes[o].cover--;
        maintain_len(o);
        return;
    }
    int M = (nodes[o].L + nodes[o].R) >> 1;
    if(ql < M) my_delete(lc, ql, qr);
    if(qr > M) my_delete(rc, ql, qr);
    maintain_len(o);
}

int main(){
    int n, kase = 0;
    double x1, y1, x2, y2;
    while(scanf("%d", &n) == 1 && n) {
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            scanlines[i<<1].x = x1;
            scanlines[i<<1].y1 = y1;
            scanlines[i<<1].y2 = y2;
            scanlines[i<<1].is_left = true;
            scanlines[(i<<1)+1].x = x2;
            scanlines[(i<<1)+1].y1 = y1;
            scanlines[(i<<1)+1].y2 = y2;
            scanlines[(i<<1)+1].is_left = false;
            y[i<<1] = y1;
            y[(i<<1)+1] = y2;
        }

        sort(y, y + 2*n);
        cnt = unique(y, y + 2*n) - y;

        sort(scanlines, scanlines + 2*n);
        build(1, 0, cnt-1);
        double area = 0;
        for(int i = 0; i < 2*n-1; i++) {
            if(scanlines[i].is_left)
                my_insert(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
            else
                my_delete(1, point_to(scanlines[i].y1), point_to(scanlines[i].y2));
            area += (scanlines[i+1].x - scanlines[i].x) * nodes[1].len;
        }
        printf("Test case #%d\n", ++kase);
        printf("Total explored area: %.2f\n\n", area);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

struct Trie{
    int num,next[30];
}trie[1005*30];

int e;
char str[1005][30],output[30];

void Insert (char str[]){
    int i,p=1;
    for (i=0;str[i];i++){
        if (trie[p].next[str[i]-'a']==0){   //构造新的节点
            trie[p].next[str[i]-'a']=++e;
            trie[e].num=0;
        }
        p=trie[p].next[str[i]-'a'];
        trie[p].num++;
    }
}

void Search (char str[]){
    int i,p=1;
    for (i=0;str[i];i++){
        if (trie[p].num==1)
            return;
        printf("%c",str[i]);
        p=trie[p].next[str[i]-'a'];
    }
}

int main (){
    int n=0;
    e=1;
    while (~scanf("%s",str[n]))
        Insert(str[n++]);
    for (int i=0;i<n;i++){
        printf("%s ",str[i]);
        Search (str[i]);
        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define maxn 200002
int t1[maxn],t2[maxn],c[maxn],r[maxn],sa[maxn],rank[maxn],height[maxn];

bool cmp(int *r,int a,int b,int l){
    return r[a]==r[b]&&r[a+l]==r[b+l];
}

void da(int str[],int sa[],int rank[],int height[],int n,int m){
    n++;
    int i,j,p,*x=t1,*y=t2;
    for(i=0;i<m;i++)c[i]=0;
    for(i=0;i<n;i++)c[x[i]=str[i]]++;
    for(i=1;i<m;i++)c[i]+=c[i-1];
    for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(j=1;j<=n;j<<=1){
        p=0;
        for(i=n-j;i<n;i++)y[p++]=i;
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
        for(i=0;i<m;i++)c[i]=0;
        for(i=0;i<n;i++)c[x[y[i]]]++;
        for(i=1;i<m;i++)c[i]+=c[i-1];
        for(i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        p=1;x[sa[0]]=0;
        for(i=1;i<n;i++)
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
        if(p>=n)break;
        m=p;
    }
    int k=0;
    n--;
    for(i=0;i<=n;i++)rank[sa[i]]=i;
        for(i=0;i<n;i++)
        {
            if(k)k--;
            j=sa[rank[i]-1];
            while(str[i+k]==str[j+k])k++;
            height[rank[i]]=k;
        }
}

char a[maxn],b[maxn];

int main(){
    while(~scanf("%s%s",a,b)){
        int la=strlen(a),lb=strlen(b);
        for(int i=0;i<la;i++)r[i]=a[i];
        r[la]='#';
        for(int i=0;i<lb;i++)r[i+la+1]=b[i];
        r[la+lb+1]=0;
        int n=la+lb+1;
        da(r,sa,rank,height,n,128);
        int ans=0;
        for(int i=2;i<=n;i++)
            if(sa[i-1]<la&&sa[i]>la||sa[i-1]>la&&sa[i]<la)
                ans=max(ans,height[i]);
        printf("%d\n",ans);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define eps 1e-9
#define LL long long
#define PI acos(-1.0)
#define bitnum(a) __builtin_popcount(a)

const int N = 10;
const int M = 100005;
const int inf = 1000000007;
const int mod = 1000000007;
const int MAXN = 100010;

//rnk从0开始
//sa从1开始,因为最后一个字符(最小的)排在第0位
//height从1开始,因为表示的是sa[i - 1]和sa[i]
//倍增算法 O(nlogn)
int wa[MAXN], wb[MAXN], wv[MAXN], ws_[MAXN];
//Suffix函数的参数m代表字符串中字符的取值范围,是基数排序的一个参数,如果原序列都是字母可以直接取128,如果原序列本身都是整数的话,则m可以取比最大的整数大1的值
//待排序的字符串放在r数组中,从r[0]到r[n-1]，长度为n
//为了方便比较大小,可以在字符串后面添加一个字符,这个字符没有在前面的字符中出现过,而且比前面的字符都要小
//同上,为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0,r[n-1]=0
//函数结束后,结果放在sa数组中,从sa[0]到sa[n-1]
void Suffix(int *r, int *sa, int n, int m){
    int i, j, k, *x = wa, *y = wb, *t;
    //对长度为1的字符串排序
    //一般来说,在字符串的题目中,r的最大值不会很大,所以这里使用了基数排序
    //如果r的最大值很大,那么把这段代码改成快速排序
    for(i = 0; i < m; ++i) ws_[i] = 0;
    for(i = 0; i < n; ++i) ws_[x[i] = r[i]]++;//统计字符的个数
    for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];//统计不大于字符i的字符个数
    for(i = n - 1; i >= 0; --i) sa[--ws_[x[i]]] = i;//计算字符排名
    //基数排序
    //x数组保存的值相当于是rank值
    for(j = 1, k = 1; k < n; j *= 2, m = k){
        //j是当前字符串的长度,数组y保存的是对第二关键字排序的结果
        //第二关键字排序
        for(k = 0, i = n - j; i < n; ++i) y[k++] = i;//第二关键字为0的排在前面
        for(i = 0; i < n; ++i) if(sa[i] >= j) y[k++] = sa[i] - j;//长度为j的子串sa[i]应该是长度为2 * j的子串sa[i] - j的后缀（第二关键字）,对所有的长度为2 * j的子串根据第二关键字来排序
        for(i = 0; i < n; ++i) wv[i] = x[y[i]];//提取第一关键字
        //按第一关键字排序 (原理同对长度为1的字符串排序)
        for(i = 0; i < m; ++i) ws_[i] = 0;
        for(i = 0; i < n; ++i) ws_[wv[i]]++;
        for(i = 1; i < m; ++i) ws_[i] += ws_[i - 1];
        for(i = n - 1; i >= 0; --i) sa[--ws_[wv[i]]] = y[i];//按第一关键字,计算出了长度为2 * j的子串排名情况
        //此时数组x是长度为j的子串的排名情况,数组y仍是根据第二关键字排序后的结果
        //计算长度为2 * j的子串的排名情况,保存到数组x
        t = x;
        x = y;
        y = t;
        for(x[sa[0]] = 0, i = k = 1; i < n; ++i)
            x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j]) ? k - 1 : k++;
        //若长度为2 * j的子串sa[i]与sa[i - 1]完全相同,则他们有相同的排名
    }
}
int Rank[MAXN], height[MAXN], sa[MAXN], r[MAXN];
void calheight(int *r,int *sa,int n){
    int i,j,k=0;
    for(i=1; i<=n; i++)Rank[sa[i]]=i;
    for(i=0; i<n; height[Rank[i++]]=k)
        for(k?k--:0,j=sa[Rank[i]-1]; r[i+k]==r[j+k]; k++);
}
bool judge(int c,int n){
    int Max=sa[0],Min=sa[0];
    for(int i=1;i<n;i++){
        if(height[i]>=c)
            Max=max(Max,sa[i]),Min=min(Min,sa[i]);
        else
            Max=sa[i],Min=sa[i];
        if(Max-Min>=c+1)
            return true;
    }
    return false;
}
int main(){
    int n,i,Max=0,L,R,mid,ans;
    while(~scanf("%d",&n)&&n){
        for(i=0;i<n;i++){
            scanf("%d",&r[i]);
            if(i)
                r[i-1]=r[i]-r[i-1]+88;
            Max=max(Max,r[i-1]);
        }
        r[i-1]=0;n--;
        Suffix(r,sa,n+1,Max+1);
        calheight(r,sa,n);
        L=0;R=n;ans=0;
        while(L<=R){
            mid=(L+R)/2;
            if(judge(mid,n+1))
                L=mid+1,ans=max(ans,mid);
            else
                R=mid-1;
        }
        if(ans<4)
            puts("0");
        else
            printf("%d\n",ans+1);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define MAX(x, y) ((x)>(y)?(x):(y))

typedef struct NODE{
    int val, data;
    int bf; //平衡因子（左子树高度与右子树高度之差）
    int h; //以当前结点为根结点的数的高度
    NODE *l, *r;
}Node;

class BalanceTree{
public:
    void Init(){
        rt = NULL;
    }
    int Height(Node *T){
        if(NULL == T) return 0;
        return T->h;
    }
    int BF(Node *l, Node *r){
        if(NULL == l && NULL == r) return 0;
        else if(NULL == l) return -r->h;
        else if(NULL == r) return l->h;
        else return l->h - r->h;
    }

    Node *LL_rotate(Node *A){
        Node *B;
        B = A->l;
        A->l = B->r;
        B->r = A;
        A->h = MAX(Height(A->l), Height(A->r)) + 1;
        B->h = MAX(Height(B->l), Height(B->r)) + 1;
        A->bf = BF(A->l, A->r);
        B->bf = BF(B->l, B->r);
        return B;
    }
    Node *RR_rotate(Node *A){
        Node *B;
        B = A->r;
        A->r = B->l;
        B->l = A;
        A->h = MAX(Height(A->l), Height(A->r)) + 1;
        B->h = MAX(Height(B->l), Height(B->r)) + 1;
        A->bf = BF(A->l, A->r);
        B->bf = BF(B->l, B->r);
        return B;
    }
    Node *LR_rotate(Node *A){
        Node *C;
        A->l = RR_rotate(A->l);
        C = LL_rotate(A);
        return C;
    }
    Node *RL_rotate(Node *A){
        Node *C;
        A->r = LL_rotate(A->r);
        C = RR_rotate(A);
        return C;
    }

    void Insert(int v, int e){
        Insert_(rt, v, e);
    }

    void Insert_(Node *&T, int v, int e){
        if(NULL == T){
            T = (Node *)malloc(sizeof(Node));
            T->val = v;
            T->data = e;
            T->bf = 0;
            T->h = 1;
            T->l = T->r = NULL;
            return;
        }
        if(e < T->data) Insert_(T->l, v, e);
        else Insert_(T->r, v, e);

        T->h = MAX(Height(T->l), Height(T->r)) + 1;
        T->bf = BF(T->l, T->r);

        if(T->bf > 1 || T->bf < -1){ //T结点失衡
            if(T->bf > 0 && T->l->bf > 0) T = LL_rotate(T); //如果T->bf > 0 则肯定有左儿子
            else if(T->bf < 0 && T->r->bf < 0) T = RR_rotate(T); //如果T->bf < 0 则肯定有右儿子
            else if(T->bf > 0 && T->l->bf < 0) T = LR_rotate(T);
            else if(T->bf < 0 && T->r->bf > 0) T = RL_rotate(T);
        }
    }

    void Delete(int flag){ //flag为1表示找最大值
        if(NULL == rt){
            printf("0\n");
            return;
        }
        Node *tmp = rt;
        if(!flag) while(tmp->l) tmp = tmp->l;
        else while(tmp->r) tmp = tmp->r;
        printf("%d\n", tmp->val);
        Delete_(rt, tmp->data);
    }

    void Delete_(Node *&T, int key){
        if(NULL == T) return;
        if(key < T->data){ //从左边删除
            Delete_(T->l, key);
            T->bf = BF(T->l, T->r); //计算删除后T结点的平衡因子
            if(T->bf < -1){ //T结点左边高度变小（删了左边的元素）导致失衡
                if(1 == T->r->bf) T = RL_rotate(T); //RL型
                else T = RR_rotate(T); //平衡因子为0或-1
            }
        }
        else if(key > T->data){ //从右边删除
            Delete_(T->r, key);
            T->bf = BF(T->l, T->r); //计算删除后T结点的平衡因子
            if(T->bf > 1){ //T结点右边高度变小（删了右边的元素）导致失衡
                if(-1 == T->l->bf) T = LR_rotate(T); //LR型
                else T = LL_rotate(T); //平衡因子为0或1
            }
        }
        else{
            if(T->l && T->r){ //左右都不为空
                Node *tmp = T;
                while(tmp->r) tmp = tmp->r;
                T->data = tmp->data;
                Delete_(T->l, tmp->data);
                T->bf = BF(T->l, T->r); //计算删除后T结点的平衡因子
                if(T->bf < -1){ //T结点左边高度变小（删了左边的元素）导致失衡
                    if(1 == T->r->bf) T = RL_rotate(T); //RL型
                    else T = RR_rotate(T); //平衡因子为0或-1
                }
            }
            else{
                Node *tmp = T;
                if(T->l) T = T->l; //有左儿子
                else if(T->r) T = T->r; //有右儿子
                else{ //T无儿子
                    free(T);
                    T = NULL;
                }
                if(T) free(tmp);
            }
        }
    }

    void Show(){
        InOrder(rt);
        printf("\n");
    }

    void InOrder(Node *T){
        if(NULL == T) return;
        InOrder(T->l);
        printf("%d(%d) ", T->val, T->data);
        InOrder(T->r);
    }

    void Free(){
        FreeTree(rt);
    }

    void FreeTree(Node *T){
        if(NULL == T) return;
        FreeTree(T->l);
        FreeTree(T->r);
        free(T);
    }

private:
    Node *rt;
};

BalanceTree bt;

int main(){
    //freopen("in.txt","r",stdin);
    int op, v, e;
    bt.Init();
    while(scanf("%d", &op), op){
        if(1 == op){
            scanf("%d%d", &v, &e);
            bt.Insert(v, e);
        }
        else if(2 == op)
            bt.Delete(1);
        else if(3 == op)
            bt.Delete(0);
    }
    bt.Free();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

#define Key_value ch[ch[root][1]][0]
const int maxn=2e5+10;

int n,m;
int a[maxn];


int root,nodecnt;
int par[maxn],ch[maxn][2];
int key[maxn],mini[maxn],size[maxn];
int lazy[maxn]; //lazy标记
bool rev[maxn]; //反转标记
int pool[maxn],poolsize; //节点回收

void NewNode(int &x,int p,int k){
    if(poolsize>0) x=pool[--poolsize];
    else x=++nodecnt;
    par[x]=p;
    ch[x][0]=ch[x][1]=0;
    key[x]=k;
    mini[x]=k;
    size[x]=1;
    lazy[x]=0;
    rev[x]=0;
}

void Update_Rev(int x){
    if(x==0) return;
    swap(ch[x][0],ch[x][1]);
    rev[x]^=1;
}

void Update_Add(int x,int val){
    if(x==0) return;
    key[x]+=val;
    mini[x]+=val;
    lazy[x]+=val;
}

void Pushup(int x){
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;

    mini[x]=key[x];
    if(ch[x][0]) mini[x]=min(mini[x],mini[ch[x][0]]);
    if(ch[x][1]) mini[x]=min(mini[x],mini[ch[x][1]]);
}

void Pushdown(int x){
    if(rev[x])
    {
        Update_Rev(ch[x][0]);
        Update_Rev(ch[x][1]);
        rev[x]=0;
    }
    if(lazy[x])
    {
        Update_Add(ch[x][0],lazy[x]);
        Update_Add(ch[x][1],lazy[x]);
        lazy[x]=0;
    }
}

void Inorder(int x){ //debug
    if(x==0) return;
    Pushdown(x);
    Inorder(ch[x][0]);
    printf("%d ",key[x]);
    Inorder(ch[x][1]);
    Pushup(x);
    if(x==root) printf("\n");
}

void Rotate(int x,int type){ //旋转，0为左旋zag，1为右旋zig
    int y=par[x];
    Pushdown(y); Pushdown(x); //先把y的标记向下传递,再把x的标记往下传递
    ch[y][!type]=ch[x][type]; par[ch[x][type]]=y;
    if(par[y]) ch[par[y]][(ch[par[y]][1]==y)]=x;
    par[x]=par[y];
    ch[x][type]=y; par[y]=x;
    Pushup(y); Pushup(x);
}

void Splay(int x,int goal){
    while(par[x]!=goal){
        if(par[par[x]]==goal) Rotate(x,ch[par[x]][0]==x); //左孩子zig，右孩子zag
        else{
            Pushdown(par[par[x]]); Pushdown(par[x]); Pushdown(x);
            int y=par[x];
            int type=(ch[par[y]][0]==y); //type=0，y是右孩子；type=1，y是左孩子
            if(ch[y][type]==x){
                Rotate(x,!type);
                Rotate(x,type);
            }
            else{
                Rotate(y,type);
                Rotate(x,type);
            }
        }
    }
    if(goal==0) root=x;
}

int Get_Kth(int x,int k){ //得到第k个节点
    Pushdown(x);
    int t=size[ch[x][0]]+1;
    if(t==k) return x;
    if(t>k) return Get_Kth(ch[x][0],k);
    else return Get_Kth(ch[x][1],k-t);
}

int Get_Min(int x){
    Pushdown(x);
    while(ch[x][0]){
        x=ch[x][0];
        Pushdown(x);
    }
    return x;
}

int Get_Max(int x){
    Pushdown(x);
    while(ch[x][1]){
        x=ch[x][1];
        Pushdown(x);
    }
    return x;
}

void Build(int &x,int l,int r,int par){ //建树，先建立中间结点，再建两端的方法
    if(l>r) return;
    int mid=(l+r)/2;
    NewNode(x,par,a[mid]);
    Build(ch[x][0],l,mid-1,x);
    Build(ch[x][1],mid+1,r,x);
    Pushup(x);
}

void Init(){ //初始化，前后各加一个空节点
    root=nodecnt=poolsize=0;
    par[root]=ch[root][0]=ch[root][1]=0;
    key[root]=size[root]=0;
    lazy[root]=rev[root]=0;
    NewNode(root,0,-1); //头部加入一个空位
    NewNode(ch[root][1],root,-1); //尾部加入一个空位
    Build(Key_value,1,n,ch[root][1]);
    Pushup(ch[root][1]);
    Pushup(root);
}

void Add(int l,int r,int val){
    Splay(Get_Kth(root,l-1+1),0); //l的前驱l-1伸展到根
    Splay(Get_Kth(root,r+1+1),root); //r的后继r+1伸展到根的右孩子
    Update_Add(Key_value,val);
    Pushup(ch[root][1]);
    Pushup(root);
}

void Move(int l,int r,int p){ //截取[l,r]放到位置p之后
    Splay(Get_Kth(root,l-1+1),0); //l的前驱l-1伸展到根
    Splay(Get_Kth(root,r+1+1),root); //r的后继r+1伸展到根的右孩子
    int tmp=Key_value; //Key_value=ch[ch[root][1]][0]所统领的子树即[l,r]
    Key_value=0; //剥离[l,r]子树
    Pushup(ch[root][1]); Pushup(root);
    Splay(Get_Kth(root,p+0+1),0); //p伸展到根
    Splay(Get_Kth(root,p+1+1),root); //p的后继p+1伸展到根的右孩子
    Key_value=tmp; par[Key_value]=ch[root][1]; //接上[l,r]子树
    Pushup(ch[root][1]); Pushup(root);
}

void Reverse(int l,int r){ //反转[l,r]区间
    Splay(Get_Kth(root,l-1+1),0);
    Splay(Get_Kth(root,r+1+1),root);
    Update_Rev(Key_value);
    Pushup(ch[root][1]);
    Pushup(root);
}

void Revolve(int l,int r,int T){
    int D=r-l+1;
    int L=T%D;
    if(L==0) return;
    Move(r-L+1,r,l-1);
}

void Insert(int p,int k){
    Splay(Get_Kth(root,p+0+1),0); //p伸展到根
    Splay(Get_Kth(root,p+1+1),root); //p的后继p+1伸展到根的右孩子
    Inorder(Key_value);
    NewNode(Key_value,ch[root][1],k);
    Pushup(ch[root][1]); Pushup(root);
}

void Collect(int x){ //回收节点x统领的子树
    if(x==0) return;
    pool[poolsize++]=x;
    Collect(ch[x][0]);
    Collect(ch[x][1]);
}

void Delete(int p){
    Splay(Get_Kth(root,p-1+1),0); //p的前驱p-1伸展到根
    Splay(Get_Kth(root,p+1+1),root); //p的后继p+1伸展到根的右孩子
    Collect(Key_value);
    par[Key_value]=0;
    Key_value=0;
    Pushup(ch[root][1]); Pushup(root);
}

int Min(int l,int r){
    Splay(Get_Kth(root,l-1+1),0);
    Splay(Get_Kth(root,r+1+1),root);
    return mini[Key_value];
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    Init();

    scanf("%d",&m);
    char op[50];
    for(int i=1;i<=m;i++){
        scanf("%s",op);
        if(op[0]=='A'){
            int x,y,D; scanf("%d%d%d",&x,&y,&D);
            Add(x,y,D);
        }
        if(op[0]=='R' && op[3]=='E'){
            int x,y; scanf("%d%d",&x,&y);
            Reverse(x,y);
        }
        if(op[0]=='R' && op[3]=='O'){
            int x,y,T; scanf("%d%d%d",&x,&y,&T);
            Revolve(x,y,T);
        }
        if(op[0]=='I'){
            int x,p; scanf("%d%d",&x,&p);
            Insert(x,p);
        }
        if(op[0]=='D'){
            int x; scanf("%d",&x);
            Delete(x);
        }
        if(op[0]=='M'){
            int x,y; scanf("%d%d",&x,&y);
            printf("%d\n",Min(x,y));
        }
        //Inorder(root);
    }
    return 0;
}