UOJ
题目链接：UOJ #671
给定一个长度为 n 的序列 a_{1sim n}，有 q 个操作：
- 1 l r v，将区间 [l,r] 每个元素 lfloor frac {a_i} v rfloor ，这里保证 v_ige 1。
- 2 l r v，将区间 [l,r] 每个元素 a_i & v
- 3 l r，求 sumlimits_{i=l}^r a_i。
nleq 3times 10^5,qleq 2times 10^5,0leq v_i,a_ileq 2^{128}。
Solution
1 朴素做法
容易发现操作 1,2 只会使 a_i 变小，若忽略掉操作 1 中 v=1 的操作，在 O(log a_i) 次除法操作后即变为 0。
区间与操作，每一位分别维护，v 为 0 的位全部清零。
时间复杂度：O(nlog ^2 V qlog nlog V)。
2 优化
朴素做法在线段树的节点上维护的是每一位的 1 的个数，显然其权值若看作二进制数，位数不超过 log n。
那么我们可以将其反转一下，转为维护每一位答案在二进制下第 i 位的值，这样每个数维护的即为自身，不需要 O(log V) 的时间来自我分解，另外维护的为 O(log n) 个变量，比 O(log V) 少，询问的时候只需要求 sum s_itimes 2^i 即可。
时间复杂度：O(nlog V qlog^2 n)。
合并上传信息的时候只需要手动模拟一下二进制加法即可。
3 吐槽
卡常卡半天，加了个 Ofast 就跑过去了》
Code
代码语言：javascript复制#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;
}
