BZOJ5312: 冒险(势能均摊线段树)

题意

题目链接

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
*/

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术之路

设计模式:单例模式

今天来简单来说一下单例模式:它要确保一个类只有一个实例,而且自行实例化并向整个系统提供这个实例。 比如我们登录一个系统的时候要记录一个员工的信息,在整个系统运行...

2218
来自专栏ChaMd5安全团队

php弱类型初级入门介绍

0x00 前言 最近DeDeCMS爆出来一个前台任意用户密码重置漏洞,由于前台resetpassword.php中对接受的safequestion参数类型比较不...

4059
来自专栏编码前线

设计模式之单例模式

单例模式指的是在应用整个生命周期内只能存在一个实例。单例模式是一种被广泛使用的设计模式。他有很多好处,能够避免实例对象的重复创建,减少创建实例的系统开销,节省内...

1143
来自专栏钟绍威的专栏

初学File类

对File类的基本方法的理解 今天刚开始学了File类 一开始看思想编程看得迷迷糊糊的,之后受不了了,直接去看API文档 归纳: File->jav...

19410
来自专栏闻道于事

单例模式你会几种写法?

1155
来自专栏Ryan Miao

java设计模式(四)--单例模式

 Singleton最熟悉不过了,下面学习单例模式。转载:http://zz563143188.iteye.com/blog/1847029 单例对象(Sin...

3155
来自专栏任浩强的运维生涯

mongodb高级应用

一、  高级查询 查询操作符 条件操作符:db.collection.find({“field”:{$gt/$lt/$gte/$lte/$eq/$ne:valu...

36410
来自专栏ml

file类之目录

     可以解决的问题是:                 有时需要列出目录下指定类型的文件,比如java,txt等扩展名的文件,可以使用File类的下述两个...

2995
来自专栏Java学习网

Java中application对象的19个常用方法

applicaton表示一个javax.servlet.ServletContext对象。他实现了用户间数据的共享,可存放全局变量。它开始于服务器的启动,直到服...

2385
来自专栏诸葛青云的专栏

教你彻底学会c语言基础——文件操作

函数定义:FILE *fopen(char *pname, char *mode)

1622

扫码关注云+社区