电商网站对比,镇江高端网站建设工作室,wordpress pc6,上海招聘信息最新招聘2021P3740 [HAOI2014] 贴海报 题解
思路
我们模拟一下贴海报的过程#xff0c;先把 x ∼ y x\sim y x∼y的数字全部变成 k k k。后面的数字可以覆盖前面的数字。 如果for循环枚举的话是会超时的#xff0c;我们考虑用线段树维护区间数字。
那么所有操作结束后如果当前区间还…P3740 [HAOI2014] 贴海报 题解
思路
我们模拟一下贴海报的过程先把 x ∼ y x\sim y x∼y的数字全部变成 k k k。后面的数字可以覆盖前面的数字。 如果for循环枚举的话是会超时的我们考虑用线段树维护区间数字。
那么所有操作结束后如果当前区间还有当前数字 a n s ans ans。 那么这么判断呢 也就是pushup怎么做
求最小值最好了。因为每个区间的最小值只能是当前数字因为当前区间已经被当前数字全部覆盖了。
代码
#includebits/stdc.h
#includecstring
#includequeue
#includeset
#includestack
#includevector
#includemap
#define ll long long
#define lhs printf(\n);
#define sync std::ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0);
using namespace std;
const int N3e510;
const int M2021;
const int inf0x3f3f3f3f;
mapint,int mp;
int n,m;
int num[N],len1;
int ans;
int minn[N];
int lazy[N];
struct node
{int x,y;
}a[N];
bool cmp(node xx,node yy)
{return xx.xyy.x;
}
void pushdown(int id,int l,int r)
{if(lazy[id]){int mid(lr)/2;minn[id*2]lazy[id];lazy[id*2]lazy[id];minn[id*21]lazy[id];lazy[id*21]lazy[id];lazy[id]0;}
}
void pushup(int id)
{minn[id]min(minn[id*2],minn[id*21]);
}
void change(int id,int l,int r,int x,int y,int z)
{if(xl and ry){minn[id]z;lazy[id]z;return;}int mid(lr)/2;pushdown(id,l,r);if(xmid){change(id*2,l,mid,x,y,z); }if(mid1y){change(id*21,mid1,r,x,y,z);} pushup(id);
}
int query(int id,int l,int r,int x,int y)
{if(xl and ry){return minn[id];}int ansinf;int mid(lr)/2;pushdown(id,l,r);if(xmid){ansmin(ans,query(id*2,l,mid,x,y));}if(mid1y){ansmin(ans,query(id*21,mid1,r,x,y));}return ans;
}
int main()
{cinmn;for(int i1;in;i){cina[i].xa[i].y; len1;num[len1]a[i].x;len1;num[len1]a[i].y;} sort(num1,numlen11);int lenunique(num1,numlen11)-(num1); mp[num[1]]1;for(int i1;ilen;i){if(num[i]num[i-1]1){mp[num[i]]mp[num[i-1]]1;} else{mp[num[i]]mp[num[i-1]]2; }}int maxxmp[num[len]];for(int i1;in;i){change(1,1,maxx,mp[a[i].x],mp[a[i].y],i);} for(int i1;in;i){if(query(1,1,maxx,mp[a[i].x],mp[a[i].y]) i){ans;}}coutans;return 0;
}AC记录
附上封面(
