HDU 5289 Assignment

题意：求一段长度为n的序列里有多少个子区间内的最大值减最小值小于k。

解法：RMQ+尺取法或单调队列。RMQ可以用st或者线段树，尺取法以前貌似YY出来过……只是不知道是这个东西……

设两个标记l和r，对于区间[l, r]如果满足题中条件则ans+=(r - l + 1)，然后r右移一位，直到不符合条件，将l左移，直到符合条件。

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

#define lson l, m, rt << 1

#define rson m + 1, r, rt << 1 | 1

using namespace std;

int MIN[100005 << 2], MAX[100005 << 2];

int a[100005];

void pushupMIN(int rt)

{

    MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]);

}

void pushupMAX(int rt)

{

    MAX[rt] = max(MAX[rt << 1], MAX[rt << 1 | 1]);

}

void build(int l, int r, int rt)

{

    if(l == r)

    {

        scanf("%d", &a[l]);

        MIN[rt] = MAX[rt] = a[l];

        return;

    }

    int m = (l + r) >> 1;

    build(lson);

    build(rson);

    pushupMIN(rt);

    pushupMAX(rt);

}

int getMIN(int ll, int rr, int l, int r, int rt)

{

    if(ll <= l && rr >= r)

        return MIN[rt];

    int res = INT_MAX;

    int m = (l + r) >> 1;

    if(ll <= m) res = min(res, getMIN(ll, rr, lson));

    if(rr > m) res = min(res, getMIN(ll, rr, rson));

    return res;

}

int getMAX(int ll, int rr, int l, int r, int rt)

{

    if(ll <= l && rr >= r)

        return MAX[rt];

    int res = 0;

    int m = (l + r) >> 1;

    if(ll <= m) res = max(res, getMAX(ll, rr, lson));

    if(rr > m) res = max(res, getMAX(ll, rr, rson));

    return res;

}

int main()

{

    int T;

    while(~scanf("%d", &T))

    {

        int n, k;

        while(T--)

        {

            scanf("%d%d", &n, &k);

            build(1, n, 1);

            int flag = 0;

            int l = 1, r = 0;

            LL ans = 0;

            while(r <= n)

            {

                if(r == n || flag)

                {

                    l++;

                    int tmp1 = getMIN(l, r, 1, n, 1);

                    int tmp2 = getMAX(l, r, 1, n, 1);

                    if(tmp2 - tmp1 < k)

                    {

                        ans += r - l + 1;

                        flag = 0;

                        if(r == n)

                            break;

                    }

                }

                else

                {

                    r++;

                    int tmp1 = getMIN(l, r, 1, n, 1);

                    int tmp2 = getMAX(l, r, 1, n, 1);

                    if(tmp2 - tmp1 < k)

                    {

                        ans += r - l + 1;

                        if(r == n)

                            break;

                    }

                    else

                        flag = 1;

                }

            }

            printf("%lld\n", ans);

        }

    }

    return 0;

}

巴特西

HDU 5289 Assignment

最新文章

热门文章