BZOJ4355: Play with sequence(吉司机线段树)
2018-09-19 02:44:35来源:博客园 阅读 ()
题意
题目链接
Sol
传说中的吉司机线段树??感觉和BZOJ冒险那题差不多,就是强行剪枝。。。
这题最坑的地方在于对于操作1,$C >= 0$, 操作2中需要对0取max,$a[i] >= 0$,这不就是统计最小值出现的次数么??
按照套路
维护好区间赋值标记 / 区间加法标记 / 区间max标记 / 区间最小值 / 区间最小值出现的次数 / 区间次小值
对于第二个操作就拆成区间加 和 区间max
区间max是一个很神奇的操作
设当前加入的数为val
若val>=mn,那该操作对该区间无影响
若se < val < mn,该操作只会对次小值产生影响,因为对其他的标记均不会产生影响,因此打一个额外的标记即可
否则暴力递归
时间复杂度:$O(n log^2n)$??
另外这东西可以做区间加 / 查询历史版本,前者维护一下标记就行,,后者嘛,,,等长大了再研究吧qwq
#include<cstdio> #include<algorithm> #define LL long long //#define int long long using namespace std; const int MAXN = 3 * 1e5 + 10; const LL INF = 1e10 +10; 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; } #define ls k << 1 #define rs k << 1 | 1 int N, Q; int a[MAXN]; struct Node { int l, r, siz, cnt; LL Mx, add, mn, se, cov; }T[MAXN << 2]; void update(int k) { //T[k].mn = min(T[ls].mn, T[rs].mn); if(T[ls].mn < T[rs].mn) T[k].cnt = T[ls].cnt, T[k].mn = T[ls].mn, T[k].se = min(T[rs].mn, T[ls].se); else if(T[ls].mn > T[rs].mn) T[k].cnt = T[rs].cnt, T[k].mn = T[rs].mn, T[k].se = min(T[ls].mn, T[rs].se); else T[k].cnt = T[ls].cnt + T[rs].cnt, T[k].mn = T[ls].mn, T[k].se = min(T[ls].se, T[rs].se); } void MemP(int k, LL val) { T[k].cov = val; T[k].cnt = T[k].siz; T[k].se = INF; T[k].Mx = -INF; T[k].add = 0; T[k].mn = val; } void AddP(int k, LL val) { if(T[k].se != INF) T[k].se += val; if(T[k].Mx != -INF) T[k].Mx += val; T[k].mn += val; T[k].add += val; } void MaxP(int k, LL val) { T[k].mn = max(T[k].mn, val);// T[k].Mx = max(T[k].Mx, val); } void pushdown(int k) { if(T[k].cov != INF) MemP(ls, T[k].cov), MemP(rs, T[k].cov), T[k].cov = INF; if(T[k].add) AddP(ls, T[k].add), AddP(rs, T[k].add), T[k].add = 0; if(T[k].Mx != -INF) MaxP(ls, T[k].Mx), MaxP(rs, T[k].Mx), T[k].Mx = -INF; } void Build(int k, int ll, int rr) { T[k] = (Node) {ll, rr, rr - ll + 1, 0, -INF, 0, 0, INF, INF}; if(ll == rr) { T[k].mn = a[ll]; T[k].cnt = 1; return ; } int mid = T[k].l + T[k].r >> 1; Build(ls, ll, mid); Build(rs, mid + 1, rr); update(k); } void IntMem(int k, int ll, int rr, LL val) { if(ll <= T[k].l && T[k].r <= rr) {MemP(k, val); return ;} pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll <= mid) IntMem(ls, ll, rr, val); if(rr > mid) IntMem(rs, ll, rr, val); update(k); } void IntAdd(int k, int ll, int rr, LL val) { if(ll <= T[k].l && T[k].r <= rr) {AddP(k, val); return ;} pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll <= mid) IntAdd(ls, ll, rr, val); if(rr > mid) IntAdd(rs, ll, rr, val); update(k); } void IntMax(int k, int ll, int rr, LL val) { if(val <= T[k].mn) return ; if(ll <= T[k].l && T[k].r <= rr && T[k].se > val) {//tag MaxP(k, val); return ; } int mid = T[k].l + T[k].r >> 1; pushdown(k); if(ll <= mid) IntMax(ls, ll, rr, val); if(rr > mid) IntMax(rs, ll, rr, val); update(k); } LL Query(int k, int ll, int rr) { // int ans = 0; if(ll <= T[k].l && T[k].r <= rr) return (T[k].mn == 0 ? T[k].cnt : 0); pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll > mid) return Query(rs, ll, rr); else if(rr <= mid) return Query(ls, ll, rr); else return Query(ls, ll, rr) + Query(rs, ll, rr); } main() { // freopen("4355.in", "r", stdin); // freopen("4355.out", "w", stdout); N = read(); Q = read(); for(int i = 1; i <= N; i++) a[i] = read(); Build(1, 1, N); while(Q--) { int opt = read(), l = read(), r = read(), val; if(opt == 3) printf("%d\n", Query(1, l, r)); else { val = read(); if(opt == 1) IntMem(1, l, r, val); else { IntAdd(1, l, r, val); IntMax(1, l, r, 0); } } } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 1.ffmpeg、ffplay、ffprobe命令使用 2020-05-11
- CodeForces 1313E Concatenation with intersection 2020-03-02
- Longest Substring Without Repeating Characters 2019-08-16
- 【阶梯报告】洛谷P3391【模板】文艺平衡树 splay 2018-11-20
- GNU编译器学习 --> 如何链接外部库【Linking with 2018-11-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash