[Luogu 2496] [SDOI 2012] 体育课

Posted on | In , | Views:

题目链接

Luogu 2496

题目大意

维护一个长度为$n$的数列，并进行$m$次操作，操作一共有三类。
(1) 询问区间最大值
(2) 交换数列的两个位置
(3) 区间加等差数列
$n,m\le 10^5$

做法

看到这种区间的题，第一反应会想到线段树，但是冷静一下发现线段树不太行，注意到数据范围是允许$\sqrt{n}$过的，我们考虑一下分块。
我们把每个点看成一个形如$kx+b$的形式，那么区间加等差数列的的话，可以看成是改变了一段区间的$x$
当$x$改变时，答案实际上是在这个区间的下凸壳上移动的。
对于点$i$，我们将他的高度看成一个一次函数$y=ix+b$。
将序列分块，对每个块维护这个块的下凸壳，以及这个区间的$x$和区间加常数标记$lazy$
查询的时候，对于整块，我们只要在单调栈上二分一下，再加上这个块的$lazy$就行了。
对于非整块，直接暴力计算即可。
区间加等差数列是，如果加在整块上，在这个区间的$x$上加一下，$lazy$标记里把多加的减掉就行了。
对于非整块，先暴力修改单点的$b$，再对于所有有部分被修改的块暴力重构。
暴力重构的复杂度为$O(\sqrt n)$，而每次修改最多只会重构两个块，所以总复杂度仍是$O(n\sqrt n)$
对于交换两个位置的操作，我们先把这两个数所在的块的标记暴力改到每个点上，交换这两个点的$b$之后，再暴力重构这两个块就行了，复杂度与上一步一样。

代码

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
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
#define M (355)
using namespace std;
int n,m,unit,tot,op,l,r,t; 
int st[M],en[M],be[N],top[M],now[M],sta[M][M];
LL lazy[N],x[N];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
struct line{
    int k;
    LL b;
}a[N];
inline bool work(line a,line b,line c){
    return 1ll*(a.b-b.b)*(c.k-b.k)>=1ll*(b.b-c.b)*(b.k-a.k);
}
inline void push(int u){
    for (int i=st[u];i<=en[u];i++) a[i].b+=1ll*a[i].k*x[u]+lazy[u];
    lazy[u]=0,x[u]=0;
}
inline void reset(int u){
    push(u);
    top[u]=0;
    sta[u][++top[u]]=st[u];
    if (st[u]<en[u]){sta[u][++top[u]]=st[u]+1;}
    for (int i=st[u]+2;i<=en[u];i++){
        while (top[u]>1&&work(a[sta[u][top[u]-1]],a[sta[u][top[u]]],a[i])) top[u]--;
        sta[u][++top[u]]=i;
    }
    now[u]=1;
}
LL get(int u){
    return 1ll*a[u].k*x[be[u]]+a[u].b+lazy[be[u]];
}
inline void change(int L,int R,int t){
    if (be[L]==be[R]){
        for (int i=L;i<=R;i++) a[i].b+=1ll*t*(i-L+1);
        reset(be[L]);
    }
    else{
        for (int i=be[L]+1;i<=be[R]-1;i++){
            x[i]+=t;
            lazy[i]+=1ll*(1-L)*t;
        } 
        for (int i=L;i<=en[be[L]];i++) a[i].b+=1ll*t*(i-L+1);
        reset(be[L]);
        for (int i=st[be[R]];i<=R;i++) a[i].b+=1ll*t*(i-L+1);
        reset(be[R]);
    }
}
inline LL query(int L,int R){
    LL maxx=0;
    if (be[L]==be[R]){
        for (int i=L;i<=R;i++) maxx=max(get(i),maxx);
    }
    else{
        for (int i=be[L]+1;i<=be[R]-1;i++){ 
            for (int j=1;j<=top[i];j++) maxx=max(maxx,get(sta[i][j]));
        }
        for (int i=L;i<=en[be[L]];i++) maxx=max(maxx,get(i));
        for (int i=st[be[R]];i<=R;i++) maxx=max(maxx,get(i));
    }
    maxx=max(0ll,maxx-get(1));
    return maxx;
}
int main(){
    read(n),read(m);
    unit=sqrt(n);
    for (int i=1;i<=n;i++){
        be[i]=(i-1)/unit+1;
        if (be[i]!=be[i-1]){
            en[be[i-1]]=i-1;
            st[be[i]]=i;
        }
    }
    tot=be[n];
    en[tot]=n;
    for (int i=1;i<=n;i++){
        read(a[i].b);
        a[i].k=i;
    }
    for (int i=1;i<=tot;i++) reset(i);
    while (m--){
        read(op);
        if (op==1){
            read(l),read(r);
            printf("%lld\n",query(l,r));
        }
        if (op==2){
            read(l),read(r);
            push(be[l]),push(be[r]);
            swap(a[l].b,a[r].b);
            reset(be[l]),reset(be[r]);
        }
        if (op==3){
            read(l),read(r),read(t);
            change(l,r,t);
        }
    }
    return 0;
}