维护一种数据结构 支持区间翻转 区间异或 区间求和…
显然 fhq treap
区间异或显然是拆位 然后复杂度*20
第一次先遍历一下整棵树 pushup 一下 就可以了不需要特意的用一个栈来pushup
注意下传懒标记，记得开 long long 就可以了 没了
#include <bits/stdc++.h>
using namespace std ;
#define ls(x) t[x].ch[0]
#define rs(x) t[x].ch[1]
int read() {
int x = 0 ; char c = getchar() ;
while(c < '0' || c > '9') c = getchar() ;
while(c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c & 15) ; c = getchar() ; }
return x ;
}
#define int long long
void print(int x) {
static char st[20] ; int stp = 0 ;
if(! x) { putchar(48) ; }
while(x) { st[++ stp] = x % 10 ^ 48 ; x /= 10 ; }
while(stp) { putchar(st[stp --]) ; }
putchar('
') ;
}
const int MAXN = 1e5 + 10 ;
struct Node { int val , rnd , sz , rev , tag , sum , ch[2] , bit[22] ; } ;
Node t[MAXN] ;
int n , m , rt = 0 , cnt = 0 ;
void pushup(int o) {
t[o].sz = t[ls(o)].sz + t[rs(o)].sz + 1 ; t[o].sum = t[ls(o)].sum + t[rs(o)].sum + t[o].val ;
for(int i = 0 ; i <= 20 ; i ++) t[o].bit[i] = t[ls(o)].bit[i] + t[rs(o)].bit[i] + ((t[o].val >> i) & 1) ;
}
void swap(int & x , int & y) { x ^= y ^= x ^= y ; }
void pushdown(int o) {
if(t[o].rev) { swap(ls(o) , rs(o)) ; if(ls(o)) t[ls(o)].rev ^= 1 ; if(rs(o)) t[rs(o)].rev ^= 1 ; t[o].rev = 0 ; }
if(t[o].tag) {
if(ls(o)) {
t[ls(o)].tag ^= t[o].tag ; t[ls(o)].sum = 0 ; t[ls(o)].val ^= t[o].tag ;
for(int i = 0 ; i <= 20 ; i ++){
if((t[o].tag >> i) & 1) t[ls(o)].bit[i] = t[ls(o)].sz - t[ls(o)].bit[i] ;
t[ls(o)].sum += t[ls(o)].bit[i] << i ;
}
}
if(rs(o)) {
t[rs(o)].tag ^= t[o].tag ; t[rs(o)].sum = 0 ; t[rs(o)].val ^= t[o].tag ;
for(int i = 0 ; i <= 20 ; i ++) {
if((t[o].tag >> i) & 1) t[rs(o)].bit[i] = t[rs(o)].sz - t[rs(o)].bit[i] ;
t[rs(o)].sum += t[rs(o)].bit[i] << i ;
}
}
t[o].tag = 0 ;
}
}
int merge(int u , int v) {
if(! u || ! v) return u | v ;
if(t[u].rnd < t[v].rnd) { pushdown(u) ; rs(u) = merge(rs(u) , v) ; pushup(u) ; return u ; }
else { pushdown(v) ; ls(v) = merge(u , ls(v)) ; pushup(v) ; return v ; }
}
void split(int cur , int k , int & u , int & v) {
if(! cur) { u = v = 0 ; return ; }
pushdown(cur) ;
if(k > t[ls(cur)].sz) { u = cur ; split(rs(u) , k - t[ls(u)].sz - 1 , rs(u) , v) ; }
else { v = cur ; split(ls(v) , k , u , ls(v)) ; }
pushup(cur) ;
}
void Reverse(int l , int r) {
int x , y , z ;
split(rt , r , x , z) ; split(x , l - 1 , x , y) ;
t[y].rev ^= 1 ; rt = merge(merge(x , y) , z) ;
}
void Modify(int l , int r , int val) {
int x , y , z ;
split(rt , r , x , z) ; split(x , l - 1 , x , y) ;
t[y].tag ^= val ; t[y].sum = 0 ; t[y].val ^= val ;
for(int i = 0 ; i <= 20 ; i ++){
if((val >> i) & 1) t[y].bit[i] = t[y].sz - t[y].bit[i] ;
t[y].sum += t[y].bit[i] << i ;
}
rt = merge(merge(x , y) , z) ;
}
int Query(int l , int r) {
int x , y , z ;
split(rt , r , x , z) ; split(x , l - 1 , x , y) ;
int res = t[y].sum ; rt = merge(merge(x , y) , z) ;
return res ;
}
int NewNode(int val) {
++ cnt ;
t[cnt].ch[0] = t[cnt].ch[1] = 0 ; t[cnt].val = val ; t[cnt].rnd = rand() ; t[cnt].sz = 1 ;
t[cnt].rev = t[cnt].tag = t[cnt].sum = 0 ;
return cnt ;
}
void Insert(int val) { rt = merge(rt , NewNode(val)) ; }
void build(int x) { if(ls(x)) build(ls(x)) ; if(rs(x)) build(rs(x)) ; pushup(x) ; }
signed main() {
srand(19260817) ;
n = read() ; m = read() ;
for(int i = 1 ; i <= n ; i ++) Insert(read()) ;
build(rt) ;
while(m --) {
int opt = read() ;
if(opt == 1) { int l = read() , r = read() ; Reverse(l , r) ; }
if(opt == 2) { int l = read() , r = read() , val = read() ; Modify(l , r , val) ; }
if(opt == 3) { int l = read() , r = read() ; print(Query(l , r)) ; }
}
return 0 ;
}