1. 1077 : RMQ问题再临-线段树

http://hihocoder.com/problemset/problem/1077

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       #define N 10005#define min(a,b) (a
       
        = node[k].r)        return node[k].min;    int minl = N, minr = N;    if (l <= node[k * 2].r)        minl = Query(l, r, k * 2);    if (r >= node[k * 2 + 1].l)        minr = Query(l, r, k * 2 + 1);    return min(minl,minr);}int Change(int p, int w, int k){    if (node[k].l == node[k].r)    {        node[k].min = w;        return 0;    }    if (p <= node[k * 2].r)        Change(p, w, k * 2);    if (p >= node[k * 2 + 1].l)        Change(p, w, k * 2 + 1);    node[k].min = min(node[k * 2].min, node[k * 2 + 1].min);    return 0;}int main(){    int q, k, a, b, i;    scanf("%d", &n);    BuildTree(1,n,1);    scanf("%d", &q);    for (i = 1; i <= q; i++)    {        scanf("%d%d%d", &k, &a, &b);        k ? Change(a, b, 1) : printf("%d\n",Query(a, b, 1));    }    return 0;}
       
      
     

 

2. #1078 : 线段树的区间修改（LazyTag）

http://hihocoder.com/problemset/problem/1078

#define _CRT_SECURE_NO_WARNINGS#include
     
      #define N 100005struct node{    int l, r;    int len;    int sum;    int lazytag; //为0时表示没有lazytag，非0时表示要修改的单价}node[N<<2];void BuildTree(int l, int r, int k){    node[k].l = l;    node[k].r = r;    node[k].len = r - l + 1;    node[k].lazytag = 0;    if (l == r)    {        scanf("%d", &node[k].sum);        return;    }    BuildTree(l, (l + r) / 2, k * 2);    BuildTree((l + r) / 2 + 1, r, k * 2 + 1);    node[k].sum = node[k * 2].sum + node[k * 2 + 1].sum;}int Query(int l, int r, int k){    if (node[k].l >= l && node[k].r <= r)        return node[k].sum;    if (node[k].lazytag)    {        node[k * 2].lazytag = node[k].lazytag;        node[k * 2].sum = node[k].lazytag * node[k * 2].len;        node[k * 2 + 1].lazytag = node[k].lazytag;        node[k * 2 + 1].sum = node[k].sum - node[k * 2].sum;        node[k].lazytag = 0;    }    int mid = (node[k].l+node[k].r)/2, lsum = 0, rsum = 0;    if (l <= mid)        lsum = Query(l, r, k * 2);    if (r > mid)        rsum = Query(l, r, k * 2 + 1);    return lsum + rsum;}void Change(int l, int r, int p, int k){//    printf("%d %d %d %d %d\n", l, r, k,node[k].l,node[k].r);    if (l == node[k].l && r == node[k].r)    {        node[k].lazytag = p;        node[k].sum = p * node[k].len;        return;    }    if (node[k].lazytag)    {        node[k * 2].lazytag = node[k].lazytag;        node[k * 2].sum = node[k].lazytag * node[k * 2].len;        node[k * 2 + 1].lazytag = node[k].lazytag;        node[k * 2 + 1].sum = node[k].sum - node[k * 2].sum;        node[k].lazytag = 0;    }    int mid = (node[k].l + node[k].r) / 2;    if (l <= mid)        Change(l, r
      
        mid)        Change(l>(mid+1)?l:(mid+1), r, p, k * 2 + 1);    node[k].sum = node[k * 2].sum + node[k * 2 + 1].sum;}void printTree(){    printf("**********\n");    for (int i = 1; i <= 25; i++)    {        printf("(%d,%d) %d\t", node[i].l, node[i].r, node[i].sum);    }    printf("**********\n");}int main(){    int n, q, k, l, r, p, i;    scanf("%d", &n);    BuildTree(1, n, 1);    printTree();    scanf("%d", &q);    for (i = 0; i < q; i++)    {        scanf("%d%d%d", &k, &l, &r);        if (0 == k)            printf("%d\n", Query(l, r, 1));        else        {            scanf("%d", &p);            Change(l, r, p, 1);        }//        printTree();    }    return 0;}
      
     

 

3. #1080 : 更为复杂的买卖房屋姿势（两种LazyTag）

http://hihocoder.com/problemset/problem/1080

#define _CRT_SECURE_NO_WARNINGS#include
     
      #define N 100005struct node{    int l, r;    int len;    int sum;    int lazyTagAdd, lazyTagSet;}node[N<<2];void BuildTree(int l, int r, int k){    node[k].l = l;    node[k].r = r;    node[k].len = r - l + 1;    node[k].lazyTagAdd = 0;    node[k].lazyTagSet = 0;    if (l == r)    {        scanf("%d", &node[k].sum);        return;    }    int mid = (l + r) >> 1;    BuildTree(l, mid, k << 1);    BuildTree(mid + 1, r, (k << 1) | 1);    node[k].sum = node[k << 1].sum + node[k << 1 | 1].sum;}void Change(int op, int l, int r, int v, int k){//    printf("%d %d %d %d %d\n", op, l, r, v, k);    if (node[k].len > 1)    {        if (node[k].lazyTagSet)        {            node[k << 1].lazyTagSet = node[k].lazyTagSet;            node[k << 1].sum = node[k].lazyTagSet * node[k << 1].len;            node[k << 1].lazyTagAdd = 0;            node[k << 1 | 1].lazyTagSet = node[k].lazyTagSet;            node[k << 1 | 1].sum = node[k].lazyTagSet * node[k << 1 | 1].len;            node[k << 1 | 1].lazyTagAdd = 0;            node[k].lazyTagSet = 0;        }        if (node[k].lazyTagAdd)        {            node[k << 1].lazyTagAdd += node[k].lazyTagAdd;            node[k << 1].sum += node[k].lazyTagAdd * node[k << 1].len;            node[k << 1 | 1].lazyTagAdd += node[k].lazyTagAdd;            node[k << 1 | 1].sum += node[k].lazyTagAdd * node[k << 1 | 1].len;            node[k].lazyTagAdd = 0;        }    }    if (l <= node[k].l && r >= node[k].r)    {        if (0 == op)  //add        {            node[k].lazyTagAdd = v;            node[k].sum += v* node[k].len;        }        else        {            node[k].lazyTagSet = v;            node[k].sum = v * node[k].len;        }        return;    }    int mid = (node[k].l + node[k].r) >> 1;    if (l <= mid)        Change(op, l, r, v, k << 1);    if (r > mid)        Change(op, l, r, v, k << 1 | 1);    node[k].sum = node[k << 1].sum + node[k << 1 | 1].sum;}void PrintTree(){    printf("\n******\n");    for (int i = 1; i < 30; i++)    {        printf("%d: %d,%d %d\n", i, node[i].l, node[i].r, node[i].sum);    }    printf("\n******\n");}int main(){    int n, m, op, l, r, v, i;    scanf("%d%d", &n, &m);    BuildTree(0, n, 1);//    for (i = 1; i < 30; i++)//        printf("%d: %d,%d %d\n", i, node[i].l, node[i].r, node[i].sum);    PrintTree();    for (i = 0; i < m; i++)    {        scanf("%d%d%d%d", &op, &l, &r, &v);        Change(op, l, r, v, 1);        printf("%d\n", node[1].sum);        PrintTree();    }    return 0;}
     

 

4. #1079 : 离散化

http://hihocoder.com/problemset/problem/1079

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       #include
       
        using namespace std;#define N 100005int s[N], e[N] ,p[N<<2];bool visit[N];typedef struct Poster{    int v;  //区间端点    int k;  //序号}Poster;Poster P[N << 1];bool cmp(Poster a, Poster b){    return a.v < b.v;}void BuildTree(int k, int l, int r, int num){    if (s[num] <= l && e[num] >= r)    {        p[k] = num;  //结点k存放的是第num张海报        return;    }    if (p[k])    {        p[k << 1] = p[k];        p[k << 1 | 1] = p[k];        p[k] = 0;    }    int mid = (l + r) / 2;    if (s[num] < mid)        BuildTree(k << 1, l, mid, num);    if (e[num] > mid)        BuildTree(k << 1 | 1, mid, r, num);}void Check(int k, int l, int r){    if (l + 1 == r)    {        visit[p[k]] = true;        return;    }    if (p[k])    {        p[k << 1] = p[k];        p[k << 1 | 1] = p[k];        p[k] = 0;    }    int mid = (l + r) / 2;    Check(k << 1, l, mid);    Check(k << 1 | 1, mid, r);}int main(){    int n, l, i, j;    cin >> n >> l;    for (i = 1; i <= n; i++)    {        cin >> P[(i << 1) - 1].v;        P[(i<<1)-1].k = i;        cin >> P[i << 1].v;        P[i<<1].k = i + n;    }    sort(P + 1, P + (n << 1) + 1, cmp);    P[(n << 1) + 1].v = -1;    for (i = 1, j = 1; i <= (n << 1); i++)    {        if (P[i].k <= n)            s[P[i].k] = j;        else            e[P[i].k - n] = j;        if (P[i].v != P[i + 1].v)            j++;    }    memset(p, 0, sizeof(p));    for (i = 1; i <= n; i++)        BuildTree(1, 1, j, i);    memset(visit, 0, sizeof(visit));    Check(1, 1, j);    for (i = 1, j = 0; i <= n; i++)    {        if (visit[i])            j++;    }    cout << j << endl;    return 0;}
       
      
     

 

5. 1116 : 计算

http://hihocoder.com/problemset/problem/1116?sid=769706

#define _CRT_SECURE_NO_WARNINGS#include
     
      #include
      
       const int MOD = 10007;const int N = 100005;typedef struct interval{    //int left, right;    int sum;    int pre; //区间内以left为前缀的所有乘积的总和    int suf; //suffix, 区间内以right为后缀的所有乘积的总和    int prd; //product, 区间内所有数的乘积，为求父节点的pre}interval;interval in[N << 1];void Update(int k){    while (k)    {        in[k].pre = (in[k << 1].pre + in[k << 1].prd * in[k << 1 | 1].pre) % MOD;        in[k].suf = (in[k << 1].suf * in[k << 1 | 1].prd + in[k << 1 | 1].suf) % MOD;        in[k].prd = (in[k << 1].prd * in[k << 1 | 1].prd) % MOD;        in[k].sum = (in[k << 1].sum + in[k << 1 | 1].sum + in[k << 1].suf * in[k << 1 | 1].pre) % MOD;        k = k >> 1;    }}void Change(int k, int left, int right, int i, int x){    if (left == right)    {        in[k].sum = x % MOD;        in[k].pre = x % MOD;        in[k].suf = x % MOD;        in[k].prd = x % MOD;        Update(k >> 1);        return;    }    int mid = (left + right) / 2;    if (i <= mid)        Change(k << 1, left, mid, i, x);    else        Change(k << 1 | 1, mid + 1, right, i, x);}int main(){    int n, q, x, i;    scanf("%d%d", &n, &q);    memset(in, 0, sizeof(in));    while (q--)    {        scanf("%d%d", &i, &x);        Change(1, 1, n, i, x);        printf("%d\n", in[1].sum);    }    return 0;}