loj#6032. 「雅礼集训 2017 Day2」水箱(并查集 贪心 扫描线)

题意

链接

Sol

神仙题+神仙做法%%%%%%%%

我再来复述一遍。。

首先按照\(y\)坐标排序,然后维护一个扫描线从低处往高处考虑。

一个连通块的内状态使用两个变量即可维护\(ans\)表示联通块内的最大答案,\(f\)表示联通块内\(k=1\)的数量

若当前的水超过了当前的挡板,那么将当前联通块和下一个位置所在的联通块合并。

若是一个\(k=0\)的操作,则一定满足。

若是\(k=1\)的操作,那么就将\(f++\),然后更新一下答案。

#include<bits/stdc++.h>
#define LL long long 
using namespace std;
const int MAXN = 1e6 + 10, INF = 1e9 + 7, mod = 998244353;
template <typename A, typename B> inline bool chmin(A &a, B b){if(a > b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline bool chmax(A &a, B b){if(a < b) {a = b; return 1;} return 0;}
template <typename A, typename B> inline LL add(A x, B y) {if(x + y < 0) return x + y + mod; return x + y >= mod ? x + y - mod : x + y;}
template <typename A, typename B> inline void add2(A &x, B y) {if(x + y < 0) x = x + y + mod; else x = (x + y >= mod ? x + y - mod : x + y);}
template <typename A, typename B> inline LL mul(A x, B y) {return 1ll * x * y % mod;}
template <typename A, typename B> inline void mul2(A &x, B y) {x = (1ll * x * y % mod + mod) % mod;}
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, cnt, ans[MAXN], f[MAXN], fa[MAXN];
int find(int x) {
    return fa[x] ? fa[x] = find(fa[x]) : x;
}
struct Query {
    int opt, x, y;
    bool operator < (const Query &rhs) const {
        return y == rhs.y ? opt < rhs.opt : y < rhs.y;
    }
}q[MAXN];
void solve() {
    memset(ans, 0, sizeof(ans)); memset(f, 0, sizeof(f)); memset(fa, 0, sizeof(fa));
    cnt = 0;
    N = read(); M = read();
    for(int i = 1; i < N; i++) q[++cnt] = {-1, i, read()};
    for(int i = 1; i <= M; i++) q[++cnt].x = read(), q[cnt].y = read(), q[cnt].opt = read();
    stable_sort(q + 1, q + cnt + 1);
    int ret = 0;
    for(int i = 1; i <= cnt; i++) {
        int op = q[i].opt, x = q[i].x;
        if(op == -1) {
            int y = find(x + 1); x = find(x);
            fa[y] = x; f[x] += f[y]; ans[x] += ans[y]; chmax(ret, ans[x]);
        } else if(op == 0) {
            chmax(ret, ++ans[find(x)]);
        } else {
            x = find(x); chmax(ans[x], ++f[x]);
            chmax(ret, ans[x]);
        }
    }
    cout << ret << '\n';
}
int main() {
    for(int T = read(); T--; solve());
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏图形学与OpenGL

实验4 二维几何变换

根据示范代码1,使用OpenGL平移、旋转、缩放变换函数来改写代码实现所要求的功能。示范代码1的代码运行结果为图1。

12720
来自专栏图形学与OpenGL

实验2 基本图元光栅化

(1) 阅读学习所给的直线光栅化的DDA算法示范代码,将其彻底弄懂,根据实验思考题找出其中的错误;同时能在计算机上编译运行,输出正确结果,指出错误并截图保存为图...

11520
来自专栏二进制文集

LeetCode 975 Odd Even Jump

You are given an integer array A. From some starting index, you can make a seri...

15630
来自专栏二进制文集

LeetCode 974 Subarray Sums Divisible by K

Given an array A of integers, return the number of (contiguous, non-empty) subar...

13420
来自专栏图形学与OpenGL

实验3 直线裁剪算法

本次实验主要结合鼠标画线程序来验证编码裁剪算法和实现梁友栋-Barsky裁剪算法,具体步骤如下:

15310
来自专栏二进制文集

Java 优先队列 PriorityQueue PriorityBlockingQueue 源码分析

通过数组实现一个堆,元素在queue数组中并不是完全有序的,仅堆顶元素最大或最小。

33620
来自专栏二进制文集

LeetCode 976 Largest Perimeter Triangle

Given an array A of positive lengths, return the largest perimeter of a triangle...

11530
来自专栏TOA

windows下获取TOA的方法

目前互联网业界主流的服务器开发系统主要包括linux和windows两款操作系统,很多网络服务商需要获取客户端的真实IP和Port,特别是IP地址,对业务策略进...

35730
来自专栏二进制文集

LeetCode 973 K Closest Points to Origin

We have a list of points on the plane. Find the K closest points to the origin ...

13430
来自专栏二进制文集

LeetCode 949 Largest Time for Given Digits

Given an array of 4 digits, return the largest 24 hour time that can be made.

12230

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励