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;
}


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

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

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