PHP动态网站开发实训总结新东方英语线下培训学校

题目链接

题意：

给定n个区间[ l, r ]和颜色c, 每次给[l, r]涂上c这个颜色. 后面的涂色会覆盖之前的涂色.

最后要求输出区间[0, 8000]中每种颜色及其出现的次数, 如果该颜色没有出现过则不输出.

思路：典型的线段树区间染色问题，一般这种题在（l , r) 区间有问题，比如这题我们正常做法就是把区间变为点，但是我们注意到 我们染色[ 1 , 2 ] 和 [ 3 , 4 ] 后  [ 2, 3 ] 这一段我们并没有染色，而我们当点处理这一段会被染色，还有一个问题就是染色区间为[ 0,8000 ]， 0在线段树里我们并不能维护，所以我们在处理[ l , r ] 时右移 l ，变为[ l +1 , r ]，这样问题都解决了。，我们可以用一个 pre 记录 前面的颜色，

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 2e4 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
const double eps = 1e-8;
int n, pre;
int ans[N];
int color[N];
void pushdown(int u)
{color[u << 1] = color[u];color[u << 1 | 1] = color[u];color[u] = -1;
}
void modify(int u, int l, int r, int L, int R, int c)
{if (l >= L && r <= R){color[u] = c;return;}if (color[u] != -1)pushdown(u);int mid = l + r >> 1;if (L <= mid)modify(u << 1, l, mid, L, R, c);if (R > mid)modify(u << 1 | 1, mid + 1, r, L, R, c);
}
void query(int u, int l, int r)//这种查询方式一定会查到底才行
{if (l == r){if (color[u] != -1 && pre != color[u]){ans[color[u]]++;}pre = color[u];return;}if (color[u] != -1)pushdown(u);int mid = l + r >> 1;query(u << 1, l, mid); // 就和dfs一样，先跑左子树，这样就相当于从左向右跑的区间query(u << 1 | 1, mid + 1, r);
}void query(int u, int l, int r)//而这一种相当于利用了懒标记的性质，
{if (color[u] != pre&&color[u]!=-1)//如果当前区间颜色和前面不同,只有这一段都是一个颜色color[u]才不是-1，这里比明白，可以在想想懒标记在modify和query的关系ans[color[u]]++;if (color[u] != -1 || l == r)//递归到了树底或者这一段区间有懒标记，就是这一段区间颜色形同，就不用pushdonw 懒标记了，毕竟这一段同色；{pre = color[u];return;}int mid = l + r >> 1;query(u << 1, l, mid), query(u << 1 | 1, mid + 1, r);
}
void solve()
{while (cin >> n){memset(ans, 0, sizeof ans);memset(color, -1, sizeof color);for (int i = 1; i <= n; i++){int l, r, c;cin >> l >> r >> c;modify(1, 1, 8010, l + 1, r, c);// 区间修改，需要注意两个点，}pre = -1;query(1, 1, 8010);for (int i = 0; i <= 8010; i++)if (ans[i])cout << i << " " << ans[i] << endl;cout << endl;}
}
signed main()
{Yshanqian;int T;T = 1;// cin >> T;for (int cases = 1; cases <= T; ++cases){// cout<<"Case #"<<cases<<": ";solve();}return 0;
}