HDU 6638 - Snowy Smile 线段树区间合并+暴力枚举

时间：2022-09-29 15:39:45

HDU 6638 - Snowy Smile

题意

给你\(n\)个点的坐标\((x,\ y)\)和对应的权值\(w\)，让你找到一个矩形，使这个矩阵里面点的权值总和最大。

思路

  1. 先离散化纵坐标\(y\)的值
  2. 对\(n\)个点根据横坐标\(s\)进行排序
  3. 枚举横坐标，按顺序把点扔到线段树里，以离散化后\(y\)的\(id\)为下标\(pos\)，存到线段树里
  • 因为线段树可以在\(\log{n}\)的时间内插入数值，在\(O(1)\)的时间内查询当前区间最大子段和（线段树区间合并）

    \(node[rt].Max :\)当前区间最大子段和

    \(node[rt].lsum :\)当前区间从左端点开始最大连续子段和

    \(node[rt].rsum:\)当前区间从右端点开始最大连续子段和

    \(node[rt].sum:\)当前区间和
node[rt].Max = max(node[rt<<1].Max, node[rt<<1|1].Max);

node[rt].Max = max(node[rt].Max, node[rt<<1].rsum + node[rt<<1|1].lsum);

node[rt].lsum = max(node[rt<<1].lsum, node[rt<<1].sum + node[rt<<1|1].lsum);

node[rt].rsum = max(node[rt<<1|1].rsum, node[rt<<1|1].sum + node[rt<<1].rsum);

node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;

然后就能愉快的解决这道题了，时间复杂度在\(O(n^2\log{n})\)，枚举\(n^2\), 线段树插入\(\log{n}\)（今天下午做题一小时，自闭一下午也是没谁了，一直想不到做法，还是太菜了）

AC代码

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<vector>

#define mes(a, b) memset(a, b, sizeof a)

using namespace std;

typedef long long ll;

const int inf = 1e9+7;

const int maxn = 2e3+10;

struct Node{

    ll Max, lsum, rsum, sum;

}node[maxn<<2];

struct A{

    int x, y;

    ll w;

    bool operator < (A const& b)const{

        return x > b.x;

    }

}a[maxn];

vector<int> y;

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

    node[rt].Max = node[rt].lsum = node[rt].rsum = node[rt].sum = 0;

    if(l == r)

        return;

    int mid = l+r>>1;

    build(l, mid, rt<<1);

    build(mid+1, r, rt<<1|1);

}

void pushup(int rt){

    node[rt].Max = max(node[rt<<1].Max, node[rt<<1|1].Max);

    node[rt].Max = max(node[rt].Max, node[rt<<1].rsum + node[rt<<1|1].lsum);

    node[rt].lsum = max(node[rt<<1].lsum, node[rt<<1].sum + node[rt<<1|1].lsum);

    node[rt].rsum = max(node[rt<<1|1].rsum, node[rt<<1|1].sum + node[rt<<1].rsum);

    node[rt].sum = node[rt<<1].sum + node[rt<<1|1].sum;

}

void update(int pos, ll c, int l, int r, int rt){

    if(l == r){

        node[rt].sum += c;

        if(node[rt].sum > 0){

            node[rt].lsum = node[rt].Max = node[rt].rsum = node[rt].sum;

        }

        else{

            node[rt].lsum = node[rt].Max = node[rt].rsum = 0;

        }

        return;

    }

    int mid = l+r>>1;

    if(pos <= mid)

        update(pos, c, l, mid, rt<<1);

    else

        update(pos, c, mid+1, r, rt<<1|1);

    pushup(rt);

}

int main(){

    int T, n;

    scanf("%d", &T);

    while(T--){

        y.clear();

        scanf("%d", &n);

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

            scanf("%d%d%lld", &a[i].x, &a[i].y, &a[i].w);

            y.push_back(a[i].y);

        }

        sort(y.begin(), y.end());

        y.erase(unique(y.begin(), y.end()), y.end());

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

        ll ans = 0;

        a[0].x = inf;

        a[0].y = inf;

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

            if(a[i].x != a[i-1].x){		//相等的就跳过

                build(1, n, 1);

                for(int j = i; j <= n; j++){		//暴力枚举所有的横坐标x的左右区间

                    int id = lower_bound(y.begin(), y.end(), a[j].y) - y.begin() + 1;

                    update(id, a[j].w, 1, n, 1);

                    if(a[j].x == a[j+1].x && j != n) continue;	//相等的就跳过

                    ans = max(ans, node[1].Max);

                }

            }

        }

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

    }

    return 0;

}

相关文章