线段树

P5670

prob:

1.区间加
2.区间异或和后 m 位 (\(m \le 10\))
3.n 1e5

sol:

用 bitset 维护线段树区间。
具体的，开 1024 位 bitset 表示每种数对异或贡献为 0/1，有区间可加性。
时间复杂度 \(O(\frac{n \log n 2^m}{w})\)，但是这题半秒，很卡常，需要优化。。（感觉甚至不如暴力/lh）
发现区间较小时 bitset 算确实不如暴力优，令长度小于阈值的区间暴力算即可。

注意：
1.暴力算的时候要把当前节点的 tag 加上。
2.不要习惯性的把循环里所有东西都写成 i ！！！（modify 里那个 p）

namespace sgt {
	#define ls(p) p<<1
	#define rs(p) p<<1|1
	const int M = 1<<10;
	const int B = 1<<5; // bf range
	bitset <M> b[N<<2];
	int ad[N<<2];
	void pushup(int p) {
		b[p] = b[ls(p)]^b[rs(p)];
	}
	void upd(int p, int k) {
		k &= M-1;
		b[p] = b[p]<<k | b[p]>>M-k;
		ad[p] += k;
	}
	void pushdown(int p) {
		if(!ad[p]) return ;
		upd(ls(p), ad[p]), upd(rs(p), ad[p]);
		ad[p] = 0;
	}
	void build(int p, int l, int r) {
		if(r-l+1 <= B) {
			rep(i, l, r) b[p].flip(a[i]);
			return ;
		}
		int mid = l+r>>1;
		build(ls(p), l, mid), build(rs(p), mid+1, r);
		pushup(p);
	}
	void modify(int p, int l, int r, int x, int y, int k) {
		if(r-l+1 <= B) {
			int lb = max(l, x), rb = min(r, y);
			rep(i, lb, rb) b[p].flip(a[i]+ad[p] & M-1);
			rep(i, lb, rb) a[i] += k;
			rep(i, lb, rb) b[p].flip(a[i]+ad[p] & M-1);
			return ;
		}
		if(l >= x && r <= y) return upd(p, k);
		pushdown(p);
		int mid = l+r>>1;
		if(x <= mid) modify(ls(p), l, mid, x, y, k);
		if(y > mid) modify(rs(p), mid+1, r, x, y, k);
		pushup(p);
	}
	bitset <M> ask(int p, int l, int r, int x, int y) {
		bitset <M> s;
		if(r-l+1 <= B) {
			int lb = max(l, x), rb = min(r, y);
			rep(i, lb, rb) s.flip(a[i]+ad[p] & M-1);
			return s;
		}
		if(l >= x && r <= y) return b[p];
		pushdown(p);
		int mid = l+r>>1;
		if(x <= mid) s ^= ask(ls(p), l, mid, x, y);
		if(y > mid) s ^= ask(rs(p), mid+1, r, x, y);
		return s;
	}
}

总结：bitset 太神秘！

ABC356F

唐题