题意
题目链接:Mayor's posters - POJ 2528 - Virtual Judge (vjudge.net)
有$T$组数据,每次有$n$个区间,第$i$个区间将会把$[l_i,r_i]$染成$i$颜色,最后从上往下看有多少种不同的颜色?
数据范围
$1\leq n\leq 10000$
$1\leq l_i\leq r_i\leq 10^7$
思路
区间太大,肯定不能用这么大的数组($O(nlogn)$),又注意到$n$比较小,所以要用到离散化。
比如这个样例:
7 11
7 8
10 11
那么我可以排序加去重得到$\lbrace 7,8,10,11\rbrace$,这样四个数在我离散化后面就变成了$\lbrace 1,2,3,4\rbrace$,我对$[7,8]$染成$2$号颜色,在我这个线段树中就变成了将$[1,2]$染成$2$号颜色,这就是离散化。
那么这样就够了吗?——不够!
就如上面的三个区间而言,本来应该是三种颜色的(第一种颜色在$9$),但是我们离散化把$9$没有离散化成3,所以我们要进行一个填空的操作:
我们排序去重发现是$\lbrace 7,8,10,11\rbrace$之后,我们扫一遍判断,如果中间有不连续的,那么就手动填一个进去,比如$7,8$之间是连续的,不用管;$8,10$之间不连续,所以需要填一个任意的进去,这里我填$9$,这样就变成了$\lbrace 7,8,9,10,11\rbrace$,离散化的时候$10$对应的$4$,这样下来就没有覆盖$9$了,也没有把$9$遗忘掉。
其实不填也可以,我只是让不连续的多$+1$即可,比如本来应该$10$此时应该是$3$,但是我让他$+1$变成$4$。
for (int i=1;i<=m;i++)
{
a[i].x = read();a[i].y = read();
b[++cnt] = a[i].x;
b[++cnt] = a[i].y;//离散化
vis[i] = 0;
}
sort(b+1,b+cnt+1);//排序
int num=0;
mp[b[1]] = ++num;
for (int i=2;i<=cnt;i++)
{
if(b[i]-b[i-1]==1)
mp[b[i]]=++num;
else if(b[i]==b[i-1])//重复,去重
continue;
else
{
num++;//多+1
mp[b[i]]=++num;
}
}
然后就是线段树的内容了。染色的话实际上就是区间赋值,把普通的+=
改为=
即可。这里我发现只需要tag
就好,并且没有pushup
,用一个全局变量vis[]
来判断颜色是否出现过,最后递归到有tag
的时候就好。
注意这里的tag
如果当前结点有(不为0)的话,那么就不用下去了,直接判断返回即可,因为下面必定一样,不一样的话说明这个结点一定经过过,那么也就说明这个tag
一定下放过,矛盾了,所以就可以直接判断返回。
线段树代码如下:
struct Segment_Tree
{
int tag[N<<2],lc[N<<2],rc[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
inline void build(int o,int l,int r)
{
lc[o]=l;rc[o]=r;tag[o]=0;
if (l==r) return;
build(lson,l,mid);build(rson,mid+1,r);
}//tag一开始全部为0.
inline void pushdown(int o)
{
if (tag[o])
{
tag[lson] = tag[o];
tag[rson] = tag[o];
tag[o] = 0;
}
}//下放
inline void update(int o,int ql,int qr,int k)
{
int l = lc[o], r = rc[o];
if (ql<=l&&r<=qr)
{
tag[o] = k;
return;
}//整个结点都在里面
pushdown(o);
if (ql<=mid) update(lson,ql,qr,k);
if (qr>mid) update(rson,ql,qr,k);
}
inline void query(int o)
{
int l = lc[o], r = rc[o];
if (tag[o])
{
if (!vis[tag[o]]) vis[tag[o]] = 1, ans++;
return;
}
if (l==r) return;
//一定要有这个判断,不然会tle,我一直找这个bug
//不是所有的结点都有tag[o],所以这里直接返回就好(到达叶子节点)
pushdown(o);
query(lson);query(rson);
}
}tree;
代码
完整代码
struct Segment_Tree
{
int tag[N<<2],lc[N<<2],rc[N<<2];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((l+r)>>1)
inline void build(int o,int l,int r)
{
lc[o]=l;rc[o]=r;tag[o]=0;
if (l==r) return;
build(lson,l,mid);build(rson,mid+1,r);
}
inline void pushdown(int o)
{
if (tag[o])
{
tag[lson] = tag[o];
tag[rson] = tag[o];
tag[o] = 0;
}
}
inline void update(int o,int ql,int qr,int k)
{
int l = lc[o], r = rc[o];
if (ql<=l&&r<=qr)
{
tag[o] = k;
return;
}
pushdown(o);
if (ql<=mid) update(lson,ql,qr,k);
if (qr>mid) update(rson,ql,qr,k);
}
inline void query(int o)
{
int l = lc[o], r = rc[o];
if (tag[o])
{
if (!vis[tag[o]]) vis[tag[o]] = 1, ans++;
return;
}
//if (tag[o]&&!vis[tag[o]]) vis[tag[o]] = 1, ans++;
if (l==r) return;
pushdown(o);
query(lson);query(rson);
}
}tree;
struct node
{
int x,y;
}a[N];
int b[N];
map<int,int> mp;
inline void Case_Test()
{
m = read();
mp.clear();
cnt = 0;
ans = 0;
for (int i=1;i<=m;i++)
{
a[i].x = read();a[i].y = read();
b[++cnt] = a[i].x;
b[++cnt] = a[i].y;
vis[i] = 0;
}
sort(b+1,b+cnt+1);
int num=0;
mp[b[1]] = ++num;
for (int i=2;i<=cnt;i++)
{
if(b[i]-b[i-1]==1)
mp[b[i]]=++num;
else if(b[i]==b[i-1])
continue;
else
{
num++;
mp[b[i]]=++num;
}
}
tree.build(1,1,num);
for (int i=1;i<=m;i++)
{
int x,y;
x = mp[a[i].x];
y = mp[a[i].y];
tree.update(1,x,y,i);
}
tree.query(1);
writeln(ans);
}
文章评论