首页 > 代码库 > 【线段树区间修改】fzu2105Digits Count
【线段树区间修改】fzu2105Digits Count
/* 题意: 给出数组A,有以下几个操作: 1: AND(opn, L, R):把区间[L, R]中的元素A[i]改为A[i] & opn;;;;;; 2: OR(opn, L, R) :把区间[L, R]中的元素A[i]改为A[i] | opn;;;;;;; 3: XOR(opn, L, R):把区间[L, R]中的元素A[i]改为A[i] ^ opn;;;;;;; 4: SUM(L, R) :对区间[L, R]中的元素求和;;;; -------------------------------------------------------------------------------- 线段树区间修改的题目: -------------------------------------------------------------------------------- void build(int l, int r, int o)递归建树 { tree[o].l = l;结点的左端点 tree[o].r = r;结点的右端点 tree[o].num = -1;标记该区间的数是否相同 if(l == r)叶子结点 { scanf("%d",&tree[o].num); return ; } int M = (l + r)/2; build(l, M, lc); build(M+1, r, rc); if(tree[lc].num != -1 && tree[lc].num == tree[rc].num)向上更新 tree[o].num = tree[lc].num; } ------------------------------------------------------------------------------------ 1,2,3操作时数组的更新: int opreate(int op, int opn, int num)对应的操作 { if(op == 1) return num & opn;------------AND if(op == 2) return num | opn;------------OR if(op == 3) return num ^ opn;------------XOR } void update(int l, int r, int o, int opn, int op) { if(tree[o].l == l && tree[o].r == r && tree[o].num >= 0)找到该区间时,跟新区间内的元素,,即修改标记 { tree[o].num = opreate(op, opn, tree[o].num); return ; } if(tree[o].num >= 0)标记传递,起作用是把num的值向下传递即:pushdown函数 { tree[lc].num = tree[rc].num = tree[o].num; tree[o].num = -1;清除本节点的标记 } int mid = (tree[o].l + tree[o].r)/2; if(r <= mid)------------------------------------------------------------? update(l, r, lc, opn, op);更新左子树 else if(l > mid) update(l, r, rc, opn, op);更新右子树 else否则都要更新 { update(l, mid, lc, opn, op); update(mid+1, r, rc, opn, op); }------------------------------------------------------------------------? if(tree[lc].num != -1 && tree[lc].num == tree[rc].num)往上更新 tree[o].num = tree[lc].num; } ---------------------------------------------------------------------------------------- LL query(int l, int r, int o) { if(tree[o].l == l && tree[o].r == r && tree[o].num >= 0) return tree[o].num*(tree[o].r - tree[o].l+1); if(tree[o].num >= 0) { tree[lc].num = tree[rc].num = tree[o].num; tree[o].num = -1; } int mid = (tree[o].l + tree[o].r)/2; if(r <= mid) return query(l, r, lc); else if( l > mid) return query(l, r, rc); else return query(l, mid, lc)+query(mid+1, r, rc); if(tree[lc].num != -1 && tree[lc].num == tree[rc].num) tree[o].num = tree[lc].num; } -------------------------------------------------------------------------------------------- */ #include <iostream> #include <cstdio> #include <cstring> #define INF 0x3f3f3f3f #define lc o*2 #define rc o*2+1 using namespace std; const int MAXN = 1000010; typedef long long LL; int n, m; int a[MAXN]; struct node{ int l, r; int num; }tree[MAXN*4]; void build(int l, int r, int o) { tree[o].l = l; tree[o].r = r; tree[o].num = -1; if(l == r) { scanf("%d",&tree[o].num); return ; } int M = (l + r)/2; build(l, M, lc); build(M+1, r, rc); if(tree[lc].num != -1 && tree[lc].num == tree[rc].num) tree[o].num = tree[lc].num; } int opreate(int op, int opn, int num) { if(op == 1) return num & opn; if(op == 2) return num | opn; if(op == 3) return num ^ opn; } void update(int l, int r, int o, int opn, int op) { if(tree[o].l == l && tree[o].r == r && tree[o].num >= 0) { tree[o].num = opreate(op, opn, tree[o].num); return ; } if(tree[o].num >= 0) { tree[lc].num = tree[rc].num = tree[o].num; tree[o].num = -1; } int mid = (tree[o].l + tree[o].r)/2; if(r <= mid) update(l, r, lc, opn, op); else if(l > mid) update(l, r, rc, opn, op); else { update(l, mid, lc, opn, op); update(mid+1, r, rc, opn, op); } if(tree[lc].num != -1 && tree[lc].num == tree[rc].num) tree[o].num = tree[lc].num; } LL query(int l, int r, int o) { if(tree[o].l == l && tree[o].r == r && tree[o].num >= 0) return tree[o].num*(tree[o].r - tree[o].l+1); if(tree[o].num >= 0) { tree[lc].num = tree[rc].num = tree[o].num; tree[o].num = -1; } int mid = (tree[o].l + tree[o].r)/2; if(r <= mid) return query(l, r, lc); else if( l > mid) return query(l, r, rc); else return query(l, mid, lc)+query(mid+1, r, rc); if(tree[lc].num != -1 && tree[lc].num == tree[rc].num) tree[o].num = tree[lc].num; } int main() { freopen("input.txt","r",stdin); char op[5]; int opn, L, R; int T; cin>>T; while(T--) { scanf("%d%d", &n,&m); build(1, n, 1); while(m--) { scanf("%s",op); getchar(); if(op[0] == 'S') { scanf("%d%d",&L, &R); printf("%lld\n",query(L+1, R+1, 1)); } else { scanf("%d%d%d",&opn, &L, &R); if(op[0] == 'A') update(L+1, R+1, 1, opn, 1); if(op[0] == 'O') update(L+1, R+1, 1, opn, 2); if(op[0] == 'X') update(L+1, R+1, 1, opn, 3); } } } return 0; }
---------------------------------------------------------------------
wuwuwuwuuuuwuuwuwuuwuwuwuwuuw....................................
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。