2018宁夏邀请赛L Continuous Intervals

题目链接：https://nanti.jisuanke.com/t/28412

题意：

　　给出n个数的序列。问序列中有多少个区间满足，排序完之后任意两个相邻的数之差不大于1。

题解：

　　用max表示区间最大值，min表示区间最小值，cnt表示区间数字的种数。那么问题转化成求max-min=cnt+1的区间数。

　　用线段树维护每个区间的max-min-cnt最小值及最小值的个数，不用单独维护max，min和cnt。注意max-min >= cnt+1.

　　从1~n枚举R。对于每个枚举的R，更新以R为后缀的[L,R]区间的max-min-cnt值。

　　对于max和min可以用单调栈维护，max和min对max-min-cnt的贡献采用区间加减的形式而不是区间覆盖。

　　对于cnt可以用一个vis[]数组维护上一次的出现位置，然后也进行区间加减。数据是1e9的，vis[]数组可以离散一下或者用map代替。

　　最后对于每一个枚举的R，统计max-min-cnt的值为-1的[L,R]数。

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+;

typedef long long ll;

int t, n, k;

int nx, nn;

int lzy[N*], sum[N*], val[N*];

ll ans;

map<int, int> m;

struct node {

    int p, w;

    node() {}

    node(int a, int b) {

        p = a; w = b;

    }

}mx[N], mn[N];

void push_up(int id) {

    val[id] = min(val[id<<], val[id<<|]);

    if(val[id<<] == val[id<<|]) sum[id] = sum[id<<]+sum[id<<|];

    else if(val[id<<] < val[id<<|]) sum[id] = sum[id<<];

    else sum[id] = sum[id<<|];

}

void push_down(int id) {

    lzy[id<<] += lzy[id];

    lzy[id<<|] += lzy[id];

    val[id<<] += lzy[id];

    val[id<<|] += lzy[id];

    lzy[id] = ;

}

void insert(int id, int l, int r, int p) {

    if(l == r) {

        val[id] = -;

        sum[id] = ;

        return ;

    }

    if(lzy[id]) push_down(id);

    int mid = l+r>>;

    if(p<=mid) insert(id<<, l, mid, p);

    else insert(id<<|, mid+, r, p);

    push_up(id);

}

void update(int id, int l, int r, int ql, int qr, int v) {

    if(ql<=l && r<=qr) {

        lzy[id] += v;

        val[id] += v;

        return ;

    }

    if(lzy[id]) push_down(id);

    int mid = l+r>>;

    if(ql<=mid) update(id<<, l, mid, ql, qr, v);

    if(qr>mid) update(id<<|, mid+, r, ql, qr, v);

    push_up(id);

}

int main() {

    scanf("%d", &t);

    for(int casee = ; casee <= t; casee++) {

        ans = nx = nn = ;

        m.clear();

        scanf("%d", &n);

        memset(lzy, , sizeof(int)*(*n+));

        memset(sum, , sizeof(int)*(*n+));

        memset(val, 0x3f3f3f3f, sizeof(int)*(*n+));

        for(int i = ; i <= n; i++) {

            scanf("%d", &k);

            insert(, , n, i);

            int p = i, v;

            while(nx >  && mx[nx].w <= k) {

                p = mx[nx].p, v = k-mx[nx].w;

                nx--;

                update(, , n, mx[nx].p+, p, v);

            }

            mx[++nx] = node(i, k);

            p = i;

            while(nn >  && mn[nn].w >= k) {

                p = mn[nn].p, v = k-mn[nn].w;

                nn--;

                update(, , n, mn[nn].p+, p, -v);

            }

            mn[++nn] = node(i, k);

            int l;

            if(m.find(k) != m.end()) l = m[k]+;

            else l = ;

            if(l <= i-) update(, , n, l, i-, -);

            m[k] = i;

            ans += sum[];

        }

        printf("Case #%d: %lld\n", casee, ans);

    }

}

巴特西

2018宁夏邀请赛L Continuous Intervals

最新文章

热门文章