首页 > 代码库 > [题解]线段树专题测试2017.1.21
[题解]线段树专题测试2017.1.21
很单纯的一道线段树题。稍微改一下pushDown()就行了。
Code(线段树模板竟然没超100行)
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 using namespace std; 15 typedef bool boolean; 16 #ifdef WIN32 17 #define AUTO "%I64d" 18 #else 19 #define AUTO "%lld" 20 #endif 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class SegTreeNode { 38 public: 39 long long sum; 40 int l, r; 41 SegTreeNode *left, *right; 42 int lazy; 43 SegTreeNode():sum(0), l(0), r(0), left(NULL), right(NULL), lazy(0){ } 44 SegTreeNode(int l, int r):sum(0), l(l), r(r), left(NULL), right(NULL), lazy(0){ } 45 46 inline void pushUp(){ 47 this->sum = this->left->sum + this->right->sum; 48 } 49 50 inline void pushDown(){ 51 left->sum = (left->r - left->l + 1) * 1LL * lazy; 52 left->lazy = lazy; 53 right->sum = (right->r - right->l + 1) * 1LL * lazy; 54 right->lazy = lazy; 55 lazy = 0; 56 } 57 }SegTreeNode; 58 59 typedef class SegTree { 60 public: 61 SegTreeNode* root; 62 63 SegTree():root(NULL){ } 64 SegTree(int size, int* list){ 65 build(root, 1, size, list); 66 } 67 68 void build(SegTreeNode*& node, int l, int r, int* list){ 69 node = new SegTreeNode(l, r); 70 if(l == r){ 71 node->sum = list[l]; 72 return; 73 } 74 int mid = (l + r) >> 1; 75 build(node->left, l, mid, list); 76 build(node->right, mid + 1, r, list); 77 node->pushUp(); 78 } 79 80 void update(SegTreeNode*& node, int l, int r, long long val){ 81 if(node->l == l && node->r == r){ 82 node->sum = (r - l + 1) * val; 83 node->lazy = val; 84 return; 85 } 86 if(node->lazy) node->pushDown(); 87 int mid = (node->l + node->r) >> 1; 88 if(r <= mid) update(node->left, l, r, val); 89 else if(l > mid) update(node->right, l, r, val); 90 else{ 91 update(node->left, l, mid, val); 92 update(node->right, mid + 1, r, val); 93 } 94 node->pushUp(); 95 } 96 97 long long query(SegTreeNode*& node, int l, int r){ 98 if(node->l == l && node->r == r){ 99 return node->sum;100 }101 if(node->lazy) node->pushDown();102 int mid = (node->l + node->r) >> 1;103 if(r <= mid) return query(node->left, l, r);104 if(l > mid) return query(node->right, l, r);105 return query(node->left, l, mid) + query(node->right, mid + 1, r);106 }107 }SegTree;108 109 int n, m;110 int* list;111 SegTree st;112 113 inline void init(){114 readInteger(n);115 list = new int[(const int)(n + 1)];116 for(int i = 1; i <= n; i++)117 readInteger(list[i]);118 readInteger(m);119 st = SegTree(n, list);120 }121 122 inline void solve(){123 char cmd[10];124 int a, b, c;125 while(m--){126 scanf("%s", cmd);127 readInteger(a);128 readInteger(b);129 if(cmd[0] == ‘m‘){130 readInteger(c);131 st.update(st.root, a, b, c);132 }else{133 long long res = st.query(st.root, a, b);134 printf(AUTO"\n", res);135 }136 }137 }138 139 int main(){140 freopen("setsum.in", "r", stdin);141 freopen("setsum.out", "w", stdout);142 init();143 solve();144 return 0;145 }
dfs序弄一下然后加一个树状数组/线段树就可以轻松应付后面的操作，然而我不小心在建树的时候，用下标为节点编号进行建树而不是访问时间(这个问题很诡异，看着数组完全不知道在干什么)，于是愉快地只有10分。
用树状数组要快一点，只不过我比较懒，一二题的线段树模板差距不但，粘过来改一下就行了。
Code
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 using namespace std; 15 typedef bool boolean; 16 #ifdef WIN32 17 #define AUTO "%I64d" 18 #else 19 #define AUTO "%lld" 20 #endif 21 #define smin(a, b) (a) = min((a), (b)) 22 #define smax(a, b) (a) = max((a), (b)) 23 template<typename T> 24 inline void readInteger(T& u){ 25 char x; 26 int aFlag = 1; 27 while(!isdigit((x = getchar())) && x != ‘-‘); 28 if(x == ‘-‘){ 29 aFlag = -1; 30 x = getchar(); 31 } 32 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 33 ungetc(x, stdin); 34 u *= aFlag; 35 } 36 37 typedef class SegTreeNode { 38 public: 39 long long sum; 40 int l, r; 41 SegTreeNode *left, *right; 42 SegTreeNode():sum(0), l(0), r(0), left(NULL), right(NULL){ } 43 SegTreeNode(int l, int r):sum(0), l(l), r(r), left(NULL), right(NULL){ } 44 inline void pushUp(){ 45 this->sum = this->left->sum + this->right->sum; 46 } 47 }SegTreeNode; 48 49 typedef class SegTree { 50 public: 51 SegTreeNode* root; 52 53 SegTree():root(NULL){ } 54 SegTree(int size, int* list, int* keyer){ 55 build(root, 1, size, list, keyer); 56 } 57 58 void build(SegTreeNode*& node, int l, int r, int* list, int* keyer){ 59 node = new SegTreeNode(l, r); 60 if(l == r){ 61 node->sum = list[keyer[l]]; 62 return; 63 } 64 int mid = (l + r) >> 1; 65 build(node->left, l, mid, list, keyer); 66 build(node->right, mid + 1, r, list, keyer); 67 node->pushUp(); 68 } 69 70 void update(SegTreeNode*& node, int index, long long val){ 71 if(node->l == index && node->r == index){ 72 node->sum += val; 73 return; 74 } 75 int mid = (node->l + node->r) >> 1; 76 if(index <= mid) update(node->left, index, val); 77 else update(node->right, index, val); 78 node->pushUp(); 79 } 80 81 long long query(SegTreeNode*& node, int l, int r){ 82 if(node->l == l && node->r == r){ 83 return node->sum; 84 } 85 int mid = (node->l + node->r) >> 1; 86 if(r <= mid) return query(node->left, l, r); 87 if(l > mid) return query(node->right, l, r); 88 return query(node->left, l, mid) + query(node->right, mid + 1, r); 89 } 90 }SegTree; 91 92 typedef class Edge{ 93 public: 94 int end; 95 int next; 96 Edge(const int end = 0, const int next = 0):end(end), next(next){ } 97 }Edge; 98 99 typedef class MapManager{100 public:101 int ce;102 int *h;103 Edge* edges;104 MapManager():ce(0), h(NULL), edges(NULL){ }105 MapManager(int points, int limits):ce(0){106 h = new int[(const int)(points + 1)];107 edges = new Edge[(const int)(limits + 1)];108 memset(h, 0, sizeof(int) * (points + 1));109 }110 inline void addEdge(int from, int end){111 edges[++ce] = Edge(end, h[from]);112 h[from] = ce;113 }114 inline void addDoubleEdge(int from, int end){115 addEdge(from, end);116 addEdge(end, from);117 }118 Edge& operator [](int pos){119 return edges[pos];120 }121 }MapManager;122 123 #define m_begin(g, i) (g).h[(i)]124 125 int n, m;126 int cnt = 0;127 int* list;128 int* keyer;129 int* visitID;130 int* exitID;131 SegTree st;132 MapManager g;133 134 void dfs(int node, int last){135 visitID[node] = ++cnt;136 keyer[cnt] = node;137 for(int i = m_begin(g, node); i != 0; i = g[i].next){138 int &e = g[i].end;139 if(e == last) continue;140 dfs(e, node);141 }142 exitID[node] = cnt;143 }144 145 inline void init(){146 readInteger(n);147 list = new int[(const int)(n + 1)];148 g = MapManager(n, n * 2);149 for(int i = 1; i <= n; i++)150 readInteger(list[i]);151 for(int i = 1, a, b; i < n; i++){152 readInteger(a);153 readInteger(b);154 g.addDoubleEdge(a, b);155 }156 visitID = new int[(const int)(n + 1)];157 exitID = new int[(const int)(n + 1)];158 keyer = new int[(const int)(n + 1)];159 dfs(1, 0);160 readInteger(m);161 st = SegTree(n, list, keyer);162 }163 164 inline void solve(){165 char cmd[10];166 int a, b;167 while(m--){168 scanf("%s", cmd);169 readInteger(a);170 if(cmd[0] == ‘m‘){171 readInteger(b);172 st.update(st.root, visitID[a], b);173 }else{174 long long res = st.query(st.root, visitID[a], exitID[a]);175 printf(AUTO"\n", res);176 }177 }178 }179 180 int main(){181 freopen("subtree.in", "r", stdin);182 freopen("subtree.out", "w", stdout);183 init();184 solve();185 return 0;186 }
不过我并没有写st表，而是一种很粗暴的方法——树套树(据说线段树套线段树特别牛逼)。
一个线段树负责一行的最大公约数。套外面的线段树就负责合并列的线段树。虽然理论上死得很惨（莫名其妙地多出了一个O(log2n * log2m))，但是可以加优化，查询的时候，查到的值为1，就return 1。实测效果不错，综合下来，windows随机数据才0.8s。(然而诡异的cena需要1.9s，指针户吃亏啊。。。)
Code（初次树套树比平衡树短）
1 #include<iostream> 2 #include<sstream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstdlib> 6 #include<cstring> 7 #include<cctype> 8 #include<queue> 9 #include<set> 10 #include<map> 11 #include<stack> 12 #include<vector> 13 #include<algorithm> 14 #include<ctime> 15 using namespace std; 16 typedef bool boolean; 17 #ifdef WIN32 18 #define AUTO "%I64d" 19 #else 20 #define AUTO "%lld" 21 #endif 22 #define smin(a, b) (a) = min((a), (b)) 23 #define smax(a, b) (a) = max((a), (b)) 24 template<typename T> 25 inline void readInteger(T& u){ 26 char x; 27 int aFlag = 1; 28 while(!isdigit((x = getchar())) && x != ‘-‘); 29 if(x == ‘-‘){ 30 aFlag = -1; 31 x = getchar(); 32 } 33 for(u = x - ‘0‘; isdigit((x = getchar())); u = u * 10 + x - ‘0‘); 34 ungetc(x, stdin); 35 u *= aFlag; 36 } 37 38 template<typename T> 39 inline T gcd(T a, T b){ 40 return (b == 0) ? (a) : (gcd(b, a % b)); 41 } 42 43 template<typename T> 44 class Matrix{ 45 public: 46 T* p; 47 int lines, rows; 48 Matrix():p(NULL), lines(0), rows(0){ } 49 Matrix(int rows, int lines):rows(rows), lines(lines){ 50 p = new T[rows * lines]; 51 } 52 T* operator [](int pos){ 53 return p + pos * lines; 54 } 55 }; 56 57 typedef class SegTreeNode1{ 58 public: 59 int val; 60 SegTreeNode1 *left, *right; 61 SegTreeNode1():left(NULL), right(NULL), val(0){ } 62 63 inline void pushUp(){ 64 val = gcd(left->val, right->val); 65 } 66 }SegTreeNode1; 67 68 typedef class SegTree1 { 69 public: 70 SegTreeNode1* root; 71 72 SegTree1():root(NULL){ } 73 SegTree1(int size, int* list){ 74 build(root, 1, size, list); 75 } 76 77 void build(SegTreeNode1*& node, int l, int r, int* list){ 78 node = new SegTreeNode1(); 79 if(l == r){ 80 node->val = list[l]; 81 return; 82 } 83 int mid = (l + r) >> 1; 84 build(node->left, l, mid, list); 85 build(node->right, mid + 1, r, list); 86 node->pushUp(); 87 } 88 89 int query(SegTreeNode1*& node, int l, int r, int from, int end){ 90 if(l == from && r == end) return node->val; 91 int mid = (l + r) >> 1; 92 if(end <= mid) return query(node->left, l, mid, from, end); 93 if(from > mid) return query(node->right, mid + 1, r, from, end); 94 int a = query(node->left, l, mid, from, mid); 95 if(a == 1) return 1; 96 int b = query(node->right, mid + 1, r, mid + 1, end); 97 return gcd(a, b); 98 } 99 }SegTree1;100 101 void merge(SegTreeNode1*& a, SegTreeNode1*& b, SegTreeNode1*& res){102 res = new SegTreeNode1();103 res->val = gcd(a->val, b->val);104 if(a->left == NULL) return;105 merge(a->left, b->left, res->left);106 merge(a->right, b->right, res->right);107 }108 109 typedef class SegTreeNode2 {110 public:111 SegTree1 val;112 SegTreeNode2* left, *right;113 SegTreeNode2():left(NULL), right(NULL){114 val = SegTree1();115 }116 117 inline void pushUp(){118 merge(left->val.root, right->val.root, val.root);119 }120 }SegTreeNode2;121 122 typedef class SegTree2{123 public:124 SegTreeNode2* root;125 126 SegTree2():root(NULL){ }127 SegTree2(int n, int m, Matrix<int>& a){128 build(root, 1, n, m, a);129 }130 131 void build(SegTreeNode2*& node, int l, int r, int m, Matrix<int>& a){132 node = new SegTreeNode2();133 if(l == r){134 node->val = SegTree1(m, a[l]);135 return;136 }137 int mid = (l + r) >> 1;138 build(node->left, l, mid, m, a);139 build(node->right, mid + 1, r, m, a);140 node->pushUp();141 }142 143 int query(SegTreeNode2*& node, int l, int r, int from, int end, int m, int from1, int end1){144 if(l == from && r == end){145 return node->val.query(node->val.root, 1, m, from1, end1);146 }147 int mid = (l + r) >> 1;148 if(end <= mid) return query(node->left, l, mid, from, end, m, from1, end1);149 if(from > mid) return query(node->right, mid + 1, r, from, end, m, from1, end1);150 int a = query(node->left, l, mid, from, mid, m, from1, end1);151 if(a == 1) return 1;152 int b = query(node->right, mid + 1, r, mid + 1, end, m, from1, end1);153 return gcd(a, b);154 }155 }SegTree2;156 157 int n, m, q;158 Matrix<int> mat;159 SegTree2 st;160 161 inline void init(){162 readInteger(n);163 readInteger(m);164 readInteger(q);165 mat = Matrix<int>(n + 1, m + 1);166 for(int i = 1; i <= n; i++){167 for(int j = 1; j <= m; j++){168 readInteger(mat[i][j]);169 }170 }171 st = SegTree2(n, m, mat);172 }173 174 inline void solve(){175 int x1, x2, y1, y2;176 while(q--){177 readInteger(x1);178 readInteger(y1);179 readInteger(x2);180 readInteger(y2);181 int res = st.query(st.root, 1, n, x1, x2, m, y1, y2);182 printf("%d\n", res);183 }184 }185 186 int main(){187 freopen("matgcd.in", "r", stdin);188 freopen("matgcd.out", "w", stdout);189 init();190 solve();191 return 0;192 }
[题解]线段树专题测试2017.1.21
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。