J - Super Mario HDU - 4417 线段树离线处理区间排序

J - Super Mario HDU - 4417

这个题目我开始直接暴力，然后就超时了，不知道该怎么做，直接看了题解，这个习惯其实不太好。

不过网上的思路真的很厉害，看完之后有点伤心，感觉自己应该可以写的，但是没有写出来。

因为我们要查找一个区间小于等于c的数有多少个，这种区间处理可以用线段树很好的解决，

但是怎么解决呢，我习惯性的直接建树，然后再想怎么做，其实这样不对，

线段树对于我们来说是一个解决问题的工具，不要本末倒置了。

我们想查找一个区间小于等于c的数的个数，用线段树查询很简单，但是怎么建树才可以

让我们每次查询都得到想要的结果呢，这个肯定是不能直接把这个墙的高度直接建树的，应该要先处理一下。

我们可以把查询的高度按升序排序，这样线段树之前更新过的值就不会影响后面的值了。

但是线段树怎么更新呢，这个也可以按升序对墙排个序，这样就解决问题了。

这个思路其实没有特别难想。。。

代码很好敲，但是要注意不要漏掉了，也许都已经更新完了，但是这个答案没有在for循环里面找到。

这个要注意！！！

然后这个题目还可以用主席树写

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <vector>

#include <algorithm>

#include <iostream>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

typedef long long ll;

const int maxn = 2e5+;

ll sum[maxn*], ans[maxn];

int n, m;

struct node

{

    ll num, id;

}a[maxn];

struct edge

{

    ll l, r, h, id;

    edge(ll l=,ll r=,ll h=,ll id=):l(l),r(r),h(h),id(id){}

}ex[maxn];

bool cmp(node a,node b)

{

    return a.num < b.num;

}

bool cmp1(edge a,edge b)

{

    return a.h < b.h;

}

void update(int id,int l,int r,int pos)

{

    if(l==r)

    {

        sum[id] = ;

        return;

    }

    int mid = (l + r) >> ;

    if (pos <= mid) update(id << , l, mid, pos);

    else update(id <<  | , mid + , r, pos);

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

    //printf("sum[%d]=%d\n", id, sum[id]);

}

ll query(int id,int l,int r,int x,int y)

{

    if (x <= l && y >= r) return sum[id];

    int mid = (l + r) >> ;

    int ans = ;

    if (x <= mid) ans += query(id << , l, mid, x, y);

    if (y > mid) ans += query(id <<  | , mid + , r, x, y);

    return ans;

}

int main()

{

    int t;

    scanf("%d", &t);

    for(int cas=;cas<=t;cas++)

    {

        memset(ans, , sizeof(ans));

        memset(sum, , sizeof(sum));

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

        for (int i = ; i <= n; i++) scanf("%lld", &a[i].num), a[i].id = i;

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

            ll l, r, h;

            scanf("%lld%lld%lld", &l, &r, &h);

            l++, r++;

            ex[i] = edge(l, r, h, i);

        }

        sort(a + , a +  + n, cmp);

        sort(ex + , ex +  + m, cmp1);

        printf("Case %d:\n", cas);

        int k = ;

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

        {

            while(a[i].num>ex[k].h&&k<=m)

            {

                ans[ex[k].id] = query(, , n, ex[k].l, ex[k].r);

                k++;

            }

            update(, , n, a[i].id);

        }

        for (int i = k; i <= m; i++) ans[ex[i].id] = query(, , n, ex[i].l, ex[i].r);//这个注意不要丢掉了！！！

        for (int i = ; i <= m; i++) printf("%lld\n", ans[i]);

    }

    return ;

}

线段树

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

#include <vector>

#define inf 0x3f3f3f3f

#define inf64 0x3f3f3f3f3f3f3f3f

using namespace std;

const int maxn = 1e5 + ;

int n, m, root[maxn], a[maxn], b[maxn], cnt;

int sum[maxn << ], lc[maxn << ], rc[maxn << ];

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

{

    rt = ++cnt;

    sum[rt] = ;

    if (l == r) return;

    int mid = (l + r) >> ;

    build(lc[rt], l, mid);

    build(rc[rt], mid + , r);

    // printf("rt=%d l=%d r=%d\n",rt,l,r);

}

int update(int rt,int l,int r,int pos)

{

    // printf("ww  rt=%d l=%d r=%d pos=%d\n", rt, l, r, pos);

    int id = ++cnt;

    sum[id] = sum[rt] + ;

    // printf("rt=%d sum[%d]=%d\n", rt, id, sum[id]);

    lc[id] = lc[rt], rc[id] = rc[rt];

    if (l == r) return id;

    int mid = (l + r) >> ;

    // printf("mid=%d rt=%d l=%d r=%d pos=%d\n", mid,rt,l,r,pos);

    if (pos <= mid) lc[id] = update(lc[id], l, mid, pos);

    else rc[id] = update(rc[id], mid + , r, pos);

    // printf("rt=%d l=%d r=%d pos=%d\n", rt, l, r, pos);

    return id;

}

int query(int l,int r,int u,int v,int h)

{

    int mid = (l + r) >> ;

    int x = sum[lc[v]] - sum[lc[u]];

    if (l == r) return sum[v] - sum[u];

    int ans = ;

    if (h <= mid) ans = query(l, mid, lc[u], lc[v], h);

    else ans = x + query(mid + , r, rc[u], rc[v], h);

    return ans;

}

int main()

{

    int t;

    scanf("%d", &t);

    for(int cas=;cas<=t;cas++)

    {

        cnt = ;

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

        for (int i = ; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];

        sort(b + , b +  + n);

        int len = unique(b + , b +  + n) - b - ;

        build(root[], , len);

        // printf("\n\n");

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

            a[i] = lower_bound(b + , b +  + len, a[i]) - b;

            //printf("a[%d]=%d\n", i, a[i]);

            root[i] = update(root[i - ], , len, a[i]);

            // printf("sum[%d]=%d\n", root[i], sum[root[i]]);

            // printf("\n");

        }

        printf("Case %d:\n", cas);

        while(m--)

        {

            int l, r, h;

            scanf("%d%d%d", &l, &r, &h);

            l++, r++;

            h = upper_bound(b + , b +  + len, h) - b - ;

            if (h == ) printf("0\n");

            else printf("%d\n", query(, len, root[l - ], root[r], h));

        }

    }

    return ;

}

主席树

巴特西

J - Super Mario HDU - 4417 线段树离线处理区间排序

J - Super Mario HDU - 4417

最新文章

热门文章

巴特西

J - Super Mario HDU - 4417 线段树 离线处理 区间排序

J - Super Mario HDU - 4417

最新文章

热门文章

J - Super Mario HDU - 4417 线段树离线处理区间排序