rprmq1

为什么不先看看 rprmq2 呢？

因为有静态，所以时间复杂度会变得非常好看。

发现 ，所以可以猜想 上面比 上面少一个 。

首先假设所有询问的 ，可以套用 rprmq2 中对于块间贡献的处理方法。我们对修改的第一维差分，然后扫描第一维，在第二维上做历史最值，这个非常模板。

但是现在 ，不过没关系，我们考虑将区间拆成两个，右边的从左向右扫，左边的从右向左扫，这样就可以有效地统一区间的一个 side。拆区间使用线段树的方式即可，每个区间按照第一个跨过的中间点拆成两个。

然后考虑修改应该怎么做。

假定 build(l,r) 会把区间 的所有修改放入线段树中，那么我们先 build(l,mid)（此时实际上 的修改都被放入了），然后重置此时的历史最大值（置为当前值），然后使用左端点相同的做法扫 为左端点的询问。

然后我们还有右边区间要处理，所以我们得把刚刚扫出来的修改滚回到只有 的状态，然后 build(mid+1,r)。

每个修改被操作 次，故总的复杂度为 ，空间复杂度 。

实现

重置最大值的标记可以直接使用标记，然后二层下推（推下去之前无视下层的重置标记 pushdown 一次，然后再下推当前的重置标记）。

也可以 ，然后对结果 ，这个好写不少，而且也快。

第二遍倒过来做考虑将 补全成 的幂，然后把所有第一维坐标翻转即可。

回滚记录每个结点的访问情况，然后访问的时候复制即可。

我的差分的端点是左闭右闭的，所以对于同一坐标内是先做正的修改再做负的修改，如果左端点刚好是 那就不拆直接做。

这个写法挺暴力的，但是是最优解（不知道为什么明明每个点都更优了洛谷总用时算出来就是慢）。

愤怒了！写 zkw 线段树强行拿下了！

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
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
using ll=long long;
const int N=65538,Q=500010,FSIZE=1<<24;
const ll INF=100000ll<<31;
int n,m,qn;
ll ans[Q];
struct ques{int l,r,x,y,i;}q[Q];
struct oper{int l,r,x;};
vector<oper> v[N];
void cmax(ll &x,ll y){if(x<y) x=y;}
struct ST{
    int bit=16;
    bool vis[N+N];
    struct node{
        ll mx,_mx,add,_add;
        void operator+=(ll x){cmax(_add,add+=x);cmax(_mx,mx+=x);}
        void operator|=(ll x){add+=x;mx+=x;}
        void operator&=(ll x){cmax(_add,add+x);cmax(_mx,mx+x);}
    }a[N+N],old[N+N];
    template<bool z=1>void pushdown(int x){
        node &p=a[x],&l=a[x<<1],&r=a[x<<1|1];
        if(z&&!vis[x]){
            old[x<<1]=l;
            old[x<<1|1]=r;
            vis[x]=1;
        }
        if(ll &_=p._add){l&=_;r&=_;_=0;}
        if(ll &_=p.add){l|=_;r|=_;_=0;}
    }
    void pushup(int x){
        a[x].mx=max(a[x<<1].mx,a[x<<1|1].mx);
        a[x]._mx=max(a[x<<1]._mx,a[x<<1|1]._mx);
    }
    void push(int x,int y){
        for(int i=16;i;--i) pushdown(x>>i);
        for(int j=__lg(x^y);j;--j) pushdown(y>>j);
    }
    template<bool _=1>void modify(int x,int y,int z){
        for(push(x+=n-2,y+=n);x^y^1;pushup(x>>=1),pushup(y>>=1)){
            if(~x&1) a[x^1]+=z;
            if(y&1) a[y^1]+=z;
        }
        for(;(x>>=1);pushup(x));
    }
    ll query(int x,int y){
        ll re=0;
        for(push(x+=n-2,y+=n);x^y^1;x>>=1,y>>=1){
            if(~x&1) cmax(re,a[x^1]._mx);
            if(y&1) cmax(re,a[y^1]._mx);
        }
        return(re);
    }
    void reset(){
        roll<0>();
        a[1]+=INF;
        old[1]=a[1];
    }
    template<bool z=1>void roll(int m=1){
        if(z) a[m]=old[m];
        if(!vis[m]) return;
        vis[m]=0;
        roll<z>(m<<1);roll<z>(m<<1|1);
    }
}t;
char BuF[FSIZE],*InF=BuF,WuF[FSIZE],*OnF=WuF,ST[30],*STC=ST;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
template<class T,class ...T1>void read(T &x,T1 &...x1){read(x);read(x1...);}
void write(ll x){
    for(!x&&(*OnF++=48);x;x/=10) *++STC=x%10^48;
    for(;STC!=ST;*OnF++=*STC--);
    *OnF++='\n';
}
void build(int l,int r,int L,int R){
    if(L>R){
        for(int i=l;i<=r;++i)
            for(auto k:v[i]) t.modify<0>(k.l,k.r,k.x);
        return;
    }
    int mid=(l+r)>>1,cl=L,cr=R;
    for(int i=cl;i<=R;++i) if(q[i].r<mid) swap(q[i],q[cl++]);
    for(int i=R;i>=cl;--i) if(q[i].l-1>mid) swap(q[i],q[cr--]);
    build(l,mid,L,cl-1);
    t.reset();
    sort(q+cl,q+cr+1,[](ques a,ques b){return(a.r<b.r);});
    for(int i=mid+1,j=cl;j<=cr;++i){
        for(;j<=cr&&q[j].r<i;++j) cmax(ans[q[j].i],t.query(q[j].x,q[j].y)%INF);
        if(j<=cr) for(auto k:v[i]) t.modify(k.l,k.r,k.x);
    }
    t.roll();
    build(mid+1,r,cr+1,R);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n,m,qn);n=1<<(__lg(n)+1);
    for(int i=1,l1,l2,r1,r2,x;i<=m;++i){
        read(l1,l2,r1,r2,x);
        v[l1].push_back({l2,r2,x});
        v[r1].push_back({l2,r2,-x});
    }
    for(int i=1;i<=qn;++i){
        read(q[i].l,q[i].x,q[i].r,q[i].y);q[i].i=i;
    }
    for(int i=1;i<=n;++i)
        sort(v[i].begin(),v[i].end(),[](oper a,oper b){return(a.x>b.x);});
    build(1,n,1,qn);
    memset(t.a,0,sizeof(ST::node)*(n+n));
    for(int i=1;i<n-i+1;++i) swap(v[i],v[n-i+1]);
    for(int i=1;i<=n;++i){
        for(auto &j:v[i]) j.x=-j.x;
        reverse(v[i].begin(),v[i].end());
    }
    for(int i=1;i<=qn;++i)
        swap(q[i].l=n+1-q[i].l,q[i].r=n+1-q[i].r);
    build(1,n,1,qn);
    for(int i=1;i<=qn;++i) write(ans[i]);
    fwrite(WuF,1,OnF-WuF,stdout);
    return(0);
}
≡