BZOJ5312: 冒险(势能均摊线段树)
2018-09-18 06:24:30来源:博客园 阅读 ()
题意
题目链接
Sol
这玩意儿是听shadowice说的,好像很厉害的样子
我们维护出区间&,区间|,区间最大值
结论:如果一次操作对区间& 和 区间| 产生的影响是相同的,那么该操作对整个区间的影响都是相同的
证明可以看这里
然后就做完了。。
时间复杂度$O(nklogn)$,$k$是二进制位数,这里是20
#include<cstdio> #include<algorithm> #define ull unsigned long long #define LL long long // #define int long long #define ls (k << 1) #define rs (k << 1 | 1) using namespace std; const int MAXN = 2 * 1e6 + 10, INF = 1e9 + 7, mod = 998244353; 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; int a[MAXN]; struct Node { int l, r, A, O, Mx, f; }T[MAXN]; void update(int k) { T[k].A = T[ls].A & T[rs].A; T[k].O = T[ls].O | T[rs].O; T[k].Mx = max(T[ls].Mx, T[rs].Mx); } void ps(int k, int val) { T[k].f += val; T[k].A += val; T[k].O += val; T[k].Mx += val; } void pushdown(int k) { if(!T[k].f) return ; ps(ls, T[k].f); ps(rs, T[k].f); T[k].f = 0; } void Build(int k, int ll, int rr) { T[k] = (Node) {ll, rr}; if(ll == rr) {T[k].A = T[k].O = T[k].Mx = a[ll]; return ;} int mid = ll + rr >> 1; Build(ls, ll, mid); Build(rs, mid + 1, rr); update(k); } void IntAnd(int k, int ll, int rr, int val) { if((T[k].O & val) == T[k].O) return ;//notice if((ll <= T[k].l) && (T[k].r <= rr) && ((T[k].A & val) - T[k].A == (T[k].O & val) - T[k].O)) { ps(k, (T[k].A & val) - T[k].A); return ; } pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll <= mid) IntAnd(ls, ll, rr, val); if(rr > mid) IntAnd(rs, ll, rr, val); update(k); } void IntOr(int k, int ll, int rr, int val) { if((T[k].A | val) == T[k].A) return ; if(ll <= T[k].l && T[k].r <= rr && ((T[k].A | val) - T[k].A == (T[k].O | val) - T[k].O)) { ps(k, (T[k].O | val) - T[k].O); return ; } pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll <= mid) IntOr(ls, ll, rr, val); if(rr > mid) IntOr(rs, ll, rr, val); update(k); } int Query(int k, int ll, int rr) { int ans = 0; if(ll <= T[k].l && T[k].r <= rr) return T[k].Mx; pushdown(k); int mid = T[k].l + T[k].r >> 1; if(ll <= mid) ans = Query(ls, ll, rr); if(rr > mid) ans = max(ans, Query(rs, ll, rr)); return ans; } main() { N = read(); M = read(); for(int i = 1; i <= N; i++) a[i] = read(); Build(1, 1, N); while(M--) { int opt = read(), l = read(), r = read(); if(opt == 1) { int x = read(); IntAnd(1, l, r, x); } else if(opt == 2) { int x = read(); IntOr(1, l, r, x); } else printf("%d\n", Query(1, l, r)); } return 0; } /* 3 2 7 11 1 5 3 8 4 7 */
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:errno的用法
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