UOJ

(Updated: )
oi
,

题目链接：UOJ #671

给定一个长度为 $n$ 的序列 $a_{1\sim n}$，有 $q$ 个操作：

  • 1 l r v，将区间 $[l,r]$ 每个元素 $\lfloor \frac {a_i} v \rfloor $，这里保证 $v_i\ge 1$。
  • 2 l r v，将区间 $[l,r]$ 每个元素 $a_i \& v$。
  • 3 l r，求 $\sum\limits_{i=l}^r a_i$。

$n\leq 3\times 10^5,q\leq 2\times 10^5,0\leq v_i,a_i\leq 2^{128}$。

Solution

1 朴素做法

容易发现操作 $1,2$ 只会使 $a_i$ 变小，若忽略掉操作 $1$ 中 $v=1$ 的操作，在 $O(\log a_i)$ 次除法操作后即变为 $0$。

区间与操作，每一位分别维护，$v$ 为 $0$ 的位全部清零。

时间复杂度：$O(n\log ^2 V+q\log n\log V)$。

2 优化

朴素做法在线段树的节点上维护的是每一位的 $1$ 的个数，显然其权值若看作二进制数，位数不超过 $\log n$。

那么我们可以将其反转一下，转为维护每一位答案在二进制下第 $i$ 位的值，这样每个数维护的即为自身，不需要 $O(\log V)$ 的时间来自我分解，另外维护的为 $O(\log n)$ 个变量，比 $O(\log V)$ 少，询问的时候只需要求 $\sum s_i\times 2^i$ 即可。

时间复杂度：$O(n\log V+q\log^2 n)$。

合并上传信息的时候只需要手动模拟一下二进制加法即可。

3 吐槽

卡常卡半天，加了个 Ofast 就跑过去了》

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
Cn int N=6e5+10;
int n,m,q; 
typedef __uint128_t u128;
u128 a[N];
inline u128 read() {
    static char buf[100];
    scanf("%s", buf);
    u128 res = 0;for(int i = 0;buf[i];++i) res = res << 4  (buf[i] <= '9' ? buf[i] - '0' : buf[i] - 'a' + 10);
    return res;
}
inline void output(u128 res) {
    if(res >= 16) output(res / 16);
    putchar(res % 16 >= 10 ? 'a' + res % 16 - 10 : '0' + res % 16);
}
class SegmentTree{
    private:
        vector<u128> T[N<<2];
        #define pb push_back
        u128 tg[N<<2];bool v[N<<2];
        #define mid (l+r>>1)
        #define PT CI x=1,CI l=1,CI r=n
        #define LT x<<1,l,mid
        #define RT x<<11,mid+1,r
        I void PU(CI x){
            v[x]=v[x<<1]v[x<<11];u128 tmp=0;RI i,lg;for(i=0,lg=T[x<<1].size();i<lg;i++) T[x][i]=T[x<<1][i]^T[x<<11][i]^tmp,
            tmp=(T[x<<1][i]&T[x<<11][i])(T[x<<1][i]&tmp)(T[x<<11][i]&tmp);T[x][lg]=tmp;
        }
        I void C(CI x,u128 v){for(auto &i:T[x]) i&=v;tg[x]&=v;}
        I void PD(CI x){~tg[x]&&(C(x<<1,tg[x]),C(x<<11,tg[x]),tg[x]=~0);}
        I u128 G(CI x){u128 S=0;for(RI i=0,lg=T[x].size();i<lg;i++) S+=T[x][i]<<i;return S;}
    public:
        I void B(PT){
            if(tg[x]=~0,l==r) return T[x].pb(a[l]),v[x]=a[l]>0,void();
            B(LT),B(RT),T[x].resize(T[x<<1].size()+1),PU(x);
        }
        I void A(CI L,CI R,u128 tv,PT){
            if(!v[x]) return ;if(L<=l&&r<=R) return C(x,tv);
            PD(x),L<=mid&&(A(L,R,tv,LT),0),R>mid&&(A(L,R,tv,RT),0),PU(x);
        }
        I void D(CI L,CI R,u128 tv,PT){
            if(!v[x]) return ;if(l==r) return v[x]=(T[x][0]/=tv)>0,void();
            PD(x),L<=mid&&(D(L,R,tv,LT),0),R>mid&&(D(L,R,tv,RT),0),PU(x);
        }
        I u128 Q(CI L,CI R,PT){
            if(L<=l&&r<=R) return G(x);
            u128 S=0;return PD(x),L<=mid&&(S+=Q(L,R,LT),0),R>mid&&(S+=Q(L,R,RT),0),S;
        }
}T;
int main(){
    u128 v;RI i,op,l,r;for(scanf("%d%d",&n,&q),i=1;i<=n;i++) a[i]=read();
    for(m=n,n=1;n<m;n<<=1);for(T.B(),i=1;i<=q;i++) scanf("%d%d%d",&op,&l,&r),op^3&&(v=read(),0),op==1&&v>1&&(T.D(l,r,v),0),
    op==2?T.A(l,r,v),0:op==3&&(output(T.Q(l,r)),pc('\n'),0);return 0;
}