题意： 一共有n张海报， 按次序贴在墙上， 后贴的海报可以覆盖先贴的海报， 问一共有多少种海报出现过。
题解： 因为长度最大可以达到1e7， 但是最多只有2e4的区间个数，并且最后只是统计能看见的不同海报的数目，所以可以先对区间进行离散化再进行区间覆盖的操作。
由于墙上不贴东西的时候对后面没有影响， 所以可以不建树， 直接memset一下就好了。
因为是区域覆盖的问题， 树上原来的点并不会对后面的结果产生影响， 所以可以只修改lazy标记而不对树进行修改。
最后再用建树的操作访问一下lazy标记 并记录答案就好了。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
const int N = +;
int tree[N<<], lazy[N<<];
int a[N];
bool vis[N];
int ans, n, t;
pair<int,int> P[N]; void Pushdown(int rt)
{
if(lazy[rt])
{
lazy[rt<<|] = lazy[rt<<] = lazy[rt];
lazy[rt] = ;
}
}
void Revise(int L, int R, int C ,int l, int r, int rt)
{
if(L <= l && r <= R)
{
lazy[rt] = C;
return ;
}
Pushdown(rt);
int m = l+r >> ;
if(L <= m) Revise(L,R,C,lson);
if(m < R) Revise(L,R,C,rson);
}
void build(int l, int r, int rt)
{
if(lazy[rt])
{
if(!vis[lazy[rt]])
{
vis[lazy[rt]] = ;
ans++;
}
return ;
}
int m = l+r >> ;
build(lson);
build(rson);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin >> t;
while(t--)
{
ans = ;
cin >> n;
for(int i = ; i <= *n; i++)
{
cin >> a[i];
P[i].fi = a[i], P[i].se = i;
}
sort(P+,P+*n+);
int last = , cnt = ;
for(int i = ; i <= *n; i++) //离散化操作
{
if(P[i].fi == last)
a[P[i].se] = cnt;
else a[P[i].se] = ++cnt, last = P[i].fi;
}
memset(lazy, , sizeof(lazy));
for(int i = ; i <= *n; i+=)
Revise(a[i],a[i+],(i+)/,,cnt,);//由于每次的海报不同所以直接给海报一个编号
memset(vis, , sizeof(vis));
build(,cnt,);
cout << ans << endl;
}
return ;
}