SQRT - Sample

#include <bits/stdc++.h>
#define speed() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;

struct block{
    vector<ll> srt;
    ll sum = 0;
};
vector<block> sq;
ll len = sqrt(3 * 1e5);
ll last_ans = 0;
ll mod = 1e9;

pii find_x( ll x ){
    int i = 0, j;
    while( i < sq.size() - 1 && sq[i].srt.back() < x ) i++;
    j = (int)(lower_bound(sq[i].srt.begin(), sq[i].srt.end(), x) - sq[i].srt.begin());
    return {i, j};
}

void split( ll i ){
    sq.insert( sq.begin() + i + 1, block() );
    for( int j = 0; j < len; ++j ){
        sq[i+1].srt.pb(sq[i].srt.back());
        sq[i+1].sum += sq[i].srt.back();
        sq[i].sum -= sq[i].srt.back();
        sq[i].srt.pop_back();
    }
    reverse( sq[i+1].srt.begin(), sq[i+1].srt.end() );
}

void add( ll x ){
    int i, j;
    tie( i, j ) = find_x(x);
    if( j != sq[i].srt.size() && sq[i].srt[j] == x ) return;

    sq[i].srt.insert( sq[i].srt.begin() + j, x );
    sq[i].sum += x;
    if( len*2 == sq[i].srt.size() ) split(i);
}

ll get_sum( ll L, ll R ){
    int l, i, r, j;
    tie(l, i) = find_x(L);
    tie(r, j) = find_x(R);
    if( j == sq[r].srt.size() || sq[r].srt[j] > R ) j--;

    ll ans = 0;

    if( i || (l == r) ){
        int end = ( l == r ? j+1 : (int)sq[l].srt.size() );
        for( ; i < end; ++i ) ans += sq[l].srt[i];
        if( l == r ) return ans;
        l++;
    }

    while( l < r ){
        ans += sq[l].sum;
        l++;
    }

    i = 0;
    for( ; i <= j; ++i ) ans += sq[l].srt[i];

    return ans;
}

int main(){
    speed();

    int n;
    cin >> n;
    len = sqrt(n);
    sq.pb(block());
    while( n-- ){
        char c;
        cin >> c;
        if( c == '+' ){
            ll x;
            cin >> x;
            add( (x + last_ans) % mod );
            last_ans = 0;
        } else{
            ll l, r;
            cin >> l >> r;
            last_ans = get_sum( l, r );
            cout << last_ans << '\n';
        }
    }

    return 0;
}