Persistent Segment Tree with minPrefix

#include <cassert>
#include <iostream>
#include <vector>
#include <algorithm>
namespace Mlxa {
    using namespace std;
    typedef long long               ll;
    typedef   signed long long      ull;

    #define all(x)              begin(x), end(x)
    #define eol                 '\n'
    #define read                cin

    template <ostream &out, class A> inline void
    write (A a)         { out << a; }
    template <ostream &out, class A, class... B> inline void
    write (A a, B... b) { out << a << ' '; write<out>(b...); }
    template <ostream &out, class I> void
    writeseq (I b, I e) { for(I i=b;i!=e;++i) out<<*i<<' '; }

    #define print(...)          write<cout>(__VA_ARGS__)
    #define println(...)        print(__VA_ARGS__, eol);
    #define printseq(...)       writeseq<cout>(__VA_ARGS__), print(eol);
    #ifdef AC
        #define addlog(...)     write<cerr>("[D]\t\t\t\t", __VA_ARGS__, eol);
    #else
        #define addlog(...)     (void(0))
    #endif
}   using namespace Mlxa;

inline ull mod (ll a, ull m)
{
    ull res = (a % m + m) % m;
    return res;
}

struct Node
{
    ll sum;
    Node *l, *r;
    Node (Node *p)
    {
        if (!p) return;
        sum = p->sum;
        l = p->l;
        r = p->r;
    }
    Node (ll s, Node *l, Node *r) : sum(s), l(l), r(r) {}
    Node (Node *l, Node *r) : Node(0, l, r){}
    Node () : Node(nullptr, nullptr) {}

}; typedef Node *Ptr;

struct Persistent
{
    const static ull MAX_V = 2000000;
    Ptr rt[MAX_V];
    ll curvs;
    #define root rt[0]
    vector<ll> arr;

    void build (vector<ll> v)
    {
        ///addlog("void build (vector<ll> v)");
        curvs = 0;
        arr = v;
        root = new Node;
        build(root, 0, arr.size() - 1);
    }
    #undef root

    void assign (ull vs, ull x, ull v)
    {
        rt[++ curvs] = assign(rt[vs], 0, arr.size() - 1, x, v);
    }

    ull query (ull vs, ull L, ull R)
    {
        return query(rt[vs], 0, arr.size() - 1, L, R);
    }

    ull minPrefix (ull vs, ull s)
    {
        return minPrefix(rt[vs], 0, arr.size() - 1, s);
    }

    ull minPrefix (Ptr v, ull l, ull r, ll s)
    {
        ull m = (l + r) / 2;
        ///addlog("minPrefix", l, m, r, " ", s, v->sum);
        if (l == r) {
            if (s <= v->sum)
                return l;
            else
                return -1;
        }
        if (v->l && v->l->sum >= s)
            return minPrefix(v->l, l, m, s);
        else if (v->r)
            return minPrefix(v->r, m+1, r, s - v->l->sum);
        return -1;
    }

    void build (Ptr v, ull l, ull r)
    {
        ///addlog("void build (Ptr v, ull l, ull r)");
        ///addlog("                       ", l, r);
        assert(v);
        assert(l <= r);
        if (l == r) {
            v->sum = arr[l];
            return;
        }
        ull m = (l + r) / 2;
        v->l = new Node;
        v->r = new Node;
        build(v->l, l, m);
        build(v->r, m + 1, r);
        v->sum = v->l->sum + v->r->sum;
    }

    Ptr assign (Ptr v, ull l, ull r, ull x, ull val)
    {
        ///addlog("Ptr assign (Ptr v, ull l, ull r, ull x, ull val)");
        ///addlog("                      ", l, r, x, val);
        assert(v);
        assert(l <= x && x <= r);
        Ptr nv = new Node(v);
        if (l < r) {
            ull m = (l + r) / 2;
            if (x <= m)
                nv->l = assign(nv->l, l, m, x, val);
            else
                nv->r = assign(nv->r, m + 1, r, x, val);
            nv->sum = nv->l->sum + nv->r->sum;
        }
        else nv->sum = val;
        return nv;
    }

    ull query (Ptr v, ull l, ull r, ull L, ull R)
    {
        assert(v);
        assert(l <= L && L <= R && R <= r);
        ull m = (l + r) / 2;
        /// Если запрос полностью покрывает
        if (l == L && r == R) return v->sum;
        ull res = 0;
        /// Если затрагивает левого сына
        if (L <= m) res += query(v->l, l, m, L, min(m, R));
        /// Если затрагивает правого сына
        if (R > m)  res += query(v->r, m+1, r, max(m+1, L), R);
        return res;
    }
};


ull N, M, Q, p = 0;
vector<ll> a, x, y;
vector<ull> last;
Persistent first;

void start ()
{
    read >> N >> M;
    a.resize(N);
    for (ull i = 0; i < N; ++ i)
        read >> a[i];
    read >> Q;

    last.assign(M + 10, 0);
    first.build(vector<ull>(N, 0));
}

// Версии идут наоборот
void prepare ()
{
    for (ull i = N - 1; i != (ull)-1; -- i) {
        first.assign(first.curvs, last[a[i]], 0);
        last[a[i]] = i;
        first.assign(first.curvs, i, 1);
    }
}

ull solve (ull l, ull k)
{
    ///l -> N-1-l
    ull vers = N-1-l;
    ///addlog("solve", l, k);
    /**vector<ull> rem(N, 5);
    for (ull i = 0; i < N; ++ i)
        rem[i] = first.query(2+2*vers, i, i);
    printseq(all(rem));**/

    ull res = first.minPrefix(2+2*vers, k);
    ///println("result: r ==", res + 1);
    if (res >= 0) return res + 1;
    return 0;
}



int main ()
{
    start();

    prepare();

    /*println("\nDEBUG!");
    vector<ull> rem(N, 5);
    for (ull vers = 0; vers < N; ++ vers) {
    for (ull i = 0; i < N; ++ i)
        rem[i] = first.query(2+2*vers, i, i);
    printseq(all(rem)); }*/

    for (ull i = 0; i < Q; ++ i) {
        ull x, y, l, k;
        read >> x >> y;
        l = mod(x + p, N);
        k = mod(y + p, M) + 1;
        ull r = solve (l, k);
        println(r);
        p = r;
    }

    return 0;
}