题解 | 小红的区间修改（一）

直接线段树维护[L,R]中是否存在1即可
// @xiaowang5242
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lll = __int128_t;
using db = long double;
using pll = pair<ll,ll>;

#define fastio    (cin.tie(0)->sync_with_stdio(0))
#define rep(i,a,b) for (ll i = (a); i <= (b); ++i)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define all1(x) (x).begin()+1, (x).end()
#define rd read
#define pt print
#define YESNO(n) println(n?"YES":"NO")

const ll MOD_DEFAULT = 998244353;
const ll INF = (ll)2e18 + 10;

struct Bint {
    static const uint32_t BASE = 1000000000u;
    static const int BASE_DIGS = 9;

    int sign;              
    std::vector<uint32_t> a;  
    Bint(): sign(0) {}
    Bint(long long v) { *this = v; }
    Bint(const string &s) { read_from_string(s); }

    Bint& operator=(long long v) {
        a.clear();
        if (v == 0) { sign = 0; return *this; }
        if (v < 0) { sign = -1; v = -v; }
        else sign = 1;
        while (v) {
            a.push_back((uint32_t)(v % BASE));
            v /= BASE;
        }
        return *this;
    }

    void normalize() {
        while (!a.empty() && a.back() == 0) a.pop_back();
        if (a.empty()) sign = 0;
    }

    static int cmp_abs(const Bint &x, const Bint &y) {
        if (x.a.size() != y.a.size()) return x.a.size() < y.a.size() ? -1 : 1;
        for (int i = (int)x.a.size() - 1; i >= 0; --i)
            if (x.a[i] != y.a[i]) return x.a[i] < y.a[i] ? -1 : 1;
        return 0;
    }

    friend bool operator<(const Bint &x, const Bint &y) {
        if (x.sign != y.sign) return x.sign < y.sign;
        if (x.sign == 0) return false;
        int c = cmp_abs(x, y);
        return x.sign > 0 ? (c < 0) : (c > 0);
    }
    friend bool operator==(const Bint &x, const Bint &y) {
        return x.sign == y.sign && x.a == y.a;
    }
    friend bool operator!=(const Bint &x, const Bint &y) { return !(x==y); }
    friend bool operator>(const Bint &x, const Bint &y) { return y < x; }
    friend bool operator<=(const Bint &x, const Bint &y) { return !(y < x); }
    friend bool operator>=(const Bint &x, const Bint &y) { return !(x < y); }

    static Bint add_abs(const Bint &x, const Bint &y) {
        Bint res; res.sign = 1;
        const size_t n = max(x.a.size(), y.a.size());
        res.a.resize(n);
        unsigned long long carry = 0;
        for (size_t i = 0; i < n; ++i) {
            unsigned long long s = carry;
            if (i < x.a.size()) s += x.a[i];
            if (i < y.a.size()) s += y.a[i];
            res.a[i] = (uint32_t)(s % BASE);
            carry = s / BASE;
        }
        if (carry) res.a.push_back((uint32_t)carry);
        res.normalize();
        return res;
    }
    static Bint sub_abs(const Bint &x, const Bint &y) {
        Bint res; res.sign = 1;
        res.a.resize(x.a.size());
        long long carry = 0;
        for (size_t i = 0; i < x.a.size(); ++i) {
            long long s = (long long)x.a[i] - carry - (i < y.a.size() ? y.a[i] : 0);
            if (s < 0) { s += BASE; carry = 1; }
            else carry = 0;
            res.a[i] = (uint32_t)s;
        }
        res.normalize();
        return res;
    }

    Bint operator-() const {
        Bint r = *this;
        if (r.sign != 0) r.sign = -r.sign;
        return r;
    }
    friend Bint operator+(const Bint &x, const Bint &y) {
        if (x.sign == 0) return y;
        if (y.sign == 0) return x;
        if (x.sign == y.sign) {
            Bint r = add_abs(x, y);
            r.sign = x.sign;
            return r;
        } else {
            int c = cmp_abs(x, y);
            if (c == 0) return Bint();
            if (c > 0) {
                Bint r = sub_abs(x, y);
                r.sign = x.sign;
                return r;
            } else {
                Bint r = sub_abs(y, x);
                r.sign = y.sign;
                return r;
            }
        }
    }
    friend Bint operator-(const Bint &x, const Bint &y) { return x + (-y); }

    friend Bint operator*(const Bint &x, const Bint &y) {
        if (x.sign == 0 || y.sign == 0) return Bint();
        Bint res; res.sign = x.sign * y.sign;
        res.a.assign(x.a.size() + y.a.size(), 0);
        for (size_t i = 0; i < x.a.size(); ++i) {
            unsigned long long carry = 0;
            unsigned long long xi = x.a[i];
            for (size_t j = 0; j < y.a.size() || carry; ++j) {
                unsigned long long cur = res.a[i+j] + carry + xi * (j < y.a.size() ? (unsigned long long)y.a[j] : 0ULL);
                res.a[i+j] = (uint32_t)(cur % BASE);
                carry = cur / BASE;
            }
        }
        res.normalize();
        return res;
    }
    static Bint mul_by_uint(const Bint &x, uint32_t m) {
        if (x.sign == 0 || m == 0) return Bint();
        Bint res; res.sign = x.sign;
        res.a.assign(x.a.size() + 1, 0);
        unsigned long long carry = 0;
        for (size_t i = 0; i < x.a.size(); ++i) {
            unsigned long long cur = carry + (unsigned long long)x.a[i] * m;
            res.a[i] = (uint32_t)(cur % BASE);
            carry = cur / BASE;
        }
        if (carry) res.a[x.a.size()] = (uint32_t)carry;
        res.normalize();
        return res;
    }
    static pair<Bint, uint32_t> divmod_by_uint(const Bint &x, uint32_t m) {
        if (m == 0) { cerr << "div by zero\n"; std::abort(); }
        if (x.sign == 0) return {Bint(), 0};
        Bint res; res.sign = x.sign;
        res.a.assign(x.a.size(), 0);
        unsigned long long rem = 0;
        for (int i = (int)x.a.size() - 1; i >= 0; --i) {
            unsigned long long cur = x.a[i] + rem * BASE;
            res.a[i] = (uint32_t)(cur / m);
            rem = cur % m;
        }
        res.normalize();
        return {res, (uint32_t)rem};
    }

    static pair<Bint, long long> divmod_by_ll(const Bint &x, long long m) {
        if (m == 0) { cerr << "div by zero\n"; std::abort(); }
        if (x.sign == 0) return {Bint(), 0};
        long long abs_m = m < 0 ? -m : m;
        Bint res; res.sign = x.sign;
        res.a.assign(x.a.size(), 0);
        __int128 rem = 0;
        for (int i = (int)x.a.size() - 1; i >= 0; --i) {
            rem = rem * (__int128)BASE + (__int128)x.a[i];
            long long qi = (long long)(rem / abs_m); // qi < BASE
            rem = rem % abs_m;
            res.a[i] = (uint32_t)qi;
        }
        res.normalize();
        long long r = (long long)rem;
        if (x.sign < 0) r = -r;
        if (m < 0) res.sign = -res.sign;
        return {res, r};
    }

    static long long mod_ll(const Bint &x, long long m) {
        return divmod_by_ll(x, m).second;
    }
    string toString() const {
        if (sign == 0) return "0";
        stringstream ss;
        if (sign < 0) ss << '-';
        int n = (int)a.size();
        ss << (uint64_t)a.back();
        for (int i = n-2; i >= 0; --i) ss << setw(BASE_DIGS) << setfill('0') << (uint64_t)a[i];
        return ss.str();
    }

    void read_from_string(const string &s) {
        a.clear();
        sign = 0;
        size_t i = 0;
        while (i < s.size() && isspace((unsigned char)s[i])) ++i;
        bool neg = false;
        if (i < s.size() && (s[i] == '+' || s[i] == '-')) { neg = (s[i] == '-'); ++i; }
        while (i < s.size() && s[i] == '0') ++i;
        if (i == s.size()) { sign = 0; return; }
        int j = (int)s.size();
        while (j > (int)i) {
            int start = max((int)i, j - BASE_DIGS);
            uint32_t block = 0;
            for (int k = start; k < j; ++k) block = block * 10 + (s[k] - '0');
            a.push_back(block);
            j = start;
        }
        sign = neg ? -1 : 1;
        normalize();
    }

    template<typename T>
    T convert_to() const {
        string s = toString();
        if constexpr (is_same<T, string>::value) return s;
        else if constexpr (is_integral<T>::value) {
            bool neg = false; size_t pos = 0;
            if (!s.empty() && s[0] == '-') { neg = true; pos = 1; }
            unsigned long long val = 0;
            for (; pos < s.size(); ++pos) {
                char c = s[pos];
                if (c < '0' || c > '9') break;
                val = val * 10 + (unsigned long long)(c - '0');
            }
            if constexpr (is_signed<T>::value) {
                long long rv = (long long)val;
                if (neg) rv = -rv;
                return (T)rv;
            } else return (T)val;
        } else {
            static_assert(sizeof(T) == 0, "Bint::convert_to unsupported type");
        }
    }

    // Implicit conversions (convenience; may truncate)
    operator long long() const noexcept { return convert_to<long long>(); }
    operator std::string() const noexcept { return toString(); }

    // with Bint
    Bint& operator+=(const Bint &rhs) { *this = *this + rhs; return *this; }
    Bint& operator-=(const Bint &rhs) { *this = *this - rhs; return *this; }
    Bint& operator*=(const Bint &rhs) { *this = *this * rhs; return *this; }
    Bint& operator/=(const Bint &rhs) { *this = *this / rhs; return *this; }
    Bint& operator%=(const Bint &rhs) { *this = *this % rhs; return *this; }
    template<typename T, typename = typename enable_if<is_integral<T>::value>::type>
    Bint& operator%=(T m) {
        long long mm = (long long)m;
        long long r = divmod_by_ll(*this, mm).second;
        *this = Bint((long long)0);
        *this = Bint(r);
        return *this;
    }
    template<typename T, typename = typename enable_if<is_integral<T>::value>::type>
    Bint& operator/=(T m) {
        long long mm = (long long)m;
        *this = divmod_by_ll(*this, mm).first;
        return *this;
    }
    template<typename T, typename = typename enable_if<is_integral<T>::value>::type>
    Bint& operator+=(T v) { *this = *this + Bint((long long)v); return *this; }
    template<typename T, typename = typename enable_if<is_integral<T>::value>::type>
    Bint& operator-=(T v) { *this = *this - Bint((long long)v); return *this; }
    template<typename T, typename = typename enable_if<is_integral<T>::value>::type>
    Bint& operator*=(T v) { *this = *this * Bint((long long)v); return *this; }

    // ---------- friend operators with integral on rhs ----------
    template<typename T> friend typename enable_if<is_integral<T>::value, Bint>::type operator%(const Bint &x, T m) {
        long long mm = (long long)m;
        long long r = divmod_by_ll(x, mm).second;
        return Bint((long long)r);
    }
    template<typename T> friend typename enable_if<is_integral<T>::value, Bint>::type operator/(const Bint &x, T m) {
        long long mm = (long long)m;
        return divmod_by_ll(x, mm).first;
    }

    // ---------- Bint / Bint division (simple safe method) ----------
    friend pair<Bint,Bint> divmod(const Bint &aa, const Bint &bb) {
        if (bb.sign == 0) { cerr << "div by zero\n"; std::abort(); }
        if (aa.sign == 0) return {Bint(), Bint()};
        // both positive logic on absolute values
        Bint a = aa; Bint b = bb;
        int qsign = aa.sign * bb.sign;
        a.sign = b.sign = 1;

        if (cmp_abs(a, b) < 0) {
            Bint zero = Bint(0);
            Bint r = aa; // remainder keeps numerator sign for compatibility
            return {zero, r};
        }

        size_t n = a.a.size();
        vector<uint32_t> q(n, 0);
        Bint R = Bint(0);

        // iterate from most significant block to least
        for (int idx = (int)n - 1; idx >= 0; --idx) {
            // R = R * BASE + a.a[idx]
            if (R.sign == 0) R = Bint((long long)a.a[idx]);
            else {
                R = mul_by_uint(R, (uint32_t)BASE);
                // add a.a[idx]
                unsigned long long carry = a.a[idx];
                size_t j = 0;
                while (carry) {
                    if (j >= R.a.size()) R.a.push_back(0);
                    unsigned long long cur = (unsigned long long)R.a[j] + carry;
                    R.a[j] = (uint32_t)(cur % BASE);
                    carry = cur / BASE;
                    ++j;
                }
                R.normalize();
            }
            // find qdigit by binary search in [0, BASE-1]
            uint32_t lo = 0, hi = (uint32_t)BASE - 1, ans = 0;
            while (lo <= hi) {
                uint32_t mid = lo + (uint32_t)((hi - lo) >> 1);
                Bint t = mul_by_uint(b, mid);
                int cmp = cmp_abs(t, R);
                if (cmp <= 0) { ans = mid; lo = mid + 1; }
                else { if (mid==0) break; hi = mid - 1; }
            }
            q[idx] = ans;
            if (ans != 0) {
                Bint t = mul_by_uint(b, ans);
                R = R - t;
            }
        }

        Bint Q;
        Q.sign = qsign;
        Q.a = q;
        Q.normalize();
        R.sign = aa.sign; // remainder sign follows numerator (C-like)
        R.normalize();
        return {Q, R};
    }

    friend Bint operator/(const Bint &x, const Bint &y) {
        return divmod(x,y).first;
    }
    friend Bint operator%(const Bint &x, const Bint &y) {
        return divmod(x,y).second;
    }

}; 

#ifndef USE_CIN
struct FastIO {
    static const int BUFSIZE = 1 << 15;
    static char ibuf[BUFSIZE];
    static int ipos;
    static int ilen;

    static inline int readChar() {
        if (ipos >= ilen) {
            ilen = (int)fread(ibuf, 1, BUFSIZE, stdin);
            ipos = 0;
            if (ilen == 0) return EOF;
        }
        return (unsigned char)ibuf[ipos++];
    }
    static inline void writeChar(int c) { putchar(c); }

    template<typename T>
    static bool readInt(T &out) {
        int c = readChar();
        if (c == EOF) return false;
        while (c != '-' && (c < '0' || c > '9')) {
            c = readChar();
            if (c == EOF) return false;
        }
        bool neg = false;
        if (c == '-') { neg = true; c = readChar(); }
        T val = 0;
        while (c >= '0' && c <= '9') {
            val = val * 10 + (c - '0');
            c = readChar();
        }
        out = neg ? T(0) - val : val;
        return true;
    }

    static bool readToken(string &s) {
        int c = readChar();
        if (c == EOF) return false;
        while (isspace(c)) {
            c = readChar();
            if (c == EOF) return false;
        }
        s.clear();
        while (c != EOF && !isspace(c)) {
            s.push_back((char)c);
            c = readChar();
        }
        return true;
    }

    template<typename T>
    static void writeInt(T x) {
        if (x == 0) { writeChar('0'); return; }
        if (x < 0) { writeChar('-'); x = -x; }
        char buf[48]; int i = 0;
        unsigned long long ux = (unsigned long long)x;
        while (ux) {
            buf[i++] = char('0' + (ux % 10));
            ux /= 10;
        }
        while (i--) writeChar(buf[i]);
    }

    static void writeString(const string &s) { for (char c : s) writeChar(c); }
};

char FastIO::ibuf[FastIO::BUFSIZE];
int FastIO::ipos = 0;
int FastIO::ilen = 0;
#endif

struct Z {
    using i128 = __int128_t;
    static inline long long MOD = MOD_DEFAULT;
    long long v;
    Z(long long _v = 0) noexcept {
        if (_v < 0) {
            _v %= MOD;
            if (_v < 0) _v += MOD;
        }
        v = (_v >= MOD ? _v % MOD : _v);
    }
    Z(const Bint &b) {
        long long r = Bint::mod_ll(b, MOD);
        r %= MOD;
        if (r < 0) r += MOD;
        v = r;
    }
    static void set_mod(long long m) { MOD = m; }
    static long long get_mod() { return MOD; }

    Z operator+ (const Z &o) const noexcept { long long x = v + o.v; if (x >= MOD) x -= MOD; return Z(x); }
    Z operator- (const Z &o) const noexcept { long long x = v - o.v; if (x < 0) x += MOD; return Z(x); }
    Z operator* (const Z &o) const noexcept { return Z((long long)((i128)v * o.v % MOD)); }
    Z operator-() const noexcept { return Z(v ? MOD - v : 0); }

    Z& operator+=(const Z &o) noexcept { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    Z& operator-=(const Z &o) noexcept { v -= o.v; if (v < 0) v += MOD; return *this; }
    Z& operator*=(const Z &o) noexcept { v = (long long)((i128)v * o.v % MOD); return *this; }

    Z pow(long long e) const {
        Z base = *this, res = 1;
        if (e < 0) { res = base.inv(); e = -e; }
        while (e) {
            if (e & 1) res *= base;
            base *= base;
            e >>= 1;
        }
        return res;
    }

    static long long egcd(long long a, long long b, long long &x, long long &y) {
        if (b == 0) { x = (a>=0?1:-1); y = 0; return llabs(a); }
        long long x1, y1;
        long long g = egcd(b, a % b, x1, y1);
        x = y1;
        y = x1 - (a / b) * y1;
        return g;
    }
    Z inv() const {
        long long x, y;
        long long g = egcd((v%MOD+MOD)%MOD, MOD, x, y);
        if (g != 1) { cerr << "mod inverse does not exist (gcd != 1)\n"; std::abort(); }
        x %= MOD; if (x < 0) x += MOD;
        return Z(x);
    }

    friend ostream& operator<<(ostream &os, const Z &x) { return os << x.v; }
};
#ifndef USE_CIN

inline bool read(Bint &b) {
    string s;
    if (!FastIO::readToken(s)) return false;
    b.read_from_string(s);
    return true;
}

template<typename T>
typename enable_if<is_integral<T>::value && !is_same<T,bool>::value && !is_same<T,lll>::value, bool>::type
read(T &x) { return FastIO::readInt<T>(x); }

inline bool read(lll &x) {
    string s;
    if (!FastIO::readToken(s)) return false;
    bool neg = false; size_t i = 0;
    if (s[i] == '-') { neg = true; ++i; }
    lll val = 0;
    for (; i < s.size(); ++i) val = val * 10 + (s[i] - '0');
    x = neg ? -val : val;
    return true;
}

// ---- added: read long double (db) for FastIO mode ----
inline bool read(db &x) {
    string s;
    if (!FastIO::readToken(s)) return false;
    try {
        x = stold(s);
    } catch(...) {
        // fallback
        x = 0;
    }
    return true;
}

inline bool read(string &s) { return FastIO::readToken(s); }
inline bool read(char &c) {
    int ch = FastIO::readChar();
    if (ch == EOF) return false;
    while (ch != EOF && isspace(ch)) ch = FastIO::readChar();
    if (ch == EOF) return false;
    c = (char)ch;
    return true;
}
inline bool read(bool &b) { int t; if (!FastIO::readInt<int>(t)) return false; b = (t != 0); return true; }
inline bool read(Z &z) { long long t; if (!FastIO::readInt<long long>(t)) return false; z = Z(t); return true; }

template<typename A, typename B> bool read(pair<A,B> &p) { if(!read(p.first)) return false; return read(p.second); }
template<typename T> bool read(vector<T> &v) { for (auto &e : v) if (!read(e)) return false; return true; }

template<typename T1, typename T2, typename... Ts, typename = typename enable_if<(sizeof...(Ts) >= 0)>::type>
bool read(T1 &a, T2 &b, Ts&... rest) {
    if (!read(a)) return false;
    if (!read(b)) return false;
    return (read(rest) && ...);
}
inline void print(const Bint &b) { FastIO::writeString(b.toString()); }
template<typename T> typename enable_if<is_integral<T>::value && !is_same<T,bool>::value && !is_same<T,lll>::value, void>::type print(const T &x) { FastIO::writeInt<T>(x); }
// ---- added: print long double (db) for FastIO mode ----
inline void print(const db &x) {
    // default 15 digits after decimal
    char buf[64];
    int n = snprintf(buf, sizeof(buf), "%.15Lf", (long double)x);
    FastIO::writeString(string(buf, n));
}
inline void print(const string &s) { FastIO::writeString(s); }
inline void print(char c) { FastIO::writeChar(c); }
inline void print(const Z &z) { FastIO::writeInt<long long>(z.v); }

// ---- added: print pair for FastIO mode ----
template<typename A, typename B>
void print(const pair<A,B> &p) {
    print(p.first);
    FastIO::writeChar(' ');
    print(p.second);
}

template<typename T, typename U, typename... Ts, typename = typename enable_if<(sizeof...(Ts) >= 0)>::type>
void print(const T &first, const U &second, const Ts&... rest) {
    print(first);
    FastIO::writeChar(' ');
    print(second);
    ((FastIO::writeChar(' '), print(rest)), ...);
}
template<typename T>
inline void print(const vector<T>& v) { for (auto &e : v) print(e, ""); }

inline void println() { FastIO::writeChar('\n'); }
template<typename T> void println(const T &x) { print(x); FastIO::writeChar('\n'); }

#else
inline bool read(Bint &b) { string s; if (!(cin >> s)) return false; b.read_from_string(s); return true; }
template<typename T> typename enable_if<is_integral<T>::value && !is_same<T,bool>::value && !is_same<T,lll>::value, bool>::type read(T &x) { if (!(cin >> x)) return false; return true; }
inline bool read(lll &x) { string s; if (!(cin >> s)) return false; bool neg=false; size_t i=0; if (s[0]=='-'){neg=true;i=1;} lll v=0; for(;i<s.size();++i) v=v*10+(s[i]-'0'); x=neg?-v:v; return true; }

// ---- added: read long double (db) for cin mode ----
inline bool read(db &x) { long double t; if (!(cin >> t)) return false; x = t; return true; }

inline bool read(string &s) { if (!(cin >> s)) return false; return true; }
inline bool read(char &c) { if (!(cin >> c)) return false; return true; }
inline bool read(bool &b) { int t; if (!(cin >> t)) return false; b=(t!=0); return true; }
inline bool read(Z &z) { long long t; if (!(cin >> t)) return false; z = Z(t); return true; }
template<typename A, typename B> bool read(pair<A,B> &p) { if(!read(p.first)) return false; return read(p.second); }
template<typename T> bool read(vector<T> &v) { for (auto &e : v) if (!read(e)) return false; return true; }
template<typename T1, typename T2, typename... Ts> bool read(T1 &a, T2 &b, Ts&... rest) { if (!read(a)) return false; if (!read(b)) return false; return (read(rest) && ...); }

inline void print(const Bint &b) { cout << b.toString(); }
template<typename T> typename enable_if<is_integral<T>::value && !is_same<T,bool>::value && !is_same<T,lll>::value, void>::type print(const T &x) { cout << x; }
// ---- added: print long double (db) for cin/cout mode ----
inline void print(const db &x) { cout.setf(std::ios::fmtflags(0), std::ios::floatfield); cout << std::setprecision(15) << (long double)x; }
inline void print(const string &s) { cout << s; }
inline void print(char c) { cout << c; }
inline void print(const Z &z) { cout << z.v; }

// ---- added: print pair for cin/cout mode ----
template<typename A, typename B>
void print(const pair<A,B> &p) {
    print(p.first);
    cout.put(' ');
    print(p.second);
}

template<typename T, typename U, typename... Ts, typename = typename enable_if<(sizeof...(Ts) >= 0)>::type>
void print(const T &first, const U &second, const Ts&... rest) {
    print(first); cout.put(' '); print(second); ((cout.put(' '), print(rest)), ...);
}
inline void println() { cout << '\n'; }
template<typename T> void println(const T &x) { print(x); cout << '\n'; }
#endif
const ll n = 3e5 + 10;
struct Nd {
    bool lz, val;
} st[n<<2];

void pushdown(int l, int r, int idx) {
    if (!st[idx].lz) return;
    st[idx<<1].lz = st[idx<<1|1].lz = st[idx].lz;
    int m = l + r >> 1;
    st[idx<<1].val = 1;
    st[idx<<1|1].val = 1;
    st[idx].lz = 0;
}

void pushup(int idx) {
    st[idx].val = st[idx<<1].val | st[idx<<1|1].val;
}

void update(int ul, int ur, int l, int r, int idx) {
    if (ul > r or ur < l) return;
    if (ul <= l and r <= ur) {
        st[idx].lz = st[idx].val = 1;
        return;
    }
    pushdown(l, r, idx);
    int m = l + r >> 1;
    update(ul, ur, l, m, idx<<1);
    update(ul, ur, m + 1, r, idx << 1 | 1);
    pushup(idx);
}

int query(int ql, int qr, int l, int r, int idx) {
    if (ql > r or qr < l) return 0;
    if (ql <= l and r <= qr) return st[idx].val;
    pushdown(l, r, idx);
    int m = l + r >> 1;
    return query(ql, qr, l, m, idx << 1) | query(ql, qr, m + 1, r, idx << 1 | 1);
}

void solve() {
    ll q; rd(q);
    int mx = 1;
    while (q--) {
        int l, r; rd(l, r);
        if (!query(l, r, 1, n, 1)) {
            update(l, r, 1, n, 1);
            mx = max(mx, r - l + 2);
        }
        println(mx);
    }
}

int main() {
    // fastio;
    int T = 1;
   // rd(T);
    while (T--) solve();
    return 0;
}