首页 > ACM题库 > HDU-杭电 > HDU 4391-Paint The Wall-线段树-[解题报告]HOJ
2015
05-24

HDU 4391-Paint The Wall-线段树-[解题报告]HOJ

Paint The Wall

问题描述 :

As a amateur artist, Xenocide loves painting the wall. The wall can be considered as a line consisting of n nodes. Each node has its own color.

Xenocide spends all day in front of the wall. Sometimes, he paints some consecutive nodes so that these nodes have the same color. When he feels tired, he focuses on a particular color and counts the number of nodes that have this color within a given interval.

Now Xenocide is tired of counting, so he turns to you for help.

输入:

The input consists of several test cases.
The first line of each test case contains two integer n, m(1<=n, m<=100000) indicating the length of the wall and the number of queries.
The following line contains N integers which describe the original color of every position.
Then m lines follow. Each line contains 4 non-negative integers a, l, r, z(1<=a<=2, 0<=l<=r<n ,0<=z<231).
a = 1 indicates that Xenocide paints nodes between l and r and the resulting color is z.
a = 2 indicates that Xenocide wants to know how many nodes between l and r have the color z.

输出:

The input consists of several test cases.
The first line of each test case contains two integer n, m(1<=n, m<=100000) indicating the length of the wall and the number of queries.
The following line contains N integers which describe the original color of every position.
Then m lines follow. Each line contains 4 non-negative integers a, l, r, z(1<=a<=2, 0<=l<=r<n ,0<=z<231).
a = 1 indicates that Xenocide paints nodes between l and r and the resulting color is z.
a = 2 indicates that Xenocide wants to know how many nodes between l and r have the color z.

样例输入:

5 5
1 2 3 4 0
2 1 3 3
1 1 3 1
2 1 3 3
2 0 3 1
2 3 4 1

样例输出:

1
0
4
1

/*
题意:
刷墙, 以开始 有 n个节点,每个节点有一种颜色 ,m 次询问
m次 输入 a,l,r,z 如果 a=1 将 l到 r 刷为 z 颜色,如果 a=2  询问 l 到 r 有 多少个 和 z 相同的 节点
官方题解是: 分段哈希,自己一开始想写 一下 ,单写着写着 就 觉得很麻烦 ,各中判断条件。。。。。
后来改为 线段树  优化了下 ,就是加了 个 mi mx  判断 查询的颜色 是否在这里面。。。。。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define MAX 100010
using namespace std;

//线段树模板
struct line
{
    int left, right; //左端点、右端点
    int c;//color
    int mini, most;
}a[4*MAX];
int v[MAX];

//建立
void build(int s, int t, int n)
{
    int mid = (s + t) / 2;
    a[n].left = s;
    a[n].right = t;
    if (s == t)
    {
        a[n].c = v[s];
        a[n].mini = v[s];
        a[n].most = v[s];
        return;
    }
    build(s, mid, 2 * n);
    build(mid + 1, t, 2 * n + 1);
    if(a[2*n].c == a[2*n+1].c)
        a[n].c = a[2*n].c;
    else
        a[n].c = -1;
    a[n].mini = min(a[2*n].mini, a[2*n+1].mini);
    a[n].most = max(a[2*n].most, a[2*n+1].most);
}
void up(int step)
{
    a[step].mini = min(a[2*step].mini, a[2*step+1].mini);
    a[step].most = max(a[2*step].most, a[2*step+1].most);
    return ;
}
void down(int step)
{
    if(a[step].c != -1)
    {
        a[2*step].c = a[2*step+1].c = a[step].c;
        a[step].c = -1;
        a[2*step].mini = a[2*step+1].mini = a[step].mini;//note
        a[2*step].most = a[2*step+1].most = a[step].most;//note
    }
}
//插入
void modify(int s, int t, int step, int col)
{
    if (s == a[step].left && t == a[step].right)
    {
        a[step].c = col;
        a[step].most = col;
        a[step].mini = col;
        return;
    }
    if (a[step].left == a[step].right)
        return;
    down(step);
    int mid = (a[step].left + a[step].right) / 2;
    if (mid >= t)
        modify(s, t, step * 2, col);
    else if (mid < s)
        modify(s, t, step * 2 + 1, col);
    else
    {
        modify(s, mid, step * 2, col);
        modify(mid + 1, t, step * 2 + 1, col);
    }
    if(a[2*step].c == a[2*step+1].c)
    {
        a[step].c = a[2*step].c;
    }
    up(step);
}
int ans;
void query(int s, int t, int step, int col)
{
    if(a[step].c != -1)//区间的颜色一样
    {
        if(a[step].c == col)//等于查询的颜色
        {
            ans += t - s + 1;
        }
        return;
    }
    if(a[step].left == a[step].right)return;//到底层
    if(a[step].mini > col || a[step].most < col) //重要的优化
        return;
    int mid = (a[step].left + a[step].right) / 2;
    if(mid >= t)
        query(s, t, 2 * step, col);
    else if(mid < s)
        query(s, t, 2 * step + 1, col);
    else
    {
        query(s, mid, 2 * step, col);
        query(mid + 1, t, 2 * step + 1, col);
    }
}

int main()
{
    int n, m;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        memset(a, 0, sizeof(a));
        int i;
        for(i = 0; i < n; i++)
        {
            scanf("%d", &v[i]);
        };
        build(0, n - 1, 1);
        int flag, lt, rt, col;
        for(i = 1; i <= m; i++)
        {
            scanf("%d%d%d%d", &flag, <, &rt, &col);
            if(flag == 1)
            {
                modify(lt, rt, 1, col);
            }
            else
            {
                ans = 0;
                query(lt, rt, 1, col);
                printf("%d\n", ans);
            }
        }
    }
    return 0;                                                                                     
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/weiguang_123/article/details/8144694


  1. 文革的结果是是让中国人民提前30年得到思想大解放,是中国的【文艺复兴】–【启蒙运动】,你回忆一下,5-60年代的学生-工农商学兵是多么好忽悠,今天呢,感谢文革。【权贵的腐朽】揭开了冰山一角。郁闷残暴的文革叫中国人民知道了【魔术】的欺骗伎俩。

  2. 风恋晚外挂这么多,这还让配角们怎么活啊?修真界小菜鸟却随身携带着两个满级王者,这要是让还在为上青铜滚摸打爬的仇敌怨家们知道了该多么绝望啊?太残忍了,,,666

  3. 风恋晚外挂这么多,这还让配角们怎么活啊?修真界小菜鸟却随身携带着两个满级王者,这要是让还在为上青铜滚摸打爬的仇敌怨家们知道了该多么绝望啊?太残忍了,,,666