线段树求条(只过Sub 1#1)

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,q;
int a[100005];
int seg1[400005];
int seg2[400005];
void crseg(int l,int r,int x){
    if(l==r){
        seg1[x]=a[l];
        seg2[x]=(a[l]==1? 0x3f3f3f3f:l);
    }
    else{
        int mid=(l+r)/2;
        crseg(l,mid,2*x);
        crseg(mid+1,r,2*x+1);
        seg1[x]=seg1[2*x]+seg1[2*x+1];
        seg2[x]=min(seg2[2*x],seg2[2*x+1]);
    }
}
void chseg(int l,int r,int x,int i,int a){
    seg1[x]+=a;
    if(l==r) return;
    int mid=(l+r)/2;
    if(i<=mid) chseg(l,mid,2*x,i,a);
    else chseg(mid+1,r,2*x+1,i,a);
}
void upseg(int l,int r,int x){
    if(l==r) seg2[x]=(a[l]==1? 0x3f3f3f3f:l);
    else{
        int mid=(l+r)/2;
        upseg(l,mid,2*x);
        upseg(mid+1,r,2*x+1);
        seg2[x]=min(seg2[2*x],seg2[2*x+1]);
    }
}
int qrmin(int l,int r,int x,int i,int j){
    if(l==i&&r==j) return seg2[x];
    int mid=(l+r)/2;
    if(j<=mid) return qrmin(l,mid,2*x,i,j);
    else if(i>mid) return qrmin(mid+1,r,2*x+1,i,j);
//    else return min(qrmin(l,mid,2*x,i,mid),qrmin(mid+1,r,2*x+1,mid+1,j));
}
int qrseg(int l,int r,int x,int i,int j){
    if(l==i&&r==j) return seg1[x];
    int mid=(l+r)/2;
    if(j<=mid) return qrseg(l,mid,2*x,i,j);
    else if(i>mid) return qrseg(mid+1,r,2*x+1,i,j);
    else return qrseg(l,mid,2*x,i,mid)+qrseg(mid+1,r,2*x+1,mid+1,j);
}
void change(int l,int r){
    while(1){
        int pos=qrmin(1,n,1,l,r);
        if(pos==0x3f3f3f3f) return;
        chseg(1,n,1,pos,floor(sqrt(a[pos]))-a[pos]);
        a[pos]=floor(sqrt(a[pos]));
        l=pos+1;
    }
    upseg(1,n,1);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    crseg(1,n,1);
    cin>>q;
    while(q--){
        int op,l,r;
        cin>>op>>l>>r;
        l=min(l,r);
        r=max(l,r);
        if(op==0) change(l,r);
        if(op==1) cout<<qrseg(1,n,1,l,r)<<"\n";
    }
}