电商网站设计规范,手机网站标准,wordpress左右滑动页面,wordpress注册邮件自定义题目链接#xff1a;洛谷 题目描述#xff1a;【看翻译】 这种强制在线的方法可真是奇妙。 主席树可真是奇妙。 我们用主席树的版本维护$x\leq l$的限制#xff0c;用线段树维护$[a,b]$的限制#xff0c;用节点的值来维护$r\leq y$的限制。 详细地说#xff0c;就是先将线…题目链接洛谷 题目描述【看翻译】 这种强制在线的方法可真是奇妙。 主席树可真是奇妙。 我们用主席树的版本维护$x\leq l$的限制用线段树维护$[a,b]$的限制用节点的值来维护$r\leq y$的限制。 详细地说就是先将线段排序$l$为第一关键字$r$为第二关键字然后倒序把所属集合作为位置右端点作为值插入主席树。 主席树的第$i$个版本维护的是排序后后面$k-i1$个线段的线段树。 因为它要求集合里面有一个满足就可以所以同一个位置的右端点取最小值。 因为它要求$[a,b]$的集合都要满足所以线段树维护区间最大值。 每次查询的时候找到左端点$\geq x$的最靠前的线段设为第$i$个则在第$i$个版本中看$[a,b]$的最大值是否$\leq y$如果是就是yes否则就是no。 1 #includebits/stdc.h2 #define Rint register int3 using namespace std;4 const int N 300003, INF 0x3f3f3f3f;5 struct Seg {6 int l, r, p;7 inline bool operator (const Seg o) const {return l o.l || l o.l r o.r;}8 } a[N];9 int n, m, k, cnt, root[N], seg[N 5], ls[N 5], rs[N 5];
10 inline void pushup(int x){
11 seg[x] max(seg[ls[x]], seg[rs[x]]);
12 }
13 inline void build(int x, int L, int R){
14 seg[x cnt] INF;
15 if(L R) return;
16 int mid L R 1;
17 build(ls[x], L, mid);
18 build(rs[x], mid 1, R);
19 }
20 inline void change(int nx, int ox, int L, int R, int pos, int val){
21 seg[nx cnt] seg[ox];
22 ls[nx] ls[ox]; rs[nx] rs[ox];
23 if(L R){
24 seg[nx] min(seg[nx], val);
25 return;
26 }
27 int mid L R 1;
28 if(pos mid) change(ls[nx], ls[ox], L, mid, pos, val);
29 else change(rs[nx], rs[ox], mid 1, R, pos, val);
30 pushup(nx);
31 }
32 inline int query(int x, int L, int R, int l, int r){
33 if(l L R r) return seg[x];
34 int mid L R 1, ans 0;
35 if(l mid) ans max(ans, query(ls[x], L, mid, l, r));
36 if(mid r) ans max(ans, query(rs[x], mid 1, R, l, r));
37 return ans;
38 }
39 int main(){
40 scanf(%d%d%d, n, m, k);
41 for(Rint i 1;i k;i )
42 scanf(%d%d%d, a[i].l, a[i].r, a[i].p);
43 sort(a 1, a k 1);
44 build(root[k 1], 1, n);
45 for(Rint i k;i;i --)
46 change(root[i], root[i 1], 1, n, a[i].p, a[i].r);
47 a[k 1].l INF;
48 while(m --){
49 int A, B, X, Y;
50 scanf(%d%d%d%d, A, B, X, Y);
51 int ans -1, mid, left 1, right k 1;
52 while(left right){
53 mid left right 1;
54 if(a[mid].l X) ans mid, right mid - 1;
55 else left mid 1;
56 }
57 puts(query(root[ans], 1, n, A, B) Y ? yes : no);
58 fflush(stdout);
59 }
60 } View Code 转载于:https://www.cnblogs.com/AThousandMoons/p/ntfakgdoi.html
