Codeforces Round #524 (Div. 2) F

题解：

首先这个东西因为强制在线区间查询

所以外面得套线段树了

然后考虑几条线段怎么判定

我们只需要按照右端点排序，然后查询的时候查找最右节点的前缀最大值就可以了

然后怎么合并子区间信息呢

（刚开始我很zz的觉得应该要线段树合并。。）

线段树都保证了区间一样大每个点暴力也就会算log次。。

于是就直接暴力合并就好了

复杂度$nlogn^2$

然后因为是cf题。。完全不管常数成功跑了luogu倒数rank1

感觉前面跑那么快应该是有$nlogn$的做法

#updata:

果然是有nlogn的做法

考虑按照x-y的x从大到小排序建立主席树，然后维护每个点y的最小值，线段树上维护最小值的最大值就可以了

于是每次二分找到第一个$>=$它的x位置然后主席树区间查询就可以了

代码：

#include <bits/stdc++.h>

using namespace std;

#define rint register int

#define IL inline

#define rep(i,h,t) for(int i=h;i<=t;i++)

#define dep(i,t,h) for(int i=t;i>=h;i--)

#define ll long long

#define me(x) memset(x,0,sizeof(x))

#define mep(x,y) memcpy(x,y,sizeof(y))

#define mid ((h+t)>>1)

namespace IO{

    char ss[<<],*A=ss,*B=ss;

    IL char gc()

    {

        return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

    }

    template<class T> void read(T &x)

    {

        rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=(c^);

        while (c=gc(),c>&&c<) x=(x<<)+(x<<)+(c^); x*=f;

    }

    char sr[<<],z[]; int Z,C1=-;

    template<class T>void wer(T x)

    {

        if (x<) sr[++C1]='-',x=-x;

        while (z[++Z]=x%+,x/=);

        while (sr[++C1]=z[Z],--Z);

    }

    IL void wer1()

    {

        sr[++C1]=' ';

    }

    IL void wer2()

    {

        sr[++C1]='\n';

    }

    template<class T>IL void maxa(T &x,T y) {if (x<y) x=y;}

    template<class T>IL void mina(T &x,T y) {if (x>y) x=y;}

    template<class T>IL T MAX(T x,T y){return x>y?x:y;}

    template<class T>IL T MIN(T x,T y){return x<y?x:y;}

};

using namespace IO;

const int N=3.1e5;

const int N1=N*;

struct re{

    int a,b;

};

bool cmp(re x,re y)

{

    return x.b<y.b;

}

vector<re> ve[N];

struct sgt{

    vector<re> ve1[N1];

    IL void updata(int x)

    {

        int l1=(int)(ve1[x*].size())-;

        int l2=(int)(ve1[x*+].size())-;

        int h1=,h2=,lst1=,lst2=;

        while (h1<=l1||h2<=l2)

        {

            int t;

            if (h1<=l1&&h2<=l2)

              t=MIN(ve1[x*][h1].b,ve1[x*+][h2].b);

            else if (h1<=l1) t=ve1[x*][h1].b; else t=ve1[x*+][h2].b;

            while (h1<=l1&&ve1[x*][h1].b==t)

              maxa(lst1,ve1[x*][h1].a),h1++;

            while (h2<=l2&&ve1[x*+][h2].b==t)

              maxa(lst2,ve1[x*+][h2].a),h2++;

            ve1[x].push_back((re){MIN(lst1,lst2),t});

        }

    }

    void build(int x,int h,int t)

    {

        if (h==t)

        {

          int l=(int)(ve[h].size())-;

          rep(i,,l) ve1[x].push_back(ve[h][i]);

          sort(ve1[x].begin(),ve1[x].end(),cmp);

          int lst=;

          rep(i,,l)

          {

              maxa(lst,ve1[x][i].a);

            ve1[x][i].a=lst;

          }

          return;

        }

        build(x*,h,mid); build(x*+,mid+,t);

        updata(x);

    }

    IL bool query(int x,int h,int t,int h1,int t1,int x1,int y)

    {

        if (h1<=h&&t<=t1)

        {

          int h=,t=(int)(ve1[x].size())-;

          if (t<) return();

          if (ve1[x][h].b>y) return();

          while (h<t)

          {

              int mid2=(h+t+)/;

              if (ve1[x][mid2].b<=y) h=mid2; else t=mid2-;

          }

          if (ve1[x][h].a>=x1) return(); else return();

        }

        bool tt=;

        if (h1<=mid) tt&=query(x*,h,mid,h1,t1,x1,y);

        if (mid<t1) tt&=query(x*+,mid+,t,h1,t1,x1,y);

        return tt;

    }

}S;

int main()

{

    int n,m,k;

    ios::sync_with_stdio(false);

    cin>>n>>m>>k;

    rep(i,,k)

    {

        int x,y,z;

        cin>>x>>y>>z;

        ve[z].push_back((re){x,y});

    }

    S.build(,,n);

    rep(i,,m)

    {

        int x1,y1,x2,y2;

        cin>>x1>>y1>>x2>>y2;

        if (S.query(,,n,x1,y1,x2,y2)) cout.flush()<<"yes"<<endl;

        else cout.flush()<<"no"<<endl;

    }

    return ;

}

巴特西

Codeforces Round #524 (Div. 2) F

最新文章

热门文章