区间修改,区间查询
题意
有一面无限长的墙,每次可以在这面墙上贴一张横跨区间$[l,r]$的海报(高度相同),新海报会覆盖旧海报,问最后可以看到哪些编号的海报,以及这些海报出现的了多少段。
分析
乍一眼看是典型的区间修改和和区间查询,但是我们会发现,每次修改的是一段连续的区间,并非离散的点,因此我们需要在修改上做一些改变,在区间修改时,将区间最左端加1,这样就可以将一个长度为1的区间用区间右端点来表示。例如,如果修改区间$[1,4]$,我们实际上修改的是点$2、3、4$。这也符合实际情况,因为修改区间$[l,r]$实际上修改的长度只有$r-l$,而非$r-l+1$.
最后查询的时候也有些不同,因为需要查询每种海报的出现的段数而非总长度,因此引入一个$last$表示上一段海报的种类,如果当前海报的种类与$last$不同,将当前种类海报的段数加1,可以这样判断的原因是,线段树是一棵二叉树,每次遍历的两个区间必定都是连续的。
#include <iostream>
#include <cstring>
#define met(a , b) memset(a , b , sizeof a);
using namespace std;
#define lc u << 1
#define rc u << 1 | 1
const int N = 8010;
int n, res[N], last = -1;
struct Node{
int l, r, lazy;
}tr[N * 4];
void build (int u, int l, int r)
{
tr[u] = {l, r, -1};
if (l == r) return;
int mid = l + r >> 1;
build (lc, l, mid), build (rc, mid + 1, r);
}
void pushdown (int u)
{
if(~tr[u].lazy)
{
tr[lc].lazy = tr[rc].lazy = tr[u].lazy;
tr[u].lazy = -1;
}
}
void modify (int u, int l, int r, int d)
{
if (tr[u].l >= l && tr[u].r <= r) tr[u].lazy = d;
else
{
pushdown (u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify (lc, l, r, d);
if (r > mid) modify (rc, l, r, d);
}
}
void query (int u)
{
if (last != tr[u].lazy) ++res[tr[u].lazy];
if (tr[u].l == tr[u].r || ~tr[u].lazy) { last = tr[u].lazy; return; }
query(lc), query(rc);
}
void solve()
{
met(res, 0);
build (1, 1, 8010);
while (n--)
{
int l, r, d;
cin >> l >> r >> d;
modify (1, l + 1, r, d);
}
query(1);
for (int i = 0; i < 8001; i++)
if (res[i] > 0)
cout << i << ' ' << res[i] << endl;
cout << endl;
}
int main()
{
ios::sync_with_stdio(0);
int T = 1;
while (cin >> n) solve();
}