题解 P6109 【[Ynoi2009]rprmq】

w4p3r · 2020-07-22 12:15:10 · 题解

一丶前言

这道题可能是本蒟蒻做过的最巧的数据结构题，没有之一qaq。

二丶思路

我们可以先考虑这样一种做法。首先对于(l_1,r_1,l_2,r_2,v)的修改操作，可以视作我们在l_1行时对l_2到r_2这个区间+v，再在r_1+1行时对l_2到r_2这个区间-v。（这样我们把一个修改操作分解成了两个修改操作）

我们考虑从小到大枚举L，并处理所有l_1=L的询问操作。然后我们先把所有修改操作进行分解，并从小到大枚举R（枚举的时候要把修改操作加进去）。我们取出所有L=l_1,R=r_1的询问操作，并对l_2到r_2这个区间进行询问。

我们询问的是什么呢？可以发现，其实我们询问的其实是历史最大值，而修改操作就是一个区间加，所以我们只要维护一个可以支持区间历史最大值和区间加的线段树即可（CPU监控简化版）。

由于这个东西比较简单，就不细讲怎么维护了

注意一个小细节，若一个时间点有多次修改，要先加负数再加正数，不然历史最大值可能只加入一个时间点的部分操作，这样是不合法的。

这样时间复杂度是O((n^2+q)logn)的，(好像时间复杂度更高了)，但可喜可贺的是我们把询问从两个log变成了一个log。

考虑在这个算法的基础上继续进行优化。

可以发现对于一个询问，我们要将1到l_1-1所有操作插入（不维护历史最大值），并再将l_1到r_1的操作插入（在插入时要维护历史最大值），并区间询问历史最大值。

考虑线段树分治，假设当前线段树节点代表的区间为l,r，mid=(l+r)/2。

对于所有l<=l_1<=r_1<=r的询问，若r_1<=mid或者l_1>mid则交给儿子处理，否则就在当前点处理（不能把询问拆成log个，不然时间复杂度还是要起飞）。

我们假设1到l-1的操作已经加入到线段树中（注意区分维护历史最大值的线段树和线段树分治的线段树）。

考虑先处理右边的贡献，所以先把l到mid的操作插入（不求历史最大值），然后把所有当前点的询问按r从小到大排序，并依次插入操作（此时就要求历史最大值了）和进行询问，然后把mid+1到r的操作回退，并递归右子树（依然满足1到l-1的操作已被加入）。

然后考虑处理左边的贡献，按l从大到小排序，然后进行类似的操作并递归左子树即可。（这个处理的顺序不是固定的，你先遍历左子树再处理左边的贡献再遍历右子树再处理右边的贡献也是可以的）。

（前面那堆东西可能有点冗杂，但如果理解了前面的话再看看代码应该就没问题了）

这样时间复杂度就是O(nlog^2n+qlogn)了

三丶代码

因为lxl貌似并不希望有人抄代码所以去了头文件。

//W4P3R
#define N 500010
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline ll read()
{
    char ch=getchar();
    ll s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
ll n,m,q,ans[N];
struct TREE{ll maxn,hmax,tag1,tag2,res;};
struct ask{ll id,l,r,x,y;}a[N];
struct node{ll l,r,val;};vector<node>v[N];
vector<ask>que[N<<2];
struct Segement_Tree
{
    TREE t[N<<2];
    inline void addtag(ll x,ll v1,ll v2)
    {
        t[x].hmax=max(t[x].maxn+v2,t[x].hmax);t[x].maxn+=v1;
        t[x].tag2=max(t[x].tag1+v2,t[x].tag2);t[x].tag1+=v1;
    }//维护历史最大值
    inline void reset(ll x)
    {
        addtag(ls,t[x].tag1,t[x].tag2);addtag(rs,t[x].tag1,t[x].tag2);
        t[x].tag1=t[x].tag2=0;
        t[x].hmax=t[x].maxn;t[x].res=1;
    }//把历史最大值重置为当前最大值
    inline void pushdown(ll x)
    {
        if(t[x].res){reset(ls);reset(rs);t[x].res=0;}
        addtag(ls,t[x].tag1,t[x].tag2),addtag(rs,t[x].tag1,t[x].tag2);
        t[x].tag1=t[x].tag2=0;
    }
    inline void pushup(ll x)
    {
        t[x].maxn=max(t[ls].maxn,t[rs].maxn);
        t[x].hmax=max(t[ls].hmax,t[rs].hmax);
    }
    void update(ll l,ll r,ll x,ll left,ll right,ll val)
    {
        if(l==left&&right==r){addtag(x,val,val);return ;}
        pushdown(x);
        if(right<=mid)update(l,mid,ls,left,right,val);
        else if(left>mid)update(mid+1,r,rs,left,right,val);
        else update(l,mid,ls,left,mid,val),update(mid+1,r,rs,mid+1,right,val);
        pushup(x);
    }
    ll query(ll l,ll r,ll x,ll left,ll right)
    {
        if(l==left&&right==r)return t[x].hmax;
        pushdown(x);
        if(right<=mid)return query(l,mid,ls,left,right);
        else if(left>mid)return query(mid+1,r,rs,left,right);
        else return max(query(l,mid,ls,left,mid),query(mid+1,r,rs,mid+1,right));
    }
}T;//维护历史最大值的线段树
void add(ll x,ll l,ll r,ask p)
{
    if(p.l<=mid+1&&mid<=p.r){que[x].pb(p);return ;}//把询问加入当前点
    if(p.r<=mid)add(ls,l,mid,p);
    else add(rs,mid+1,r,p);
}
inline ll cmp(node a,node b){return a.val<b.val;}
inline ll cmp1(ask a,ask b){return a.r<b.r;}
inline ll cmp2(ask a,ask b){return a.l>b.l;}
inline void Up(ll x,ll opt)
{
    if(opt==1){for(auto p:v[x]){T.update(1,n,1,p.l,p.r,p.val);}}
    else {REP(i,v[x].size()-1,0)T.update(1,n,1,v[x][i].l,v[x][i].r,-v[x][i].val);}
}//1是加入操作，-1是回退操作
void Solve(ll x,ll l,ll r)
{
    FOR(i,l,mid)Up(i,1);//把l到mid的操作加入
    ll cnt=0,nowp=1;
    for(auto p:que[x])a[++cnt]=p;//将询问按r从小到大排序
    sort(a+1,a+cnt+1,cmp1);
    while(nowp<=cnt&&a[nowp].r==mid)nowp++;//r=mid的询问肯定跟右边的修改无关啦
    FOR(i,mid+1,r)
    {
        Up(i,1);//加入当前修改
        if(i==mid+1)T.reset(1);//1到mid的修改操作不应该求历史最大值
        while(a[nowp].r==i&&nowp<=cnt){ans[a[nowp].id]=max(ans[a[nowp].id],T.query(1,n,1,a[nowp].x,a[nowp].y));nowp++;}//正常的询问
    }
    REP(i,r,mid+1)Up(i,-1);//回退
    if(l!=r)Solve(rs,mid+1,r);//遍历右子树
    cnt=0,nowp=1;
    for(auto p:que[x])a[++cnt]=p;
    sort(a+1,a+cnt+1,cmp2);//将询问按l从大到小排序
    while(nowp<=cnt&&a[nowp].l==mid+1)nowp++;//同上
    REP(i,mid,l)
    {
        if(i==mid)T.reset(1);
        while(a[nowp].l==i&&nowp<=cnt){ans[a[nowp].id]=max(ans[a[nowp].id],T.query(1,n,1,a[nowp].x,a[nowp].y));nowp++;}
        Up(i,-1);
    }//同上
    if(l!=r)Solve(ls,l,mid);//遍历左子树
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read(),q=read();
    FOR(i,1,m)
    {
        ll l=read(),x=read(),r=read(),y=read(),val=read();
        v[l].pb((node){x,y,val});
        v[r+1].pb((node){x,y,-val});
    }
    FOR(i,1,q)
    {
        ll l=read(),x=read(),r=read(),y=read();
        add(1,1,n,(ask){(ll)i,l,r,x,y});
    }
    FOR(i,1,n)sort(v[i].begin(),v[i].end(),cmp);
    Solve(1,1,n);
    FOR(i,1,q)printf("%lld\n",ans[i]);
    return 0;
}

如果你觉得这篇题解对你有帮助，那你可以点个赞支持我一下qwq。如果你对题解有任何问题/认为我的题解有任何问题，可以私信/在评论区发出来，当然如果你对我的题解有任何意见/建议也欢迎指出。我会尽我全力把我题解写到最好的qwq