Codeforces 1093E. Intersection of Permutations (Divide and Conquer + Fenwick Tree)

日付: 12月 16, 2018

[Problem - 1093E - Codeforces](https://codeforces.com/contest/1093/problem/E)
## Problem
Given two permutation array $A$ and $B$ of $1\sim n$, you are asked to perform $m$ such operations:
* $1\ l_a\ r_a\ l_b\ r_b$ - Calculate the number of values that exists in both $[l_a, r_a]$ of $A$ and $[l_b, r_b]$ of $B$.
* $2\ x\ y$ - Swap the values of $B$ at position $x$ and $y$

**Constraints:** $1\le n \le 2\cdot 10^5,\ 1 \le m \le 2\cdot 10^5$

## Solution
Let's ignore modification first. For query $1\ l_a\ r_a\ l_b\ r_b$, we iterate the value $v$ in $[l_b, r_b]$. We maintain a fenwick tree, for each $v$, find its position in $A$ and add this position by 1 in the fenwick tree. After all values are processed, the answer is the sum of $[l_a, r_a]$ in the fenwick tree. Notice that the answer of $[l_b, r_b]$ is equal to the answer of $[1, r_b]$ minus the answer of $[1, l_b-1]$, we can split this query into two sub-queries and reduce a dimension.

Now this question is converted to a **2-dimensional partial order** question. The first dimension is operation order, the second dimension is operation position. We can solve it by divide and conquer.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

struct Fenwick {
    using T = int;
    vector<T> V;
    Fenwick(int n): V(n) {}
    void add(size_t i, T x) { for (; i < V.size(); i |= i + 1) V[i] += x; }
    T sum(int i) { T r = T(); for (--i; i >= 0; i = (i & (i + 1)) - 1) r += V[i]; return r; }
    T sum(int l, int r) { return sum(r) - sum(l); }
};

const int N = 2e5 + 5;
struct Query { int p, x; } Q[N * 5];
int n, m, A[N], B[N], P[N], tq = 0, ta = 0, Ans[N], La[N], Ra[N];

int main() {
    scanf("%d%d", &n, &m);
    Fenwick fw(n + 1);
    FI(i, 1, n) scanf("%d", A + i), P[A[i]] = i;
    FI(i, 1, n) scanf("%d", B + i), Q[tq++] = {i, B[i]};
    FI(i, 1, m) {
        int t;
        scanf("%d", &t);
        if (t == 1) {
            int la, ra, lb, rb;
            scanf("%d%d%d%d", &la, &ra, &lb, &rb);
            Q[tq++] = {rb, N + (++ta)};
            Q[tq++] = {lb - 1, -N - ta};
            La[ta] = la, Ra[ta] = ra;
        } else {
            int x, y;
            scanf("%d%d", &x, &y);
            Q[tq++] = {x, -B[x]};
            Q[tq++] = {x, B[y]};
            Q[tq++] = {y, -B[y]};
            Q[tq++] = {y, B[x]};
            swap(B[x], B[y]);
        }
    }
    vector<int> I(tq);
    vector<char> L1(tq);
    iota(I.begin(), I.end(), 0);
    auto dac = [&](int l, int r, auto f) -> void {
        if (l + 1 >= r) return;
        int m = (l + r) >> 1;
        f(l, m, f), f(m, r, f);
        for (int i = l; i < r; i++) L1[I[i]] = i >= m;
        inplace_merge(&I[l], &I[m], &I[r], [&](int i, int j) { return Q[i].p < Q[j].p; });
        vector<PII> H;
        for (int i = l; i < r; i++) {
            int j = I[i];
            if (!L1[j] && abs(Q[j].x) <= N) {
                if (Q[j].x < 0) fw.add(P[-Q[j].x], -1), H.emplace_back(P[-Q[j].x], 1);
                else fw.add(P[Q[j].x], 1), H.emplace_back(P[Q[j].x], -1);
            }
            if (L1[j] && abs(Q[j].x) > N) {
                int idx = abs(Q[j].x) - N;
                if (Q[j].x < 0) Ans[idx] -= fw.sum(La[idx], Ra[idx] + 1);
                else Ans[idx] += fw.sum(La[idx], Ra[idx] + 1);
            }
        }
        for (auto p : H) fw.add(p.first, p.second);
    };
    dac(0, tq, dac);
    FI(i, 1, ta) printf("%d\n", Ans[i]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1093E. Intersection of Permutations (Divide and Conquer + Fenwick Tree)

コメント

コメントを投稿