Untitled
unknown
plain_text
a month ago
3.0 kB
1
Indexable
Never
#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bits/stdc++.h> #define all(c) c.begin(), c.end() #define MOD((int) 1e9 + 7) using namespace __gnu_pbds; using namespace std; typedef tree < int, int, less < int > , rb_tree_tag, tree_order_statistics_node_update > ost; typedef tuple < int, int, int > iii; typedef vector < int > vi; typedef long long ll; class SegmentTree { private: int n; vi st; int l(int p) { return p << 1; } int r(int p) { return (p << 1) + 1; } ll mod(ll a) { a %= MOD; return a < 0 ? a + MOD : a; } int conquer(int a, int b) { return (int) mod(mod((ll) a) * mod((ll) b)); } int query(int p, int L, int R, int i, int j) { if (i > j) return 1; if ((L >= i) && (R <= j)) return st[p]; int m = (L + R) / 2; return conquer(query(l(p), L, m, i, min(m, j)), query(r(p), m + 1, R, max(i, m + 1), j)); } void update(int p, int L, int R, int i, int j, int val) { if (i > j) return; if ((L >= i) && (R <= j)) st[p] = val; else { int m = (L + R) / 2; update(l(p), L, m, i, min(m, j), val); update(r(p), m + 1, R, max(i, m + 1), j, val); st[p] = conquer(st[l(p)], st[r(p)]); } } public: SegmentTree(int sz): n(sz), st(4 * n, 0) {} void update(int i, int val) { update(1, 0, n - 1, i, i, val); } int query(int i, int j) { return query(1, 0, n - 1, i, j); } int pquery(int i) { return query(1, 0, n - 1, i, i); } }; int main() { int t, n, q; scanf("%d", & t); while (t-- && scanf("%d%d", & n, & q)) { ost map; vi vn(n); int T, l, r; vector < iii > vq; for (auto & val: vn) { scanf("%d", & val); ++map[val]; } while (q-- && scanf("%d%d%d", & T, & l, & r)) { if (T == 1) { l--; map[r] = map[r]; } vq.push_back({ T, l, r }); } int i = 0; SegmentTree st(map.size()); for (auto[_, val]: map) st.update(i++, val); auto plusX = [ & st](int v, int x) { st.update(v, st.pquery(v) + x); }; for (auto[T, l, r]: vq) { if (T == 1) { plusX(map.order_of_key(vn[l]), -1); vn[l] = r; plusX(map.order_of_key(vn[l]), 1); } else { int L = map.order_of_key(l), R = map.order_of_key(r); if (map.find(l) == map.end() || map.find(r) == map.end() || (R - L) != (r - l)) printf("0\n"); else printf("%d\n", st.query(L, R)); } } } return 0; }
Leave a Comment