Link.
给定序列 \(\{a_n\}\),支持 \(q\) 次操作:
给定 \(l,r,v\),\(\forall i\in[l,r],~a_i\leftarrow\lfloor\frac{a_i}{v}\rfloor\);
给定 \(l,r,v\),\(\forall i\in[l,r],~a_i\leftarrow a_i\otimes v\),其中 \(\otimes\) 表示二进制按位与;
给定 \(l,r\),求 \(\sum_{i=l}^ra_i\)。
\(n\le3\times10^5\),\(q\le2\times10^5\),值域 \(V<2^{128}\),答案对 __uint128_t
自然溢出。
写个“暴力”,证明复杂度,得到正解√
不考虑 (1) 操作,想想如何支持区间与-区间求和。我们用一棵线段树来维护,对于一个长为 \(s\) 的区间,维护一个表格 \(S_{0..\log s}\),设某个 bit \(x\) 在该区间中出现了 \(c\) 次,则在 \(S\) 中每个 \(c\) 的 bit 处加上 \(x\) 的贡献。可以发现 \(\sum S_i2^i\) 就是区间和,合并类似高精度加法做到 \(\mathcal O(s)\),而区间与直接在令 \(S_i\leftarrow S_i\otimes v\) 即可解决,也是 \(\mathcal O(s)\)。不失为一种奇怪的小 trick√
取整除,自然而然暴力做。那么至多遍历 \(\omega=\log V\) 次线段树,乘上 \(\mathcal O(s)\)(\(s\) 为区间长度)的上传代价,遍历整棵树的上传代价和式 \(T(n)=2T(n/2)+\log n=\mathcal O(n)\),所以总复杂度 \(\mathcal O(\omega n)\),加上区间与和求答案,最终复杂度 \(\mathcal O(q\log^2n+\omega n)\)。
用 template
实现线段树√
/*~Rainybunny~*/
#include <set>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )
#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )
typedef __uint128_t UI;
inline UI rxint() {
static char buf[100]; scanf( "%s", buf );
UI ret = 0;
for ( int i = 0; buf[i]; ++i ) {
ret = ret << 4 | ( buf[i] <= '9' ? buf[i] ^ '0' : buf[i] - 'a' + 10 );
}
return ret;
}
inline int rdint() {
int x = 0, f = 1, s = getchar();
for ( ; s < '0' || '9' < s; s = getchar() ) f = s == '-' ? -f : f;
for ( ; '0' <= s && s <= '9'; s = getchar() ) x = x * 10 + ( s ^ '0' );
return x * f;
}
inline void wxint( const UI x ) {
if ( x >= 16 ) wxint( x >> 4 );
putchar( ( x & 15 ) >= 10 ? 'a' + ( x & 15 ) - 10 : '0' ^ ( x & 15 ) );
}
inline int imax( const int a, const int b ) { return a < b ? b : a; }
const int MAXN = 3e5, MAXQ = 2e5;
int n, q;
template<const int H>
struct Atom {
UI val[H + 1];
inline UI& operator [] ( const int k ) { return val[k]; }
friend inline Atom<H + 1> operator + ( Atom<H>& u, Atom<H>& v ) {
static Atom<H + 1> ret;
ret[0] = u[0] ^ v[0]; UI up = u[0] & v[0];
rep ( i, 1, H ) {
ret[i] = up ^ u[i] ^ v[i];
up = ( up & u[i] ) | ( up & v[i] ) | ( u[i] & v[i] );
}
ret[H + 1] = up;
return ret;
}
inline Atom& operator &= ( const UI& x ) {
rep ( i, 0, H ) val[i] &= x;
return *this;
}
inline UI get() const {
UI ret = 0;
rep ( i, 0, H ) ret += val[i] << i;
return ret;
}
};
template<const int H>
struct SegmentTree {
Atom<H> sum; bool zero; UI tag;
SegmentTree<H - 1> lch, rch;
inline void pushup() {
sum = lch.sum + rch.sum, zero = lch.zero && rch.zero;
}
inline void pushan( const UI& v ) {
tag &= v, sum &= v;
}
inline void pushdn() {
if ( ~tag ) {
lch.pushan( tag ), rch.pushan( tag );
tag = ~UI( 0 );
}
}
inline void build( const int l, const int r ) {
int mid = l + r >> 1; tag = ~UI( 0 );
lch.build( l, mid ), rch.build( mid + 1, r );
pushup();
}
inline void secAnd( const int l, const int r,
const int ql, const int qr, const UI& v ) {
if ( zero ) return ;
if ( ql <= l && r <= qr ) return void( pushan( v ) );
int mid = l + r >> 1; pushdn();
if ( ql <= mid ) lch.secAnd( l, mid, ql, qr, v );
if ( mid < qr ) rch.secAnd( mid + 1, r, ql, qr, v );
pushup();
}
inline void secDiv( const int l, const int r,
const int ql, const int qr, const UI& v ) {
if ( zero || v == 1 ) return ;
if ( l == r ) return void( zero = !( sum[0] /= v ) );
int mid = l + r >> 1; pushdn();
if ( ql <= mid ) lch.secDiv( l, mid, ql, qr, v );
if ( mid < qr ) rch.secDiv( mid + 1, r, ql, qr, v );
pushup();
}
inline UI query( const int l, const int r, const int ql, const int qr ) {
if ( zero ) return 0;
if ( ql <= l && r <= qr ) return sum.get();
int mid = l + r >> 1; UI ret = 0; pushdn();
if ( ql <= mid ) ret += lch.query( l, mid, ql, qr );
if ( mid < qr ) ret += rch.query( mid + 1, r, ql, qr );
return ret;
}
};
template<>
struct SegmentTree<0> {
Atom<0> sum; bool zero; UI tag;
inline void pushan( const UI& v ) { tag &= v, sum &= v; }
inline void build( const int l, const int r ) {
assert( l == r );
tag = ~UI( 0 ), zero = !( sum[0] = r < n ? rxint() : 0 );
}
inline void secAnd( const int l, const int r,
const int ql, const int qr, const UI& v ) {
if ( zero ) return ;
assert( ql <= l && r <= qr ), pushan( v );
}
inline void secDiv( const int l, const int r,
const int ql, const int qr, const UI& v ) {
if ( zero || v == 1 ) return ;
zero = !( sum[0] /= v );
}
inline UI query( const int l, const int r, const int ql, const int qr ) {
if ( zero ) return 0;
return assert( ql <= l && r <= qr ), sum.get();
}
};
SegmentTree<19> sgt;
int main() {
// freopen( "machine.in", "r", stdin );
// freopen( "machine.out", "w", stdout );
n = rdint(), q = rdint();
int R = 1 << 19;
sgt.build( 0, R - 1 );
for ( int op, l, r; q--; ) {
op = rdint(), l = rdint() - 1, r = rdint() - 1;
if ( op == 1 ) sgt.secDiv( 0, R - 1, l, r, rxint() );
else if ( op == 2 ) sgt.secAnd( 0, R - 1, l, r, rxint() );
else wxint( sgt.query( 0, R - 1, l, r ) ), putchar( '\n' );
}
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章