P8251-题解

Galex · 2022-03-26 13:49:18 · 题解

惊险的提交记录。 卡到了 993 毫秒。。。

进入正题

先看题目，经典静态查询问题，用普通莫队就行啦。

对于每个位置 i 记录一个值 pre_i，表示这个二元组 (a_i,b_i) 在 pre_i + 1 到 i 的位置是成功的。这个可以一开始用单调栈预处理出来。

然后就是莫队的事情了，我们要找的相当于就是 p_l 到 p_r 中有多少个数是比 l 小的。所以在转移过程中记录一下插入和删除的位置的数量就行了。

最后查询的时候，把值域分块即可，这样可以保证复杂度是 O(n \times \sqrt n) 的。

最后莫队排序的时候记得用奇偶玄学优化。

#include <bits/stdc++.h>
#define int long long
using namespace std;

int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9')
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * f;
}

int n, Q;
int a[500005], b[500005], p[500005];
int s[500005], top = 0;
int bl[500005];
struct qry{
    int l, r, id;
    friend bool operator < (const qry &x, const qry &y) {
        if (bl[x.l] != bl[y.l])
            return bl[x.l] < bl[y.l];
        if (bl[x.l] % 2 == 0)
            return x.r > y.r;
        return x.r < y.r;
    }
}q[500005];
int ans[500005], c[500005];
int head = 1, tail = 0;

int l[1005], r[1005], sum[1005], pos[500005];

void buildblock(){
    int k = sqrt(n);
    for (int i = 1; i <= k; i++)
        l[i] = r[i - 1] + 1, r[i] = r[i - 1] + k;
    if (r[k] < n)
        l[k + 1] = r[k] + 1, r[k + 1] = n, k++;
    for (int i = 1; i <= k; i++)
        for (int j = l[i]; j <= r[i]; j++)
            pos[j] = i;
}

int query(int p){
    int P = 0, ans = 0;
    for (int i = 1; i < pos[p]; i++)
        ans += sum[i];
    for (int i = l[pos[p]]; i <= p; i++)
        ans += c[i];
    return ans;
}

void mdf(int x, int v){
    c[p[x]] += v;
    sum[pos[p[x]]] += v;
}

signed main() {
    n = read(), Q = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    for (int i = 1; i <= n; i++)
        b[i] = read();
    for (int i = 1; i <= n; i++){
        while (top > 0 && !(a[i] != a[s[top]] && b[i] < b[s[top]]))
            top--;
        p[i] = s[top] + 1;
        s[++top] = i;
    }
    buildblock();
    int t = sqrt(n);
    for (int i = 1; i <= n; i++)
        bl[i] = (i - 1) / t + 1;
    for (int i = 1; i <= Q; i++)
        q[i].l = read(), q[i].r = read(), q[i].id = i;
    sort(q + 1, q + Q + 1);
    for (int i = 1; i <= Q; i++){
        while (tail < q[i].r)
            mdf(++tail, 1);
        while (tail > q[i].r)
            mdf(tail--, -1);
        while (head < q[i].l)
            mdf(head++, -1);
        while (head > q[i].l)
            mdf(--head, 1);
        ans[q[i].id] = query(q[i].l);
    }
    for (int i = 1; i <= Q; i++)
        printf("%d\n", ans[i]);
    return 0;
}