백준18702 Array Queries

작성일 | In

문제 링크

  • http://icpc.me/18702

문제 출처

  • 2017 Arab Collegiate Programming Contest J번

사용 알고리즘

  • 세그먼트 트리 비츠

시간복잡도

  • $O((N+Q) \log N)$

풀이

수열과 쿼리 28(풀이)과 동일한 문제입니다.

수쿼28 코드를 복붙하면 가볍게 TLE가 뜨게 되는데, 최적화할 생각하지 않고 fastio를 사용하면 AC를 받을 수 있습니다.
5시간동안 여러가지 방법을 시도해봤지만 모두 실패했고, fastio를 사용하는 것이 가장 좋은 것 같습니다. fastio 버퍼 사이즈에 주의하세요.

전체 코드

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
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx,avx2,sse")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
	static char buf[buf_size];
	static int len = 0, pos = 0;
	if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
	if(pos == len) return -1;
	return buf[pos++];
}
inline int readChar(){
	int c = getChar();
	while(c <= 32) c = getChar();
	return c;
}
template <class T>
inline T readInt(){
	int s = 1, c = readChar();
	T x = 0;
	if(c == '-') s = -1, c = getChar();
	while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
	return s == 1 ? x : -x;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
	if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
	write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
	if(x < 0) writeChar('-'), x = -x;
	char s[24]; int n = 0;
	while(x || !n) s[n++] = '0' + x % 10, x /= 10;
	while(n--) writeChar(s[n]);
	if(end) writeChar(end);
}
inline void writeWord(const char *s){
	while(*s) writeChar(*s++);
}
struct Flusher{
	~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;

struct Node{
    ll mn, mx, sum, tmp;
    Node(){ mn = mx = sum = tmp = 0; }
    Node(ll v){ mn = mx = sum = v; tmp = 0; }
    void push(Node &node, ll v){
        if(mn == mx){
            node.mn = node.mx = mn; node.tmp = 0; node.sum = mn * v;
        }else{
            node.mn += tmp; node.mx += tmp; node.tmp += tmp; node.sum += tmp * v;
        }
    }
};

int n, m, q; int a[101010];

const int sz = 1 << 17;
struct Seg{
    Node tree[1 << 18];
    void merge(int a, int b, int r){
        tree[r].mn = min(tree[a].mn, tree[b].mn);
        tree[r].mx = max(tree[a].mx, tree[b].mx);
        tree[r].sum = tree[a].sum + tree[b].sum;
        tree[r].tmp = 0;
    }
    void push(int node, ll v){
        tree[node].push(tree[node << 1], v + 1 >> 1);
        tree[node].push(tree[node << 1 | 1], v >> 1);
    }
    void init(int node, int s, int e){
        if(s == e){ tree[node] = Node(a[s]); return; }
        int m = s + e >> 1;
        init(node << 1, s, m); init(node << 1 | 1, m+1, e);
        merge(node << 1, node << 1 | 1, node);
    }
    void update(int node, int s, int e, int l, int r, ll v){
        if(r < s || e < l) return;
        if(l <= s && e <= r){
            if(!v && tree[node].mx == 0) return;
            ll a = sqrt(tree[node].mn), b = sqrt(tree[node].mx);
            if(!v && a == b){
                tree[node].mn = tree[node].mx = a; tree[node].tmp = 0;
                tree[node].sum = a * (e-s+1);
                return;
            }
            else if(!v && tree[node].mx - tree[node].mn == 1){
                v = a - tree[node].mn;
            }
            if(v){
                tree[node].mn += v; tree[node].mx += v;
                tree[node].tmp += v;
                tree[node].sum += v * (e-s+1);
                return;
            }
        }
        int m = s + e >> 1;
        push(node, e-s+1);
        if(s <= r) update(node << 1, s, m, l, r, v);
        if(l <= e) update(node << 1 | 1, m+1, e, l, r, v);
        merge(node << 1, node << 1 | 1, node);
    }
    ll query(int node, int s, int e, int l, int r){
        if(r < s || e < l) return 0;
        int m = s + e >> 1;
        push(node, e-s+1);
        ll ret = 0;
        if(l <= s && m <= r) ret += tree[node << 1].sum;
        else if(s <= r) ret += query(node << 1, s, m, l, r);
        if(l <= m+1 && e <= r) ret += tree[node << 1 | 1].sum;
        else if(l <= e) ret += query(node << 1 | 1, m+1, e, l, r);
        merge(node << 1, node << 1 | 1, node);
        return ret;
    }
} seg;

void solve(){
    n = readInt(); q = readInt();
    for(register int i=1; i<=n; i++) a[i] = readInt();
    seg.init(1, 1, n);
    while(q--){
        int op = readInt();
        int a = readInt();
        int b = readInt();
        int c;
        if(op == 1) seg.update(1, 1, n, a, b, 0);
        else if(op == 3) c = readInt(), seg.update(1, 1, n, a, b, c);
        else writeInt(seg.query(1, 1, n, a, b), '\n');
    }
    m = n;
}

int main(){
	int t = readInt(), pv = 0;
    for(int i=1; i<=t; i++){
        solve();
    }
    Flusher();
}