线段树专题测试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"
", 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"
", 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表，而是一种很粗暴的方法——树套树(据说线段树套线段树特别牛逼)。

　　一个线段树负责一行的最大公约数。套外面的线段树就负责合并列的线段树。还有可以加优化，查询的时候，查到的值为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
", 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 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/yyf0309/p/6337579.html