JZOJ 3992 Chrismas

发表于 | 分类于 | 10

乐色数据，暴力开 O3 可过可太草了……

Segment Tree Beats 裸题（

代码： 

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
#include <cstdio>
#include <algorithm>
#define ls (p << 1)
#define rs (ls | 1)
using namespace std;
const int N = 1e5;
int n,m,a[N + 5];
struct node
{
    int min,sec;
    long long sum,cnt;
    int tag,add,tag_cnt,add_cnt;
    int chg_cnt;
} seg[(N << 2) + 5];
inline void push_add(int p,int tl,int tr,int k,int cnt)
{
    seg[p].sum += (tr - tl + 1LL) * k,seg[p].add += k,seg[p].min += k,seg[p].add_cnt += cnt,seg[p].chg_cnt += (tr - tl + 1LL) * cnt;
    if(seg[p].sec < 0x3f3f3f3f)
        seg[p].sec += k;
    if(seg[p].tag > -0x3f3f3f3f)
        seg[p].tag += k;
}
inline void push_max(int p,int k,int cnt)
{
    if(k > seg[p].min)
        seg[p].sum += (long long)(k - seg[p].min) * seg[p].cnt,seg[p].tag_cnt += cnt,seg[p].chg_cnt += (long long)seg[p].cnt * cnt,seg[p].min = seg[p].tag = k;
}
inline void push(int p,int tl,int tr)
{
    int mid = tl + tr >> 1;
    if(seg[p].add_cnt)
        push_add(ls,tl,mid,seg[p].add,seg[p].add_cnt),push_add(rs,mid + 1,tr,seg[p].add,seg[p].add_cnt),
        seg[p].add = seg[p].add_cnt = 0;
    if(seg[p].tag_cnt)
        push_max(ls,seg[p].tag,seg[p].tag_cnt),push_max(rs,seg[p].tag,seg[p].tag_cnt),
        seg[p].tag = -0x3f3f3f3f,seg[p].tag_cnt = 0;
}
void build(int p,int tl,int tr)
{
    seg[p].tag = -0x3f3f3f3f;
    if(tl == tr)
    {
        seg[p].sum = seg[p].min = a[tl],seg[p].sec = 0x3f3f3f3f,seg[p].cnt = 1;
        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].chg_cnt = seg[ls].chg_cnt + seg[rs].chg_cnt,
    seg[p].min = min(seg[ls].min,seg[rs].min);
    if(seg[ls].min == seg[rs].min)
        seg[p].cnt = seg[ls].cnt + seg[rs].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].sec);
    else if(seg[ls].min < seg[rs].min)
        seg[p].cnt = seg[ls].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].min);
    else
        seg[p].cnt = seg[rs].cnt,
        seg[p].sec = min(seg[ls].min,seg[rs].sec);
}
void update(int l,int r,int k,int p,int tl,int tr)
{
    if(l <= tl && tr <= r)
    {
        push_add(p,tl,tr,k,(bool)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].chg_cnt = seg[ls].chg_cnt + seg[rs].chg_cnt,
    seg[p].min = min(seg[ls].min,seg[rs].min);
    if(seg[ls].min == seg[rs].min)
        seg[p].cnt = seg[ls].cnt + seg[rs].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].sec);
    else if(seg[ls].min < seg[rs].min)
        seg[p].cnt = seg[ls].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].min);
    else
        seg[p].cnt = seg[rs].cnt,
        seg[p].sec = min(seg[ls].min,seg[rs].sec);
}
void chmax(int l,int r,int k,int p,int tl,int tr)
{
    if(seg[p].min >= k)
        return ;
    if(l <= tl && tr <= r && seg[p].sec > k)
    {
        push_max(p,k,1);
        return ;
    }
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    l <= mid && (chmax(l,r,k,ls,tl,mid),1);
    r > mid && (chmax(l,r,k,rs,mid + 1,tr),1);
    seg[p].sum = seg[ls].sum + seg[rs].sum,
    seg[p].chg_cnt = seg[ls].chg_cnt + seg[rs].chg_cnt,
    seg[p].min = min(seg[ls].min,seg[rs].min);
    if(seg[ls].min == seg[rs].min)
        seg[p].cnt = seg[ls].cnt + seg[rs].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].sec);
    else if(seg[ls].min < seg[rs].min)
        seg[p].cnt = seg[ls].cnt,
        seg[p].sec = min(seg[ls].sec,seg[rs].min);
    else
        seg[p].cnt = seg[rs].cnt,
        seg[p].sec = min(seg[ls].min,seg[rs].sec);
}
int query(int x,int p,int tl,int tr)
{
    if(tl == tr)
        return seg[p].sum;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    return x <= mid ? query(x,ls,tl,mid) : query(x,rs,mid + 1,tr);
}
int query_cnt(int x,int p,int tl,int tr)
{
    if(tl == tr)
        return seg[p].chg_cnt;
    push(p,tl,tr);
    int mid = tl + tr >> 1;
    return x <= mid ? query_cnt(x,ls,tl,mid) : query_cnt(x,rs,mid + 1,tr);
}
int main()
{
    scanf("%d",&n);
    for(register int i = 1;i <= n;++i)
        scanf("%d",a + i);
    build(1,1,n),scanf("%d",&m);
    char op;
    int l,r,k;
    for(;m;--m)
    {
        scanf(" %c%d",&op,&l);
        if(op == 'A')
            scanf("%d%d",&r,&k),update(l,r,k,1,1,n);
        else if(op == 'M')
            scanf("%d%d",&r,&k),chmax(l,r,k,1,1,n);
        else
            printf("%d %d\n",query(l,1,1,n),query_cnt(l,1,1,n));
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment