博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
线段树(区间合并) HDOJ 3308 LCIS
阅读量:6229 次
发布时间:2019-06-21

本文共 4465 字,大约阅读时间需要 14 分钟。

 

题意:线段树操作:1. 单点更新 2. 求区间的LCIS(longest consecutive increasing subsequence)

分析:注意是连续的子序列,就是简单的区间合并,记录线段的端点的值,如果rx[rt<<1] < lx[rt<<1|1]就区间合并,最后结果保存在ms中。因为记录的数据较多,索性结构体内再开一个结构体,感觉还不错。写完这题,对区间合并的操作有了更深的理解。

/************************************************* Author        :Running_Time* Created Time  :2015/9/25 星期五 10:37:34* File Name     :G.cpp ************************************************/#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;struct ST { struct Node { int lx, rx; int ls, rs, ms; }node[N<<2]; void push_up(int l, int r, int rt) { node[rt].ls = node[rt<<1].ls; node[rt].rs = node[rt<<1|1].rs; node[rt].lx = node[rt<<1].lx; node[rt].rx = node[rt<<1|1].rx; node[rt].ms = max (node[rt<<1].ms, node[rt<<1|1].ms); int mid = (l + r) >> 1; if (node[rt<<1].rx < node[rt<<1|1].lx) { if (node[rt<<1].ls == mid - l + 1) { node[rt].ls += node[rt<<1|1].ls; } if (node[rt<<1|1].rs == r - mid) { node[rt].rs += node[rt<<1].rs; } node[rt].ms = max (node[rt].ms, node[rt<<1].rs + node[rt<<1|1].ls); } } void build(int l, int r, int rt) { if (l == r) { scanf ("%d", &node[rt].lx); node[rt].rx = node[rt].lx; node[rt].ls = node[rt].rs = node[rt].ms = 1; return ; } int mid = (l + r) >> 1; build (lson); build (rson); push_up (l, r, rt); } void updata(int p, int c, int l, int r, int rt) { if (l == r) { node[rt].lx = node[rt].rx = c; return ; } int mid = (l + r) >> 1; if (p <= mid) updata (p, c, lson); else updata (p, c, rson); push_up (l, r, rt); } int query(int ql, int qr, int l, int r, int rt) { if (ql <= l && r <= qr) { return node[rt].ms; } int mid = (l + r) >> 1, ret = 0; if (ql <= mid) { ret = max (ret, query (ql, qr, lson)); } if (qr > mid) { ret = max (ret, query (ql, qr, rson)); } if (node[rt<<1].rx < node[rt<<1|1].lx) { ret = max (ret, min (mid - ql + 1, node[rt<<1].rs) + min (qr - mid, node[rt<<1|1].ls)); } return ret; }}st;int main(void) { int T; scanf ("%d", &T); while (T--) { int n, q; scanf ("%d%d", &n, &q); st.build (1, n, 1); for (int a, b, i=1; i<=q; ++i) { char s[2]; scanf ("%s%d%d", &s, &a, &b); if (s[0] == 'Q') { printf ("%d\n", st.query (a + 1, b + 1, 1, n, 1)); } else { st.updata (a + 1, b, 1, n, 1); } } } return 0;}

新代码

#include 
using namespace std;typedef long long ll;const int N = 1e5 + 5;#define lc o << 1#define rc o << 1 | 1int s[N<<2], sl[N<<2], sr[N<<2];int al[N<<2], ar[N<<2];int x[N];void push_up(int o, int l, int r) { sl[o] = sl[lc]; sr[o] = sr[rc]; al[o] = al[lc]; ar[o] = ar[rc]; s[o] = max(s[lc], s[rc]); int mid = l + r >> 1; if (ar[lc] < al[rc]) { s[o] = max(s[o], sr[lc]+sl[rc]); if (sl[o] == mid-l+1) sl[o] += sl[rc]; if (sr[o] == r-mid) sr[o] += sr[lc]; }}void build(int o, int l, int r) { if (l == r) { al[o] = ar[o] = x[l]; s[o] = sl[o] = sr[o] = 1; return ; } int mid = l + r >> 1; build(lc, l, mid); build(rc, mid+1, r); push_up(o, l, r);}void modify(int o, int l, int r, int p, int v) { if (l == r) { al[o] = ar[o] = v; return ; } int mid = l + r >> 1; if (p <= mid) modify(lc, l, mid, p, v); else modify(rc, mid+1, r, p, v); push_up(o, l, r);}int query(int o, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return s[o]; int mid = l + r >> 1, ret = 0; if (ql <= mid) ret = max(ret, query(lc, l, mid, ql, qr)); if (qr > mid) ret = max(ret, query(rc, mid+1, r, ql, qr)); if (ql <= mid && qr > mid) { if (ar[lc] < al[rc]) { ret = max(ret, min(sr[lc], mid-ql+1)+min(sl[rc], qr-mid)); } } return ret;}int main() { int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d%d", &n, &m); for (int i=1; i<=n; ++i) { scanf("%d", &x[i]); } build(1, 1, n); char str[5]; int a, b; while (m--) { scanf("%s%d%d", &str, &a, &b); if (str[0] == 'U') modify(1, 1, n, a+1, b); else printf("%d\n", query(1, 1, n, a+1, b+1)); } } return 0;}

  

转载于:https://www.cnblogs.com/Running-Time/p/4837805.html

你可能感兴趣的文章
我的友情链接
查看>>
nginx在reload时候报错invalid PID number
查看>>
神经网络和深度学习-第二周神经网络基础-第二节:Logistic回归
查看>>
Myeclipse代码提示及如何设置自动提示
查看>>
ElasticSearch 2 (32) - 信息聚合系列之范围限定
查看>>
VS2010远程调试C#程序
查看>>
[MicroPython]TurniBit开发板DIY自动窗帘模拟系统
查看>>
由String类的Split方法所遇到的两个问题
查看>>
Python3.4 12306 2015年3月验证码识别
查看>>
从Handler.post(Runnable r)再一次梳理Android的消息机制(以及handler的内存泄露)
查看>>
windows查看端口占用
查看>>
Yii用ajax实现无刷新检索更新CListView数据
查看>>
JDBC的事务
查看>>
Io流的概述
查看>>
App 卸载记录
查看>>
JavaScript变量和作用域
查看>>
开源SIP服务器加密软件NethidPro升级
查看>>
《别做正常的傻瓜》的一些读书心得
查看>>
作业:实现简单的shell sed替换功能和修改haproxy配置文件
查看>>
Altium 拼板方法以及 注意的 地方
查看>>