【洛谷P7290】「EZEC-5」暴力出奇迹

Author Avatar
mrsrz 1月 27, 2021

分块。

题目大意：

给定一个平面，有 $n$ 条线段，第 $i$ 条线段的端点为 $(i,a_i)$ 和 $(i,b_i)$。

$m$ 组询问，每次给出 $l,r,x,y$，你要选择一个 $i\in[l,r]$ 使得以 $(x,i)$ 和 $(y,i)$ 为端点的线段与平面上已有线段的交点个数最多。需要回答最多的交点个数。

题解：

这篇题解仅讲述问题的转化。

先将题意转述为更容易理解的形式。

有 $n$ 个操作，第 $i$ 个操作为 $[l_i,r_i]$，表示对 $[l_i,r_i]$ 区间加一。

$m$ 组询问，每次给出 $l,r,x,y$，要求对一个初始为空的序列执行编号在 $x$ 到 $y$ 之间的操作，然后查询区间 $[l,r]$ 的最大值。

考虑对区间加进行差分，即将 $[l,r]$ 的区间加变成 $l$ 处加一，$r+1$ 处减一，然后区间查询，相当于查询右端点在 $[x,y]$ 内的前缀的最大前缀和。不难发现，$1\sim x-1$ 处的值一定会被统计到答案中，因此可以把询问分成查询 $[1,x-1]$ 的和，以及 $[x,y]$ 的区间最大前缀和。前者可以使用二维数点在 $O(n\log n+m\log n)$ 内解决，重点在于求出后者。

对每个 $i$，从 $[l_i,r_i]$ 中可以得到两个三元组 $(l_i,i,1)$，$(r_i,i,-1)$。

我们将所有三元组以第一个元素为关键字从小到大排序，得到一个长度为 $2n$ 的三元组序列。我们称位置 $i$ 的第三个元素为位置 $i$ 的值（为保证结果正确，在第一个元素相同时，值为 $1$ 的在前）。然后一次查询的 $[x,y]$ 对应这个序列上的一个区间。

于是现在的查询操作实际上是：仅保留第二个元素在 $[l,r]$ 内的位置的值，其他位置的值为 $0$ 时，查询 $[x,y]$ 对应的区间的区间最大前缀和。

这个问题有一个强化版的问题，查询的是最大子段和信息，而维护该信息的同时需要维护本题所需的最大前缀和信息。因此直接使用该题的做法即可解决本题。具体可以见我的题解。

该做法的时间复杂度为 $O((n+m)\sqrt n)$，空间复杂度为 $O(n+m)$，实现时需要注意常数因子。

Code：

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef unsigned long long u64;
const int N=5e5+5,siz=800,B=siz+2;
int n,m,b[B],tmp[N],prex[N];
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,5000000,stdin),pa==pb)?EOF:*pa++
static char buf[5000000],*pa(buf),*pb(buf);
inline int readint() {
    int x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15);
    return x;
}
struct ostream {
    static const int size = 1 << 22;
    char buf[size], *vout;
    unsigned map[10000];
    inline ostream() {
        for(int i = 0;i < 10000;++i) {
            map[i] = i % 10 + 48 << 24 | i / 10 % 10 + 48 << 16 | i / 100 % 10 + 48 << 8 | i / 1000 + 48;
        }
        vout = buf + size;
    }
    inline ~ ostream()
    { fwrite(vout,1,buf + size - vout,stdout), std::cerr << double(clock()) / CLOCKS_PER_SEC << '\n'; }
    inline ostream& operator << (unsigned x) {
        for(;x >= 10000;x /= 10000) *--(unsigned*&)vout = map[x % 10000];
        do *--vout = x % 10 + 48; while(x /= 10);
        return * this;
    }
    inline ostream& operator << (char x) {
        *--vout = x;
        return * this;
    }
} Cout;
struct dat{
    int x,v,k;
    inline bool operator<(const dat&rhs)const{return x==rhs.x?v>rhs.v:x<rhs.x;}
}a[N],g[B],h[B];
inline bool operator < (const dat & rhs, int x) { return rhs.x < x; }
inline bool operator < (int x, const dat & rhs) { return x < rhs.x; }
struct xppsb { int V, K; } AAAA[N];
struct info{
    int lmx,sum;
    inline info(int a,int b):lmx(a),sum(b){}
    inline info(){}
    inline void set(const info & lhs, const info & rhs) {
        lmx = max(lhs.lmx, lhs.sum + rhs.lmx);
        sum = lhs.sum + rhs.sum;
    }
    inline info operator+(const info&rhs)const{
        return info(max(lmx,sum+rhs.lmx),sum+rhs.sum);
    }
    inline void operator+=(const info&rhs){
        lmx=max(lmx,sum+rhs.lmx),sum+=rhs.sum;
    }
}ans[N],Lt[2000000],Rt[2000000],mem[2000000],*const qt=mem+1;
struct Sinfo{
    int zt;
    info v;
}D[8000000],*ed;
struct que{
    int L,R,l,r;
}q[N];
pair<int,int>Q[N];
void solve(int l,int r,Sinfo*V,int&tot){
    if(l==r){
        V[tot++]=(Sinfo){b[l]<<10|b[r],info(h[l].v,h[r].v)};
        return;
    }
    const int mid=(l+r)/2;
    Sinfo*L=ed;ed+=(mid-l+1)*(mid-l+2);
    Sinfo*R=ed;ed+=(r-mid)*(r-mid+1);
    int cntL=0,cntR=0;
    solve(l,mid,L,cntL);
    solve(mid+1,r,R,cntR);
    int i=l,j=mid+1,t=l,k=0;
    while(i<=mid&&j<=r)
    if(b[i]<b[j])tmp[t++]=b[i++];else tmp[t++]=b[j++];
    while(i<=mid)tmp[t++]=b[i++];
    while(j<=r)tmp[t++]=b[j++];
    for(int i=0;i<cntL;++i)Lt[L[i].zt+1]=L[i].v;
    for(int i=0;i<cntR;++i)Rt[R[i].zt+1]=R[i].v;
    static int LfL[B],LfR[B],RgL[B],RgR[B];
    t=l,k=mid+1;
    for(int i=l;i<=r;++i){
        while(t<=mid&&b[t]<tmp[i])++t;
        while(k<=r&&b[k]<tmp[i])++k;
        LfL[i]=t<=mid?b[t]:B,RgL[i]=k<=r?b[k]:B;
    }
    t=mid,k=r;
    for(int i=r;i>=l;--i){
        while(t>=l&&b[t]>tmp[i])--t;
        while(k>mid&&b[k]>tmp[i])--k;
        LfR[i]=t>=l?b[t]:-1,RgR[i]=k>mid?b[k]:-1;
    }
    for(int i=l;i<=r;++i)b[i]=tmp[i];
    for(int i=l;i<=r;++i) {
        int idx = tot - i;
        for(int j=i;j<=r;++j){
            const info&ztL=Lt[LfL[i]<<10|(LfR[j]+1u)],&ztR=Rt[RgL[i]<<10|(RgR[j]+1u)];
            const int nt=b[i]<<10|b[j];
            V[idx + j].zt = nt;
            V[idx + j].v.set(ztL, ztR);
        }
        tot += r - i + 1;
    }
    ed=L;
}
inline void up(int & x, int y) {
    if(x < y) x = y;
}
info get(int L,int R,int l,int r){
    int rx=0,sm=0;
    const unsigned A = r - l;
    for(int i=L;i<=R;++i)if(AAAA[i].K-l<=A)up(rx,sm+=AAAA[i].V);
    return info(rx,sm);    
}
int BT[N];
inline void add(int i,int x){for(;i<=n>>1;i+=i&-i)BT[i]+=x;}
inline int ask(int i){int x=0;for(;i;i&=i-1)x+=BT[i];return x;}
void _2D(){
    sort(Q+1,Q+m+1);
    for(int i=1,it=1;i<=m;++i){
        while(it<=Q[i].fi)add(a[it].k,a[it].v),++it;
        int id=Q[i].se;
        prex[id]=ask(q[id].r)-ask(q[id].l-1);
    }
}
int main(){
    n=readint()<<1;
    for(int i=1;i<=n;i+=2){
        int x=readint(),y=readint();
        a[i]=(dat){x,1,(i+1)/2},a[i+1]=(dat){y,-1,(i+1)/2};
    }
    sort(a+1,a+n+1);
    for(int i = 1;i <= n;++i) {
        AAAA[i].V=a[i].v;
        AAAA[i].K=a[i].k;
    }
    m=readint();
    for(int i=1;i<=m;++i){
        int x=readint(),y=readint();
        q[i].l=readint(),q[i].r=readint();
        q[i].L=lower_bound(a+1,a+n+1,x)-a;
        q[i].R=upper_bound(a+1,a+n+1,y)-a-1;
        Q[i]=make_pair(q[i].L-1,i);
    }
    _2D();
    for(int L=1,R;L<=n;L=R+1){
        R=min(n,L+siz-1);
        int len=R-L+1;
        for(int i=L;i<=R;++i)g[i-L]=h[i-L]=(dat){a[i].k,a[i].v,i-L};
        sort(g,g+len);
        for(int i=0;i<len;++i)b[g[i].k]=i;
        ed=D+len*(len+1);
        int tot=0;
        solve(0,len-1,D,tot);
        for(int i=0;i<tot;++i)qt[D[i].zt+1]=D[i].v;
        static int _[N];
        for(int i=1,it=0;i<=n;++i){
            while(it<len&&g[it].x<i)++it;
            _[i]=it;
        }
        for(int i=1;i<=m;++i)if(q[i].L<L&&R<q[i].R)
        ans[i]+=qt[_[q[i].l]<<10|_[q[i].r+1]];
    }
    for(int i=m;i;--i){
        int l=q[i].L,r=q[i].R;
        int res=0;
        const int bL=(l-1)/siz+1,bR=(r-1)/siz+1;
        if(bR-bL<2)res=get(l,r,q[i].l,q[i].r).lmx;
        else res=(get(l,bL*siz,q[i].l,q[i].r)+ans[i]+get(bR*siz-siz+1,r,q[i].l,q[i].r)).lmx;
        res=prex[i]+max(0,res);
        Cout<<'\n'<<unsigned(res);
    }
    return 0;
}
Powered by Hexo
Theme - Material