多校补题2_牛客博客

第6场
$05$ Snowy Smile
赛场上队友上来就开这道题敲的特high，敲完后 $T$ 了好几发，还在说自己复杂度正确。。。最后不 $T$ 了一直 $W A$ 。
我和另外一个队友在搞 $02$ ，因为感觉可以可以做，但是整个下午都没怼过，思路也不对。。
这道题不是很难，思路是枚举矩形的左下端点和右上端点，用线段树维护矩形内的纵坐标方向的最大子段和，这样就可以在log的复杂度内找到一个矩形的权值最大的"连续纵坐标方向的子矩形"了。。如图，红色矩形就是"连续纵坐标方向的子矩形"。

代码参考了 $c l a r i s$ 的标程，学到一些技巧。。 $c l a r i s N B!$

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ft first
#define sd second
#define all(c) ((c).begin()), ((c).end())
#define mp(a, b) make_pair(a, b)
#define pb(x) push_back(x)
template<typename T>T gcd(T a, T b) {return b==0?a:gcd(b, a%b);}
#ifndef ONLINE_JUDGE
#define debug(fmt, ...) {printf("debug ");printf(fmt,##__VA_ARGS__);puts("");}
#else
#define debug(fmt, ...)
#endif
const int maxn = 1e5+5;
typedef long long ll;
const ll mod = 1e9+7;
int Case = 1;
int n, m;
ll ms[maxn<<2], ls[maxn<<2], rs[maxn<<2], sum[maxn<<2];
int pos[maxn];
void pushup(int rt) {
    ls[rt] = max(ls[rt<<1], sum[rt<<1]+ls[rt<<1|1]);
    rs[rt]=max(rs[rt<<1|1], sum[rt<<1|1] + rs[rt<<1]);
    sum[rt]=sum[rt<<1] + sum[rt<<1|1];
    ms[rt]=max(max(ms[rt<<1], ms[rt<<1|1]), rs[rt<<1] + ls[rt<<1|1]);
}
void build(int rt, int l, int r) {
    sum[rt] = ms[rt] = ls[rt] = rs[rt] = 0;
    if(l == r) {pos[l] = rt;return;}
    int mid = (l+r)/2;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
}
void update(int rt, int val) {
    sum[rt]+=val;
    if(sum[rt]>0)ls[rt] = rs[rt] = ms[rt] = sum[rt];
    else ls[rt] = rs[rt] = ms[rt] = 0;
    for(rt>>=1; rt; rt>>=1) {
        pushup(rt);
    }
}
struct node{int x, y, z;bool operator<(const node s)const{return x < s.x;}}cc[maxn];
vector<int>ve;
int getid(int x) {
    return lower_bound(all(ve), x)-ve.begin()+1;
}
void solve() {
    cin>>n;ve.clear();
    for(int i = 1; i <= n; i++) {
        cin>>cc[i].x>>cc[i].y>>cc[i].z;
        ve.pb(cc[i].y);
    }
    sort(all(ve));ve.erase(unique(all(ve)), ve.end());
    sort(cc+1, cc+1+n);
    m = ve.size();ll res = 0;
    for(int i = 1; i <= n; i++) cc[i].y = getid(cc[i].y);
    for(int i = 1; i <= n; i++) {
        if(i == 1 || cc[i].x != cc[i-1].x) {
            build(1, 1, m);int k;
            for(int j = i; j <= n; j = k) {
                for(k = j; k <= n && cc[k].x == cc[j].x; k++) update(pos[cc[k].y], cc[k].z);
                res = max(res, ms[1]);
            }
        }
    }
    cout<<res<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
#endif
    //scanf("%d", &Case);
    cin>>Case;
    while(Case--) {
        solve();
    }
    return 0;
}

~~某左队友。。感觉多校在打假赛~~