洛谷5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

2021-01-18

Solution

1225 Words

提供一种理论复杂度正确($O(n\sqrt n)$)的做法

我们维护以下几个东西:

pre[i]：$i$到它的块首这段序列的逆序对数量

suf[i]：$i$到它的块尾这段序列的逆序对数量

cnt[i][j]：前$i$个块中小于$j$的数的个数

f[i][j]：第$i$个块到第$j$块的逆序对个数

v[i] 第$i$个块中数从小到大排序的结果

pre和suf可以用树状数组在$O(n \log n)$时间内求出

cnt可以用两次前缀和在$O(n \sqrt n)$时间内求出

f可以用以下方法求出:
$f_{i,j}=f_{i+1,j}+f_{i,j+1}-f_{i+1,j-1}+(i,j)$这两块之间产生的贡献

由于我们已经维护好了v，于是我们可以用归并排序在$O(\sqrt n)$时间内求出$(i,j)$这两块之间产生的贡献,总复杂度$O(n \sqrt n)$

（下面用$[l,r] \times [L,R]$表示$[l,r]$与$[L,R]$产生的贡献）

接下来我们考虑询问，设询问区间为$[l,r]$，我们分三种情况考虑：

1.$[l,r]$在一个块内

设$R$表示$l,r$块的块尾

由于我们已经维护好了pre，于是答案可以表示成$pre[l]-pre[r+1]-[l,r] \times [r+1,R]$

2.$[l,r]$在相邻两个块内

设$R$表示$l$块的块尾,$L$表示$r$块的块首

那么答案可以表示成$pre[l] + suf[r] + [l,R] \times [L, r]$

3.$[l,r]$横跨至少$3$个块

设$R$表示$l$块的块尾,$L$表示$r$块的块首

那么[l,r]的贡献可以拆分成$[l,R],[R+1,L-1],[L,r]$三个块两两之间的贡献，由于$[R+1,L-1]$是整块，于是我们的贡献就非常好求，它等于

$pre[l]+suf[r]+f[id(R+1)][id(L-1)]+[l,R]\times[R+1,L-1]+[R+1,L-1]\times[L,r]+[l,R]\times[L,r]$

其中$id(i)$表示$i$所属的块编号

于是主体部分就写完了，有没人教教怎么卡常啊/kel

#include <bits/stdc++.h>
#include<sys/mman.h>

#define ll long long
#define pair std::pair<int, int>
#define mp(i, j) std::make_pair(i, j)
#define getl(i) ((i - 1) * siz + 1)
#define getr(i) (std::min(n, i * siz))
#define id(x) (((x - 1) / siz) + 1)
#define meow(cat...) fprintf(stderr, cat)

const int MaxB = 7e2 + 10;
const int MaxN = 1e5 + 10;

pair v[MaxB][MaxB];
ll ans, f[MaxB][MaxB];
int len[MaxB], pre[MaxN], cnt[MaxB][MaxN], suf[MaxN];
int n, m, siz, num, a[MaxN], Id[MaxN], bl[MaxN], br[MaxN];

struct BIT
{
    int c[MaxN];
    int lowbit(int x)
    {
        return x & (-x);
    }
    void add(int x, int val)
    {
        while (x <= n)
            c[x] += val, x += lowbit(x);
    }
    int query(int x)
    {
        int ret = 0;
        while (x)
            ret += c[x], x -= lowbit(x);
        return ret;
    }
} T;

const int size = 1 << 22;
char out[size], *p3 = out - 1;
#define pc(x) *++p3=x
void print(ll x)
{
    if(x > 9)print(x / 10);
    pc(x % 10 + 48);
}

char *s;
inline int read()
{
    register int u = 0;
    while(*s < 48) s++;
    while(*s > 32)
        u = u * 10 + *s++ -48;
    return u;
}

int ta[MaxB], tb[MaxB];

ll query(int l1, int r1, int l2, int r2)
{
    int lena = 0, lenb = 0;
    int L = Id[l1], R = Id[l2];
    for (int i = 1; i <= len[L]; i++)
    {
        pair x = v[L][i];
        if (x.second >= l1 && x.second <= r1)
            ta[++lena] = x.first;
    }
    for (int i = 1; i <= len[R]; i++)
    {
        pair x = v[R][i];
        if (x.second >= l2 && x.second <= r2)
            tb[++lenb] = x.first;
    }
    ll ans = 0;
    int A = 1, B = 1;
    while (A <= lena && B <= lenb)
    {
        if (A <= lena)
        {
            if (ta[A] < tb[B] || B > lenb)
                ++A;
            else
                ++B, ans += lena - A + 1;
        }
        else
            ++B;
    }
    return ans;
};

signed main()
{
    // freopen("sqrt.in", "r", stdin);
    // freopen("sqrt.out", "w", stdout);
    s = (char*)mmap(0, 900 << 20, PROT_READ, MAP_PRIVATE, fileno(stdin), 0);
    n = read(), m = read();
    siz = 160, num = id(n);
    for (int i = 1; i <= n; i++)
        a[i] = read(), Id[i] = id(i);
    for (int i = 1; i <= num; i++)
    {
        bl[i] = getl(i), br[i] = getr(i);
        len[i] = br[i] - bl[i] + 1;
    }
    for (int i = 1; i <= n; i++)
        v[Id[i]][i - bl[Id[i]] + 1] = mp(a[i], i);
    for (int i = 1; i <= num; i++)
        std::sort(v[i] + 1, v[i] + len[i] + 1);
    for (int i = 1; i <= num; i++)
    {
        int l = bl[i], r = br[i];
        for (int j = l; j <= r; ++j)
            cnt[i][a[j]]++;
        for (int j = 1; j <= n; ++j)
            cnt[i][j] += cnt[i - 1][j];
    }
    for (int i = 1; i <= num; i++)
        for (int j = 1; j <= n; ++j)
            cnt[i][j] += cnt[i][j - 1];
    for (int i = 1; i <= num; i++)
    {
        int l = bl[i], r = br[i], x = 0, y;
        for (int j = l; j <= r; ++j)
        {
            y = T.query(n) - T.query(a[j]);
            x += y, pre[j] = x, T.add(a[j], 1);
        }
        f[i][i] = x;
        for (int j = l; j <= r; ++j)
        {
            y = T.query(a[j] - 1), suf[j] = x;
            x -= y, T.add(a[j], -1);
        }
    }
    // for(ll i = 1; i <= n; i++)
    //     meow("%d %d %d\n", i, pre[i], suf[i]);
    for (int len = 1; len < num; len++)
    {
        int x = num - len + 1;
        for (int i = 1; i <= x; i++)
        {
            int j = i + len;
            f[i][j] = f[i + 1][j] + f[i][j - 1];
            if (i + 1 <= j - 1) f[i][j] -= f[i + 1][j - 1];
            f[i][j] += query(bl[i], br[i], bl[j], br[j]);
        }
    }
    // meow("xzakioi!\n");
    for (int i = 1; i <= m; i++)
    {
        ll now = 0;
        int l = read() ^ ans, r = read() ^ ans;
        int L = Id[l], R = Id[r], Ll, rr, LL, RR;
        if (L == R)
        {
            rr = br[R];
            if (r == rr)
                now = suf[l];
            else
            {
                now = suf[l] - suf[r + 1];
                now -= query(l, r, r + 1, rr);
            }
        }
        else if (R == L + 1)
        {
            Ll = bl[R], rr = br[L];
            now = suf[l] + pre[r];
            now += query(l, rr, Ll, r);
        }
        else
        {

            LL = bl[R], RR = br[L], rr = br[R - 1];
            now = suf[l] + f[L + 1][R - 1];
            now += query(l, RR, LL, r) + pre[r];
            for (int i = l; i <= RR; i++)
                now += cnt[R - 1][a[i]] - cnt[L][a[i]];
            for (int i = LL; i <= r; i++)
            {
                now += cnt[R - 1][n] - cnt[R - 1][a[i]];
                now -= cnt[L][n] - cnt[L][a[i]];
            }
        }
        ans = now, print(ans), pc('\n');
    }
    meow("used %d ms\n", clock());
    fwrite(out, 1, p3 - out + 1, stdout);
    return 0;
}

Ynoi, 分块

洛谷5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I

分类

Your browser is out-of-date!