首页 > 代码库 > [题解]线段树专题测试2017.1.21

[题解]线段树专题测试2017.1.21

2024-09-01 23:22:36   223人阅读

技术分享

　　很单纯的一道线段树题。稍微改一下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


联系
我们