LuoguP5046 [Ynoi2019模拟赛]Yuno loves sqrt technology I 题解

分享一个思路较简单但容易被卡空间的算法。
预处理以下几个东西:
1、 ansLi,j​ ,表示以 j 为左端点,第i块的右端点为右端点的区间中的逆序对数。
2、 ansRi,j​ ,表示以 j 为右端点,第i块的左端点为左端点的区间中的逆序对数。
3、 ansl,r​ ,表示以第 l 块的左端点为左端点,第 r 块的右端点为右端点的区间中的逆序对数。
那么对于每次询问我们只需要把1+2-3,就可以得到答案了。
——好像漏了啥。左散块对右散块的贡献没有统计。将所有块事先排好序,查询时归并一下即可。
如何预处理?
预处理出 cnti,j​ 为前 i 块大于/小于等于j的数字个数,prei​为位置i到i所在块左端点中大于/小于等于ai​的数字个数,即可做到O(1)移动端点。
关于第三个ansl,r​,不难发现在处理前两个值的时候已经顺便求出来了,不需要做更多处理。
查询时若l,r在同一个块中,简单容斥一下即可。这个部分其他题解已经说明得非常清楚了不再赘述。
总复杂度O(nsqrtn)。

#include <bits/stdc++.h>
#define bl(x) (((x)-1)/siz+1)
#define L(x) (((x)-1)*siz+1)
#define R(x) std::min(1ll*(x)*siz, 1ll*n)
using namespace std; typedef long long lint;
const int MAXN = 100050, MAXB = 205;
namespace fastIO {
    const int buffer_size = 1024 * 1024 * 40;
    char input[buffer_size], output[buffer_size];
    char *fin, *fout;
    inline void init() {
        fread(input, 1, buffer_size, stdin);
        fin = input; fout = output;
    }
    inline void flush() {
        fwrite(output, 1, fout - output, stdout);
        fflush(stdout);
    }
    inline int read(int u = 0, char c = *fin++, bool f = false) {
        for (;!isdigit(c); c = *fin++) f |= c == '-';
        for (; isdigit(c); c = *fin++) u = u * 10 + c - '0';
        return f ? -u : u;
    }
    inline void read(char *s, char c = *fin++) {
        for (;!isspace(c); c = *fin++);
        for (; isspace(c); c = *fin++) *s++ = c;
        *s = '\0';
    }
    inline void print(lint u) {
        u < 0 ? 
            *fout++ = '-', print(-u) :
            void(u > 9 ?
                print(u / 10), *fout++ = u % 10 + '0' :
                *fout++ = u + '0');
    }
    inline void print(char *s) { while (*s) *fout++ = *s++; }
    inline void print(char c) { *fout++ = c; }
}
using fastIO::read; using fastIO::print;
int P[MAXN], cx, cy, x[MAXN], y[MAXN], c[MAXN], d[MAXN], n, m, a[MAXN], siz, cnt[MAXN], pre[MAXN], suf[MAXN], c1[MAXB][MAXN], c2[MAXB][MAXN]; 
struct BT {int id, c;} b[MAXN]; lint ansR[MAXB][MAXN], ansL[MAXB][MAXN];
int cmp(BT p, BT q) {return p.c < q.c;}
struct BITS1 {
    int t[MAXN];
    void update(int x, int k) {for(; x <= n; t[x] += k, x += x&-x);}
    int query(int x) {int res = 0; for(; x > 0; res += t[x], x -= x&-x); return res;}
} T1;
struct BITS2 {
    int t[MAXN];
    void update(int x, int k) {for(; x > 0; t[x] += k, x -= x&-x);}
    int query(int x) {int res = 0; for(; x <= n; res += t[x], x += x&-x); return res;}
} T2;
int merg(int *p, int *q, int lp, int lq) {
    int i = 1, j = 1, res = 0;
    while(i <= lp && j <= lq)
        if(p[i] < q[j]) ++i; else res += lp - i + 1, ++j;
    return res;
}
int main() {
    fastIO::init();
    n = read(); m = read(); siz = 500;
    for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = (BT) {i, a[i]};
    for(int i = 1; i <= bl(n); ++i) {
        sort(b+L(i), b+R(i)+1, cmp);
        for(int j = L(i); j <= R(i); ++j) d[j] = b[j].id, c[j] = b[j].c;
        for(int j = L(i); j <= R(i); ++j) pre[j] = T2.query(a[j]), T2.update(a[j], 1);
        for(int j = L(i); j <= R(i); ++j) T2.update(a[j], -1);
        for(int j = R(i); j >= L(i); --j) suf[j] = T1.query(a[j]), T1.update(a[j], 1);
        for(int j = R(i); j >= L(i); --j) T1.update(a[j], -1); P[L(i)] = pre[L(i)];
        for(int j = L(i)+1; j <= R(i); ++j) P[j] = P[j-1] + pre[j];
    }
    for(int k = 1, i = 1; i <= n; ++i) {
        ++cnt[a[i]];
        if(i == R(k)) {
            for(int j = 1; j <= n; ++j)
                c1[k][j] = c1[k][j-1] + cnt[j];
            for(int j = n; j >= 1; --j)
                c2[k][j] = c2[k][j+1] + cnt[j];
            ++k;
        }
    }
    for(int i = 1; i <= bl(n); ++i)
        for(int j = L(i); j <= n; ++j)
            ansR[i][j] = ansR[i][j-1] + (c2[bl(j)-1][a[j]+1] - c2[i-1][a[j]+1]) + pre[j];
    for(int i = 1; i <= bl(n); ++i)
        for(int j = R(i); j >= 1;  --j)
            ansL[i][j] = ansL[i][j+1] + (c1[i][a[j]-1] - c1[bl(j)][a[j]-1]) + suf[j];
    lint ans = 0;
    for(int l, r; m--; ) {
        l = read(); r = read(); l ^= ans; r ^= ans;
        if(l > r) swap(l, r); ans = 0; cx = cy = 0;
        if(bl(l) == bl(r)) {
            for(int i = L(bl(l)); i <= R(bl(l)); ++i)
                if(l <= d[i] && d[i] <= r) y[++cy] = c[i];
                else if(d[i] < l) x[++cx] = c[i];
            ans = P[r] - ((l == L(bl(l))) ? 0 : (P[l-1])) - merg(x, y, cx, cy);
            print(ans); print('\n');
        } else {
            ans = ansL[bl(r)-1][l] + ansR[bl(l)+1][r] - ansL[bl(r)-1][L(bl(l)+1)];
            for(int i = L(bl(l)); i <= R(bl(l)); ++i) if(d[i] >= l) x[++cx] = c[i];
            for(int i = L(bl(r)); i <= R(bl(r)); ++i) if(d[i] <= r) y[++cy] = c[i];
            ans += merg(x, y, cx, cy);
            print(ans); print('\n');
        }
    } fastIO::flush();
}

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

正在获取,请稍候...
00:00/00:00