线段树(ALGO-8重刷)

  1. #include <iostream>
  2. #define max(a,b) a > b ? a : b;
  3. using namespace std;
  5. const int MAXN = 1e2 + 1;
  6. int num = 0;
  8. /*线段树元素结构体*/
  9. struct NODE {
  10.     int l;
  11.     int r;
  12.     int maxValue;
  13.     int sum;
  14. }node[MAXN];
  16. /*初始化线段树*/
  17. void init(int i,int l,int r) {
  18.     node[i].l = l;
  19.     node[i].r = r;
  20.     node[i].maxValue = 0;
  21.     node[i].sum = 0;
  22.     num++;
  24.     if (node[i].l != node[i].r) {
  25.         int mid = (l + r) / 2;
  26.         init(2 * i,l, mid);
  27.         init(2 * i + 1,mid + 1, r);
  28.     }
  29. }
  31. /*插入线段树元素*/
  32. void insert(int i,int pos,int value) {
  33.     if (node[i].l == node[i].r) {  //错误五：“node[i].l = node[i].r” 判断条件错误，排查费时
  34.         node[i].maxValue = value;
  35.         node[i].sum = value;
  36.         return;  //错误一：遗漏return
  37.     }
  39.     int mid = (node[i].l + node[i].r) / 2;
  40.     if (pos <= mid) insert(2 * i, pos, value);
  41.     else insert(2 * i + 1, pos, value);
  43.     /*同时初始化最大权值和总权值*/
  44.     node[i].maxValue = max(node[2 * i].maxValue, node[2 * i + 1].maxValue);
  45.     node[i].sum = node[2 * i].sum + node[2 * i + 1].sum;
  46. }
  48. /*查找范围内元素个体最大权值*/
  49. int search_max(int i, int x, int y) {
  50.     if (node[i].l == x && node[i].r == y) {  //错误三：node[i].l == node[i].r 条件判断错误
  51.         return node[i].maxValue;
  52.     }
  53.     int mid = (node[i].l + node[i].r) / 2;
  54.     if (y <= mid) return search_max(2 * i, x, y);  //错误二：还是遗漏return
  55.     else if (x > mid) return search_max(2 * i + 1, x, y);
  56.     else {
  57.         return max(search_max(2 * i, x, mid), search_max(2 * i + 1, mid + 1, y));
  58.     }
  59. }
  61. /*查找范围内元素的权值和*/
  62. int search_sum(int i, int x, int y) {
  63.     if (x == node[i].l && y == node[i].r) {  //错误四：还是 node[i].l == node[i].r 条件判断错误
  64.         return node[i].sum;
  65.     }
  66.     int mid = (node[i].l + node[i].r) / 2;
  67.     if (y <= mid) return search_sum(2 * i, x, y);  
  68.     else if (x > mid) return search_sum(2 * i + 1, x, y);
  69.     else {
  70.         return search_sum(2 * i, x, mid) + search_sum(2 * i + 1, mid + 1, y);
  71.     }
  72. }
  74. int main() {
  75.     int n, m;
  76.     cin >> n >> m;
  78.     /*初始化*/
  79.     init(1,1,n);
  81.     /*看树*/
  82.     cout << "show tree after init" << endl;
  83.     int count = 1;
  84.     for (int i = 1; i <= num; i++) {
  85.         if (i >= pow(2, count)) {
  86.             cout << endl;
  87.             count++;
  88.         }
  89.         cout << "( " << node[i].l << ',' << node[i].r << " )";
  90.     }
  91.     cout << endl;
  93.     /*插入*/
  94.     int value;
  95.     for (int i = 1; i <= n; i++) {
  96.         cin >> value;
  97.         insert(1, i, value);
  98.     }
  100.     /*再看树*/
  101.     cout << "show tree after insert" << endl;
  102.     count = 1;
  103.     for (int i = 1; i <= num; i++) {
  104.         if (i >= pow(2, count)) {
  105.             cout << endl;
  106.             count++;
  107.         }
  108.         cout << "( max:" << search_max(i,node[i].l,node[i].r) <<" ; sum:"
  109.             << search_sum(i, node[i].l, node[i].r) << " )";
  110.     }
  111.     cout << endl;
  113.     /*题目要求*/
  114.     for (int i = 1; i <= m; i++) {
  115.         int p, x, y;
  116.         cin >> p >> x >> y;
  117.         if (p == 1) insert(1, x, y);
  118.         if (p == 2) cout << "sum = "<< search_sum(1, x, y) << endl;
  119.         if (p == 3) cout << "max = "<< search_max(1, x, y) << endl;
  120.     }
  122.     return 0;
  123. }
  124. /*
  125. 4 3
  126. 1 2 3 4
  127. 2 1 3
  128. 1 4 3
  129. 3 1 4*/

线段树提升，懒惰标记

  1. #include <iostream>
  2. #include <cmath>
  3. using namespace std;
  5. const int MAXN = 1e2 + 1;
  6. int num = 0;
  7. struct NODE {
  8.     int l;
  9.     int r;
  10.     int sum;
  11.     int tag;  //懒惰标记
  12. }node[MAXN];
  14. void init(int i, int left, int right);  //初始化线段树
  15. void chahgeRespectively(int i, int pos, int value);  //单点更新（错误1）
  16. void changeSegment(int i, int x, int y, int value);  //区间更新（错误5）
  17. int findSum(int i, int x, int y);  //查询区间内权值总和（错误2,4,6）
  18. void pushDown(int i);  //下推标记（错误3）
  19. void update(int i); //节点递归更新
  20. void showTree();  //看树
  22. int main() {
  23.     int n, x, y, t, pos;
  24.     cin >> x >> y;
  25.     init(1, x, y);
  26.     showTree();  //showTree
  28.     /*单点更新*/
  29.     cin >> n;
  30.     for (int i = 0; i < n; i++) {
  31.         cin >> pos >> t;
  32.         chahgeRespectively(1, pos, t);
  33.     }
  34.     showTree();  //showTree
  36.     /*区间更新测试*/
  37.     changeSegment(1, 1, 3, 1);
  38.     showTree();  //showTree
  40.     changeSegment(1, 2, 4, 2);
  41.     showTree();  //showTree
  43.     /*查询函数测试*/
  44.     cout << "test F_findSum:" << endl;
  45.     showTree();
  46.     cout<<findSum(1, 2, 4);
  48.     return 0;
  49. }
  51. /*初始化结点*/
  52. void init(int i, int left, int right) {
  53.     node[i].l = left;
  54.     node[i].r = right;
  55.     node[i].sum = 0;
  56.     node[i].tag = 0;
  57.     num++;
  59.     if (node[i].l != node[i].r) {
  60.         int mid = (node[i].l + node[i].r) / 2;
  61.         init(2 * i, left, mid);
  62.         init(2 * i + 1, mid + 1, right);
  63.     }
  64. }
  65. /*节点递归更新*/
  66. void update(int i) {
  67.     node[i].sum = node[2 * i].sum + node[2 * i + 1].sum;
  68.     return;
  69. }
  70. /*下推一次懒惰标记*/
  71. void pushDown(int i) {
  72.     cout << endl << "i = " << i << endl;
  73.     if (node[i].l == node[i].r)  //错误三：“叶节点无需操作”，部分情况下节点tag要清零
  74.     {
  75.         node[i].tag = 0;  //即使这次叶节点tag不清零答案没影响sum
  76.         showTree();
  77.         return;
  78.     }
  79.     /*更新到左右子节点，清除自身tag*/
  80.     node[2 * i].sum += (node[2 * i].r - node[2 * i].l + 1) * node[i].tag;
  81.     node[2 * i + 1].sum += (node[2 * i + 1].r - node[2 * i + 1].l + 1) * node[i].tag;
  82.     node[2 * i].tag += node[i].tag;
  83.     node[2 * i + 1].tag += node[i].tag;
  84.     node[i].tag = 0;
  85.     showTree();
  86.     return;
  87. }
  88. /*单点更新*/
  89. void chahgeRespectively(int i,int pos,int value) {
  90.     if (node[i].l == node[i].r) {
  91.         node[i].sum = value;
  92.         return;  //错误一：再次漏了return
  93.     }
  94.     int mid = (node[i].l + node[i].r) / 2;
  95.     if (pos <= mid) { chahgeRespectively(2 * i, pos, value); }
  96.     if (pos > mid) { chahgeRespectively(2 * i + 1, pos, value); }
  98.     update(i);
  99. }
  100. /*区间更新*/
  101. void changeSegment(int i, int x, int y, int value) {
  102.     if (node[i].tag) pushDown(i);  //如果已经有标记，下推标记
  104.     if (node[i].l == x && node[i].r == y) {  //正中靶心,信息只更新到该节点，并打上标记
  105.         node[i].sum += (node[i].r - node[i].l + 1) * value;
  106.         node[i].tag += value;
  107.         return;
  108.     }
  109.     int mid = (node[i].l + node[i].r) / 2;
  110.     if (y <= mid) {
  111.         changeSegment(2 * i, x, y, value);
  112.     }
  113.     else if (x > mid) {    //错误五：同错误四，else if (x >= mid)找区间判断条件错误
  114.         changeSegment(2 * i + 1, x, y, value);
  115.     }
  116.     else {
  117.         changeSegment(2 * i, x, mid, value);  
  118.         changeSegment(2 * i + 1, mid + 1, y, value);
  119.     }
  120.     update(i);
  121. }
  122. /*查询区间内权值总和*/
  123. int findSum(int i, int x, int y) {
  124.     if (node[i].tag) pushDown(i);  //查询节点有标记，下推标记
  125.     if (node[i].l == x && node[i].r == y) {  //正中靶心
  126.         return node[i].sum;
  127.     }
  128.     int mid = (node[i].l + node[i].r) / 2;
  129.     if (y <= mid) return findSum(2 * i, x, y);  //错误二：if (y <= node[i].l) 条件写错
  130.     else if(x > mid) return findSum(2 * i + 1, x, y);  //错误四：else if(x >= mid) 条件写错
  131.     else return findSum(2 * i, x, mid) + findSum(2 * i + 1, mid + 1, y);  //错误六：引用范围错误，压根没用到mid
  132. }
  133. /*查看线段树*/
  134. void showTree() {
  135.     cout << "show tree below" << endl;
  136.     int count = 1;
  137.     for (int i = 1; i <= num; i++) {
  138.         if (i >= pow(2, count)) {
  139.             cout << endl;
  140.             count++;
  141.         }
  142.         cout << "( " << node[i].l << ',' << node[i].r <<",sum:"<<node[i].sum<<",tag:"<<node[i].tag<< " )";
  143.     }
  144.     cout <<endl<<"Dode"<<endl;
  145. }
  146. /*
  147. 1 5
  148. 5
  149. 1 1
  150. 2 2
  151. 3 3
  152. 4 4
  153. 5 5*/

repeat 1

  • 重复犯了上次的两个错误，并犯了两个新错误

    1. void changeSegment(int i, int x, int y, int value) {
    2.   if (node[i].tag) pushDown(i);   //有tag,下推一次
    3.   if (x == node[i].l && node[i].r == y) {
    4.       node[i].sum += (node[i].r - node[i].l + 1) * value;
    5.       node[i].tag = value;
    6.       return;  //(新)错误三：这次区间更新没有加return
    7.   }
    8.   int mid = (node[i].l + node[i].r) / 2;
    9.   if (y <= mid) changeSegment(2 * i, x, y, value);  //错误一：y <= node[i].l 这种重复性错误
    10.   else if (x > mid) changeSegment(2 * i + 1, x, y, value);  //能不能长点脑子.jpg
    11.   else {
    12.       changeSegment(2 * i, x, mid, value);
    13.       changeSegment(2 * i + 1, mid + 1, y, value);
    14.   }
    16.   update(i);
    17. }
    18. void pushDown(int i) {
    19.   cout << endl << "i = " << i << endl;
    20.   if (node[i].l == node[i].r) {
    21.       node[i].tag = 0;
    22.       showTree();
    23.       return;
    24.   }
    25.   node[2 * i].sum +=  (node[2 * i].r - node[2 * i].l + 1) * node[i].tag;  //(新)错误四：“sum =”错了，是sum += 
    26.   node[2 * i + 1].sum += (node[2 * i + 1].r - node[2 * i + 1].l + 1) * node[i].tag;
    27.   node[2 * i].tag += node[i].tag;
    28.   node[2 * i + 1].tag += node[i].tag;
    29.   node[i].tag = 0;  //错误二，更新左右子节点后，没有清除自身tag
    30.   showTree();
    31. }

    洛谷线段树1

  • 建树插入一气呵成 ```cpp

    include

    include

    using namespace std; const int MAXN = 100010; int n, m; struct NODE { int l; int r; long long tag; long long sum; }node[4*MAXN+2]; int a[MAXN];

void built(int i,int left,int right) { node[i].l = left; node[i].r = right; if (node[i].l == node[i].r) { node[i].sum = a[left]; return; } int mid = (left + right) / 2; built(2 i, left, mid); built(2 i + 1, mid + 1, right); node[i].sum = node[2 i].sum + node[2 i + 1].sum; } void pushDown(int i) { if (node[i].l == node[i].r) { return; } node[2 i].sum += (node[2 i].r - node[2 i].l + 1) node[i].tag; node[2 i + 1].sum += (node[2 i + 1].r - node[2 i + 1].l + 1) node[i].tag; node[2 i].tag += node[i].tag; node[2 i + 1].tag += node[i].tag; node[i].tag = 0; } /chanfeSegment/ void addSegment(int i, int x, int y, int value) { if (x <= node[i].l && node[i].r <= y) { node[i].sum += (long long)(node[i].r - node[i].l + 1) value; node[i].tag += value; return;
} if (node[i].tag) pushDown(i); int mid = (node[i].l + node[i].r) / 2; if(x <= mid) addSegment(2 i, x, y, value); if(y > mid) addSegment(2 i + 1, x, y, value); node[i].sum = node[2 i].sum + node[2 i + 1].sum;
} /findSum/ long long findSum(int i, int x, int y) { if (node[i].tag) pushDown(i); if (node[i].l == x && node[i].r == y) return node[i].sum; int mid = (node[i].l + node[i].r) / 2; if (y <= mid) return findSum(2 i, x, y); else if(x > mid) return findSum(2 i + 1, x, y); else return findSum(2 i, x, mid) + findSum(2 * i + 1, mid + 1, y); } int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { scanf(“%d”, &a[i]); } built(1, 1, n); int p, x, y, k; for (int i = 1; i <= m; i++) { //cin >> p; scanf(“%d”, &p); if (p == 1) { //cin >> x >> y >> k; scanf(“%d%d%d”, &x,&y,&k); addSegment(1, x, y, k); } else if (p == 2) { //cin >> x >> y; scanf(“%d%d”, &x,&y); cout << findSum(1, x, y) << endl; } } }

  1. <a name="qPomY"></a>
  2. ## 约瑟夫问题
  4. - 数学模拟
  5. ```cpp
  6. #include<cstdio>
  7. #include <iostream>
  8. using namespace std;
  9. int i, finds, k, m, begins;
  10. int check(int remain)
  11. {
  12.     cout << "b = " << begins << ' ' << "m = " << m <<" remain = "<< remain << ' ';
  13.     int result = (begins + m - 1) % remain;
  14.     cout << result << ' ' << endl;
  15.     if (result >= k) {//判断出列的那个人
  16.         begins = result;
  17.         return 1;
  18.     }
  19.     else { return 0; }
  20. }
  21. int main() {
  22.     cin >> k;
  23.     m = k;
  24.     while (!finds)
  25.     {
  26.         cout <<endl<< "m = " << m << endl;
  27.         finds = 1; begins = 0;//设置第一个
  28.         for (i = 0; i < k; i++)
  29.         {
  30.             if (!check(2 * k - i))//如果判断好，就可以退出了……
  31.             {
  32.                 finds = 0; break;
  33.             }
  34.         }
  35.         m++;
  36.     }
  37.     cout<<m-1;//多加了一个，减回去
  38.     return 0;
  39. }
  • 数组模拟
  • 迭代器模拟

最长公共子序列LCS

  • 处理好f[][]和s[]的坐标 ```cpp

    include

    include

    using namespace std; const int MAXN = 1e2 + 10; char s1[MAXN]; char s2[MAXN]; int f[MAXN][MAXN]; int m, n;

void LCS(int i, int j) { if (i == 0 || j == 0) return; //错误1：if (i == 0 && j == 0) if (s1[i-1] == s2[j-1]) { //错误2：if (s1[i] == s2[j]) LCS(i - 1, j - 1); cout << s1[i-1]; //错误3：cout << s1[i]; } else if (f[i][j - 1] > f[i - 1][j]) {
LCS(i, j - 1); } else { LCS(i - 1, j); } } int main() { gets_s(s1); gets_s(s2); m = strlen(s1); n = strlen(s2); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s1[i - 1] == s2[j - 1]) f[i][j] = 1 + f[i - 1][j - 1];
else f[i][j] = max(f[i][j - 1], f[i - 1][j]); } } cout << “LCS长度为：” << f[m][n] << endl; LCS(m, n);

  1. return 0;

} / algorithms alchemist 5 alhms/ ```