F.Count Color

Mayor's poster

题意

在1-10000000的墙上贴上10000张海报，可以互相覆盖，求最终可见多少张海报

思路

若要建树，每次查找到树底部的时间是log 1e8 * 1e8次查找一定超时！

又需要空间为4*1e8 空间也超了

发现这里只贴10000张海报，所以可以采用离散化的手法。

1.可以把用相对大小来代替数的位置。

但会出现1，10 1，3 6，10

1，，，4

1 2

? 3 4

只有两个点但按题目原意应该有3个点

为什么会出现这样的情况？？？

3和6本不相邻，变成了相邻

所以我们对离散化进行优化，数原来相邻就相邻，不相邻就隔一项

int a[N];
a[0]=1;
int kk=1;
for(int i=0;i


建树
这题其实只需要lazytag即可，当贴上海报，标记某段的lazy值为i，若新贴了，则pushdown操作；最后查询的时候，直接查lazy的标记，放进set中计数，
若查到底都没有lazy标记，则直接返回，说明这里为空
AC代码
#include
#include
#include
#include
#include
#include
using namespace std;
const int N = 2e5+5;
struct rec{
	int l,r,lazy;
}tr[N<<2];
int n;
setnum; 
void bt(int u,int l,int r)
{
	if(l==r)
	{
		tr[u]={l,r,0};
		return ;
	}
	tr[u]={l,r,0};
	int mid=l+r>>1;
	bt(u<<1,l,mid);
	bt(u<<1|1,mid+1,r);
}
void down(int u)
{
	if(tr[u].lazy)
	{
		tr[u<<1].lazy=tr[u<<1|1].lazy=tr[u].lazy;
		tr[u].lazy=0;
	}
}
void update(int u,int l,int r,int k)
{
	if(l<=tr[u].l&&tr[u].r<=r)
	{
		tr[u].lazy=k;
		return ;
	}
	down(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid)
	{
		update(u<<1,l,r,k);
	}
	if(mid>1;
	ask(u<<1,l,mid);
	ask(u<<1|1,mid+1,r);
	
}
bool cmp(int x,int y)
{
	return x<=y;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		num.clear();
		cin>>n;
		vector >ve;
		vectorv; 
		int x,y;
		//离散化处理 
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d",&x,&y);
			ve.push_back({x,y});
			v.push_back(x);
			v.push_back(y);
		}
		sort(v.begin(),v.end());
        //去重
		v.erase(unique(v.begin(),v.end()),v.end());
		int index=0;
		int a[N];
		a[0]=1;
		int kk=1;
		for(int i=0;i

注意
我在这里的sort本来使用了cmp，我返回值是a<=b，错误了，使得runtime error，cmp要严格单调
参考	https://blog.csdn.net/Strengthennn/article/details/107738011


					
					
					
						相关
						
				
						
			
																
								
										#直径，线段树#51nod 1766 树上的最远点对
									
									
								 

        
								
							
							

																
								
										「NOI2020」命运（树形DP+线段树合并）
									
									
								 

        
								
							
							

																
								
										线段树学习笔记 1
									
									
								 

        
								
							
							

																
								
										关于 线段树 的一些认识
									
									
								 

        
								
							
							

																
								
										线段树
									
									
								 

        
								
							
							

																
								
										[NOI2015]软件包管理器（巧用线段树）
									
									
								 

        
								
							
							

																
								
										P6242 【模板】线段树 3
									
									
								 

        
								
							
							

																
								
										P5494 【模板】线段树分裂
									
									
								 

        
								
							
							

																
								
										CF1557D Ezzat and Grid（线段树）
									
									
								 

        
								
							
							

																
								
										cf739 C. Alyona and towers（线段树）
									
									
								 

        
								
							
							

																
								
										可持久化线段树
									
									
								 

        
								
							
							

																
								
										Codeforces Round #625 Div1 C,二维偏序，排序+线段树

F.Count Color

Mayor's poster

题意

思路

建树

AC代码

注意

相关

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于线段树的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

P6242 【模板】线段树 3

P5494 【模板】线段树分裂

CF1557D Ezzat and Grid（线段树）

cf739 C. Alyona and towers（线段树）

可持久化线段树

Codeforces Round #625 Div1 C,二维偏序，排序+线段树

标签