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

#define ls (i<<1) // 左子节点
#define rs (i<<1|1) // 右子节点
#define mid ((l+r)>>1) // 当前区间中部

int tree[1000005<<2],tag[1000005<<2];
int n,m;
int a[1000005];

void pushup(int i){
    tree[i]=tree[ls]+tree[rs];
}
void build(int i,int l,int r){
    if(l==r){
        tree[i]=a[l];
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}
void pushdown(int i,int l,int r){
    if(tag[i]){ // 如果有标记
        tag[ls]+=tag[i]; // 左节点更新标记
        tag[rs]+=tag[i]; // 右节点更新标记
        tree[ls]+=(mid-l+1)*tag[i]; // 左节点更新值
        tree[rs]+=(r-mid)*tag[i]; // 右节点更新值
        tag[i]=0; // 清除当前节点标记
    }
}
void update(int i,int l,int r,int x,int y,int k){
    if(l>=x&&r<=y){ // 被包含
        tree[i]+=(r-l+1)*k; // 修改本身的值
        tag[i]+=k; // 打标记
        return ;
    }
    pushdown(i,l,r); // 标记下传
    if(mid>=x) update(ls,l,mid,x,y,k);
    if(mid<y) update(rs,mid+1,r,x,y,k); // 二分
    pushup(i); // 上传
}
int query(int i,int l,int r,int x,int y){
    if(l>=x&&r<=y){ // 被包含
        return tree[i];
    }
    pushdown(i,l,r);// 标记下传
    int ret=0;
    if(mid>=x) ret+=query(ls,l,mid,x,y);
    if(mid<y) ret+=query(rs,mid+1,r,x,y);// 二分
    return ret;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        int opt,l,r,k;
        cin>>opt>>l>>r;
        if(opt==1){
            cin>>k;
            update(1,1,n,l,r,k);
        }
        else{
            cout<<query(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
}


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

const int SIZE = 1e6 + 5;
int t[SIZE << 2], a[SIZE];
int n, m;

void pushup(int i) {
    t[i] = t[i << 1] + t[i << 1 | 1];
}

void build(int i, int l, int r) {
    if (l == r) {
        t[i] = a[l];
        return;
    }

    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    pushup(i);
}

int query(int ql, int qr, int l, int r, int i) {
    if (ql <= l && r <= qr) {
        return t[i];
    }

    int mid = (l + r) >> 1;
    int result = 0;

    if (ql <= mid) {
        result += query(ql, qr, l, mid, i << 1);
    }

    if (qr > mid) {
        result += query(ql, qr, mid + 1, r, i << 1 | 1);
    }

    return result;
}

void update(int p, int l, int r, int i, int v) {
    if (l == r) {
        t[i] += v;
        return;
    }

    int mid = (l + r) >> 1;

    if (p <= mid) {
        update(p, l, mid, i << 1, v);
    }

    if (p > mid) {
        update(p, mid + 1, r, i << 1 | 1, v);
    }

    pushup(i);
}

signed main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build(1, 1, n);

    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;

        if (op == 1) {
            update(x, 1, n, 1, y);
        } else {
            cout << query(x, y, 1, n, 1) << endl;
        }
    }

    return 0;
}



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

const int SIZE = 2e5+5;
int t[SIZE<<2],a[SIZE];
int n,m;

void pushup(int i){
    t[i]=max(t[i<<1],t[i<<1|1]);
}

void build(int i,int l,int r){
    if(l==r){
        t[i]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}

int query(int ql,int qr,int l,int r,int i){
    if(ql<=l && r <= qr){
        return t[i];
    }
    int mid = (l+r)>>1;
    int result = 0;
    if(ql <= mid){
        result = max(result,query(ql,qr,l,mid,i<<1));
    }
    if(qr > mid){
        result = max(result,query(ql,qr,mid+1,r,i<<1|1));
    }
    return result;
}

void update(int p,int l,int r,int i,int v){
    if(l==r){
        if(t[i]<v){
            t[i]=v;
        }
        return;
    }
    int mid=(l+r)>>1;
    if(p <= mid){
        update(p,l,mid,i<<1,v);
    }
    if(p > mid){
        update(p,mid+1,r,i<<1|1,v);
    }
    pushup(i);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(m--){
        char op;int a,b;
        cin>>op>>a>>b;
        if(op=='Q'){
            cout<<query(a,b,1,n,1)<<endl;
        }
        else{
            update(a,1,n,1,b);
        }
    }
    return 0;
}


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

int t[800005];
int m,d;
char op;
int x,tt,cnt;

void pushup(int i){
    t[i]=max(t[i<<1],t[i<<1|1])%d;
}
void update(int pv,int v,int i,int l,int r){
    if(l==r){
        t[i]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=pv){
        update(pv,v,i<<1,l,mid);
    }
    if(mid<pv){
        update(pv,v,i<<1|1,mid+1,r);
    }
    pushup(i);
}

int ask(int ql,int qr,int i,int l,int r){
    if(ql<=l&&qr>=r){
        return t[i];
    }
    int mid=(l+r)>>1;
    int result=LLONG_MIN;
    if(ql<=mid){
        result=max(result,ask(ql,qr,i<<1,l,mid));
    }
    if(qr>mid){
        result=max(result,ask(ql,qr,i<<1|1,mid+1,r));
    }
    return result;
}

signed main(){
    cin>>m>>d;
    for(int i=1;i<=m;i++){
        cin>>op>>x;
        if(op=='A'){
            update(cnt+1,(x+tt)%d,1,1,m);
            cnt++;
        }
        else{
            if(x==0)tt=0;
            else tt=ask(cnt-x+1,cnt,1,1,m)%d;
            cout<<tt<<endl;
        }
    }
    return 0;
}


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

int n, q, a[1000005];
int maxn[1000005 << 2], minn[1000005 << 2];
bool flag = true;

void pushup(int i) {
    maxn[i] = max(maxn[i << 1], maxn[i << 1 | 1]);
    minn[i] = min(minn[i << 1], minn[i << 1 | 1]);
}

void build(int i, int l, int r) {
    if (l == r) {
        maxn[i] = minn[i] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    pushup(i);
}

int querymax(int L, int R, int l, int r, int i) {
    if (L <= l && r <= R) {
        return maxn[i];
    }
    int mid = (l + r) >> 1;
    int result = INT_MIN;
    if (L <= mid) {
        result = max(result, querymax(L, R, l, mid, i << 1));
    }
    if (R > mid) {
        result = max(result, querymax(L, R, mid + 1, r, i << 1 | 1));
    }
    return result;
}
int querymin(int L, int R, int l, int r, int i) {
    if (L <= l && r <= R) {
        return minn[i];
    }
    int mid = (l + r) >> 1;
    int result = INT_MAX;
    if (L <= mid) {
        result = min(result, querymin(L, R, l, mid, i << 1));
    }
    if (R > mid) {
        result = min(result, querymin(L, R, mid + 1, r, i << 1 | 1));
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<querymax(l,r,1,n,1)-querymin(l,r,1,n,1)<<endl;
    }
    return 0;
}


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

int n, m, c, a[1000005];
int maxn[1000005 << 2], minn[1000005 << 2];
bool flag = true;

void pushup(int i) {
    maxn[i] = max(maxn[i << 1], maxn[i << 1 | 1]);
    minn[i] = min(minn[i << 1], minn[i << 1 | 1]);
}

void build(int i, int l, int r) {
    if (l == r) {
        maxn[i] = minn[i] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid);
    build(i << 1 | 1, mid + 1, r);
    pushup(i);
}

int querymax(int L, int R, int l, int r, int i) {
    if (L <= l && r <= R) {
        return maxn[i];
    }
    int mid = (l + r) >> 1;
    int result = INT_MIN;
    if (L <= mid) {
        result = max(result, querymax(L, R, l, mid, i << 1));
    }
    if (R > mid) {
        result = max(result, querymax(L, R, mid + 1, r, i << 1 | 1));
    }
    return result;
}
int querymin(int L, int R, int l, int r, int i) {
    if (L <= l && r <= R) {
        return minn[i];
    }
    int mid = (l + r) >> 1;
    int result = INT_MAX;
    if (L <= mid) {
        result = min(result, querymin(L, R, l, mid, i << 1));
    }
    if (R > mid) {
        result = min(result, querymin(L, R, mid + 1, r, i << 1 | 1));
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> c;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= n - m + 1; i++) {
        //cout<<i<<' '<<querymax(i, i + m - 1, 1, n, 1)<<' '<<querymin(i, i + m - 1, 1, n, 1)<<endl;
        if ((querymax(i, i + m - 1, 1, n, 1) - querymin(i, i + m - 1, 1, n, 1)) <= c) {
            cout << i << endl;
            flag = false;
        }
    }
    if (flag) {
        cout << "NONE" << endl;
    }
    return 0;
}

内带数据生成程序 sj。

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

const int SIZE = 2e5+5;
int t[SIZE<<2],a[SIZE];
int n,m;

void pushup(int i) {
    t[i]=max(t[i<<1],t[i<<1|1]);
}

void build(int i,int l,int r) {
    if(l==r) {
        t[i]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(i<<1,l,mid);
    build(i<<1|1,mid+1,r);
    pushup(i);
}

int query(int ql,int qr,int l,int r,int i) {
    if(ql<=l && r <= qr) {
        return t[i];
    }
    int mid = (l+r)>>1;
    int result = 0;
    if(ql <= mid) {
        result = max(result,query(ql,qr,l,mid,i<<1));
    }
    if(qr > mid) {
        result = max(result,query(ql,qr,mid+1,r,i<<1|1));
    }
    return result;
}

void update(int p,int l,int r,int i,int v) {
    if(l==r) {
        if(t[i]<v) {
            t[i]=max(t[i],v);
        }
        return;
    }
    int mid=(l+r)>>1;
    if(p <= mid) {
        update(p,l,mid,i<<1,v);
    }
    if(p > mid) {
        update(p,mid+1,r,i<<1|1,v);
    }
    pushup(i);
}

void solve() {
    memset(a,0,sizeof(a));
    memset(t,0,sizeof(t));
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    build(1,1,n);
    while(m--) {
        int opt,a,b;
        cin>>opt>>a>>b;
        if(opt==2) {
            if(b<a)swap(b,a);
            cout<<query(a,b,1,n,1)<<endl;
        } else {
            update(a,1,n,1,b);
        }
    }
    return;
}

int sj()    {

    srand(time(0));
    for(int i=1; i<=49; i++) {
        char buff[114],buff2[514];
        sprintf(buff,"data/%d.in",i);
        sprintf(buff2,"data/%d.out",i);
        freopen(buff,"w",stdout);
        int n=rand()%(int(1e5))+1,m=rand()%(int(4000))+1;
        cout<<n<<' '<<m<<endl;
        for(int j=1; j<=n; j++) {
            cout<<rand()%(int(1e5))+1<<' ';
        }
        cout<<endl;
        for(int j=1; j<=m; j++) {
            int op = rand()%2+1;
            int l,r;
            if(op==1) {
                l=rand()%(int(n))+1;
                r=rand()%(int(1e5))+1;
            } else {
                l=rand()%(int(n))+1;
                r=rand()%(int(n))+1;
            }
            cout<<op<<' '<<l<<' '<<r<<endl;
        }
        fclose(stdout);
        freopen(buff2,"w",stdout);
        freopen(buff,"r",stdin);
        solve();
        fclose(stdin);
        fclose(stdout);
    }
    return 0;

}

int main(){
    solve();
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;

struct node{
    int maxv,add,cov;
    node(){
        this->cov = LLONG_MIN;
        this->add = 0;
    }
} t[4000005];
int a[1000005];
int n,q;

inline void pushup(int i){
    t[i].maxv=max(t[ls].maxv,t[rs].maxv);
}

void build(int i,int l,int r){
    if(l==r){
        t[i].maxv=a[l];
    }
    else{
        build(ls,l,mid);
        build(rs,mid+1,r);
        pushup(i);
    }
}

void pushdown(int i){
    if(t[i].cov!=LLONG_MIN){
        t[ls].maxv=t[rs].maxv=t[ls].cov=t[rs].cov=t[i].cov;
        //t[ls].cov+=t[ls].add;
        //t[rs].cov+=t[rs].add;
        t[ls].add=t[rs].add=0;
        t[i].cov=LLONG_MIN;
    }
    if(t[i].add){
        t[ls].add+=t[i].add;
        t[rs].add+=t[i].add;
        t[ls].maxv+=t[i].add;
        t[rs].maxv+=t[i].add;
        t[i].add=0;
    }
}

void add(int ql,int qr,int v,int i,int l,int r){
    if(ql<=l&&r<=qr){
        t[i].maxv+=v;
        t[i].add+=v;
        return;
    }
    pushdown(i);
    if(ql<=mid){
        add(ql,qr,v,ls,l,mid);
    }
    if(mid<qr){
        add(ql,qr,v,rs,mid+1,r);
    }
    pushup(i);
}

void cover(int ql,int qr,int v,int i,int l,int r){
    if(ql<=l&&r<=qr){
        t[i].maxv=v;
        t[i].cov=v;
        t[i].add=0;
        return;
    }
    pushdown(i);
    if(ql<=mid){
        cover(ql,qr,v,ls,l,mid);
    }
    if(mid<qr){
        cover(ql,qr,v,rs,mid+1,r);
    }
    pushup(i);
}

int query(int ql,int qr,int i,int l,int r){
    if(ql<=l&&r<=qr){
        return t[i].maxv;
    }
    pushdown(i);
    int result=LLONG_MIN;
    if(ql<=mid){
        result=max(result,query(ql,qr,ls,l,mid));
    }
    if(mid<qr){
        result=max(result,query(ql,qr,rs,mid+1,r));
    }
    return result;
}

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(q--){
        int op,l,r,x;
        cin>>op;
        if(op==2){
            cin>>l>>r>>x;
            add(l,r,x,1,1,n);
        }
        if(op==1){
            cin>>l>>r>>x;
            cover(l,r,x,1,1,n);
        }
        if(op==3){
            cin>>l>>r;
            cout<<query(l,r,1,1,n)<<endl;
        }
    }
    return 0;
}



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

long long c[500010];
long long p;

struct sgt{
    long long sum[2000010];
    long long addv[2000010];
    long long mulv[2000010];
    void build(int o,int l,int r){
        addv[o]=0;
        mulv[o]=1;
        if(l==r)sum[o]=c[l];
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            build(lson,l,mid);
            build(rson,mid+1,r);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }
    void push_down(int o,int l,int r,int mid,int lson,int rson){
        mulv[lson]=(mulv[lson]*mulv[o])%p;
        mulv[rson]=(mulv[rson]*mulv[o])%p;
        addv[lson]=(addv[lson]*mulv[o])%p;
        addv[rson]=(addv[rson]*mulv[o])%p;
        sum[lson]=(sum[lson]*mulv[o])%p;
        sum[rson]=(sum[rson]*mulv[o])%p;
        mulv[o]=1;
        addv[lson]=(addv[lson]+addv[o])%p;
        addv[rson]=(addv[rson]+addv[o])%p;
        sum[lson]=(sum[lson]+(mid-l+1)*addv[o])%p;
        sum[rson]=(sum[rson]+(r-mid)*addv[o])%p;
        addv[o]=0;
    }
    void addall(int o,int l,int r,int a,int b,int x){
        if(l>=a && r<=b){
            addv[o]=(addv[o]+x)%p;
            sum[o]=(sum[o]+(r-l+1)*x)%p;
            return;
        }
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)addall(lson,l,mid,a,b,x);
            if(b>mid)addall(rson,mid+1,r,a,b,x);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }
    void mulall(int o,int l,int r,int a,int b,int x){
        if(l>=a && r<=b){
            mulv[o]=(mulv[o]*x)%p;
            addv[o]=(addv[o]*x)%p;
            sum[o]=(sum[o]*x)%p;
            return;
        }
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)mulall(lson,l,mid,a,b,x);
            if(b>mid)mulall(rson,mid+1,r,a,b,x);
            sum[o]=(sum[lson]+sum[rson])%p;
        }
    }
    long long query(int o,int l,int r,int a,int b){
        if(l>=a && r<=b)return sum[o]%p;
        else{
            int mid=(l+r)>>1;
            int lson=o<<1;
            int rson=lson|1;
            long long ans=0;
            if(mulv[o]!=1 || addv[o])push_down(o,l,r,mid,lson,rson);
            if(a<=mid)ans+=query(lson,l,mid,a,b);
            if(b>mid)ans+=query(rson,mid+1,r,a,b);
            return ans%p;
        }
    }
} tree;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>p;
    for(int i=1;i<=n;i++){
        cin>>c[i];
    }
    cin>>m;
    tree.build(1,1,n);
    for(int i=1;i<=m;i++){
        int f;
        long long x,y,k;
        cin>>f;
        if(f==1){
            cin>>x>>y>>k;
            tree.mulall(1,1,n,x,y,k);
        }
        else if(f==2){
            cin>>x>>y>>k;
            tree.addall(1,1,n,x,y,k);
        }
        else{
            cin>>x>>y;
            cout<<tree.query(1,1,n,x,y)<<endl;
        }
    }
    return 0;
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
#define int long long
using namespace std;

const int MOD = 1e9+7;

struct Matrix{
    int a[3][3];
    const int size = 2;
    Matrix(){
        memset(a,0,sizeof(a));
    }
    Matrix(int aba){
        a[aba][aba]=1;
        a[aba][aba+1]=0;
        a[aba+1][aba]=0;
        a[aba+1][aba+1]=1;
    }
    Matrix(int A,int b,int c,int d){
        a[1][1]=A;
        a[1][2]=b;
        a[2][1]=c;
        a[2][2]=d;
    }
    Matrix operator*(const Matrix &ano) const {
        Matrix ans;
        for(int i=1;i<=size;i++){
            for(int k=1;k<=size;k++){
                for(int j=1;j<=size;j++){
                    ans.a[i][k]=(ans.a[i][k]+a[i][j]*ano.a[j][k])%MOD;
                }
            }
        }
        return ans;
    }
    Matrix operator+(const Matrix aa){
        Matrix res;
        for(int i=1;i<=size;i++){
            for(int j=1;j<=size;j++){
                res.a[i][j]=a[i][j]+aa.a[i][j];
                res.a[i][j]%=MOD;
            }
        }
        return res;
    }
    void operator=(const Matrix A){
        for(int i=1;i<=size;i++){
            for(int j=1;j<=size;j++){
                a[i][j]=A.a[i][j];
            }
        }
    }
    bool empty(){
        return (a[1][1]==0)&&(a[1][2]==0)&&(a[2][1]==0)&&(a[2][2]==0);
    }
    Matrix operator^(int power){
        Matrix res(1);
        Matrix base = (*this);
        while(power){
            if(power&1){
                res=res*base;
            }
            base=base*base;
            power>>=1;
        }
        return res;
    }
};

const int SIZE = 1e5+5;
Matrix t[SIZE<<2],tag[SIZE<<2];
int v[SIZE];
const Matrix unit(1);
int n,m;

inline void pushup(int i){
    t[i]=t[ls]+t[rs];
}

void build(int i,int l,int r){
    tag[i]=unit;
    if(l==r){
        t[i]=Matrix(1,1,0,0)*(Matrix(1,1,1,0)^(v[l]-1));
        return;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(i);
}

void pushdown(int i){
    if(tag[i].empty()){
        return;
    }
    t[ls]=t[ls]*tag[i];
    tag[ls]=tag[ls]*tag[i];
    t[rs]=t[rs]*tag[i];
    tag[rs]=tag[rs]*tag[i];
    tag[i]=unit;
}

void update(int i,int ql,int qr,int l,int r,Matrix x){
    if(ql<=l && qr>=r){
        t[i]=t[i]*x;
        tag[i]=tag[i]*x;
        return;
    }
    pushdown(i);
    if(ql<=mid){
        update(ls,ql,qr,l,mid,x);
    }
    if(qr>mid){
        update(rs,ql,qr,mid+1,r,x);
    }
    pushup(i);
}

Matrix query(int i,int ql,int qr,int l,int r){
    if(ql<=l && qr>=r){
        return t[i];
    }
    pushdown(i);
    Matrix res;
    if(ql<=mid){
        res = res + query(ls,ql,qr,l,mid);
    }
    if(qr > mid){
        res = res+query(rs,ql,qr,mid+1,r);
    }
    return res;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>v[i];
    }
    build(1,1,n);
    while(m--){
        int op,l,r,x;
        cin>>op;
        if(op==1){
            cin>>l>>r>>x;
            update(1,l,r,1,n,Matrix(1,1,1,0)^x);
        }
        else{
            cin>>l>>r;
            cout<<(query(1,l,r,1,n).a[1][2]%MOD)<<'\n';
        }
    }
    return 0;
}

注：LibreOJ需要改一改输入。亲测可以AC

#include<bits/stdc++.h>
#define ls(i) (i<<1)
#define rs(i) (i<<1|1)
#define mid(l,r) ((l+r)>>1)
using namespace std;
const int SIZE=100010;
#define int long long
int n,m;

int a[SIZE*4],tag[SIZE*4];

inline void pushup(int t) {
    a[t]=a[ls(t)]+a[rs(t)];
    tag[t]=max(tag[ls(t)],tag[rs(t)]);
}
void build(int l=1,int r=n,int t=1) {
    if(l==r) {
        cin>>a[t];
        tag[t]=a[t];
        return;
    }
    build(l,mid(l,r),ls(t));
    build(mid(l,r)+1,r,rs(t));
    pushup(t);
}
void update(int L,int R,int l=1,int r=n,int t=1) {
    if(R<l||L>r) return;
    if(tag[t]==1) return;
    if(l==r) {
        tag[t]=a[t]=(int)sqrt(a[t]);
        return;
    }
    update(L,R,l,mid(l,r),ls(t));
    update(L,R,mid(l,r)+1,r,rs(t));
    pushup(t);
}
int ask(int L,int R,int l=1,int r=n,int t=1) {
    if(l>=L&&r<=R) {
        return a[t];
    }
    int ret=0;
    if(mid(l,r)>=L) ret+=ask(L,R,l,mid(l,r),ls(t));
    if(mid(l,r)<R) ret+=ask(L,R,mid(l,r)+1,r,rs(t));
    return ret;
}
signed main() {
    cin>>n;
    build();
    cin>>m;
    while(m--) {
        int k,l,r;
        cin>>k>>l>>r;
        if(l>r) swap(l,r);
        if(k==0) {
            update(l,r);
        } else {
            cout<<ask(l,r)<<'\n';
        }
    }
    return 0;
}


#include<bits/stdc++.h>
#define int long long
#define ls (now<<1)
#define rs (now<<1|1)
#define mid (l+r>>1)
#define MAX(a,b) (a>b?a:b)
using namespace std;
int n,m;
int a[100001];
int tree[100001<<2],maxn[100001<<2];

inline void pushup(int now) {
    tree[now]=tree[ls]+tree[rs];
    maxn[now]=MAX(maxn[ls],maxn[rs]);
}
void build(int now,int l,int r) {
    if(l==r) {
        tree[now]=maxn[now]=a[l];
        return ;
    }
    build(ls,l,mid);
    build(rs,mid+1,r);
    pushup(now);
}
void update_mod(int now,int l,int r,int x,int y,int mod) {
    if(maxn[now]<mod) return ;
    if(l==r) {
        tree[now]%=mod;
        maxn[now]%=mod;
        return ;
    }
    if(mid>=x) {
        update_mod(ls,l,mid,x,y,mod);
    }
    if(mid<y) {
        update_mod(rs,mid+1,r,x,y,mod);
    }
    pushup(now);
}
void update_assign(int now,int l,int r,int x,int k) {
    if(l==r) {
        tree[now]=maxn[now]=k;
        return ;
    }
    if(mid>=x) {
        update_assign(ls,l,mid,x,k);
    }
    else {
        update_assign(rs,mid+1,r,x,k);
    }
    pushup(now);
}
void update_sqrt(int now,int l,int r,int x,int y) {
    if(l==r) {
        maxn[now]=tree[now]=sqrt(tree[now]);
        return ;
    }
    if(mid>=x&&maxn[ls]>1) {
        update_sqrt(ls,l,mid,x,y);
    }
    if(mid<y&&maxn[rs]>1){
        update_sqrt(rs,mid+1,r,x,y);
    }
    pushup(now);
}
int query(int now,int l,int r,int x,int y) {
    if(l>=x&&r<=y) {
        return tree[now];
    }
    int ret=0;
    if(mid>=x) {
        ret+=query(ls,l,mid,x,y);
    }
    if(mid<y) {
        ret+=query(rs,mid+1,r,x,y);
    }
    return ret;
}
signed main() {
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    cin>>m;
    build(1,1,n);
    while(m--) {
        int op,l,r,k;
        cin>>op;
        if(op==1) {
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<endl;
        }
        if(op==2) {
            cin>>l>>r;
            update_sqrt(1,1,n,l,r);
        }
        if(op==3) {
            cin>>l>>r>>k;
            update_mod(1,1,n,l,r,k);
        }
        if(op==4) {
            cin>>l>>k;
            update_assign(1,1,n,l,k);
        }
    }
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
int c = 1;
const int SIZE = 2e6 + 5;
int t[SIZE << 2];
struct node {
    int v, id;
    bool operator<(const node ano) const {
        return v < ano.v;
    }
} a[SIZE];
int u[SIZE];
int mm[SIZE];
int m, n, cnt, I = 1;

void pushup(int i) {
    t[i] = t[ls] + t[rs];
}
void update(int p, int i, int l, int r) {
    if (l == r && l == p) {
        t[i]++;
        return;
    }
    t[i]++;
    if (p <= mid) {
        update(p, ls, l, mid);
    } else {
        update(p, rs, mid + 1, r);
    }
    pushup(i);
}

int query(int p, int i, int l, int r) {
    if (l == r) {
        return l;
    }
    if (t[ls] >= p) {
        return query(p, ls, l, mid);
    } else {
        return query(p - t[ls], rs, mid + 1, r);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> m >> n;
    for (int i = 1; i <= m; i++) {
        cin >> a[i].v;
        a[i].id = i;
        //cout<<a[i].id<<' '<<a[i].v<<endl;
    }
    sort(a + 1, a + m + 1);
    for (int i = 1; i <= m; i++) {
        mm[a[i].id] = i;
    }
    for (int i = 1; i <= n; i++)cin >> u[i];
    for (int i = 1; i <= m; i++) {
        //cout<<'\t'<<mm[i]<<endl;
        update(mm[i], 1, 1, m);
        while (u[c] == i) {
            cout << a[query(I, 1, 1, m)].v << '\n';
            I++;
            c++;
        }
    }
    return 0;
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;

const int SIZE = 1e6+5;
struct{
    int l,r,v; // 线段树节点，存了区间方便搞
}t[SIZE*25];
int top; // 历史版本数
int root[SIZE*25]; // 历史版本根节点位置
int a[SIZE]; // 原始数组
int n,m;

int newnode(int i){  // 新建节点
    t[++top]=t[i];
    return top;
}

int build(int i,int l,int r){ // 建树
    i=(++top); // 建立新版本
    if(l==r){
        // 叶子节点
        t[i].v=a[l];
        return i; // 返回当前版本
    }
    t[i].l=build(t[i].l,l,mid); // 向下递归
    t[i].r=build(t[i].r,mid+1,r); // 向下递归
    return i; // 返回当前版本
}

int update(int i,int l,int r,int p,int val){
    // 单点更新，即数组赋值。
    i=newnode(i);
    if(l==r){// 叶子节点
        t[i].v=val; // 直接更新
        return i;// 返回当前版本
    }
    if(p<=mid){// 向下递归
        t[i].l=update(t[i].l,l,mid,p,val);
    }
    else{// 向下递归
        t[i].r=update(t[i].r,mid+1,r,p,val);
    }
    return i;// 返回当前版本
}

int query(int i,int l,int r,int p){
    if(l==r){// 叶子节点
        return t[i].v; // 直接返回
    }
    if(p<=mid){// 向下递归
        return query(t[i].l,l,mid,p);
    }
    else{// 向下递归
        return query(t[i].r,mid+1,r,p);
    }
}

inline void Assign(int i,int version,int p,int val){
    // 封装：在某版本下赋值
    root[i]=update(root[version],1,n,p,val);
    // 记得新建版本
}

inline int Get(int i,int version,int p){
    // 封装：在某版本下取值
    root[i]=root[version]; //新建版本
    return query(root[version],1,n,p);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    root[0]=build(0,1,n);// 建立原树
    for(int i=1,vi,op,loci,valuei;i<=m;i++){
        cin>>vi>>op>>loci;
        if(op==1){
            cin>>valuei;
            Assign(i,vi,loci,valuei);
        }
        else{
            cout<<Get(i,vi,loci)<<'\n';
        }
    }
    return 0;
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;

const int SIZE = 2e5+5;
struct ArckaAKIOI{
    int l,r,v;
    ArckaAKIOI(){
        l=0,r=0,v=0;
    }
}t[SIZE*32];
int top;
int root[SIZE];
int a[SIZE],b[SIZE];
int n,m;

int newnode(int i){
    t[++top]=t[i];
    return top;
}

int build(int i,int l,int r){
    i=(++top);
    if(l==r){
        t[i].v=a[l];
        return i;
    }
    t[i].l=build(t[i].l,l,mid);
    t[i].r=build(t[i].r,mid+1,r);
    return i;
}

int update(int i,int l,int r,int p,int val){
    i=newnode(i);
    t[i].v++;
    if(l==r){
        return i;
    }
    if(p<=mid){
        t[i].l=update(t[i].l,l,mid,p,val);
    }
    else{
        t[i].r=update(t[i].r,mid+1,r,p,val);
    }
    return i;
}

int query(int i,int l,int r,int ql,int qr){
    if(l==r){
        return l;
    }
    int delta = t[t[qr].l].v-t[t[ql].l].v;
    if(delta>=i){
        return query(i,l,mid,t[ql].l,t[qr].l);
    }
    else{
        return query(i-delta,mid+1,r,t[ql].r,t[qr].r);
    }
}

int kkksc03;
void discretization(){
    for(int i=1;i<=n;i++){
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    kkksc03 = unique(b+1,b+n+1)-(b+1);
    root[0]=build(0,1,kkksc03);
    for(int i=1;i<=n;i++){
        root[i]=update(root[i-1],1,kkksc03,lower_bound(b+1,b+kkksc03+1,a[i])-b,114514);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    discretization();
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[query(k,1,kkksc03,root[l-1],root[r])]<<'\n';
    }
    return 0;
}


#include <bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;

const int SIZE = 100005;
struct ArckaAKIOI{
    int l,r,v;
    ArckaAKIOI(){
        l=0,r=0,v=0;
    }
}t[SIZE<<5];
int top;
int root[SIZE<<5];
int a[SIZE],b[SIZE];
int n,m;

int newnode(int i){
    t[++top]=t[i];
    return top;
}

int build(int i,int l,int r){
    i=(++top);
    if(l==r){
        t[i].v=a[l];
        return i;
    }
    t[i].l=build(t[i].l,l,mid);
    t[i].r=build(t[i].r,mid+1,r);
    return i;
}

int update(int i,int l,int r,int p,int val){
    i=newnode(i);
    t[i].v++;
    if(l==r){
        return i;
    }
    if(p<=mid){
        t[i].l=update(t[i].l,l,mid,p,val);
    }
    else{
        t[i].r=update(t[i].r,mid+1,r,p,val);
    }
    return i;
}

int query(int i,int l,int r,int ql,int qr){
    if(l==r){
        return l;
    }
    int delta = t[t[qr].l].v-t[t[ql].l].v;
    if(delta>=i){
        return query(i,l,mid,t[ql].l,t[qr].l);
    }
    else{
        return query(i-delta,mid+1,r,t[ql].r,t[qr].r);
    }
}

int kkksc03;
void discretization(){
    for(int i=1;i<=n;i++){
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    kkksc03 = unique(b+1,b+n+1)-(b+1);
    root[0]=build(0,1,kkksc03);
    for(int i=1;i<=n;i++){
        root[i]=update(root[i-1],1,kkksc03,lower_bound(b+1,b+kkksc03+1,a[i])-b,114514);
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    discretization();
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<b[query(k,1,kkksc03,root[l-1],root[r])]<<'\n';
    }
    return 0;
}


#include <bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;

int n, m, cnt, q;
const int SIZE = 1e6 + 5;
struct {
    int fa[SIZE];
    void init(int n) {
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
    }
    int find(int x) {
        if (fa[x] == x)return x;
        else return fa[x] = find(fa[x]);
    }
    void merge(int x, int y) {
        fa[x] = y;
    }
} uf;

struct node {
    int l, r, v;
} t[SIZE << 2];
int kkk[SIZE],a[SIZE],root[SIZE];

void newnode(int &i, int l, int r, int p) {
    if (!i) {
        i = (++cnt);
    }
    t[i].v++;
    if (l == r)return;
    if (p <= mid) {
        newnode(t[i].l, l, mid, p);
    } else {
        newnode(t[i].r, mid + 1, r, p);
    }
}

void merge(int &a, int &b) {
    if (!a) {
        a = b;
    } else if (!b) {}
    else {
        t[a].v += t[b].v;
        merge(t[a].l, t[b].l);
        merge(t[a].r, t[b].r);
    }
}

int query(int i,int l,int r,int p){
    if(l==r){
        return kkk[l];
    }
    int lsum = t[t[i].l].v;
    if(p<=lsum){
        return query(t[i].l,l,mid,p);
    }
    else{
        return query(t[i].r,mid+1,r,p-lsum);
    }
}

int main() {
    cin>>n>>m;
    uf.init(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        kkk[a[i]]=i;
        newnode(root[i],1,n,a[i]);
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        merge(root[uf.find(y)],root[uf.find(x)]);
        uf.merge(uf.find(x),uf.find(y));
    }
    cin>>q;
    for(int i=1,x,y;i<=q;i++){
        char op[1145];
        cin>>op;
        cin>>x>>y;
        if(op[0]=='B'){
            merge(root[uf.find(y)],root[uf.find(x)]);
            uf.merge(uf.find(x),uf.find(y));
        }
        else{
            if(t[root[uf.find(x)]].v<y){
                cout<<-1<<'\n';
            }
            else{
                cout<<query(root[uf.find(x)],1,n,y)<<'\n';
            }
        }
    }
    return 0;
}