贴海报 题解

题目传送门

这道题题解里各位都用的线段树、浮水法，本蒟蒻完全不会，这里给出我的方法，既没有线段树也没有浮水法，较为易懂（?）。

可以发现$n$的范围极其大，但是$m$的范围很小，只有1000，所以可以想到一个大致为$m^2$的算法。

假设输入顺序代表时间顺序，一行为一天（这样好理解）

每当一张海报贴到墙上时，只需要知道这张海报对以前贴的海报造成了什么影响即可。

具体修改方法：通过修改一张海报左端点右端点位置实现。

假设一张海报左端点为$l_i$，右端点为$r_i$

（注：下列图中红色表示以前贴的海报，蓝色表示今天贴的海报）

• 情况一：完全覆盖，如图。

可以专门设计一个bool数组，$u_i=1$表示这个海报没有用了。

• 情况二：毫不相关，如图。

这时我们不用管就行。

• 情况三：覆盖了左边部分，如图。

此时要将红色海报的左端点挪到蓝色海报右端点的右边。

因为红色海报的地盘被蓝色海报盖掉了一部分，那一部分已经不再是红色海报的地盘了，可以视为红色海报本来就没有这个地盘。

• 情况四：覆盖了右边部分，如图。

将红色海报的右端点挪到蓝色海报左端点的左边。

• 情况五，也是最麻烦的，刚好劈开了以前的海报，如图。

这时候我们可以视为这个红色海报不再是一个整体了，而是变成了颜色相同的两张海报。

第一张海报的$l_j$还是原来的红色海报的$l_i$，而$r_j$变成了蓝色海报左端点的左边。

第二张海报的$l_k$变成了蓝色海报右端点的右边，而$r_k$还是原来的红色海报的$r_i$。

为了避免统计时认成两张不同的海报，我们还需要一个数组$d$，$d_i$来标记它的颜色，多张海报颜色相同就视为这些海报是同一张海报。

到这里，每张海报的信息点就出来了，$l$表示左端点位置，$r$表示右端点位置，$u$表示是否永远离开了这面墙，$d$表示颜色。

因为我们随时有可能在增加新海报，海报总数是不可估量的，所以要用C++的STL中的vector

如果不清楚vector的话，直接把他理解成一个可以自动伸缩长短的数组，有一个叫push_back的函数可以在这个数组后面挤进去一个数。

struct photo{
   int l,r,d;
   bool u;
};
vector<photo> a;

下面的码风过丑，需要逐行理解。

for(register int i=1;i<=m;++i){
   photo p;
   s=a.size(); //因为海报总数不一定是m了（情况五会增加海报数），所以需要实时更新海报数量
   p.l=read();
   p.r=read();
   p.d=i;// 第i个海报颜色标记为i，绝对就不会搞混了
   p.u=0;//刚贴的海报不可能全被覆盖

   // 贴海报前需要审核，看看这张海报造成的影响

   for(register int j=s-1;j>=0;--j) if(!a[j].u){  // 如果这张海报已经阵亡就跳过
  
   	if(p.l>a[j].r || p.r<a[j].l) continue;// 毫无关系就跳过（情况二）
   	if(p.l<=a[j].l && p.r>=a[j].r) {a[j].u=1;continue;} //完全覆盖，标记一下这张海报凉了，然后不管了（情况一）
       
   	if(p.l>a[j].l && p.l<a[j].r && p.r>a[j].l && p.r<a[j].r) a.push_back((photo){p.r+1,a[j].r,a[j].d,0}),a[j].r=p.l-1;
       /*
        * 如果是要劈成两半（情况五），
        * 放一个新的海报（和原来海报颜色一样），再更新原来海报大小，
        * if里面的条件需要仔细咀嚼
        */
       
   	if(p.l>a[j].l && p.l<a[j].r) a[j].r=p.l-1; //情况四
   	if(p.r>=a[j].l && p.r<a[j].r) a[j].l=p.r+1;//情况三

   	if(a[j].l>a[j].r) a[j].u=1; 
      // 如果一张海报被折磨到左端点在右端点右边，说明他SPFA了
   }
   a.push_back(p); //所有事情搞完后，这张临时海报就审核通过贴墙上了
}

最终我们把所有海报审核通过了，然后把这几天的活着的海报数一数就行。

map<int,bool> k;	// k存储一个颜色是否出现过了
/*
 * C++中的map可以视为一个万能数组，它的下标可以是任何东西
 * map<int,bool> 类似于创建一个 bool 类型的数组，它的下标的类型是 int
 * 需要注意的是，map的查询和修改不是O(1)，是O(logn)
 */
s=a.size();
for(register int i=0;i<s;++i)
   if(!a[i].u && !k[a[i].d]){ // 如果这张海报还“活着”而且还没出现过
   	++ans; // 墙上又多了一张能被看见过的海报
       k[a[i].d]=1; // 标记这张海报出现过了，避免以后又遇到它就重复累加
   }
write(ans);

$\color{Red}\text{基本完整代码}$（省略了快读快写函数）

#include<bits/stdc++.h>
using namespace std;

int n,m,ans,s; // n，m和题意一样，ans表示答案，s表示vector的长度
struct photo{
   int l,r,d;
   bool u;
};// 每个变量什么意思见上文

vector<photo> a; // 存海报
map<int,bool> k; // 判重

int main(){
   n=read(),m=read();
  
   for(register int i=1;i<=m;++i){
   photo p;
   s=a.size(); //因为海报总数不一定是m了（情况五会增加海报数），所以需要实时更新海报数量
   p.l=read();
   p.r=read();
   p.d=i;// 第i个海报颜色标记为i，绝对就不会搞混了
   p.u=0;//刚贴的海报不可能全被覆盖

   // 贴海报前需要审核，看看这张海报造成的影响

   for(register int j=s-1;j>=0;--j) if(!a[j].u){  // 如果这张海报已经阵亡就跳过
  
   	if(p.l>a[j].r || p.r<a[j].l) continue;// 毫无关系就跳过（情况二）
   	if(p.l<=a[j].l && p.r>=a[j].r) {a[j].u=1;continue;} //完全覆盖，标记一下这张海报凉了，然后不管了（情况一）
       
   	if(p.l>a[j].l && p.l<a[j].r && p.r>a[j].l && p.r<a[j].r) a.push_back((photo){p.r+1,a[j].r,a[j].d,0}),a[j].r=p.l-1;
       /* 如果是要劈成两半（情况五），
        * 放一个新的海报（和原来海报颜色一样），再更新原来海报大小，
        * if里面的条件需要仔细咀嚼
        */
   	if(p.l>a[j].l && p.l<a[j].r) a[j].r=p.l-1; //情况四
   	if(p.r>=a[j].l && p.r<a[j].r) a[j].l=p.r+1;//情况三

   	if(a[j].l>a[j].r) a[j].u=1; 
      // 如果一张海报被折磨到左端点在右端点右边，说明他SPFA了
   }
   a.push_back(p); //所有事情搞完后，这张临时海报就审核通过贴墙上了
}
   s=a.size();
   for(register int i=0;i<s;++i)
   	if(!a[i].u && !k[a[i].d]){ // 如果这张海报还“活着”而且还没出现过
 	     ++ans; // 墙上又多了一张能被看见过的海报
  	     k[a[i].d]=1; // 标记这张海报出现过了，避免以后又遇到它就重复累加
   	}
   write(ans);
   return 0;
}