[东师培训D5T2] 公主的朋友
题目
题目背景
由于 Wulala 在上个问题中的精彩表现，公主认为 Wulala 是一个很棒的人，就把 Wulala 留在了 X 国。这时正好公主的一位传教士朋友来拜访公主，于是想找 wulala 帮忙。X 国如同一条直线，其中有 n 个城市, 从东向西分别编号为 1~n。而他的国家中有 m 种宗教，每个城市一定会有一种信仰的宗教。有时候有些城市为了获得更多的认可，会派出信仰本城市宗教的传教士前往其他国家。X 国的传教士都十分厉害，只要是他途经的地方都会改信他所传播的宗教。传教士们在路上碰到自己宗教的城市自然就不用传教了，可以停下来看看里番啥的，所以每一个传教士在旅行前都会计算自己可以在多少城市停下来(不包括起始的城市)。而传教士们都是文科僧，数学是很差的，所以他希望 Wulala 能帮他计算。可 Wulala 数学也不好，但他又不想在公主面前丢脸，你能帮帮他吗？
输入
第一行两个整数 n，m
第二行 n 个整数第 i 个整数代表第 i 各城市信仰的宗教
第三行一个整数 T 代表传教士的个数
接下来 T 行每行两个整数 x，y 代表 x 城向 y 城派遣了一个传教士(保证 x < y)
输出
输出 T 行，第 i 行代表第 i 个传教士询问的答案。
数据范围
对于 30%的数据 n <= 100000, m <= 10, T <= 100
对于 60%的数据 n <= 100000, m <= 10, T <= 100000
对于 100%的数据 n <= 100000, m <= 300, T <= 100000
想法
又臭又长的题目背景…
抽象来看，问题实质是维护一个序列，支持区间修改为同一值，并查询区间内某一值元素个数。所以是一道典型的线段树。但是考场上写挂了T_T… 调不出来，不得已写了暴力30分… 所以当天滚粗超级惨，还是来记录一下。
其实思想还是非常简单的。对区间打上懒标记（记为ch），表示该区间有没有被修改为同一值。如果有，ch就为被修改后的值，如果没有就记为0。
题解中顺便维护了区间最大值和最小值。这是为了在查询时判一下所查询的值是否在最小值和最大值中间，如果不在就不用继续在子树里找了，肯定返回0。一个小小的优化，似乎没有维护也可以A掉…
为了让传教士去传教，我们还得知道这个传教士信仰的是什么宗教，所以还得支持单点查询。随便搞一个就好了。
区间查询，主要是判到懒标记的时候，直接加上懒标记就好了，说明这个子树都信同一个宗教。
所以为什么会写挂呢… 玄学…
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
const int MAXN = 100005;
int n, m, q, rt = 1;
struct Node
{
int l, r, mn, mx, ch;
Node() : mn(0), mx(0), ch(0) {}
} p[MAXN << 2];
struct SegTree
{
void build(int x, int l, int r);
void update(int x, int v);
void pushUp(int x);
void pushDown(int x);
int query(int x, int l, int r, int v);
int value(int x, int p);
void modify(int x, int l, int r, int v);
} st;
void SegTree::build(int x, int l, int r)
{
p[x].l = l;
p[x].r = r;
if (l == r)
{
scanf("%d", &p[x].mx);
p[x].mn = p[x].mx;
return;
}
int mid = l + r >> 1;
build(ls(x), l, mid);
build(rs(x), mid + 1, r);
pushUp(x);
}
void SegTree::update(int x, int v)
{
p[x].mx = p[x].mn = p[x].ch = v;
}
void SegTree::pushUp(int x)
{
p[x].mx = max(p[ls(x)].mx, p[rs(x)].mx);
p[x].mn = min(p[ls(x)].mn, p[rs(x)].mn);
}
void SegTree::pushDown(int x)
{
if (p[x].ch)
{
update(ls(x), p[x].ch);
update(rs(x), p[x].ch);
p[x].ch = 0;
}
}
int SegTree::query(int x, int l, int r, int v)
{
if (p[x].mx < v || p[x].mn > v)
return 0;
if (p[x].mx == p[x].mn)
{
if (p[x].mx == v) return r - l + 1;
else return 0;
}
pushDown(x);
int mid = p[x].l + p[x].r >> 1;
if (r <= mid) return query(ls(x), l, r, v);
else if (l > mid) return query(rs(x), l, r, v);
else return query(ls(x), l, mid, v) + query(rs(x), mid + 1, r, v);
}
int SegTree::value(int x, int pos)
{
if (p[x].l == p[x].r) return p[x].mx;
pushDown(x);
int mid = p[x].l + p[x].r >> 1;
if (pos <= mid) return value(ls(x), pos);
else return value(rs(x), pos);
}
void SegTree::modify(int x, int l, int r, int v)
{
if (l == p[x].l && r == p[x].r)
{
update(x, v);
return;
}
pushDown(x);
int mid = p[x].l + p[x].r >> 1;
if (r <= mid) modify(ls(x), l, r, v);
else if (l > mid) modify(rs(x), l, r, v);
else
{
modify(ls(x), l, mid, v);
modify(rs(x), mid + 1, r, v);
}
pushUp(x);
}
int main()
{
scanf("%d%d", &n, &m);
st.build(rt, 1, n);
scanf("%d", &q);
while (q--)
{
int l, r;
scanf("%d%d", &l, &r);
int v = st.value(rt, l);
printf("%d\n", st.query(rt, l + 1, r, v));
st.modify(rt, l + 1, r, v);
}
return 0;
}