Slicnost

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 1 << 17;

template<typename T> T spoji(T a, T b){
    if(a.fi != b.fi) return max(a, b);
    return {a.fi, a.se + b.se};
}
struct Node{
    Node *lc = nullptr, *rc = nullptr;
    pii val;
    int lazy = 0;
    void calc(){
        val = spoji(lc->val, rc->val);
    }
};
Node* build(int l = 0, int r = MAX){
    Node* node = new Node;
    if(r - l == 1){
        node->val = {0, 1};
        return node;
    }
    int m = (l + r) / 2;
    node->lc = build(l, m);
    node->rc = build(m, r);
    node->calc();
    return node;
}
Node* clone(Node* node){
    Node* novi = new Node;
    novi->lc = node->lc;
    novi->rc = node->rc;
    novi->val = node->val;
    novi->lazy = node->lazy;
    return novi;
}
void prop(Node* node, int l, int r){
    if(!node->lazy || r - l == 1) return;

    node->lc = clone(node->lc);
    node->lc->val.fi += node->lazy;
    node->lc->lazy += node->lazy;

    node->rc = clone(node->rc);
    node->rc->val.fi += node->lazy;
    node->rc->lazy += node->lazy;

    node->lazy = 0;
}
Node* update(int lu, int ru, int val, Node* node, int l = 0, int r = MAX){
    if(l >= lu && r <= ru){
        Node* novi = clone(node);
        novi->val.fi += val;
        novi->lazy += val;
        return novi;
    }
    if(l >= ru || r <= lu) return node;

    prop(node, l, r);

    int m = (l + r) / 2;
    Node* novi = new Node;
    novi->lc = update(lu, ru, val, node->lc, l, m);
    novi->rc = update(lu, ru, val, node->rc, m, r);
    novi->calc();

    return novi;
}
void print(Node* node, int l = 0, int r = MAX){
    if(r - l == 1){
        printf("(%d, %d) ", node->val.fi, node->val.se);
        return;
    }
    prop(node, l, r);

    int m = (l + r)/2;
    print(node->lc, l, m);
    print(node->rc, m, r);
}

struct Tour2{
    pair<int, ll> nodes[2*MAX];

    void update(int ind, pii val, int node = 1, int l = 0, int r = MAX){
        if(r - l == 1){
            nodes[node] = val;
            return;
        }

        int m = (l + r) / 2;
        if(ind < m) update(ind, val, 2*node, l, m);
        else update(ind, val, 2*node + 1, m, r);

        nodes[node] = spoji(nodes[2*node], nodes[2*node + 1]);
    }
};

int n, k, q, pos[MAX];
pii lrs[MAX];

Node *tours[MAX];
Tour2 t2;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k >> q;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        pos[x] = i;
    }
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        int l = max(i - k + 1, 0), r = min(i, n - k) + 1;

        lrs[pos[x]] = {l, r};
    }

    tours[0] = build();
    for(int i = 0; i < k - 1; i++){
        tours[0] = update(lrs[i].fi, lrs[i].se, 1, tours[0]);
    }

    for(int i = k - 1; i < n; i++){
        tours[i - k + 1] = update(lrs[i].fi, lrs[i].se, 1, tours[i - k + 1]);
        t2.update(i - k + 1, tours[i - k + 1]->val);
        tours[i - k + 2] = update(lrs[i - k + 1].fi, lrs[i - k + 1].se, -1, tours[i - k + 1]);
    }
    cout << t2.nodes[1].fi << ' ' << t2.nodes[1].se << '\n';

    while(q--){
        int x;
        cin >> x;
        x--;
        int a = x - k + 1, b = x + 1;

        if(a >= 0){
            tours[a] = update(lrs[x].fi, lrs[x].se, -1, tours[a]);
            tours[a] = update(lrs[x + 1].fi, lrs[x + 1].se, 1, tours[a]);
            t2.update(a, tours[a]->val);
        }
        if(b <= n - k){
            tours[b] = update(lrs[x + 1].fi, lrs[x + 1].se, -1, tours[b]);
            tours[b] = update(lrs[x].fi, lrs[x].se, 1, tours[b]);
            t2.update(b, tours[b]->val);
        }

        swap(lrs[x], lrs[x + 1]);
        cout << t2.nodes[1].fi << ' ' << t2.nodes[1].se << '\n';
    }

    return 0;
}