// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; } template bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; } namespace RBST { unsigned xrand() { static unsigned x = 314159265, y = 358979323, z = 846264338, w = 327950288; unsigned t = x ^ x << 11; x = y; y = z; z = w; return w = w ^ w >> 19 ^ t ^ t >> 8; } constexpr int MAX = 30000010; int n, l[MAX], r[MAX], size[MAX]; Int key[MAX], sum[MAX]; int node(Int key_) { n[l] = n[r] = -1; n[size] = 1; n[key] = n[sum] = key_; return n++; } int change(int a, int l_, int r_) { a[l] = l_; a[r] = r_; a[size] = (~l_ ? l_[size] : 0) + 1 + (~r_ ? r_[size] : 0); a[sum] = (~l_ ? l_[sum] : 0) + a[key] + (~r_ ? r_[sum] : 0); return a; } int merge(int a, int b) { if (!~a) return b; if (!~b) return a; if ((int)(xrand() % (a[size] + b[size])) < a[size]) { return change(a, a[l], merge(a[r], b)); } else { return change(b, merge(a, b[l]), b[r]); } } pair splitKey(int a, Int key_) { if (!~a) return {-1, -1}; if (key_ <= a[key]) { const auto l_ = splitKey(a[l], key_); return {l_.first, change(a, l_.second, a[r])}; } else { const auto r_ = splitKey(a[r], key_); return {change(a, a[l], r_.first), r_.second}; } } pair splitHead(int a) { if (~a[l]) { const auto l_ = splitHead(a[l]); return {l_.first, change(a, l_.second, a[r])}; } else { const int r_ = a[r]; return {change(a, -1, -1), r_}; } } int insert(int a, Int key_) { const auto sp = splitKey(a, key_); return merge(merge(sp.first, node(key_)), sp.second); } int eraseKey(int a, Int key_) { const auto sp = splitKey(a, key_); return merge(sp.first, splitHead(sp.second).second); } pair sumLessThan(int a, Int key_) { int ret0 = 0; Int ret1 = 0; for (; ~a; ) { if (key_ <= a[key]) { a = a[l]; } else { if (a[l]) { ret0 += a[l][size]; ret1 += a[l][sum]; } ret0 += 1; ret1 += a[key]; a = a[r]; } } return {ret0, ret1}; } void print(int a) { if (!~a) return; printf("["); print(a[l]); printf(" (%d;%lld) ", a, a[key]); print(a[r]); printf("]"); } } // RBST constexpr int MAX_N = 70010; constexpr int MASK_16 = (1 << 16) - 1; constexpr Int MASK_40 = (1LL << 40) - 1; int N, Q; Int A[MAX_N]; int segN; int seg[MAX_N << 2]; pair get(int a, int b) { int ret0 = 0; Int ret1 = 0; for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) { if (a & 1) { ret0 += seg[a][RBST::size]; ret1 += seg[a][RBST::sum]; ++a; } if (b & 1) { --b; ret0 += seg[b][RBST::size]; ret1 += seg[b][RBST::sum]; } } return {ret0, ret1}; } pair get(int a, int b, Int key_) { int ret0 = 0; Int ret1 = 0; for (a += segN, b += segN; a < b; a >>= 1, b >>= 1) { if (a & 1) { const auto res = RBST::sumLessThan(seg[a++], key_); ret0 += res.first; ret1 += res.second; } if (b & 1) { const auto res = RBST::sumLessThan(seg[--b], key_); ret0 += res.first; ret1 += res.second; } } return {ret0, ret1}; } int main() { for (; ~scanf("%d%d", &N, &Q); ) { for (int i = 0; i < N; ++i) { scanf("%lld", &A[i]); } RBST::n = 0; for (segN = 1; segN < N; segN <<= 1) {} fill(seg, seg + (segN << 1), -1); for (int i = 0; i < N; ++i) { for (int a = segN + i; a; a >>= 1) { seg[a] = RBST::insert(seg[a], A[i]); } } // for(int a=1;a>= 1) { seg[a] = RBST::insert(RBST::eraseKey(seg[a], A[x]), y); } A[x] = y; } break; case 2: { int l, r; scanf("%d%d", &l, &r); l ^= (s & MASK_16); r ^= (s & MASK_16); if (l > r) { swap(l, r); } --l; assert(0 <= l && l < r && r <= N); // cerr<<"query 2 "<= (r - l + 1) / 2) ? hi : lo) = mid; } // cerr<<" lo = "<