JZOJ 5020 牛奶装瓶

发表于 | 分类于 | 6

奇妙的均摊复杂度线段树题，打开了 Segment Tree Beats 的大门（

考虑在线段树上维护区间最大值 / 最小值，2 操作时，若最大值的改变量与最小值的改变量相等，那么显然这一段区间的改变量都相等，直接区间打标记（意味着最大值和最小值最多相差 1），否则递归。

复杂度证明：
对于 i,j，若 |ai−aj|≤1，称 i,j 在同一段。
那么一次 1 操作最多会在区间首尾各分裂出一段，而相邻两端一定会在 O(logC) 次 2 操作之内合并，故复杂度为 O(nlognlogC)（假装 n,q 同阶，C 为值域。

代码： 

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
#include <cmath>
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;

const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
#define gc() (BB == BE ? (BE = (BB = BUFF) + fread(BUFF,1,BUFF_SIZE,stdin),BB == BE ? EOF : *BB++) : *BB++)
template<class T>
inline void read(T &x)
{
    x = 0;
    char ch = 0,w = 0;
    for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
    for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
    w && (x = -x);
}

const int N = 1e5;
int n,q,a[N + 5];
struct node
{
    long long sum,tag;
    long long max,min;
} seg[(N << 2) + 10];
inline void push(int p,int tl,int tr)
{
    if(seg[p].tag)
    {
        int mid = tl + tr >> 1;
        long long &k = seg[p].tag;
        seg[ls].tag += k,seg[ls].sum += k * (mid - tl + 1),seg[ls].max += k,seg[ls].min += k;
        seg[rs].tag += k,seg[rs].sum += k * (tr - mid),seg[rs].max += k,seg[rs].min += k;
        k = 0;
    }
}
void build(int p,int tl,int tr)
{
    if(tl == tr)
    {
        seg[p].sum = seg[p].max = seg[p].min = a[tl];
        return ;
    }
    int mid = tl + tr >> 1;
    build(ls,tl,mid),build(rs,mid + 1,tr);
    seg[p].sum = seg[ls].sum + seg[rs].sum;
    seg[p].max = max(seg[ls].max,seg[rs].max);
    seg[p].min = min(seg[ls].min,seg[rs].min);
}
void update(int l,int r,long long k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        seg[p].tag += k,seg[p].sum += k * (tr - tl + 1),seg[p].max += k,seg[p].min += k;
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    l <= mid && (update(l,r,k,ls,tl,mid),1);
    r > mid && (update(l,r,k,rs,mid + 1,tr),1);
    seg[p].sum = seg[ls].sum + seg[rs].sum;
    seg[p].max = max(seg[ls].max,seg[rs].max);
    seg[p].min = min(seg[ls].min,seg[rs].min);
}
void divide(int l,int r,int d,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        if(seg[p].max - floor((double)seg[p].max / d) == seg[p].min - floor((double)seg[p].min / d))
        {
            long long k = floor((double)seg[p].max / d) - seg[p].max;
            seg[p].tag += k,seg[p].sum += k * (tr - tl + 1),seg[p].max += k,seg[p].min += k;
        }
        else
        {
            push(p,tl,tr);
            int mid = tl + tr >> 1;
            divide(l,r,d,ls,tl,mid),divide(l,r,d,rs,mid + 1,tr);
            seg[p].sum = seg[ls].sum + seg[rs].sum;
            seg[p].max = max(seg[ls].max,seg[rs].max);
            seg[p].min = min(seg[ls].min,seg[rs].min);
        }
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    l <= mid && (divide(l,r,d,ls,tl,mid),1);
    r > mid && (divide(l,r,d,rs,mid + 1,tr),1);
    seg[p].sum = seg[ls].sum + seg[rs].sum;
    seg[p].max = max(seg[ls].max,seg[rs].max);
    seg[p].min = min(seg[ls].min,seg[rs].min);
}
int query_min(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].min;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    int ret = 0x7fffffff;
    l <= mid && (ret = min(ret,query_min(l,r,ls,tl,mid)));
    r > mid && (ret = min(ret,query_min(l,r,rs,mid + 1,tr)));
    return ret;
}
long long query_sum(int l,int r,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
        return seg[p].sum;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    long long ret = 0;
    l <= mid && (ret += query_sum(l,r,ls,tl,mid));
    r > mid && (ret += query_sum(l,r,rs,mid + 1,tr));
    return ret;
}
int main()
{
    freopen("milk.in","r",stdin),freopen("milk.out","w",stdout);
    read(n),read(q);
    for(register int i = 1;i <= n;++i)
        read(a[i]);
    build(1,1,n);
    int i = 0;
    for(int op,l,r,k;q;--q)
    {
        read(op),read(l),read(r);
        if(op == 1)
            read(k),update(l,r,k,1,1,n);
        else if(op == 2)
            read(k),divide(l,r,k,1,1,n);
        else if(op == 3)
            printf("%d\n",query_min(l,r,1,1,n));
        else
            printf("%lld\n",query_sum(l,r,1,1,n));
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment