Solution to CF Educational Round 56 Problem E, with CDQ divide-and-conquer （CDQ分治）

cdq.cpp

#include <bits/stdc++.h>
/*
  https://codeforces.com/contest/1093/problem/E
  
  Convert all modification and query into single-point events (t, x, y). Initially sort by t,
  for each interval, recursively handle independent two parts. Then calc the interference
  between part one and two: only mod in part 1 can affect result in part 2. Therefore, we can
  sort part1 and 2 respectively by x, then process all mod event in part 1 and all query events in
  part 2 in a sort-merge-like way. The Y-dimension is maintained with a fenwick tree.
  In the end all elements will be sorted by x.
*/
vector<int> b;
struct Event {
    enum Type {
        ADDANS,
        SUBANS,
        ADD,
        REMOVE
    } type;
    int t, x, y;
    int ansid;
};

vector<Event> e;
vector<int> ans;
int n;
int m;

struct Fenwick {
    vector<int> a;
    Fenwick(int cap): a(cap+2) {}
    static int lowbit(int x) {
        return x & (-x);
    }

    int prefix(int p) {
        ++p;
        int ans = 0;
        while (p > 0)
        {
            ans += a[p];
            p -= lowbit(p);
        }
        return ans;
    }

    void add(int p, int x) {
        ++p;
        while (p < a.size()){
            a[p] += x;
            p += lowbit(p);
        }
    }
} f(1);

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;
    cdq(l, mid);
    cdq(mid + 1, r);
    static vector<Event> buf;
    buf.clear();
    buf.reserve(r-l+1);

    int t1 = l, t2 = mid + 1;
    while (t1 <= mid || t2 <= r)
        if (t1 <= mid && (t2 > r || e[t1].x <= e[t2].x))
        {
            buf.push_back(e[t1]);
            switch (e[t1].type) {
                case Event::Type::ADD:
                    f.add(e[t1].y, 1);
                    break;
                case Event::Type::REMOVE:
                    f.add(e[t1].y, -1);
                    break;
            }
            ++t1;
        } else {
            buf.push_back(e[t2]);
            switch (e[t2].type) {
                case Event::Type::ADDANS:
                    ans[e[t2].ansid] += f.prefix(e[t2].y);
                    break;
                case Event::Type::SUBANS:
                    ans[e[t2].ansid] -= f.prefix(e[t2].y);
                    break;
            }
            ++t2;
        }
    for (int i=l; i<=mid; ++i)
        switch (e[i].type) {
                case Event::Type::ADD:
                    f.add(e[i].y, -1);
                    break;
                case Event::Type::REMOVE:
                    f.add(e[i].y, 1);
                    break;
        }
    copy(buf.begin(), buf.end(), e.begin() + l);
}

int main()
{
    std::ios::sync_with_stdio(false);std::cin.tie(0);ios_base::sync_with_stdio(0);
    cin >> n >> m;
    f = Fenwick(n+1);
    vector<int> pos(n);
    int t = 0;
    for(int i=0;i<n;++i) {
        int w;
        cin >> w;
        pos[w-1] = i;
    }
    for(int i=0;i<n;++i) {
        int w;
        cin >> w;
        b.push_back(pos[w-1]);
        e.push_back(Event{Event::Type::ADD, t++, i, pos[w-1]});
    }
    for(int i=0;i<m;++i) {
        int q;
        cin >> q;
        if (q == 1)
        {
            int vl, vr, l, r;
            cin >> vl >> vr >> l >> r;
            --vl; --vr; --l; --r;
            ans.push_back(0);
            e.push_back(Event{Event::Type::ADDANS, t++, r, vr, (int)ans.size() - 1});
            e.push_back(Event{Event::Type::ADDANS, t++, l-1, vl-1, (int)ans.size() - 1});
            e.push_back(Event{Event::Type::SUBANS, t++, r, vl-1, (int)ans.size() - 1});
            e.push_back(Event{Event::Type::SUBANS, t++, l-1, vr, (int)ans.size() - 1});
        } else {
            int p1, p2;
            cin >> p1 >> p2;
            --p1; --p2;
            e.push_back(Event{Event::Type::REMOVE, t++, p1, b[p1]});
            e.push_back(Event{Event::Type::REMOVE, t++, p2, b[p2]});
            swap(b[p1], b[p2]);
            e.push_back(Event{Event::Type::ADD, t++, p1, b[p1]});
            e.push_back(Event{Event::Type::ADD, t++, p2, b[p2]});
        }
    }

    cdq(0, t-1);
    for (int v: ans)
        cout << v << '\n';
}