CF785E （动态逆序对）

题意描述

对长度为\(n\)的排列进行\(k\)次操作，每次操作交换两个数字，求每次交换以后，整个序列的逆序对数量

思路

\(1.\) 分块
对于查询和修改，我们可以直接在块内暴力解决。
观察发现，如果交换\(a[l]\)和\(a[r]\)，则对\([l + 1, r - 1]\)区间内有影响的数的值域在\([a[l],a[r]]\)之间。
因为上面的性质，对于整块我们要快速找到值域在\([a[l],a[r]]\)的数，所以对于每个块我们可以维护一个有序的vector，这样查询操作就可以快速解决。
对于修改来说，我们直接在对应的块内暴力修改，修改完后一定要对vector排序
对于查询来说，非整块可以直接暴力找值域在\([a[l],a[r]]\)范围内的数，整块的话，可以二分找到\(a[l]\)和\(a[r]\)，再相减即可（可以用\(lower\_bound\)和\(upper\_bound\)，由于是闭区间，所以对于右端点必须使用\(upper\_bound\)，但是本题中是排列，所以无影响），记\([a[l],a[r]]\)的数量为\(cnt\)，则总贡献为\((2*cnt)+1\)，如果\(a[l] > a[r]\)则此时的交换操作会导致逆序对减少，特判即可。
总复杂度为\(O(q\sqrt{n}logn)\)
\(2.\) 树套树

待补

代码

#include 

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

using ll = long long;
using pii = std::pair;

const int MOD = 1e9 + 7;
const int N = 2 * 1e5 + 5;
const int INF = 0x3f3f3f3f;

int a[N], n, k, block;
std::vector g[N];

void init()
{
    block = sqrt(n + 0.5);
    for(int i = 1; i <= n; ++i)
    {
        a[i] = i;
        g[i / block].push_back(a[i]);
    }
}

ll query(int l, int r)
{
    int idl = l / block, idr = r / block;
    int x = a[l], y = a[r];
    int k = std::lower_bound(g[idl].begin(), g[idl].end(), x) - g[idl].begin();
    g[idl][k] = y;
    std::sort(g[idl].begin(), g[idl].end());
    k = std::lower_bound(g[idr].begin(), g[idr].end(), y) - g[idr].begin();
    g[idr][k] = x;
    std::sort(g[idr].begin(), g[idr].end());
    ll ans = 0, f;
    // 特判符号位
    if(x > y) f = -1, std::swap(x, y);
    else f = 1;

    if(idl == idr)
    {
        for(int i = l; i <= r; ++i)
        {
            if(x < a[i] && a[i] < y) ++ans;
        }
    }
    else
    {
        int i = l, j = r;
        while(i / block == l / block)
        {
            if(x < a[i] && a[i] < y)
            {
                ++ans;
            }
            ++i;
        }
        while(j / block == r / block)
        {
            if(x < a[j] && a[j] < y)
            {
                ++ans;
            }
            --j;
        }
        for(int k = i / block; k <= j / block; ++k)
        {
            ans += std::upper_bound(g[k].begin(), g[k].end(), y) - std::lower_bound(g[k].begin(), g[k].end(), x);
        }
    }
    std::swap(a[l], a[r]);
    return f * (2 * ans + 1);
}

void solve()
{
    std::cin >> n >> k;
    init();
    ll ans = 0;
    while(k--)
    {
        int l, r;
        std::cin >> l >> r;
        if(l > r) std::swap(l, r);
        if(l != r) ans += query(l, r);
        std::cout << ans << '\n';
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cout << std::fixed << std::setprecision(8);
    int T = 1;
    // std::cin >> T;
    while(T--) solve();
}