http://acm.fzu.edu.cn/problem.php?pid=2105
这个是有点东西，分解位操作之后要考虑lazy的影响，假如不顾一切往下PushDown的话要先判断叶子，叶子是不能PushDown的。其次要Build的时候清空lazy。不顾一切先PushDown并不能改变运算符优先级的影响，因为子树也可能有lazy标记。所以当时银川重赛弄的那个是白弄的。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const int MAXLOGAI = 4;
int a[MAXN + 5];
int st[MAXN * 4 + 5][MAXLOGAI];
char lazy[MAXN * 4 + 5][MAXLOGAI];
inline void PushUp(int o) {
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = st[o << 1][id] + st[o << 1 | 1][id];
}
inline void PushDown(int o, int l, int r) {
//op=1 ^
//op=2 |
//op=3 &
for(int id = 0; id < MAXLOGAI; ++id) {
if(lazy[o][id]) {
int mid = l + r >> 1;
if(lazy[o][id] == 1) {
if(lazy[o << 1][id] == 0) {
st[o << 1][id] = (mid - l + 1) - st[o << 1][id];
lazy[o << 1][id] = 1;
} else if(lazy[o << 1][id] == 1) {
st[o << 1][id] = (mid - l + 1) - st[o << 1][id];
lazy[o << 1][id] = 0;
} else if(lazy[o << 1][id] == 2) {
st[o << 1][id] = 0;
lazy[o << 1][id] = 3;
} else if(lazy[o << 1][id] == 3) {
st[o << 1][id] = (mid - l + 1);
lazy[o << 1][id] = 2;
}
if(lazy[o << 1 | 1][id] == 0) {
st[o << 1 | 1][id] = (r - (mid + 1) + 1) - st[o << 1 | 1][id];
lazy[o << 1 | 1][id] = 1;
} else if(lazy[o << 1 | 1][id] == 1) {
st[o << 1 | 1][id] = (r - (mid + 1) + 1) - st[o << 1 | 1][id];
lazy[o << 1 | 1][id] = 0;
} else if(lazy[o << 1 | 1][id] == 2) {
st[o << 1 | 1][id] = 0;
lazy[o << 1 | 1][id] = 3;
} else if(lazy[o << 1 | 1][id] == 3) {
st[o << 1 | 1][id] = (r - (mid + 1) + 1);
lazy[o << 1 | 1][id] = 2;
}
} else if(lazy[o][id] == 2) {
st[o << 1][id] = (mid - l + 1);
lazy[o << 1][id] = 2;
st[o << 1 | 1][id] = (r - (mid + 1) + 1);
lazy[o << 1 | 1][id] = 2;
} else {
st[o << 1][id] = 0;
lazy[o << 1][id] = 3;
st[o << 1 | 1][id] = 0;
lazy[o << 1 | 1][id] = 3;
}
lazy[o][id] = 0;
}
}
}
void Build(int o, int l, int r) {
for(int id = 0; id < MAXLOGAI; ++id)
lazy[o][id] = 0;
if(l == r) {
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = (a[l] & (1 << id)) ? 1 : 0;
} else {
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
PushUp(o);
}
}
void Update(int o, int l, int r, int ql, int qr, int op, int x) {
//op=1 ^
//op=2 |
//op=3 &
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr) {
if(op == 1) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1) - st[o][id];
lazy[o][id] = op;
}
}
} else if(op == 2) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1);
lazy[o][id] = op;
}
}
} else {
for(int id = 0; id < MAXLOGAI; ++id) {
if(!(x & (1 << id))) {
st[o][id] = 0;
lazy[o][id] = op;
}
}
}
} else {
int mid = l + r >> 1;
if(ql <= mid)
Update(o << 1, l, mid, ql, qr, op, x);
if(qr >= mid + 1)
Update(o << 1 | 1, mid + 1, r, ql, qr, op, x);
PushUp(o);
}
}
ll Query(int o, int l, int r, int ql, int qr) {
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr) {
ll res = 0;
for(int id = 0; id < MAXLOGAI; ++id)
res += 1ll * (1 << id) * (st[o][id]);
return res;
} else {
ll res = 0;
int mid = l + r >> 1;
if(ql <= mid)
res += Query(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res += Query(o << 1 | 1, mid + 1, r, ql, qr);
return res;
}
}
int main() {
#ifdef localll
freopen("lyz.in", "r", stdin);
#endif // local
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
Build(1, 1, n);
for(int i = 1; i <= m; ++i) {
char ops[10];
int l, r, x;
scanf("%s", ops);
if(ops[0] == 'S') {
scanf("%d%d", &l, &r);
++l, ++r;
printf("%lld
", Query(1, 1, n, l, r));
} else {
scanf("%d%d%d", &x, &l, &r);
++l, ++r;
if(ops[0] == 'X') {
Update(1, 1, n, l, r, 1, x);
} else if(ops[0] == 'O') {
Update(1, 1, n, l, r, 2, x);
} else if(ops[0] == 'A') {
Update(1, 1, n, l, r, 3, x);
}
}
}
}
}
有人说一堆if else太可怕了，make him happy？换成迷惑性更强的操作。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e6;
const int MAXLOGAI = 4;
int a[MAXN + 5];
int st[MAXN * 4 + 5][MAXLOGAI];
char lazy[MAXN * 4 + 5][MAXLOGAI];
inline void PushUp(int o) {
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = st[o << 1][id] + st[o << 1 | 1][id];
}
inline void PushDown(int o, int l, int r) {
//op=1 ^
//op=2 |
//op=3 &
for(int id = 0; id < MAXLOGAI; ++id) {
if(lazy[o][id]) {
int mid = l + r >> 1;
if(lazy[o][id] == 1) {
st[o << 1][id] = (mid - l + 1) - st[o << 1][id];
lazy[o << 1][id] ^= 1;
st[o << 1 | 1][id] = (r - (mid + 1) + 1) - st[o << 1 | 1][id];
lazy[o << 1 | 1][id] ^= 1;
} else if(lazy[o][id] == 2) {
st[o << 1][id] = (mid - l + 1);
lazy[o << 1][id] = 2;
st[o << 1 | 1][id] = (r - (mid + 1) + 1);
lazy[o << 1 | 1][id] = 2;
} else {
st[o << 1][id] = 0;
lazy[o << 1][id] = 3;
st[o << 1 | 1][id] = 0;
lazy[o << 1 | 1][id] = 3;
}
lazy[o][id] = 0;
}
}
}
void Build(int o, int l, int r) {
for(int id = 0; id < MAXLOGAI; ++id)
lazy[o][id] = 0;
if(l == r) {
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = (a[l] & (1 << id)) ? 1 : 0;
} else {
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
PushUp(o);
}
}
void Update(int o, int l, int r, int ql, int qr, int op, int x) {
//op=1 ^
//op=2 |
//op=3 &
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr) {
if(op == 1) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1) - st[o][id];
lazy[o][id] = op;
}
}
} else if(op == 2) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1);
lazy[o][id] = op;
}
}
} else {
for(int id = 0; id < MAXLOGAI; ++id) {
if(!(x & (1 << id))) {
st[o][id] = 0;
lazy[o][id] = op;
}
}
}
} else {
int mid = l + r >> 1;
if(ql <= mid)
Update(o << 1, l, mid, ql, qr, op, x);
if(qr >= mid + 1)
Update(o << 1 | 1, mid + 1, r, ql, qr, op, x);
PushUp(o);
}
}
ll Query(int o, int l, int r, int ql, int qr) {
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr) {
ll res = 0;
for(int id = 0; id < MAXLOGAI; ++id)
res += 1ll * (1 << id) * (st[o][id]);
return res;
} else {
ll res = 0;
int mid = l + r >> 1;
if(ql <= mid)
res += Query(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res += Query(o << 1 | 1, mid + 1, r, ql, qr);
return res;
}
}
int main() {
#ifdef localll
freopen("lyz.in", "r", stdin);
#endif // local
int T, n, m;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]);
Build(1, 1, n);
for(int i = 1; i <= m; ++i) {
char ops[10];
int l, r, x;
scanf("%s", ops);
if(ops[0] == 'S') {
scanf("%d%d", &l, &r);
++l, ++r;
printf("%lld
", Query(1, 1, n, l, r));
} else {
scanf("%d%d%d", &x, &l, &r);
++l, ++r;
if(ops[0] == 'X') {
Update(1, 1, n, l, r, 1, x);
} else if(ops[0] == 'O') {
Update(1, 1, n, l, r, 2, x);
} else if(ops[0] == 'A') {
Update(1, 1, n, l, r, 3, x);
}
}
}
}
}
看了一下有人超级省空间，我居然用了80多MB，我想了一下。首先浪费的最多的就是线段树那个*4，事实上直接取左移21位就刚刚够，这样可以成功压缩到40多MB，然后我想了一下假如我把线段树的首层的查询裂成对两棵子树的询问，那么首层PushUp的时候造成的溢出就无所谓了，所以可以用unsigned short来压缩到25MB，当然这样做的前提是我把它的标记下推了，否则应该会有奇怪的bug出现。然后该const int &的全部const int &，套个文件快读（手写一个ReadString不知会不会出bug）。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
namespace FastIO {
#define BUF_SIZE 1000000
bool IOError = 0;
inline char NextChar() {
static char buf[BUF_SIZE], *pl = buf + BUF_SIZE, *pr = buf + BUF_SIZE;
if(pl == pr) {
pl = buf, pr = buf + fread(buf, 1, BUF_SIZE, stdin);
if(pr == pl) {
IOError = 1;
return -1;
}
}
return *pl++;
}
#undef BUF_SIZE
inline bool Blank(char c) {
return c == ' ' || c == '
' || c == '
' || c == ' ';
}
template<class T> inline void Read(T &x) {
char c;
while(Blank(c = NextChar()));
if(!IOError) {
for(x = 0; '0' <= c && c <= '9'; c = NextChar())
x = (x << 3) + (x << 1) + c - '0';
}
}
inline void ReadString(char *x) {
char c;
while(Blank(c = NextChar()));
if(!IOError) {
do {
*(x++) = c;
c = NextChar();
} while(!Blank(c));
}
}
template<class T> inline void PutChar(T x) {
if(x > 9)
PutChar(x / 10);
putchar(x % 10 + '0');
}
template<class T> inline void Write(T &x) {
PutChar(x);
putchar('
');
}
}
using namespace FastIO;
const int MAXN = 1e6;
const int MAXLOGAI = 4;
unsigned short st[(1 << 21) + 5][MAXLOGAI];
char lazy[(1 << 21) + 5][MAXLOGAI];
inline void PushUp(const int &o) {
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = st[o << 1][id] + st[o << 1 | 1][id];
}
inline void PushDown(const int &o, const int &l, const int &r) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(lazy[o][id]) {
int mid = l + r >> 1;
if(lazy[o][id] == 1) {
st[o << 1][id] = (mid - l + 1) - st[o << 1][id];
lazy[o << 1][id] ^= 1;
st[o << 1 | 1][id] = (r - (mid + 1) + 1) - st[o << 1 | 1][id];
lazy[o << 1 | 1][id] ^= 1;
} else if(lazy[o][id] == 2) {
st[o << 1][id] = (mid - l + 1);
lazy[o << 1][id] = 2;
st[o << 1 | 1][id] = (r - (mid + 1) + 1);
lazy[o << 1 | 1][id] = 2;
} else {
st[o << 1][id] = 0;
lazy[o << 1][id] = 3;
st[o << 1 | 1][id] = 0;
lazy[o << 1 | 1][id] = 3;
}
lazy[o][id] = 0;
}
}
}
inline void Build(const int &o, const int &l, const int &r) {
for(int id = 0; id < MAXLOGAI; ++id)
lazy[o][id] = 0;
if(l == r) {
int x;
Read(x);
for(int id = 0; id < MAXLOGAI; ++id)
st[o][id] = (x & (1 << id)) ? 1 : 0;
} else {
int mid = l + r >> 1;
Build(o << 1, l, mid);
Build(o << 1 | 1, mid + 1, r);
PushUp(o);
}
}
inline void Update(const int &o, const int &l, const int &r, const int &ql, const int &qr, const int &op, const int &x) {
//op=1 ^
//op=2 |
//op=3 &
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr) {
if(op == 1) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1) - st[o][id];
lazy[o][id] = op;
}
}
} else if(op == 2) {
for(int id = 0; id < MAXLOGAI; ++id) {
if(x & (1 << id)) {
st[o][id] = (r - l + 1);
lazy[o][id] = op;
}
}
} else {
for(int id = 0; id < MAXLOGAI; ++id) {
if(!(x & (1 << id))) {
st[o][id] = 0;
lazy[o][id] = op;
}
}
}
} else {
int mid = l + r >> 1;
if(ql <= mid)
Update(o << 1, l, mid, ql, qr, op, x);
if(qr >= mid + 1)
Update(o << 1 | 1, mid + 1, r, ql, qr, op, x);
PushUp(o);
}
}
inline ll Query(const int &o, const int &l, const int &r, const int &ql, const int &qr) {
if(l != r)
PushDown(o, l, r);
if(ql <= l && r <= qr && (r - l + 1) <= (65535)) {
ll res = 0;
for(int id = 0; id < MAXLOGAI; ++id)
res += 1ll * (1 << id) * (st[o][id]);
return res;
} else {
ll res = 0;
int mid = l + r >> 1;
if(ql <= mid)
res += Query(o << 1, l, mid, ql, qr);
if(qr >= mid + 1)
res += Query(o << 1 | 1, mid + 1, r, ql, qr);
return res;
}
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // local
int T, n, m;
Read(T);
while(T--) {
Read(n), Read(m);
Build(1, 1, n);
char ops[10];
for(int i = 1, l, r, x; i <= m; ++i) {
ReadString(ops);
if(ops[0] == 'S') {
Read(l), Read(r);
++l, ++r;
ll res = Query(1, 1, n, l, r);
Write(res);
} else {
Read(x), Read(l), Read(r);
++l, ++r;
if(ops[0] == 'X') {
Update(1, 1, n, l, r, 1, x);
} else if(ops[0] == 'O') {
Update(1, 1, n, l, r, 2, x);
} else if(ops[0] == 'A') {
Update(1, 1, n, l, r, 3, x);
}
}
}
}
}