HDU5200 – Trees(线段树+离线)

题目链接:HDU5200

【分析】这题也很水,但是,但是,被A卡住了,结果就差那么几分钟就写完了,比完赛再交就1A了,不想说了。

就是线段树维护有多少个连续区间块,然后按照查询高度排序为了离线,以及把所有树的也按高度排序,这样就可以枚举查询的高度的时候枚举到<=当前查询的高度的树,这样总的复杂度是O(nlogn)的。

【AC CODE】639ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#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 = 50000+10;
struct NODE{
    int h,pos;
    bool operator<(const NODE&t) const{
        return h < t.h;
    }
}p[MAXN];
struct Q{
    int qh, id;
    bool operator<(const Q&t) const{
        return qh < t.qh;
    }
}q[MAXN];
bool cov[MAXN];
int ans[MAXN];
int sum[MAXN<<1];

inline int id(int x, int y){
    return x+y|x!=y;
}
void push_up(int x, int y, int m)
{
    int u = id(x,y), l = id(x,m), r = id(m+1,y);
    sum[u] = sum[l]+sum[r];
    if(cov[m] && cov[m+1]) sum[u]--;
}
void bulid(int x, int y)
{
    if(x == y)
    {
        sum[id(x,y)] = 1;
        cov[x] = 1;
        return;
    }
    int m = (x+y)>>1;
    bulid(x,m);
    bulid(m+1,y);
    push_up(x,y,m);
}
void del(int x, int y, int p)
{
    if(x == y)
    {
        cov[x] = 0;
        sum[id(x,y)] = 0;
        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 n,m;
void sloved()
{
    int pn = 0;
    bulid(0,n-1);
    rep(i,0,m)
    {
        while(p[pn].h <= q[i].qh)
        {
            del(0,n-1,p[pn].pos);
            pn++;
        }
        ans[q[i].id] = sum[id(0,n-1)];
    }
}
int main()
{
#ifdef SHY
    freopen("d:\\1.txt", "r", stdin);
#endif
    while(~scanf("%d %d%*c", &n, &m))
    {
        rep(i,0,n)
        {
            scanf("%d%*c", &p[i].h);
            p[i].pos = i;
        }
        sort(p,p+n);
        rep(i,0,m)
        {
            scanf("%d%*c", &q[i].qh);
            q[i].id = i;
        }
        sort(q,q+m);
        sloved();
        rep(i,0,m)
            printf("%d\n", ans[i]);
    }
    return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码