/* In this problem we use Cartesian Tree with implicit key. */ #include #include #include #include using namespace std; typedef struct tree* pTree; struct tree{ int val, cnt, prior, lval, rval; int ans; pTree l, r; tree() {} tree(int _val) { val = _val; cnt = 1; lval = rval = val; l = r = NULL; ans = 1; prior = rand() % 1000000000 + 1; } }; int get_cnt(pTree v) { if (!v) return 0; return v->cnt; } int get_ans(pTree v) { if (!v) return 0; return v->ans; } void upd_cnt(pTree v) { if (!v) return; v->cnt = 1 + get_cnt(v->l) + get_cnt(v->r); if (v->l) v->lval = v->l->lval; else v->lval = v->val; if (v->r) v->rval = v->r->rval; else v->rval = v->val; v->ans = 1 + get_ans(v->l) + get_ans(v->r); if (v->l && v->l->rval == v->val) v->ans -= 1; if (v->r && v->r->lval == v->val) v->ans -= 1; } void split(pTree t, pTree &l, pTree &r, int key, int add = 0) { if (!t) { l = r = NULL; return; } int cur_add = add + get_cnt(t->l); if (cur_add >= key) split(t->l, l, t->l, key, add), r = t; else split(t->r, t->r, r, key, add + get_cnt(t->l) + 1), l = t; upd_cnt(l); upd_cnt(r); } void merge(pTree &t, pTree l, pTree r) { upd_cnt(l); upd_cnt(r); if (!l || !r) { t = l ? l : r; return; } if (l->prior > r->prior) merge(l->r, l->r, r), t = l; else merge(r->l, l, r->l), t = r; upd_cnt(t); } void insert(pTree &t, int val) { pTree tmp = new tree(val); merge(t, t, tmp); } void write(pTree t) { // DEBUG INFO if (!t) return; write(t->l); cout << t->val << " "; write(t->r); } int get(pTree root, int l, int r) { pTree t1, t2, t3; // spliting tree in three segments t1, t2, t3 split(root, t1, t3, r); split(t1, t1, t2, l - 1); // t2 = segment from l to r int ret = t2->ans; // get back to start position merge(t1, t1, t2); merge(root, t1, t3); return ret; } void replacing(pTree &root, int l, int r) { pTree t1, t2, t3; // spliting tree in three segments t1, t2, t3 split(root, t1, t3, r); split(t1, t1, t2, l - 1); // merging them in this order: t2, t1, t3 (t2 - segment for this tree is equal to (l, r)) merge(t1, t2, t1); merge(root, t1, t3); } int main() { // number of test cases int tests; scanf("%d", &tests); while (tests--) { pTree root = NULL; int n, val; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &val); // insert element with value that are equal to val in Cartesian Tree insert(root, val); } int m, l, r; scanf("%d", &m); for (int i = 0; i < m; ++i) { int type; scanf("%d", &type); if (type == 1) { scanf("%d%d", &l, &r); // counting ans for segment (l, r) int ret = get(root, l, r); printf("%d\n", ret); } else { scanf("%d%d", &l, &r); // replacing segment (l, r) to prefix replacing(root, l, r); } } } return 0; }