在线安装软件网站开发,wordpress环境配置文件,如何免费建购物网站,网站开发用几种字体题目描述
对于一个长度为n的数列给出m个描述 每一个描述给出一个区间[a,b]的最小值的x 求从第几个描述开始矛盾
解析
本题关键是一个关于矛盾的充要条件#xff1a; 如果存在一个最小值x#xff0c;其所在的区间的交集#xff08;就是它真正可以存在的区间#xff09;是…题目描述
对于一个长度为n的数列给出m个描述 每一个描述给出一个区间[a,b]的最小值的x 求从第几个描述开始矛盾
解析
本题关键是一个关于矛盾的充要条件 如果存在一个最小值x其所在的区间的交集就是它真正可以存在的区间是比x大的所有最小值的区间的并集的子集那么就会矛盾因为x肯定在那些区间中的一个里那么那个区间的最小值就应该是x了 知道这个之后后面就好做了 把所有区间按最小值降序排序 二分出现矛盾的位置mid 每次按新顺序考虑mid之前的描述 用线段树维护之前所有的并集并查询交集 判断是否矛盾即可
复杂度
二分logm\log mlogm 枚举询问mmm 线段树logn\log nlogn 总复杂度m∗logm∗lognm*\log m*\log nm∗logm∗logn
代码
#includebits/stdc.h
#define ll long long
#define mid ((lr) 1)
#define ls k1
#define rs k1|1
using namespace std;
const int N1e6100;
int n,m;
struct node{int a,b,x,id;bool operator (const node y)const{return xy.x;}
}p[N];
int tr[4*N];
void build(int k,int l,int r){if(lr){tr[k]1;return;}build(ls,l,mid);build(rs,mid1,r);tr[k]tr[ls]tr[rs];return;
}
void change(int k,int l,int r,int x,int y){if(tr[k]0) return;if(xlry){tr[k]0;return;}if(xmid) change(ls,l,mid,x,y);if(ymid) change(rs,mid1,r,x,y);tr[k]tr[ls]tr[rs];return;
}
int ask(int k,int l,int r,int x,int y){if(tr[k]0) return 0;if(xlry){return tr[k];}int ans0;if(xmid) ansask(ls,l,mid,x,y);if(ymid) ansask(rs,mid1,r,x,y);tr[k]tr[ls]tr[rs];return ans;
}
bool check(int k){build(1,1,n);int now-1,l,r,ml,mr;for(int i1;im;i){if(p[i].idk) continue;if(p[i].xnow){lmax(p[i].a,l);rmin(p[i].b,r);mlmin(p[i].a,ml);mrmax(p[i].b,mr);}else{//printf(now%d l%d r%d ml%d mr%d\n,now,l,r,ml,mr);if(now!-1ask(1,1,n,l,r)0) return false;if(now!-1) change(1,1,n,ml,mr);lmlp[i].a;rmrp[i].b;nowp[i].x;}}if(ask(1,1,n,l,r)0) return false;else return true;
}
int main(){scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d%d,p[i].a,p[i].b,p[i].x);p[i].idi;}sort(p1,p1m);check(2);int st1,edm;while(sted){int mmidsted11;if(check(mmid)) stmmid;else edmmid-1;}
// printf(%dok ,check(2));printf(%d,st1);
}
/*
20 4
1 10 7
5 19 7
3 12 8
1 20 1
*/
