Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- const bool debug = false;
- #define ff first
- #define ss second
- inline int readInt() {
- int c = getc(stdin);
- int x = 0;
- while (c <= 32) {
- c = getc(stdin);
- }
- while ('0' <= c && c <= '9') {
- x = x * 10 + c - '0', c = getc(stdin);
- }
- return x;
- }
- char readChar() {
- char c = getc(stdin);
- while (c != '?' && c != '!') {
- c = getc(stdin);
- }
- return c;
- }
- inline void writeInt(int x){
- char s[15];
- int n = 0;
- while (x || !n) {
- s[n++] = '0' + x % 10, x /= 10;
- }
- while (n--) {
- putc(s[n], stdout);
- }
- putc('\n', stdout);
- }
- typedef long long ll;
- typedef long double ld;
- typedef unsigned long long ull;
- const int maxn = 2e5 + 7;
- const int inf = 2e9 + 7;
- const ll infl = 1e18 + 7;
- const long double eps = 1e-9;
- const ll mod = 998244353;
- typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> os;
- int a[maxn], b[maxn], arr[maxn];
- int pre[maxn];
- os t[4 * maxn];
- void build(int v, int tl, int tr) {
- if (tl == tr) {
- t[v].insert({arr[tl], tl});
- return;
- }
- int tm = (tl + tr) / 2;
- build(2 * v, tl, tm);
- build(2 * v + 1, tm + 1, tr);
- t[v] = t[2 * v];
- for (pair<int, int> i : t[2 * v + 1]) {
- t[v].insert(i);
- }
- }
- void upd(int v, int tl, int tr, int pos, pair<int, int> was, pair<int, int> x) {
- t[v].erase(was);
- t[v].insert(x);
- if (tl == tr) return;
- int tm = (tl + tr) / 2;
- if (pos <= tm) upd(2 * v, tl, tm, pos, was, x);
- else upd(2 * v + 1, tm + 1, tr, pos, was, x);
- }
- int get(int v, int tl, int tr, int l, int r, int lp, int rp) {
- if (tl == l && tr == r) {
- int rr = t[v].order_of_key({rp + 1, -1});
- int ll = t[v].order_of_key({lp, -1});
- return rr - ll;
- }
- int tm = (tl + tr) / 2;
- if (r <= tm) return get(2 * v, tl, tm, l, r, lp, rp);
- else if (l > tm) return get(2 * v + 1, tm + 1, tr, l, r, lp, rp);
- else return get(2 * v, tl, tm, l, tm, lp, rp) + get(2 * v + 1, tm + 1, tr, tm + 1, r, lp, rp);
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n = readInt(), m = readInt();
- for (int i = 0; i < n; i++) {
- int x;
- x = readInt();
- pre[x] = i;
- a[i] = pre[x];
- }
- for (int i = 0; i < n; ++i) {
- int x;
- x = readInt();
- b[i] = pre[x];
- arr[pre[x]] = i;
- }
- build(1, 0, n - 1);
- while (m--) {
- int tp;
- tp = readInt();
- if (tp == 1) {
- int l1 = readInt(), r1 = readInt(), l2 = readInt(), r2 = readInt();
- writeInt(get(1, 0, n - 1, l1 - 1, r1 - 1, l2 - 1, r2 - 1));
- }
- else {
- int x = readInt(), y = readInt();
- --x;
- --y;
- upd(1, 0, n - 1, b[x], {x, b[x]}, {y, b[x]});
- upd(1, 0, n - 1, b[y], {y, b[y]}, {x, b[y]});
- swap(b[x], b[y]);
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement