数列分块七0分求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
const int N=4e5+20;
int tot=1,len;
int a[N];
int l[N],r[N],from[N],lazy[N],lazy2[N],Lazy[N];
int opt;
int L,R,k;
bool vis[N];
const int mod=10007;
const int kk=3e10;
void change(int o,int ll,int rr,int k){
    if(o==1){
        if(from[ll]==from[rr]){
            for(int i=ll;i<=rr;i++) a[i]+=k;
            return ;
        }
        for(int i=ll;i<=r[from[ll]];i++) a[i]+=k;
        for(int i=from[ll]+1;i<from[rr];i++) lazy[i]+=k;
        for(int i=l[from[rr]];i<=rr;i++) a[i]+=k;
    }
    else{
        if(from[ll]==from[rr]){
            for(int i=l[from[ll]];i<=r[from[ll]];i++){
                a[i]=((a[i]*lazy2[from[i]]+kk*mod)%mod+lazy[from[i]]+kk*mod)%mod;
            }
            lazy2[from[ll]]=1,lazy[from[ll]]=0;
            for(int i=ll;i<=rr;i++){
                a[i]=(a[i]*k+kk*mod)%mod;
            }
            return ;
        }
        for(int i=l[from[ll]];i<=r[from[ll]];i++){
           a[i]=((a[i]*lazy2[from[i]]+kk*mod)%mod+lazy[from[i]]+kk*mod)%mod;
        }
        lazy2[from[ll]]=1,lazy[from[ll]]=0;
        for(int i=ll;i<=r[from[ll]];i++){
             a[i]=(a[i]*k+kk*mod)%mod;
        }
        for(int i=from[ll]+1;i<from[rr];i++) lazy2[i]=lazy2[i]*k%mod,lazy[i]=lazy[i]*k%mod;
        for(int i=l[from[rr]];i<=r[from[rr]];i++){
           a[i]=((a[i]*lazy2[from[i]]+kk*mod)%mod+lazy[from[i]]+kk*mod)%mod; 
        }
        lazy2[from[rr]]=1,lazy[from[rr]]=0;
        for(int i=l[from[rr]];i<=rr;i++){
             a[i]=(a[i]*k+kk*mod)%mod;
        }
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    len=sqrt(n);
    l[tot]=1;
    lazy2[tot]=1;
    for(int i=1;i<=n;i++){
        from[i]=tot;
        if(i%len==0){
            r[tot]=i;
            if(i!=n){
                tot++;
                lazy2[tot]=1;
                l[tot]=i+1;
            }
        }
    }   
    if(!r[tot]) r[tot]=n;
    for(int i=1;i<=n;i++){
        cin>>opt;
        if(opt==0){
            cin>>L>>R>>k;
            change(1,L,R,k);
        }
        if(opt==1){
            cin>>L>>R>>k;
            change(2,L,R,k);
        }
        if(opt==2){
            cin>>L>>R>>k;
cout<<(((a[R]*lazy2[from[R]]+kk*mod)%mod+lazy[from[R]]+kk*mod))%mod<<"\n";
        }
    }
}