CF1080F Katya and Segments Sets （可持久化数组，排序降维）

CF1080F Katya and Segments Sets

题目链接：CF1080F

我们考虑先将 $l$ 按从大到小排序，我们就可以降掉一维。

我们通过二分可以在 $log K$ 的时间复杂度内快速找到有效的 $l$ 端点；

我们对于每个 $l$ 的数组下标为根建一个线段树

我们的线段树维护的是：以集合的标号 $p$ 为下标，每一个集合内所有线段的 $r$

考虑每一个 $l$ 只会在 $p$ 处修改一个值，且我们需要查找 $root[1]$ 到 $root[l]$ 的 $r$ 的最小值

所以我们用主席树优化时间和空间

主席树不只只是求区间第K大，它还是可持久化数组

所以我们只需先二分找到第一个大于等于 $x$ 的 $l$ 的数组下标，在在主席树上以该点数组下标为根，查询 $A$ ， $B$ 集合之间的最大值即可

 1 #include<bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define MAXN 300010
 4 using namespace std;
 5 inline int read ()
 6 {
 7     int s=0,w=1;
 8     char ch=getchar ();
 9     while (ch<'0'||ch>'9'){if (ch=='-') w=-1;ch=getchar ();}
10     while ('0'<=ch&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar ();
11     return s*w;
12 }
13 struct Line{
14     int l,r,p;
15     bool operator < (const Line &rhs) const
16     {
17         return l!=rhs.l?l>rhs.l:r>rhs.r;
18     }
19 }a[MAXN];
20 struct President_Tree{
21     int l,r,Min;
22     President_Tree(){Min=INF;}
23 }tr[MAXN*50];
24 int n,m,k,len;
25 int root[MAXN];
26 void pushup (int x)
27 {
28     tr[x].Min=max (tr[tr[x].l].Min,tr[tr[x].r].Min);
29 }
30 void update (int &x,int y,int pos,int val,int l,int r)
31 {
32     tr[x=++len]=tr[y];
33     if (l==r)
34     {
35         tr[x].Min=min (tr[x].Min,val);
36         return;
37     }
38     int mid=(l+r)>>1;
39     if (pos<=mid) update (tr[x].l,tr[y].l,pos,val,l,mid);
40     else update (tr[x].r,tr[y].r,pos,val,mid+1,r);
41     pushup (x);
42 }
43 int query (int x,int l,int r,int ql,int qr)
44 {
45     if (ql<=l&&r<=qr) return tr[x].Min;
46     int mid=(l+r)>>1;
47     int ans=-INF;
48     if (ql<=mid) ans=max (ans,query (tr[x].l,l,mid,ql,qr));
49     if (mid<qr) ans=max (ans,query (tr[x].r,mid+1,r,ql,qr));
50     return ans;
51 }
52 int main()
53 {
54     n=read (),m=read (),k=read ();
55     for (int i=1;i<=k;i++)
56         a[i].l=read (),a[i].r=read (),a[i].p=read ();
57     sort (a+1,a+k+1);
58     for (int i=1;i<=k;i++)
59         update (root[i],root[i-1],a[i].p,a[i].r,1,n);
60     while (m--)
61     {
62         int x=read (),y=read (),l=read (),r=read ();
63         int L=1,R=k;
64         while (L<R)
65         {
66             int mid=(L+R+1)>>1;
67             if (a[mid].l>=l) L=mid;
68             else R=mid-1;
69         }
70         if (a[L].l<l) printf ("no
");
71         else
72         {
73             int ans=query (root[L],1,n,x,y);
74             if (ans<=r) printf ("yes
");
75             else printf ("no
");
76         }
77         fflush (stdout);
78     }
79     return 0;
80 }