用手机域名做网站,淘宝网站首页怎么做,枣庄网站建设制作,实现wordpress redis加速正题 题意
一块长m的墙#xff0c;有n个大小不同的盒子放在前面#xff0c;求可以看到多少盒子 解题思路
用线段树#xff0c;用cover表示可以看到的颜色#xff0c;-1表示可以看到多种颜色#xff0c;然后统计#xff0c;用find数组去重。 代码
#includecstdio…正题 题意
一块长m的墙有n个大小不同的盒子放在前面求可以看到多少盒子 解题思路
用线段树用cover表示可以看到的颜色-1表示可以看到多种颜色然后统计用find数组去重。 代码
#includecstdio
using namespace std;
struct xjq{int l,r,cover;
}tree[400001];
int n,ll,rr,w,s;
bool flag[100001];
void build(int x,int a,int b)//建树
{tree[x].la;tree[x].rb;if (b-a1) return;else{int m(ab)/2;build(x*2,a,m);build(x*21,m,b);}
}
void inster(int x,int a,int b,int c)//插入
{if (tree[x].coverc) return;if (tree[x].la tree[x].rb) //标记颜色{tree[x].coverc;return;}if (tree[x].cover0)//下传颜色{tree[x*2].covertree[x].cover;tree[x*21].covertree[x].cover;tree[x].cover-1;}int m(tree[x].rtree[x].l)/2;if (bm) inster(x*2,a,b,c);else if (am) inster(x*21,a,b,c);else{inster(x*2,a,m,c);inster(x*21,m,b,c);}return;
}
void find(int x)
{if (tree[x].cover0 !flag[tree[x].cover]){s;flag[tree[x].cover]true;//标记去重}if (tree[x].cover0) return;if (tree[x].r-tree[x].l1) return;else {find(x*2);find(x*21);return;}
}
int main()
{scanf(%d,w);scanf(%d,n);build(1,1,w);flag[0]true;for (int i1;in;i){scanf(%d%d,ll,rr);inster(1,ll,rr,i);}s0;find(1);printf(%d,s);
}
