hdu1754 I Hate It && hdu1166 敌兵布阵 ——线段树复习

April 23, 2013
Hdu Data Structure

题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=1754　　 http://acm.hdu.edu.cn/showproblem.php?pid=1166 都是最基础的线段树，考的知识点就是点更新，区间求和，区间求最大值。再次学线段树，感觉理解加深了一些。但是写的时候还是会出现各种奇葩的错误。唉。 hdu1754


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 200000+10;
int gra[MAX<<2], m , n;
void pushup(int rt)
{
  gra[rt] = max(gra[rt<<1], gra[rt<<1|1]);
}
void build(int l, int r, int rt)
{
  if (l == r) { scanf("%d", &gra[rt]); return; }
  int m = (l + r) >> 1;
  build(lson); build(rson); pushup(rt);
}
void update(int p, int k, int l, int r, int rt)
{
  if (l == r) { gra[rt] = k; return; }
  int m = (l + r) >> 1;
  if (p <= m) update(p, k, lson);
  else update(p, k, rson);
  pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
  if (L <= l && R >= r) { return gra[rt]; }
  int m = (l + r) >> 1, ret = 0;
  if (L <= m) ret = max(ret, query(L, R, lson));
  if (R > m) ret = max(ret, query(L, R, rson));
  return ret;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu1754.in", "r", stdin);
#endif
  while (~scanf("%d%d", &n,&m)){
    char c[2]; int a, b, i; build(1, n, 1);
    for (i = 0; i < m; ++i){
      scanf("%s%d%d", c, &a, &b);
      if (c[0] == 'U') update(a, b, 1, n, 1);
      else printf("%d\n", query(a, b, 1, n ,1));
    }
  }

  return 0;
}

这道题目，开始写的时候，建树的时候没有 return ，运行都会失败…… 然后改了之后，发现数组开小了，把max<<2 写成了 max…… hdu1166


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x3f3f3f3f;
const int  MIN =  -0x3f3f3f3f;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};
const int MAX = 55555;
int gra[MAX<<2];
void pushup(int rt)
{
  gra[rt] = gra[rt<<1] + gra[rt<<1|1];
}
void build(int l, int r, int rt)
{
  if (l == r) { scanf("%d", &gra[rt]); return; }
  int m = (l + r) >> 1;
  build(lson); build(rson); pushup(rt);
}
void update(int p, int k, int l, int r, int rt)
{
  if (l == r) { gra[rt] += k; return; }
  int m = (l + r) >> 1;
  if (p <= m) update(p, k, lson);
  else update(p, k,rson);
  pushup(rt);
}
int query(int L, int R, int l, int r, int rt)
{
  if (L <= l && R >= r) return gra[rt];
  int m = (l + r) >> 1, sum = 0;
  if (L <= m) sum += query(L, R, lson);
  if (R > m) sum += query(L, R, rson);
  return sum;
}
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu1166.in", "r", stdin);
#endif
  int t, i, n, j, k, a, b; scanf("%d", &t); char c[20];
  for (i = 1; i <= t; ++i) {
    printf("Case %d:\n", i); scanf("%d", &n);
    build(1, n, 1);
    while (~scanf("%s", c)){
      if (c[0] == 'E') break;
      scanf("%d%d", &a, &b);
      if (c[0] == 'A') update(a, b, 1, n, 1);
      else if (c[0] == 'S') update(a, -b, 1, n, 1);
      else if (c[0] == 'Q') printf("%d\n", query(a, b, 1, n, 1));
    }
  }

  return 0;
}

这道题目RE了好多次，原因就是读入的时候，如果遇到END就应该立刻退出，我在最后才判断是不是END，也就是多读了数字，而数据里面又没有，所以RE了…… 和上一道题目一样，也是，忘了写max<<2……另外这道题目有加有减，用一个Update就行了，传参的时候传成负的不就行了，别像第一遍似的傻乎乎地写一个add，再写一个几乎一样的add……⊙﹏⊙b汗两道题目都是写第一遍的时候实在找不出错来了，然后就写第二遍的时候才写对的。。这才发现原来错在哪里了。。唉

Read more