Proficient.
Put your skills to the test.

Problem summary

Maintain positive integers without zero digits. Rotate every number in a requested interval by moving its last decimal digit to the front, or report an interval sum.

Constraints

N ≤ 1000000; Q ≤ 50000; 1 ≤ Ai < 1000000, with no zero digits.

Worked example

An independently prepared example for this explanation.

3 5
15 35 112
2 1 2
1 2 3
2 1 3
1 1 2
2 2 3

50
279
246

Solution analysis

1. Partition positions by their original number of digits d, for d=1,...,6. Rotation preserves this length because there are no zero digits. Each original interval maps to a contiguous interval in each position list, found with binary searches.
2. For each list build a lazy segment tree. A node stores d sums: entry k is the sum if every current number in the node is rotated another k times. Applying one rotation cyclically shifts these d sums and increments a lazy shift modulo d. Merge children by componentwise addition.
3. The first example update changes 35 into 53 and 112 into 211. The full sum is then 15+53+211=279. Rotating the first two numbers yields 51 and 35, so the final query gives 35+211=246. Compact preorder node indexing keeps all six trees within linear memory.

Why it works

A leaf stores exactly all d cyclic rotations of its number. Componentwise addition preserves this meaning for an internal node. Rotating all numbers shifts entry k to old entry k+1, so the lazy action and its composition are exact. Binary searches select exactly the positions in the original interval. Summing the zero-rotation entries of all six disjoint lists therefore gives the requested sum.

Watch out. Use 64-bit sums. Rotation periods depend on digit length, so a single period of six is invalid for five-digit numbers. Empty digit classes must be skipped.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<array>
#include<algorithm>
// Algorithm: Partition positions by their original number of digits d, for d=1,...,6.
using namespace std;
struct RotationTree{
    int digits,n;
    vector<int>positions,lazy;
    vector<array<long long,6>>sum;
    RotationTree(int length):digits(length),n(0){
    }
    void build(int node,int l,int r,const vector<int>&a){
        if(l==r){
            int value=a[positions[l]-1],power=1;
            for(int i=1;i<digits;++i){
                power*=10;
            }
            for(int k=0;k<digits;++k){
                sum[node][k]=value;
                value=value/10+value%10*power;
            }
            return;
        }
        int mid=(l+r)/2;
        int other=node+2*(mid-l+1);
        build(node+1,l,mid,a);
        build(other,mid+1,r,a);
        pull(node,other);
    }
    void pull(int node,int other){
        for(int i=0;i<digits;++i){
            sum[node][i]=sum[node+1][i]+sum[other][i];
        }
    }
    void apply(int node,int shift){
        auto old=sum[node];
        for(int i=0;i<digits;++i){
            sum[node][i]=old[(i+shift)%digits];
        }
        lazy[node]=(lazy[node]+shift)%digits;
    }
    long long visit(int node,int l,int r,int first,int last,bool update){
        if(last<l||r<first){
            return 0;
        }
        if(first<=l&&r<=last){
            if(update){
                apply(node,1);
            }
            return sum[node][0];
        }
        int mid=(l+r)/2;
        int other=node+2*(mid-l+1);
        apply(node+1,lazy[node]);
        apply(other,lazy[node]);
        lazy[node]=0;
        long long result=visit(node+1,l,mid,first,last,update);
        result+=visit(other,mid+1,r,first,last,update);
        pull(node,other);
        return result;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>a(n);
    vector<RotationTree>trees;
    for(int d=1;d<=6;++d){
        trees.emplace_back(d);
    }
    for(int i=0;i<n;++i){
        cin>>a[i];
        int d=0;
        for(int v=a[i];v;v/=10){
            ++d;
        }
        trees[d-1].positions.push_back(i+1);
    }
    for(auto&tree:trees){
        tree.n=static_cast<int>(tree.positions.size());
        if(tree.n){
            tree.sum.resize(2*tree.n);
            tree.lazy.resize(2*tree.n);
            tree.build(0,0,tree.n-1,a);
        }
    }
    while(q--){
        int type,l,r;
        cin>>type>>l>>r;
        long long answer=0;
        for(auto&tree:trees){
            int first=lower_bound(tree.positions.begin(),tree.positions.end(),l)-tree.positions.begin();
            int last=
                upper_bound(tree.positions.begin(),tree.positions.end(),r)-tree.positions.begin()-1;
            if(first<=last){
                answer+=tree.visit(0,0,tree.n-1,first,last,type==1);
            }
        }
        if(type==2){
            cout<<answer<<'\n';
        }
    }
}