bzoj3956: Count (单调栈+st表)

题面链接

bzoj

题解

非常巧妙的一道题

类似[hnoi影魔]

每个点会给左右第一个大于它的点对产生贡献

可以用单调栈求出

这里有点小细节,就是处理相等的点时,最左边的点管左边的贡献,最右边的点管最右边的贡献

然后对于每个点,求出了一对\(x, y\)

那么,对于询问区间\(l,r\)

答案就是有多少个\(x,y\)在区间\(l,r\)之间, 即\(l<=x<=r\) && \(l<=y<=r\)

再加上相邻的点对

这就可以用二维数点做

但是有没有更优秀的做法呢?

我们设\(a[pos]\)为区间\([l,r]\)之间最大的数

那么\(x\)在\([l,pos-1]\)之间的点对,\(y\)一定不会越过\(pos\)

那么只要求出\([l,pos-1]\)之间有多少\(x\),就可以求出有多少点对\((x,y)\)在\([l,pos-1]\)

同理另一半也可以求出

那么,前缀和就可以解决问题了

Code

#include<bits/stdc++.h>

#define LL long long
#define RG register

using namespace std;
template<class T> inline void read(T &x) {
    x = 0; RG char c = getchar(); bool f = 0;
    while (c != '-' && (c < '0' || c > '9')) c = getchar(); if (c == '-') c = getchar(), f = 1;
    while (c >= '0' && c <= '9') x = x*10+c-48, c = getchar();
    x = f ? -x : x;
    return ;
}
template<class T> inline void write(T x) {
    if (!x) {putchar(48);return ;}
    if (x < 0) x = -x, putchar('-');
    int len = -1, z[20]; while (x > 0) z[++len] = x%10, x /= 10;
    for (RG int i = len; i >= 0; i--) putchar(z[i]+48);return ;
}
const int N = 300010;
int n, m, a[N];
int f[21][N], g[21][N];
int query(int l, int r) {
    int k = log2(r - l + 1);
    if (f[k][l] >= f[k][r - (1 << k) + 1]) return g[k][l];
    return g[k][r - (1 << k) + 1];
}
int L[N], R[N];
int suml[N], sumr[N];
int q[N];
int main() {
    int type;
    read(n), read(m), read(type);
    for (int i = 1; i <= n; i++) read(a[i]), f[0][i] = a[i], g[0][i] = i;
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            if (f[j - 1][i] >= f[j - 1][i + (1 << (j - 1))]) {
                f[j][i] = f[j - 1][i];
                g[j][i] = g[j - 1][i];
            }
            else {
                f[j][i] = f[j - 1][i + (1 << (j - 1))];
                g[j][i] = g[j - 1][i + (1 << (j - 1))];
            }
    int top = 0;
    for (int i = 1; i <= n; i++) {
        while (top && a[q[top]] < a[i]) top--;
        if (top && a[i] != a[q[top]]) L[i] = q[top];
        q[++top] = i;
    }
    top = 0;
    for (int i = n; i; i--) {
        while (top && a[q[top]] < a[i]) top--;
        if (top && a[i] != a[q[top]]) R[i] = q[top];
        q[++top] = i;
    }
    
    /*for (int i = 1; i <= n; i++)
        printf("%d %d\n", L[i], R[i]);*/
    
    for (int i = 1; i <= n; i++)
        suml[L[i]]++, sumr[R[i]]++;
    for (int i = 1; i <= n; i++)
        suml[i] += suml[i - 1], sumr[i] += sumr[i - 1];
    int lastans = 0;
    while (m--) {
        int x, y, l, r;
        read(x), read(y);
        if (type) l = (x + lastans - 1) % n + 1, r = (y + lastans - 1) % n + 1;
        else l = x, r = y;
        if (l > r) swap(l, r);
        int pos = query(l, r);
        lastans = suml[pos - 1] - suml[l - 1] + sumr[r] - sumr[pos] + r - l;
        printf("%d\n", lastans);
    }
    return 0;
}

bzoj3956: Count (单调栈+st表)

原文：https://www.cnblogs.com/zzy2005/p/10597038.html