HDU5289 – Assignment(线段树上二分 || 单调队列)

传送门：HDU5289

【题意】给出一个N(<=10^5)长的序列，每个组定义为：1个或多个连续编号的数字最大最小值之差<k；问总共有多少个这样的组。

【分析】不难发现，对于每个数字对答案的影响其实就是他所能达到的最右边的端点的长度，每个每个端点找出他的右端点即可，注意会超过int，我使用了在线段树上二分复杂度n*logn。或者可以用单调队列维护实现O(n)复杂度。两个单调队列维护最值，另外再用一个指针指向左端点，当最值>=k时左端点+1，这是的i就是左端点最右能到达的值的右边一个，并把左边‘过期’的最值都删了，最后没有加到的左端点都是可以到达最右边的。

【AC CODE(线段树)】452ms(加上输入挂280ms)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int a[MAXN];

inline int id(int x, int y){return x+y|x!=y;}
int mx[MAXN<<1],mi[MAXN<<1];
void push_up(int x, int y, int m)
{
    int u = id(x,y),l = id(x,m),r = id(m+1,y);
    if(-1 == mx[l]) mx[u] = mx[r], mi[u] = mi[r];
    else if(-1 == mx[r]) mx[u] = mx[l],mi[u] = mi[l];
    else mx[u] = max(mx[l],mx[r]), mi[u] = min(mi[l],mi[r]);
}
void bulid(int x, int y)
{
    if(x == y)
    {
        mx[id(x,y)] = mi[id(x,y)] = a[x];
        return;
    }
    int m = (x+y)>>1;
    bulid(x,m);
    bulid(m+1,y);
    push_up(x,y,m);
}
int k;
int query(int x, int y, int mxx, int mii)
{
    if(x == y)
    {
        mxx = max(mxx,mx[id(x,y)]);
        mii = min(mii,mi[id(x,y)]);
        return x+(bool)(mxx-mii < k);
    }
    int m = (x+y)>>1;
    int tmx = max(mxx,mx[id(x,m)]), tmi = -1 == mi[id(x,m)]?mii:min(mi[id(x,m)],mii);
    if(tmx-tmi >= k) return query(x,m,mxx,mii);
    return query(m+1,y,tmx,tmi);
}
void del(int x, int y, int p)
{
    if(x == y)
    {
        mx[id(x,y)] = mi[id(x,y)] = -1;
        return;
    }
    int m = (x+y)>>1;
    if(p <= m) del(x,m,p);
    else del(m+1,y,p);
    push_up(x,y,m);
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d %d", &n, &k);
        repe(i,1,n) scanf("%d", &a[i]);
        bulid(1,n);
        LL ans = 0;
        repe(i,1,n)
        {
            int r = query(1,n,-INF,INF);
            ans += r-i;
            del(1,n,i);
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

【AC CODE(单调队列)】343ms(加上输入挂可以达到46ms)

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100000+10;
int a[MAXN];
deque<int> qmx,qmi;

int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n,k;
        scanf("%d %d", &n, &k);
        repe(i,1,n) scanf("%d", &a[i]);
        qmx.clear();qmi.clear();
        int p = 1;
        LL ans = 0;
        repe(i,1,n)
        {
            while(!qmx.empty() && qmx.front() < a[i]) qmx.pop_front();
            qmx.push_front(a[i]);
            while(!qmi.empty() && qmi.front() > a[i]) qmi.pop_front();
            qmi.push_front(a[i]);
            while(!qmx.empty() && !qmi.empty() && qmx.back()-qmi.back() >= k)
            {
                ans += (i-p);
                if(qmx.back() == a[p]) qmx.pop_back();
                if(qmi.back() == a[p]) qmi.pop_back();
                p++;
            }
        }
        while(p <= n)
        {
            ans += n+1-p;
            p++;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}