#include #include #include #include #include #include using std::pair; using std::vector; struct TreeNode { int value, size, diff, sum; TreeNode *lch, *rch; TreeNode() : value(0), size(0), diff(0), sum(0), lch(nullptr), rch(nullptr) {} TreeNode(int val); pair Split(int pos); void Update() { // Update the sum of the diff in the subtree sum = diff + lch->sum + rch->sum; // Update the size of the subtree size = 1 + lch->size + rch->size; } int GetRightValue(); void UpdateLeftNode(int val); int QuerySum(int rank); } *null, *root; vector pool; int n; bool Branch(int l, int r) { return rand() % (l + r) < l; } TreeNode::TreeNode(int val) : value(val), size(1), diff(1), lch(null), rch(null) {} int TreeNode::GetRightValue() { if (rch == null) return value; return rch->GetRightValue(); } void TreeNode::UpdateLeftNode(int val) { // If the value of the leftest node of the tree is equal to val, set diff to 0. // Otherwise, set diff to 1. // Then update the sum. if (lch == null) { diff = val != value; Update(); return; } lch->UpdateLeftNode(val); Update(); } TreeNode *Merge(TreeNode *p, TreeNode *q) { // Merge two subtree if (p == null) return q; if (q == null) return p; if (Branch(p->size, q->size)) { p->rch = Merge(p->rch, q); p->Update(); return p; } else { q->lch = Merge(p, q->lch); q->Update(); return q; } } TreeNode *DoMerge(TreeNode *p, TreeNode *q) { // Merge Treap q to the left of Treap p int lval = p->GetRightValue(); q->UpdateLeftNode(lval); return Merge(p, q); } pair TreeNode::Split(int pos) { // Split a Treap into two Treap at pos if (this == null) return {null, null}; if (pos <= lch->size) { pair res = lch->Split(pos); lch = null; Update(); return {res.first, Merge(res.second, this)}; } else { pair res = rch->Split(pos - lch->size - 1); rch = null; Update(); return {Merge(this, res.first), res.second}; } } int TreeNode::QuerySum(int rank) { // Query the sum of diff of the first rank node in the subtree. if (this == null) return 0; if (rank <= lch->size) return lch->QuerySum(rank); return lch->sum + diff + rch->QuerySum(rank - lch->size - 1); } void Query2(int l, int r) { // Deal with the type 2 query. if (l == 1) return; if (r == n) { auto res = root->Split(l - 1); res.second->UpdateLeftNode(0); root = DoMerge(res.second, res.first); } else { auto res = root->Split(r); auto c = res.second; res = res.first->Split(l - 1); auto a = res.first; auto b = res.second; b->UpdateLeftNode(0); root = DoMerge(b, DoMerge(a, c)); } } void Init() { while (!pool.empty()) { delete pool.back(); pool.pop_back(); } // Build the Treap from the array root = null; assert(scanf("%d", &n) == 1); for (int i = 0; i < n; ++i) { int val; assert(scanf("%d", &val) == 1); pool.push_back(new TreeNode(val)); root = DoMerge(root, pool.back()); } } void Work() { int m; assert(scanf("%d", &m) == 1); while (m--) { int t, l, r; assert(scanf("%d%d%d", &t, &l, &r) == 3); if (t == 1) { printf("%d\n", root->QuerySum(r) - root->QuerySum(l) + 1); } else { Query2(l, r); } } } int main() { srand(time(0)); null = new TreeNode(); null->lch = null->rch = null; int cases; assert(scanf("%d", &cases) == 1); while (cases--) { Init(); Work(); } return 0; }