Liveddd's Blog

愛にできることはまだあるかい

P6109 [Ynoi2009] rprmq1

发表于 分类于
本文字数： 4.9k 阅读时长 ≈ 11 分钟

线段树 + 猫树分治

修改均在询问之前，相当于没有时间轴，于是是离线下来。但是二维我们还是不好做，考虑将 $x$ 这一维看作时间轴，只考虑 $y$ 这一维的答案。我们考虑类似扫描线的过程，将修改操作拆成 $(l_x,l_y,r_y,x),(r_x+1,l_y,r_y,-x)$。那么询问就变成了 $[l_x,r_x]$ 这段时间内最值的查询。但是仍然不好处理，因为最值查询不满足可减性。

但是其满足快速合并的性质，容易想到对 $x$ 这一维进行猫树分治，过程中用历史最值线段树维护。

每次将跨过中点的询问按照中点分开，向两边扩展，在本层处理并合并答案；否则下放到分治的下一层处理。

而对于修改操作，假设当前求 $[l,mid]$ 的答案，我们对于另一半 $[mid+1,r]$ 的修改全部加入（但是不更新历史最值），再进行扫描线加入 $[l,mid]$ 的修改，并且处理询问。需要注意的是要先处理右端点的修改，否则历史最值可能会出错。

每个修改操作在每一层都会被执行一次，而每个查询只会被执行一次，所以时间复杂度为 $\mathcal O(m\log^2 n+q\log n)$。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N=5e4+10,M=5e4+10,Q=5e5+10;
const ll INF=1e18;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,q;
int pos;
ll ans[Q];
struct Modify
{
    int t,l,r,x;
    const bool operator<(const Modify &e)const{if(t!=e.t)return t<e.t;return x<e.x;} 
}a[M<<1];
struct Query
{
    int id,tl,tr,l,r;
}b[Q];
vector<int>p[N];

struct Node
{
    int l,r;
    ll v,vh;
    ll a,ah;
    bool s;
    ll tag;
};
struct Seg
{
    Node tr[N<<2];
    void pushup(int x)
    {
        tr[x].v=max(tr[x<<1].v,tr[x<<1|1].v);
        tr[x].vh=max(tr[x<<1].vh,tr[x<<1|1].vh);
    }
    void build(int x,int l,int r)
    {
        tr[x].l=l,tr[x].r=r;
        if(l==r)return ;
        int mid=l+r>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    }
    void update(int x,ll k,ll kh)
    {
        tr[x].vh=max(tr[x].vh,tr[x].v+kh),tr[x].v+=k;
        tr[x].ah=max(tr[x].ah,tr[x].a+kh),tr[x].a+=k;
    }
    void set(int x,ll k)
    {
        tr[x].vh=(tr[x].v+=k);
        tr[x].tag+=tr[x].a+k,tr[x].s=1;
        tr[x].a=tr[x].ah=0;
    }
    void pushdown(int x)
    {
        if(tr[x].s)set(x<<1,tr[x].tag),set(x<<1|1,tr[x].tag),tr[x].s=0,tr[x].tag=0;
        if(tr[x].a||tr[x].ah)update(x<<1,tr[x].a,tr[x].ah),update(x<<1|1,tr[x].a,tr[x].ah),tr[x].a=tr[x].ah=0;
    }
    void modify(int x,int l,int r,ll k)
    {
        if(l<=tr[x].l&&r>=tr[x].r)return update(x,k,k);
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        if(l<=mid)modify(x<<1,l,r,k);
        if(r>mid)modify(x<<1|1,l,r,k);
        pushup(x);
    }
    ll query_h(int x,int l,int r)
    {
        if(l<=tr[x].l&&tr[x].r<=r)return tr[x].vh;
        pushdown(x);
        int mid=tr[x].l+tr[x].r>>1;
        ll res=-INF;
        if(l<=mid)res=max(res,query_h(x<<1,l,r));
        if(r>mid)res=max(res,query_h(x<<1|1,l,r));
        return res;
    }
}t;

inline void ckmax(ll &x,ll y){x=(x>y)?x:y;}
inline void move(int x)
{
    while(pos+1<=m&&a[pos+1].t<=x)pos++,t.modify(1,a[pos].l,a[pos].r,a[pos].x);
    while(pos&&a[pos].t>x)t.modify(1,a[pos].l,a[pos].r,-a[pos].x),pos--;
}
void solve(int l,int r,int lb,int rb)
{
    if(l>r)return ;
    int mid=l+r>>1,x=lb,y=rb;
    for(int i=lb;i<=rb;i++)if(b[i].tr<mid)swap(b[i],b[x++]);
    for(int i=rb;i>=lb;i--)if(b[i].tl>mid)swap(b[i],b[y--]);
    solve(l,mid-1,lb,x-1),solve(mid+1,r,y+1,rb);
    if(x>y)return ;
    for(int i=x;i<=y;i++)
    {
        p[b[i].tl].push_back(i);
        if(b[i].tr>mid)p[b[i].tr].push_back(i);
    }
    move(mid),t.set(1,0);
    for(int i=mid;i>=l;move(--i))
        for(int j:p[i])
            ckmax(ans[b[j].id],t.query_h(1,b[j].l,b[j].r));
    move(mid+1),t.set(1,0);
    for(int i=mid+1;i<=r;move(++i))
        for(int j:p[i])
            ckmax(ans[b[j].id],t.query_h(1,b[j].l,b[j].r));
    for(int i=l;i<=r;i++)p[i].clear();
}
int main()
{
    read(n,m,q);
    for(int i=1;i<=m;i++)
    {
        int tl,tr,l,r,x;
        read(tl,l,tr,r,x);
        a[i]={tl,l,r,x},a[i+m]={tr+1,l,r,-x};
    }
    m<<=1;
    sort(a+1,a+m+1);
    for(int i=1;i<=q;i++)
    {
        int tl,tr,l,r;
        read(tl,l,tr,r);
        b[i]={i,tl,tr,l,r};
    }
    t.build(1,1,n);
    solve(1,n,1,q);
    for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
    return 0;
}