—— Summon, Light!
0%

hdu 5828 Rikka with Sequence

发表于 更新于 Valine：

多校8的一道题。。。 【看标题识出题人 ←_←
非常蛋疼的一道题，官方题解根本不知道在说什么，标程写得跟坨屎一样= =
先贴一份比赛中菊苣AC的代码

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
148
149
150
151
152
153
154
155
156
157
158
/************************************************
 *Author        :mathon
 *Email         :luoxinchen96@gmail.com
*************************************************/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned long long ull;
#define xx first
#define yy second
#define pr(x) cout << #x << " " << x << " "
#define prln(x) cout << #x << " " << x << endl
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
template<class T> inline T lowbit(T x) { return x & (-x); }
const int MAXN = 1e5 + 5;
int A[MAXN];
struct SegT {
    ll sum[MAXN<<2];
    ll is_same[MAXN<<2], lazy[MAXN<<2];
    void init() {
        memset(sum, 0, sizeof(sum));
        memset(is_same, 0, sizeof(is_same));
        memset(lazy, 0, sizeof(lazy));
    }
   
    void push_up(int rt) {
        if(is_same[rt << 1] && is_same[rt << 1 | 1] &&
                is_same[rt << 1] == is_same[rt << 1 | 1]) {
            is_same[rt] = is_same[rt << 1];
        } else {
            is_same[rt] = 0;
        }
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    void push_down(int rt, int l, int r) {
        int m = (l + r) >> 1;
        if(is_same[rt]) {
            is_same[rt << 1] = is_same[rt];
            is_same[rt << 1 | 1] = is_same[rt];
            sum[rt << 1] = is_same[rt] * (m - l + 1);
            sum[rt << 1 | 1] = is_same[rt] * (r - m);
        } else {
            lazy[rt << 1] += lazy[rt];
            lazy[rt << 1 | 1] += lazy[rt];
            sum[rt << 1] += lazy[rt] * (m - l + 1);
            sum[rt << 1 | 1] += lazy[rt] * (r - m);
            lazy[rt] = 0;
            if(is_same[rt << 1]) {
                is_same[rt << 1] += lazy[rt << 1];
                lazy[rt << 1] = 0;
            }
            if(is_same[rt << 1 | 1]) {
                is_same[rt << 1 | 1] += lazy[rt << 1 | 1];
                lazy[rt << 1 | 1] = 0;
            }
        }
    }
    
    void build(int l, int r, int rt) {
        if(l == r) {
            sum[rt] = A[l];
            is_same[rt] = A[l];
            return;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        push_up(rt);
    }
    void update1(int L, int R, int x, int l, int r, int rt) {
        if(L <= l && r <= R) {
            sum[rt] += (ll)x * (r - l + 1);
            if(is_same[rt]) {
                is_same[rt] += x;
            } else {
                lazy[rt] += x;
            }
            return;
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        if(m >= L) update1(L, R, x, lson);
        if(m < R) update1(L, R, x, rson);
        push_up(rt);
    }
    void update2(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R && is_same[rt]) {
            is_same[rt] = sqrt(is_same[rt]);
            sum[rt] = is_same[rt] * (r - l + 1);
            return;
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        if(m >= L) update2(L, R, lson);
        if(m < R) update2(L, R, rson);
        push_up(rt);
    }
    ll query(int L, int R, int l, int r, int rt) {
        if(L <= l && r <= R) {
            return sum[rt];
        }
        int m = (l + r) >> 1;
        push_down(rt, l, r);
        ll res = 0;
        if(m >= L) res += query(L, R, lson);
        if(m <  R) res += query(L, R, rson);
        return res;
    }
}seg;
int main(void) {
#ifdef MATHON
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    int T; scanf("%d", &T);
    while(T--) {
        int n, m;
        scanf("%d%d", &n, &m);
        seg.init();
        for (int i = 1; i <= n; i++) {
            scanf("%d", &A[i]);
        }
        seg.build(1, n, 1);
        for (int i = 0; i < m; i++) {
            int op;
            scanf("%d", &op);
            if(op == 1) {
                int l, r, x;
                scanf("%d%d%d", &l, &r, &x);
                seg.update1(l, r, x, 1, n, 1);
            } else if(op == 2) {
                int l, r;
                scanf("%d%d", &l, &r);
                seg.update2(l, r, 1, n, 1);
            } else if(op == 3) {
                int l, r;
                scanf("%d%d", &l, &r);
                ll res = seg.query(l, r, 1, n, 1);
                printf("%lld\n", res);
            }
        }
    }
    return 0;
}

这个用到了记录相等的一段，这样就不用每次更新到叶子了。
赛后题库里的数据加强了，我用这种方法T了好几遍只好去找新的姿势了。。。

应该考虑一下记相等到底有什么作用。
实际上就是把区间开根号变成了类似于区间增减的东西，然后就可以 lazy-tag。
所以用一种奇怪的姿势（反正我是想不出来。。。）
对于一个区间，可以分为三种情况：

  • 区间内所有数相等
  • 区间内极差大于1
  • 区间内极差等于1

情况1开根号相当于区间增减。
情况2会转化成3或者1。
情况3，开根号后极差可能相等，转化为情况1。
如果仍然差一，此时显然区间所有数减去了相同的值。

又是改了一遍才过。。。OTZ

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 <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long llint;
const int N=1e5+5;
llint add[N<<2],sum[N<<2];
llint mav[N<<2],miv[N<<2];
void push_up(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    mav[rt]=max(mav[rt<<1],mav[rt<<1|1]);
    miv[rt]=min(miv[rt<<1],miv[rt<<1|1]);
}
void push_down(int rt,int l,int r)
{
    if (add[rt]) {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        mav[rt<<1]+=add[rt];
        mav[rt<<1|1]+=add[rt];
        miv[rt<<1]+=add[rt];
        miv[rt<<1|1]+=add[rt];
        int m=(l+r)>>1;
        sum[rt<<1]+=add[rt]*(m-l+1);
        sum[rt<<1|1]+=add[rt]*(r-m);
        add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    if (l==r) {
        scanf("%I64d",&sum[rt]);
        mav[rt]=miv[rt]=sum[rt];
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    push_up(rt);
}
void update(int L,int R,int d,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        add[rt]+=d;
        mav[rt]+=d;
        miv[rt]+=d;
        sum[rt]+=(llint)d*(r-l+1);
        return ;
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    if (L<=m) update(L,R,d,lson);
    if (m<R) update(L,R,d,rson);
    push_up(rt);
}
void update2(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        if (mav[rt]==miv[rt]) {
            llint tmp=sqrt(mav[rt]);
            add[rt]+=tmp-mav[rt];
            sum[rt]+=(llint)(tmp-mav[rt])*(r-l+1);
            mav[rt]=miv[rt]=tmp;
            return;
        } else if (mav[rt]==miv[rt]+1) {
            llint t1=sqrt(mav[rt]);
            llint t2=sqrt(miv[rt]);
            if (t1==t2+1) {
                add[rt]+=t1-mav[rt];
                sum[rt]+=(llint)(t1-mav[rt])*(r-l+1);
                mav[rt]=t1;
                miv[rt]=t2;
                return;
            }
        }
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    if (L<=m) update2(L,R,lson);
    if (m<R) update2(L,R,rson);
    push_up(rt);
}
llint query(int L,int R,int l,int r,int rt)
{
    if (L<=l&&r<=R) {
        return sum[rt];
    }
    push_down(rt,l,r);
    int m=(l+r)>>1;
    llint res=0;
    if (L<=m) res+=query(L,R,lson);
    if (m<R) res+=query(L,R,rson);
    return res;
}
void init()
{
    memset(add,0,sizeof(add));
}
int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        init();
        build(1,n,1);
        int k,l,r,x;
        while (m--) {
            scanf("%d%d%d",&k,&l,&r);
            if (k==1) {
                scanf("%d",&x);
                update(l,r,x,1,n,1);
            } else if (k==2) {
                update2(l,r,1,n,1);
            } else {
                printf("%I64d\n",query(l,r,1,n,1));
            }
        }
    }
    return 0;
}

啥？你说复杂度？
我怎么知道= =

咖啡，亦我所需也