电商网站的多选菜单插件,做好公司网站,房屋装修公司哪家好,wordpress 系统安装https://codeforces.com/problemset/problem/1887/D
左边区间最大值小于右边区间最小值
肯定要离线
感觉分治#xff1f; 枚举左边区间最大值
求出其影响范围#xff0c;推出左端点可取范围
然后可取右端点就是一段连续大于此值得区间
也就是左端点在一段区间时右端点可…https://codeforces.com/problemset/problem/1887/D
左边区间最大值小于右边区间最小值
肯定要离线
感觉分治 枚举左边区间最大值
求出其影响范围推出左端点可取范围
然后可取右端点就是一段连续大于此值得区间
也就是左端点在一段区间时右端点可以在另一端区间取
差分一下拿个数据结构维护即可
发现枚举最大值过程从大往小枚举最优。求范围set即可 后面官方题解有另一种理解
映射到坐标系上相当于一堆矩形询问点是否在矩形内
扫描线即可
#includebits/stdc.h
using namespace std;
//#define int long long
inline int read(){int x0,f1;char chgetchar(); while(ch0||
ch9){if(ch-)f-1;chgetchar();}while(ch0ch9){
x(x1)(x3)(ch^48);chgetchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 300010
//#define M
//#define mo
struct node {int x, id;
}b[N];
struct Node {int x, l, r, op;
}a[N2];
int n, m, i, j, k, T;
int ans[N], l, r, q;
setints, Nots;
setint::iterator it1, it2, it3; bool cmp(Node x, Node y) {if(x.x y.x) return x.op y.op; return x.x y.x;
}struct Sline {int i, k, rt; struct Segment_tree {int tot, ls[N2], rs[N2]; int s[N2]; void build(int k, int l, int r) {if(!k) ktot; if(lr) return ; int mid(lr)1; build(ls[k], l, mid); build(rs[k], mid1, r); }void push_down(int k) {s[ls[k]]s[k]; s[rs[k]]s[k]; s[k]0; }void add(int k, int l, int r, int x, int y, int z) {if(lx ry) return s[k]z, void(); int mid(lr)1; push_down(k); if(xmid) add(ls[k], l, mid, x, y, z); if(ymid1) add(rs[k], mid1, r, x, y, z); }int que(int k, int l, int r, int x) {if(lr) return s[k]; int mid(lr)1; push_down(k); if(xmid) return que(ls[k], l, mid, x); else return que(rs[k], mid1, r, x); }}Seg;void add_op(int lx, int rx, int ly, int ry) {
// printf([%d %d] [%d %d]\n, lx, rx, ly, ry); a[k].xly; a[k].llx; a[k].rrx; a[k].op1; a[k].xry1; a[k].llx; a[k].rrx; a[k].op-1; }void add_que(int l, int r, int i) {a[k].xr; a[k].ll; a[k].ri; a[k].op2; }void calc() {sort(a1, ak1, cmp); Seg.build(rt, 1, n); for(i1; ik; i) {if(a[i].op 2) {
// printf(Add %d [%d %d] %d\n, a[i].x, a[i].l, a[i].r, a[i].op); Seg.add(1, 1, n, a[i].l, a[i].r, a[i].op); }else {ans[a[i].r]Seg.que(1, 1, n, a[i].l);
// printf(Que : %d | %d(%d)\n, a[i].l, ans[a[i].r], a[i].r); }}}
}San;signed main()
{
// freopen(in.txt, r, stdin);
// freopen(out.txt, w, stdout);
// Tread();
// while(T--) {
//
// }nread(); for(i1; in; i) b[i].xread(), b[i].idi; sort(b1, bn1, [] (node x, node y) { return x.xy.x; }); for(i1; in1; i) Nots.insert(i); s.insert(0); s.insert(n1); for(j1; jn; j) {i b[j].id; it1 it2 s.lower_bound(i); --it1; it3 Nots.lower_bound(*it2); s.insert(i); Nots.erase(i); San.add_op((*it1)1, i, (*it2), (*it3)-1); }qread(); for(i1; iq; i) {l read(); r read(); San.add_que(l, r, i); }San.calc(); for(i1; iq; i) printf(ans[i] ? Yes\n : No\n); return 0;
}
