Magic multisets - VietMX's Blog

In the School of Magic in Dirtpolis a lot of interesting objects are studied on Computer Science lessons.

Consider, for example, the magic multiset. If you try to add an integer to it that is already presented in the multiset, each element in the multiset duplicates. For example, if you try to add the integer $2$ to the multiset $\{1, 2, 3, 3\}$, you will get $\{1, 1, 2, 2, 3, 3, 3, 3\}$.

If you try to add an integer that is not presented in the multiset, it is simply added to it. For example, if you try to add the integer $4$ to the multiset $\{1, 2, 3, 3\}$, you will get $\{1, 2, 3, 3, 4\}$.

Also consider an array of $n$ initially empty magic multisets, enumerated from $1$ to $n$.

You are to answer $q$ queries of the form “add an integer $x$ to all multisets with indices $l, l + 1, \ldots, r$” and “compute the sum of sizes of multisets with indices $l, l + 1, \ldots, r$”. The answers for the second type queries can be large, so print the answers modulo $998244353$.

Input

The first line contains two integers $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^{5}$) — the number of magic multisets in the array and the number of queries, respectively.

The next $q$ lines describe queries, one per line. Each line starts with an integer $t$ ($1 \leq t \leq 2$) — the type of the query. If $t$ equals $1$, it is followed by three integers $l$, $r$, $x$ ($1 \leq l \leq r \leq n$, $1 \leq x \leq n$) meaning that you should add $x$ to all multisets with indices from $l$ to $r$ inclusive. If $t$ equals $2$, it is followed by two integers $l$, $r$ ($1 \leq l \leq r \leq n$) meaning that you should compute the sum of sizes of all multisets with indices from $l$ to $r$ inclusive.

Output

For each query of the second type print the sum of sizes of multisets on the given segment.

The answers can be large, so print them modulo $998244353$.

Examples

input

output

input

output

4
8

Note

In the first example after the first two queries the multisets are equal to $[\{1, 2\},\{1, 2\},\{\},\{\}]$, after the third query they are equal to $[\{1, 1, 2, 2\},\{1, 1, 2, 2\},\{1\},\{1\}]$.

In the second example the first multiset evolves as follows:

$\{\} \to \{3\} \to \{3, 3\} \to \{2, 3, 3\} \to \{1, 2, 3, 3\} \to \{1, 1, 2, 2, 3, 3, 3, 3\}$.

Solution:

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

const int md = 998244353;

inline void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

inline void sub(int &a, int b) {
a -= b;
if (a < 0) a += md;
}

inline int mul(int a, int b) {
#if !defined(_WIN32) || defined(_WIN64)
  return (int) ((long long) a * b % md);
#endif
  unsigned long long x = (long long) a * b;
  unsigned xh = (unsigned) (x >> 32), xl = (unsigned) x, d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (md)
);
return m;
}

inline int power(int a, long long b) {
int res = 1;
while (b > 0) {
if (b & 1) {
res = mul(res, a);
}
a = mul(a, a);
b >>= 1;
}
return res;
}

inline int inv(int a) {
a %= md;
if (a < 0) a += md;
  int b = md, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += md;
  return u;
}

class segtree {
  public:
  struct node {
    int ad = 0;
    int mu = 1;
    int sum = 0;

    void apply(int l, int r, int v) {
      if (v >= 0) {
add(ad, v);
add(sum, mul(v, r - l + 1));
} else {
v = ~v;
ad = mul(ad, v);
mu = mul(mu, v);
sum = mul(sum, v);
}
}
};

node unite(const node &a, const node &b) const {
node res;
res.sum = a.sum;
add(res.sum, b.sum);
return res;
}

inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    if (tree[x].mu != 1) {
      tree[x + 1].apply(l, y, ~tree[x].mu);
      tree[z].apply(y + 1, r, ~tree[x].mu);
      tree[x].mu = 1;
    }
    if (tree[x].ad != 0) {
      tree[x + 1].apply(l, y, tree[x].ad);
      tree[z].apply(y + 1, r, tree[x].ad);
      tree[x].ad = 0;
    }
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}

template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}

int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}

int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}

template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}

node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, tt;
  cin >> n >> tt;
vector<set<pair<int,int>>> s(n);
for (int i = 0; i < n; i++) {
    s[i].emplace(0, n - 1);
  }
  segtree st(n);
  while (tt--) {
    int op;
    cin >> op;
if (op == 1) {
int l, r, v;
cin >> l >> r >> v;
l--; r--; v--;
vector<pair<int,int>> inside;
int needed = 1;
{
auto it = s[v].lower_bound(make_pair(l, -1));
if (it != s[v].begin()) {
it--;
if (it->second >= l) {
int x = it->first;
int y = it->second;
if (y <= r) {
              s[v].erase(it);
              s[v].emplace(x, l - 1);
              inside.emplace_back(l, y);
            } else {
              s[v].erase(it);
              s[v].emplace(x, l - 1);
              s[v].emplace(r + 1, y);
              inside.emplace_back(l, r);
              needed = 0;
            }
          }
        }
      }
      if (needed) {
        auto it = s[v].lower_bound(make_pair(l, -1));
        auto start = it;
        pair<int,int> to_add(-1, -1);
while (it != s[v].end()) {
if (it->first > r) {
break;
}
if (it->second > r) {
to_add = make_pair(r + 1, it->second);
}
inside.emplace_back(it->first, min(it->second, r));
it++;
}
s[v].erase(start, it);
if (to_add.first != -1) {
s[v].insert(to_add);
}
}
int last = l - 1;
for (auto &p : inside) {
if (p.first - 1 >= last + 1) {
st.modify(last + 1, p.first - 1, ~2);
}
st.modify(p.first, p.second, 1);
last = p.second;
}
if (r >= last + 1) {
st.modify(last + 1, r, ~2);
}
} else {
int l, r;
cin >> l >> r;
l--; r--;
cout << st.get(l, r).sum << '\n';
    }
  }
  return 0;
}

Messy

New Year Tree

Perfect Triples

Dynamic Programming on Broken Profile

Kate and imperfection