网站建设与管理实施方案,delphi 做直播网站,韶关网站建设的公司,北京软件开发培训Problem - E - Codeforces 区间求和#xff0c;区间异或的操作跟线段树的区间求和、区间相见相似#xff0c;考虑用线段树。
发现数组初始值最多是1e6#xff0c;有不到25位#xff0c;可以知道异或最大值是这些位数全是1的情况。
发现可以对每一位进行运算就和。
我们开…Problem - E - Codeforces 区间求和区间异或的操作跟线段树的区间求和、区间相见相似考虑用线段树。
发现数组初始值最多是1e6有不到25位可以知道异或最大值是这些位数全是1的情况。
发现可以对每一位进行运算就和。
我们开23个线段树表示每一位的情况根据位运算求出每一位的贡献即可。
注意ans需要开LL且数组不能开大不能全用long long。
#include iostream
#include vector
#include string
#include cstring
#include set
#include map
#include queue
#include ctime
#include random
#include sstream
#include numeric
#include stdio.h
#include functional
#include bitset
#include algorithm
using namespace std;// #define Multiple_groups_of_examples
// #define int_to_long_long
#define IOS std::cout.tie(0);std::cin.tie(0)-sync_with_stdio(false); // 开IOS需要保证只使用Cpp io流 *
#define dbgnb(a) std::cout #a a \n;
#define dbgtt cout !!!test!!! \n;
#define rep(i,x,n) for(int i x; i n; i)#define all(x) (x).begin(),(x).end()
#define pb push_back
#define vf first
#define vs secondtypedef long long LL;
#ifdef int_to_long_long
#define int long long
#endif
typedef pairint,int PII;const int INF 0x3f3f3f3f;
const int N 2e5 21;// 异或 线段树板子
struct SegTree {static const int N 1e5 21;struct node {int l, r;LL sum,lz;}tr[N 2];// 左子树int w[N];inline int ls(int p) {return p1; }// 右子树inline int rs(int p) {return p1|1; }// 向上更新void pushup(int u) {tr[u].sum tr[ls(u)].sum tr[rs(u)].sum;}// 向下回溯时先进行更新void pushdown(int u) { // 懒标记该节点曾经被修改但其子节点尚未被更新。auto root tr[u], right tr[rs(u)], left tr[ls(u)];if(root.lz) {right.lz ^1; right.sum (right.r - right.l 1 - right.sum);left.lz ^ 1; left.sum (left.r - left.l 1 - left.sum);root.lz 0;}}// 建树void build(int u, int l, int r) {if(l r) tr[u] {l, r, w[r], 0};else {tr[u] {l,r}; // 容易忘int mid l r 1;build(ls(u), l, mid), build(rs(u), mid 1, r);pushup(u);}}// 修改void modify(int u, int l, int r, int d) {if(tr[u].l l tr[u].r r) {tr[u].lz ^ 1;tr[u].sum (tr[u].r - tr[u].l 1 - tr[u].sum);}else {pushdown(u);int mid tr[u].l tr[u].r 1;if(l mid) modify(ls(u), l ,r, d);if(r mid) modify(rs(u), l, r, d);pushup(u);}}// 查询LL query(int u, int l, int r) {if(tr[u].l l tr[u].r r) {return tr[u].sum;}pushdown(u);int mid tr[u].l tr[u].r 1;LL sum 0;if(l mid) sum query(ls(u), l, r);if(r mid ) sum query(rs(u), l, r);return sum;}
}tree[23];void inpfile();
void solve() {int n; cinn;vectorint ad(n 1);for(int i 1; i n; i) cinad[i];for(int i 1; i n; i) {for(int j 0; j 22; j) {// ad[i] 的第j位是0还是1tree[j].w[i] (ad[i] j) 1;}}// 建树for(int i 0; i 22; i) tree[i].build(1,1,n);int q; cinq;while(q--) {int opt, x, y, v;cinoptxy;if(opt 1) {LL ans 0;// 求出每一位的贡献相加即为答案for(int i 0; i 22; i) ans (LL)tree[i].query(1,x,y) * (1 i);coutansendl;} else {cinv;for(int i 0; i 22; i) {// 每一位进行修改int t (v i) 1;if(!t) continue;tree[i].modify(1,x,y,1);}}}
}
#ifdef int_to_long_long
signed main()
#else
int main()
#endif{#ifdef Multiple_groups_of_examplesint T; cinT;while(T--)#endifsolve();return 0;
}
void inpfile() {#define mytest#ifdef mytestfreopen(ANSWER.txt, w,stdout);#endif
}XOR on Segment - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
CF242E XOR on Segment 拆位线段树_牛客博客 (nowcoder.net)
