HDU 1698 & UESTC 1228 Just a hook

By | 12月24日
Advertisement

算是线段树中的一道水题了,必须用到懒操作,否则会超时。或者也可以刚开始不计算和,只更新节点,最后算整个线段的颜色和。

1.懒操作法

HDU 1698 & UESTC 1228 Just a hook
HDU 1698 & UESTC 1228 Just a hook

/* 908ms  3448KB  in HDU OJ*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 100011

struct node
{
    int sum;
    int mark;
}tree[4*N];

int n,q;

void build(int l,int r,int rt)
{
    if(l == r)
    {
        tree[rt].sum = 1;
        tree[rt].mark = 0;
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
}

void update(int len,int rt)
{
    if(!tree[rt].mark)
        return;
    tree[2*rt].mark = tree[2*rt+1].mark = tree[rt].mark;
    tree[2*rt].sum = tree[2*rt].mark*(len - len/2);
    tree[2*rt+1].sum = tree[2*rt+1].mark*(len/2);
    tree[rt].mark = 0;
}

void change(int l,int r,int aa,int bb,int flag,int rt)
{
    if(aa<=l&&bb>=r)   //不用更新到底部,只要更新到区间
    {
        tree[rt].sum = flag*(r-l+1);
        tree[rt].mark = flag;
        return;
    }
    update(r-l+1,rt);
    int mid = (l+r)/2;
    if(aa<=mid)
        change(l,mid,aa,bb,flag,2*rt);
    if(bb>mid)
        change(mid+1,r,aa,bb,flag,2*rt+1);
    tree[rt].sum = tree[2*rt].sum + tree[2*rt+1].sum;
}

int main()
{
    int t,i;
    int cs = 1;
    int aa,bb,val;
    scanf("%d",&t);
    while(t--)
    {
        memset(tree,0,sizeof(tree));
        scanf("%d%d",&n,&q);
        build(1,n,1);
        for(i=0;i<q;i++)
        {
            scanf("%d%d%d",&aa,&bb,&val);
            change(1,n,aa,bb,val,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",cs++,tree[1].sum);
    }
    return 0;
}

View Code

2.最后求和法

HDU 1698 &amp; UESTC 1228 Just a hook
HDU 1698 &amp; UESTC 1228 Just a hook

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
#define N 100011

struct node
{
    int le,ri;
    int sum;
}tree[4*N];

int n,q;

void build(int l,int r,int rt)
{

    tree[rt].sum = 1;
    tree[rt].le = l;
    tree[rt].ri = r;
    if(l == r)
    {
        return;
    }
    int mid = (l+r)/2;
    build(l,mid,2*rt);
    build(mid+1,r,2*rt+1);
}

void change(int l,int r,int aa,int bb,int flag,int rt)
{
    if(aa<=l&&bb>=r)   //不用更新到底部,只要更新到区间
    {
        tree[rt].sum = flag;
        return;
    }
    if(tree[rt].sum != 0)
    {
        tree[2*rt].sum = tree[2*rt+1].sum = tree[rt].sum;
        tree[rt].sum = 0;
    }
    int mid = (l+r)/2;
    if(aa<=mid)
        change(l,mid,aa,bb,flag,2*rt);
    if(bb>mid)
        change(mid+1,r,aa,bb,flag,2*rt+1);
}

int query(int rt)
{
    if(tree[rt].sum != 0)
        return (tree[rt].ri - tree[rt].le + 1)*tree[rt].sum;
    return query(2*rt)+query(2*rt+1);
}

int main()
{
    int t,i;
    int cs = 1;
    int aa,bb,val;
    scanf("%d",&t);
    while(t--)
    {
        memset(tree,0,sizeof(tree));
        scanf("%d%d",&n,&q);
        build(1,n,1);
        for(i=0;i<q;i++)
        {
            scanf("%d%d%d",&aa,&bb,&val);
            change(1,n,aa,bb,val,1);
        }
        printf("Case %d: The total value of the hook is %d.\n",cs++,query(1));
    }
    return 0;
}

View Code

Similar Posts:

  • HDU 1698 &amp;amp; UESTC 1228 Just a hook

    算是线段树中的一道水题了,必须用到懒操作,否则会超时.或者也可以刚开始不计算和,只更新节点,最后算整个线段的颜色和. 1.懒操作法 /* 908ms 3448KB in HDU OJ*/ #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <cstdlib> using names

  • 【解题报告】 HDU 1698 Just a Hook 线段树 (线段替换) 插线问线 + 延时标记

    // HDU 1698 Just a Hook 线段树(线段替换)插线插线+ 延时标记 // 延时标记:起一个缓冲的作用,第一次遇到的更新先不更新到底,等下一次更新或者查询的时候再更新到位. // 因此线段树结构中的区间和 并不是实际值. // 此处的更新到位是指 本次更新或查询所需的最后一层(因为我查的不是点,而是区间),并非到最底层 // 延时标记下沉的前提:线段树结构中遇到了一个区间完全的包含于待更新区间,即遇到一个待更新区间的子区间 // 注意的是: // 1.下沉这个标记的时候也要更新

  • 成段改A为B更新区间求和 hdu 1698 Just a Hook

    题目链接 hdu 1698 Just a Hook 题目大意:给你n个数(初始时每个数的值为1),m个操作,每个操作把区间[l,r]里的数更新为c,问最后这n个数的和是多少. 解题思路:O(-1) #include <cstdio> #include <iostream> using namespace std; const int maxn=100005; int tree[4*maxn]; int flag[4*maxn]; void down(int u, int l, in

  • HDU 1698 Just a Hook (线段树 成段更新 lazy-tag思想)

    题目链接 题意: n个挂钩,q次询问,每个挂钩可能的值为1 2 3, 初始值为1,每次询问 把从x到Y区间内的值改变为z.求最后的总的值. 分析:用val记录这一个区间的值,val == -1表示这个区间值不统一,而且已经向下更新了, val != -1表示这个区间值统一, 更新某个区间的时候只需要把这个区间分为几个区间更新就行了, 也就是只更新到需要更新的区间,不用向下更新每一个一直到底了,在更新的过程中如果遇到之前没有向下更新的, 就需要向下更新了,因为这个区间的值已经不统一了. 其实这就是

  • hdu 1698 Just a Hook(线段树基础)

    成段更新的线段树,加入了延时标记............ 线段树这种东西细节上的理解因人而异,还是要自己深入理解......慢慢来 #include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <ve

  • hdu 1698 Just a Hook (线段树---成段更新)

    用到了懒惰标记lazy[]即我的代码中的col[]. 以前不知道这东西是什么,昨天跟着hh的线段树代码看了一遍.看懂了... 就是每次只更新到包含左右端点的最大节点,就停止. 下一次要更新的时候,先把上次未更新到底的往下更新... #include<cstdio> #define maxn 100010 int sum[maxn<<2],col[maxn<<2]; void PushUp(int rt) { sum[rt] = sum[rt<<1]+sum[

  • hdu 1698 Just a Hook lazy线段树

    Just a Hook Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description In the game of DotA, Pudge's meat hook is actually the most horrible thing for most of the heroes. The hook is made up of several consecu

  • hdu 1698 Just a Hook 线段树区域更新

    分析: *每个线段树的结点存储该结点所代表区间的颜色d[v].c,如果该区间全为同样的颜色,则用一个正数(1,2,3)表示,如果含有多种颜色,则用0表示, *每次执行染色操作时,如果所要染的颜色与区间颜色一样,则停止,如果所要染区间跟当前结点区间一致,则直接将所要染颜色赋给当前结点的d[v].c, *否则,如果当前结点区间不是混合色,则先将当前结点的颜色赋给左右子结点lc(2*v)和rc(2*v+1),并递归下去. code_1: Description In the game of DotA,

  • hdu 1698 Just a Hook 只是一个钩

    这道题是一道线段树的成段更新的题目,刚开始做的时候没A过去,后来看别人的解题报告,代码如下. #include<stdio.h> #include<string.h> #define maxn 100005 int a[maxn*4]; int s[maxn*4]; void push(int rt) { a[rt]=a[rt*2]+a[rt*2+1]; } void pdown(int rt, int x) { if(s[rt]!=-1) { s[rt*2]=s[rt*2+1]

  • HDU 1698 Just a Hook(改变区间的变形)

    题目链接 调试了好一会..把模版上的lz标记,如何满足题意就OK了... 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #define N 100001 5 int p[4*N],lz[4*N]; 6 void pushup(int rt) 7 { 8 p[rt] = p[rt<<1]+p[rt<<1|1]; 9 } 10 void pushdown(int

Tags: