2015
05-24

# 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

/*

m次 输入 a，l，r，z 如果 a=1 将 l到 r 刷为 z 颜色，如果 a=2  询问 l 到 r 有 多少个 和 z 相同的 节点

*/
#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;
}