icontofig | 发布于 2019-08-08 13:50:48 | 阅读量 301 | 线段树
发布于 2019-08-08 13:50:48 | 线段树

题目大意

平面直角坐标系上有n个点,每个点有wi的价值,你可以选出一个矩形,获得矩形内部和边界上所有点的价值总和,求问最大的价值总和是多少。

题解

一开始一看,这题简单啊,直接离散化上二维前缀和好了。

然后写着写着发现不对劲,二维前缀和枚举是O(n^4)的。。。

然后后面想到了其实也就是离散化后维护最大子矩阵和,大概是要用二维线段树维护的……不过这个代码难度和复杂度就……

最后是队友给了思路:把问题通过一系列手法降维处理,把最大子段和转化为最大子区间和,这样就可以用一维的普通线段树去维护了。

首先还是要离散化,然后对于所有点按离散化后的x坐标从小到大排序。

然后我们枚举一个左侧的边界作为起始,枚举右侧边界作为终止,建立一棵投影到y轴上的线段树,把我们枚举的两个边界及其中间的所有点全部投影到y轴,并加入线段树进行单点修改,维护线段树区间最大子段和,这样我们枚举的两个边界中所维护的线段树的最大子段和就是以这两条边为边界的最大子矩阵和。

由于点数比较少,所以每枚举一次左侧边界后面的操作都是复杂度O(nlogn)的。所以对于每一个case,我们这个解决方案的总复杂度就是O(n2logn)的

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long ll;
ll ans = 0;
int T;
int n;
const int maxn = 2e5+5;
struct point{
    int x,y;
    ll w;
}p[maxn];
int xx[maxn],yy[maxn];
int tot1,tot2;
struct tree{
    int l,r;
    ll sum,mxl,mxr,mxs;
}tr[maxn<<2];
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = (num<<3) + (num<<1) + c - '0';
    return (flag ? -1 : 1) * num;
}
void build(int now,int l,int r){
    tr[now].l = l;
    tr[now].r = r;
    tr[now].sum = tr[now].mxs = tr[now].mxl = tr[now].mxr = 0;
    if(l == r)
        return;
    int mid = (l + r) >> 1;
    build(now<<1,l,mid);
    build(now<<1|1,mid+1,r);
    return;
}
void push_up(int now){
    tr[now].sum = tr[now<<1].sum + tr[now<<1|1].sum;
    tr[now].mxl = max(tr[now<<1].mxl,tr[now<<1].sum + tr[now<<1|1].mxl);
    tr[now].mxr = max(tr[now<<1|1].mxr,tr[now<<1|1].sum + tr[now<<1].mxr);
    tr[now].mxs = max(tr[now<<1].mxs,max(tr[now<<1|1].mxs,tr[now<<1].mxr + tr[now<<1|1].mxl));
    return;
}
void update(int now,int pos,int val){
    if(tr[now].l == tr[now].r){
        tr[now].sum += val;
        tr[now].mxl += val;
        tr[now].mxr += val;
        tr[now].mxs += val;
        return;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)update(now<<1,pos,val);
    else update(now<<1|1,pos,val);
    push_up(now);
    return;
}
bool cmp(point a,point b){
    return a.x < b.x;
}
int main(){
    T = get_num();
    while(T--){
        ans = 0;
        n = get_num();
        for(int i = 1;i <= n;++i){
            p[i].x = get_num();
            p[i].y = get_num();
            p[i].w = get_num();
            xx[i] = p[i].x;
            yy[i] = p[i].y;
        }
        sort(xx+1,xx+n+1);
        sort(yy+1,yy+n+1);
        tot1 = unique(xx+1,xx+n+1) - (xx+1);
        tot2 = unique(yy+1,yy+n+1) - (yy+1);
        for(int i = 1;i <= n;++i){
            p[i].x = lower_bound(xx+1,xx+tot1+1,p[i].x) - xx;
            p[i].y = lower_bound(yy+1,yy+tot2+1,p[i].y) - yy;
        }
        sort(p+1,p+n+1,cmp);
        for(int i = 1;i <= tot1;++i){
            build(1,1,tot2);
            int l = 0;
            for(int j = 1;j <= n;++j){
                if(p[j].x == i){
                    l = j;
                    break;
                }
            }
            int r = l;
            for(int j = i;j <= tot1;++j){
                for(;p[r].x <= j && r <= n;++r){
                    update(1,p[r].y,p[r].w);
                }
                ans = max(ans,tr[1].mxs);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}



内容更新于: 2019-08-08 13:50:52
链接地址: http://blog.leanote.com/post/icontofig/54619540e6e3

上一篇: CodeChef - ELHIDARR Find an element in hidden array 人机交互+二分

下一篇: APIO 2012 dispatching BZOJ 2809 左偏树

301 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航