NC19837. 位运算？位运算！
描述
输入描述
第一行n,q表示数列长度及操作次数。
第二行n个数表示初始序列。
接下来q行表示操作。
操作格式如下：
一行表示一个操作。所有操作形如 opt l r v。
opt=1 表示将区间[l,r]循环右移v位。
opt=2 表示将区间[l,r]循环左移v位。
opt=3 表示将区间[l,r]按位或上v。
opt=4 表示将区间[l,r]按位与上v。
opt=5 询问区间[l,r]的和。
保证opt=1或2时 1 ≤ v ≤ 20
注意：为了优化你的做题体验，操作5也会输入一个v，但是是没有意义的。
注意：循环左右移在20个二进制位的意义下进行
输出描述
对于每个opt=5的操作，输出一个数表示答案。
示例1
输入:
10 10 10112 23536 1305 7072 12730 29518 12315 3459 12435 29055 4 5 10 12373 2 1 6 7 5 4 10 24895 1 1 4 8 5 3 7 7767 5 7 9 6127 4 2 8 30971 5 4 10 2663 1 7 10 1 1 2 9 5
输出:
2001530 1600111 24611 49482
C++14(g++5.4) 解法, 执行用时: 1707ms, 内存消耗: 45384K, 提交时间: 2019-10-27 16:54:25
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second
typedef long long LL;
const int N = 2e5 + 10;
int s[N << 2][21], tmp[21], lazy[N << 2];
int a[N];
int n, q;
int op, l, r, v;
LL ans;
void rotate(int x, int v){
rep(i, 0, 19) tmp[i] = s[x][(i + v) % 20];
rep(i, 0, 19) s[x][i] = tmp[i];
lazy[x] += v;
lazy[x] %= 20;
}
void build(int x, int l, int r){
if (l == r){
rep(i, 0, 19) s[x][i] = (a[l] >> i) & 1;
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
rep(i, 0, 19) s[x][i] = s[x << 1][i] + s[x << 1 | 1][i];
}
void update(int x, int L, int R){
if (l <= L && R <= r){
if (op == 1) rotate(x, v);
else if (op == 2) rotate(x, 20 - v);
else if (op == 3){
rep(i, 0, 19) if ((v >> i) & 1) s[x][i] = R - L + 1;
}
else if (op == 4){
rep(i, 0, 19) if (!((v >> i) & 1)) s[x][i] = 0;
}
else{
rep(i, 0, 19) ans += ((LL)s[x][i] << i);
}
return ;
}
int len = R - L + 1, mid = (L + R) >> 1;
if (lazy[x]){
rotate(x << 1, lazy[x]);
rotate(x << 1 | 1, lazy[x]);
lazy[x] = 0;
}
rep(i, 0, 19){
if (s[x][i] == len){
s[x << 1][i] = len - len / 2;
s[x << 1 | 1][i] = len / 2;
}
else if (s[x][i] == 0){
s[x << 1][i] = 0;
s[x << 1 | 1][i] = 0;
}
}
if (l <= mid) update(x << 1, L, mid);
if (r > mid) update(x << 1 | 1, mid + 1, R);
rep(i, 0, 19) s[x][i] = s[x << 1][i] + s[x << 1 | 1][i];
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d%d", &n, &q);
rep(i, 1, n) scanf("%d", a + i);
build(1, 1, n);
while (q--){
scanf("%d%d%d%d", &op, &l, &r, &v);
ans = 0;
update(1, 1, n);
if (op == 5) printf("%lld\n", ans);
/*for (int i=1; i<=n; i++){
l=i,r=i,op=5;
update(1,1,n);
printf ("...%lld%c",ans,i==n?'\n':' ');
}*/
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1357ms, 内存消耗: 45152K, 提交时间: 2018-10-20 14:28:35
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
#define MP make_pair
#define fi first
#define se second
typedef long long LL;
const int N = 2e5 + 10;
int s[N << 2][21], tmp[21], lazy[N << 2];
int a[N];
int n, q;
int op, l, r, v;
LL ans;
void rotate(int x, int v){
rep(i, 0, 19) tmp[i] = s[x][(i + v) % 20];
rep(i, 0, 19) s[x][i] = tmp[i];
lazy[x] += v;
lazy[x] %= 20;
}
void build(int x, int l, int r){
if (l == r){
rep(i, 0, 19) s[x][i] = (a[l] >> i) & 1;
return;
}
int mid = (l + r) >> 1;
build(x << 1, l, mid);
build(x << 1 | 1, mid + 1, r);
rep(i, 0, 19) s[x][i] = s[x << 1][i] + s[x << 1 | 1][i];
}
void update(int x, int L, int R){
if (l <= L && R <= r){
if (op == 1) rotate(x, v);
else if (op == 2) rotate(x, 20 - v);
else if (op == 3){
rep(i, 0, 19) if ((v >> i) & 1) s[x][i] = R - L + 1;
}
else if (op == 4){
rep(i, 0, 19) if (!((v >> i) & 1)) s[x][i] = 0;
}
else{
rep(i, 0, 19) ans += ((LL)s[x][i] << i);
}
return ;
}
int len = R - L + 1, mid = (L + R) >> 1;
if (lazy[x]){
rotate(x << 1, lazy[x]);
rotate(x << 1 | 1, lazy[x]);
lazy[x] = 0;
}
rep(i, 0, 19){
if (s[x][i] == len){
s[x << 1][i] = len - len / 2;
s[x << 1 | 1][i] = len / 2;
}
else if (s[x][i] == 0){
s[x << 1][i] = 0;
s[x << 1 | 1][i] = 0;
}
}
if (l <= mid) update(x << 1, L, mid);
if (r > mid) update(x << 1 | 1, mid + 1, R);
rep(i, 0, 19) s[x][i] = s[x << 1][i] + s[x << 1 | 1][i];
}
int main(){
scanf("%d%d", &n, &q);
rep(i, 1, n) scanf("%d", a + i);
build(1, 1, n);
while (q--){
scanf("%d%d%d%d", &op, &l, &r, &v);
ans = 0;
update(1, 1, n);
if (op == 5) printf("%lld\n", ans);
}
return 0;
}