F. Intersection and Union.cpp

#include <bits/stdc++.h>

using namespace std;

const int MX = 3e5 + 5;
long long int MOD = 998244353;

struct mat{
    long long int a, b, c, d;
    mat(){a = d = 1;}

    mat operator *(mat &other){
        mat res;
        res.a = (a * other.a + b * other.c) % MOD;
        res.b = (a * other.b + b * other.d) % MOD;
        res.c = (c * other.a + d * other.c) % MOD;
        res.d = (c * other.b + d * other.d) % MOD;
        return res;
    }

    bool isI(){
        return a == 1 && d == 1 && b == 0 && c == 0;
    }

    void print(){
        cout << "(a, b, c, d): " << "(" << a << ", " << b << ", " << c << ", " << d << ")\n";
    }
};

mat I, m0, m1;
mat tree[MX * 4], lazy[MX * 4];

void prop(int n, int nL, int nR){
    tree[n] = lazy[n] * tree[n];
    if(nL != nR){
        lazy[n * 2] = lazy[n] * lazy[n * 2];
        lazy[n * 2 + 1] = lazy[n] * lazy[n * 2 + 1];
    }
    lazy[n] = I;
}

void Update(int n, int L, int R, int nL, int nR, mat m){
    if(!lazy[n].isI()) prop(n, nL, nR);
    if(R < nL || L > nR) return;
    if(L <= nL && nR <= R){
        lazy[n] = m * lazy[n];
        prop(n, nL, nR);
        return;
    }

    int mid = (nL + nR) >> 1;
    Update(n * 2, L, R, nL, mid, m);
    Update(n * 2 + 1, L, R, mid + 1, nR, m);
}

mat Query(int n, int tar, int nL, int nR){
    if(!lazy[n].isI()) prop(n, nL, nR);
    if(nL == nR) return tree[n];

    int mid = (nL + nR) >> 1;
    if(tar <= mid) return Query(n * 2, tar, nL, mid);
    else return Query(n * 2 + 1, tar, mid + 1, nR);
}

int main(){
    cin.tie(nullptr), ios::sync_with_stdio(false);
    m0.a = 3, m0.b = 1, m0.c = 0, m0.d = 2;
    m1.a = 1, m1.b = 1, m1.c = 2, m1.d = 2;

    int initL, initR;
    int n, l, r;
    cin >> n;
    n--;
    cin >> initL >> initR;

    while(n--){
        cin >> l >> r;
        if(l != 0) Update(1, 0, l - 1, 0, 3e5, m0);
        Update(1, l, r, 0, 3e5, m1);
        if(r != 3e5) Update(1, r + 1, 3e5, 0, 3e5, m0);
    }

    long long int ans = 0;
    for(int i = 0; i <= 3e5; i++){
        if(initL <= i && i <= initR) ans += Query(1, i, 0, 3e5).d;
        else ans += Query(1, i, 0, 3e5).c;
        ans %= MOD;
    }

    cout << ans;
}