Submission #67468

ソースコード

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

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

#include<bits/stdc++.h>
using namespace std;
// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1>
class BaseImplicitTreap {
    // T0上の演算、単位元
    virtual T0 f0(T0, T0) = 0;
    const T0 u0;
    // T1上の演算、単位元
    virtual T1 f1(T1, T1) = 0;
    const T1 u1;
    // T0に対するT1の作用
    virtual T0 g(T0, T1) = 0;
    // 多数のt1(T1)に対するf1の合成
    virtual T1 p(T1, int) = 0;
 
    class xorshift {
        uint64_t x;
 
    public:
        xorshift() {
            mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
            x = rnd();
            for (int i = 0; i < 100; i++) {
                random();
            }
        }
 
        uint64_t random() {
            x = x ^ (x << 7);
            return x = x ^ (x >> 9);
        }
    } rnd;
 
    struct Node {
        T0 value, acc;
        T1 lazy;
        int priority, cnt;
        bool rev;
        Node *l, *r;
 
        Node(T0 value_, int priority_, T0 u0_, T1 u1_)
            : value(value_), acc(u0_), lazy(u1_), priority(priority_), cnt(1), rev(false), l(nullptr), r(nullptr) {}
    } *root = nullptr;
 
    using Tree = Node *;
 
    int cnt(Tree t) { return t ? t->cnt : 0; }
 
    T0 acc(Tree t) { return t ? t->acc : u0; }
 
    void update_cnt(Tree t) {
        if (t) {
            t->cnt = 1 + cnt(t->l) + cnt(t->r);
        }
    }
 
    void update_acc(Tree t) {
        if (t) {
            t->acc = f0(acc(t->l), f0(t->value, acc(t->r)));
        }
    }
 
    void pushup(Tree t) { update_cnt(t), update_acc(t); }
 
    void pushdown(Tree t) {
        if (t && t->rev) {
            t->rev = false;
            swap(t->l, t->r);
            if (t->l) t->l->rev ^= 1;
            if (t->r) t->r->rev ^= 1;
        }
        if (t && t->lazy != u1) {
            if (t->l) {
                t->l->lazy = f1(t->l->lazy, t->lazy);
                t->l->acc = g(t->l->acc, p(t->lazy, cnt(t->l)));
            }
            if (t->r) {
                t->r->lazy = f1(t->r->lazy, t->lazy);
                t->r->acc = g(t->r->acc, p(t->lazy, cnt(t->r)));
            }
            t->value = g(t->value, p(t->lazy, 1));
            t->lazy = u1;
        }
        pushup(t);
    }
 
    void split(Tree t, int key, Tree &l, Tree &r) {
        if (!t) {
            l = r = nullptr;
            return;
        }
        pushdown(t);
        int implicit_key = cnt(t->l) + 1;
        if (key < implicit_key) {
            split(t->l, key, l, t->l), r = t;
        } else {
            split(t->r, key - implicit_key, t->r, r), l = t;
        }
        pushup(t);
    }
 
    void insert(Tree &t, int key, Tree item) {
        Tree t1, t2;
        split(t, key, t1, t2);
        merge(t1, t1, item);
        merge(t, t1, t2);
    }
 
    void merge(Tree &t, Tree l, Tree r) {
        pushdown(l);
        pushdown(r);
        if (!l || !r) {
            t = l ? l : r;
        } else if (l->priority > r->priority) {
            merge(l->r, l->r, r), t = l;
        } else {
            merge(r->l, l, r->l), t = r;
        }
        pushup(t);
    }
 
    void erase(Tree &t, int key) {
        Tree t1, t2, t3;
        split(t, key + 1, t1, t2);
        split(t1, key, t1, t3);
        merge(t, t1, t2);
    }
 
    void update(Tree t, int l, int r, T1 x) {
        if (l >= r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->lazy = f1(t2->lazy, x);
        t2->acc = g(t2->acc, p(x, cnt(t2)));
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }
 
    T0 query(Tree t, int l, int r) {
        if (l == r) return u0;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        T0 ret = t2->acc;
        merge(t2, t2, t3);
        merge(t, t1, t2);
        return ret;
    }
 
    // [l, r)の中で左から何番目か
    int find(Tree t, T0 x, int offset, bool left = true) {
        if (f0(t->acc, x) == x) {
            return -1;
        } else {
            if (left) {
                if (t->l && f0(t->l->acc, x) != x) {
                    return find(t->l, x, offset, left);
                } else {
                    return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->r, x, offset + cnt(t->l) + 1, left);
                }
            } else {
                if (t->r && f0(t->r->acc, x) != x) {
                    return find(t->r, x, offset + cnt(t->l) + 1, left);
                } else {
                    return (f0(t->value, x) != x) ? offset + cnt(t->l) : find(t->l, x, offset, left);
                }
            }
        }
    }
 
    void reverse(Tree t, int l, int r) {
        if (l > r) return;
        Tree t1, t2, t3;
        split(t, l, t1, t2);
        split(t2, r - l, t2, t3);
        t2->rev ^= 1;
        merge(t2, t2, t3);
        merge(t, t1, t2);
    }
 
    // [l, r)の先頭がmになるようにシフトさせる。std::rotateと同じ仕様
    void rotate(Tree t, int l, int m, int r) {
        reverse(t, l, r);
        reverse(t, l, l + r - m);
        reverse(t, l + r - m, r);
    }
 
    void dump(Tree t) {
        if (!t) return;
        pushdown(t);
        dump(t->l);
        cout << t->value << " ";
        dump(t->r);
    }
 
public:
    BaseImplicitTreap(T0 u0_, T1 u1_) : u0(u0_), u1(u1_) {}
 
    void set_by_vector(const vector<T0> &a) {
        for (int i = 0; i < a.size(); i++) {
            insert(i, a[i]);
        }
    }
 
    int size() { return cnt(root); }
 
    void insert(int pos, T0 x) { insert(root, pos, new Node(x, rnd.random(), u0, u1)); }
 
    void update(int l, int r, T1 x) { update(root, l, r, x); }
 
    T0 query(int l, int r) { return query(root, l, r); }
 
    // 二分探索。[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のもの。存在しない場合は-1
    // たとえばMinMonoidの場合、x未満の最左/最右の要素の位置を返す
    int binary_search(int l, int r, T0 x, bool left = true) {
        if (l >= r) return -1;
        Tree t1, t2, t3;
        split(root, l, t1, t2);
        split(t2, r - l, t2, t3);
        int ret = find(t2, x, l, left);
        merge(t2, t2, t3);
        merge(root, t1, t2);
        return ret;
    }
 
    void erase(int pos) { erase(root, pos); }
 
    void reverse(int l, int r) { reverse(root, l, r); }
 
    void rotate(int l, int m, int r) { rotate(root, l, m, r); }
 
    void dump() {
        dump(root);
        cout << endl;
    }
 
    T0 operator[](int pos) { return query(pos, pos + 1); }
};
 
//作用としてminを行う、
template <class T0, class T1>
struct MinUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinUpdateQuery() : MinUpdateQuery(numeric_limits<T0>::max(), numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};
 
template <class T0, class T1>
struct SumAddQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumAddQuery() : SumAddQuery(0, 0) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x * len; }
};
 
template <class T0, class T1>
struct MinAddQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinAddQuery() : MinAddQuery(numeric_limits<T0>::max(), 0) {}
    T0 f0(T0 x, T0 y) override { return min(x, y); }
    T1 f1(T1 x, T1 y) override { return x + y; }
    T0 g(T0 x, T1 y) override { return x + y; }
    T1 p(T1 x, int len) override { return x; }
};
 
template <class T0, class T1>
struct SumUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumUpdateQuery() : SumUpdateQuery(0, numeric_limits<T1>::min()) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::min() ? x : y; }
    T1 p(T1 x, int len) override { return x == numeric_limits<T1>::min() ? numeric_limits<T1>::min() : x * len; }
};
 
template <class T0>
struct SumAffineQuery : public BaseImplicitTreap<T0, pair<T0, T0>> {
    using T1 = pair<T0, T0>;  // first * x + second
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    SumAffineQuery() : SumAffineQuery(0, {1, 0}) {}
    T0 f0(T0 x, T0 y) override { return x + y; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override { return y.first * x + y.second; }
    T1 p(T1 x, int len) override { return {x.first, x.second * len}; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};
 
template <class T>
struct MinmaxAffineQuery : public BaseImplicitTreap<pair<T, T>, pair<T, T>> {
    using T0 = pair<T, T>;  // {min, max}
    using T1 = pair<T, T>;  // first * x + second
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MinmaxAffineQuery()
        : MinmaxAffineQuery({numeric_limits<T>::max(), -numeric_limits<T>::max()}, {1, 0}) {
    }  // TODO: _u1を使うとコンパイル通らない原因不明
    T0 f0(T0 x, T0 y) override { return {min(x.first, y.first), max(x.second, y.second)}; }
    T1 f1(T1 x, T1 y) override { return {x.first * y.first, x.second * y.first + y.second}; }
    T0 g(T0 x, T1 y) override {
        T0 ret = {x.first * y.first + y.second, x.second * y.first + y.second};
        if (y.first < 0) swap(ret.first, ret.second);
        return ret;
    }
    T1 p(T1 x, int len) override { return x; }
    // update(i, j, {a, b}); // [i, j)にax + bを作用
    // update(i, j, {0, a}); // update
    // update(i, j, {1, a}); // 加算
    // update(i, j, {a, 0}); // 倍
};
 
template <class T0, class T1>
struct MaxUpdateQuery : public BaseImplicitTreap<T0, T1> {
    using BaseImplicitTreap<T0, T1>::BaseImplicitTreap;
    MaxUpdateQuery() : MaxUpdateQuery(numeric_limits<T0>::min(), numeric_limits<T1>::max()) {}
    T0 f0(T0 x, T0 y) override { return max(x, y); }
    T1 f1(T1 x, T1 y) override { return y == numeric_limits<T1>::max() ? x : y; }
    T0 g(T0 x, T1 y) override { return y == numeric_limits<T1>::max() ? x : y; }
    T1 p(T1 x, int len) override { return x; }
};
 
/*リファレンス
int size()
現時点でのサイズを返します。O(1)
 
void insert(int pos, T0 x)
先頭からposの位置にxを挿入します。たとえばpos = 0なら先頭に挿入します。O(logn)
 
void update(int l, int r, T1 x)
[l, r)の半開区間にxを作用させます。O(logn)
 
T0 query(int l, int r)
[l, r)の半開区間について累積を求めます。O(logn)
 
int binary_search(int l, int r, T0 x, bool left = true)
[l, r)内のkでf0(tr[k], x) != xとなる最左/最右のものの位置を返し、存在しない場合は-1を返します。O(logn)
説明が非直感的かと思うので具体例で説明すると、累積用の演算がminの場合、[l, r)の範囲にあるx未満の最左/最右の要素の位置を返します。
 
void erase(int pos)
位置posの要素を削除します。O(logn)
 
void reverse(int l, int r)
区間[l, r)を反転します。O(logn)
 
void rotate(int l, int m, int r)
区間の[l, r)の先頭がmになるようにシフトさせます。std::rotateと同じ仕様です。O(logn)
 
T0 operator[](int k)
インデックスアクセスができます。O(logn)
 
void dump()
デバッグ用です。配列の中身をprintします。
*/
int main(){
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  MinUpdateQuery<int,int> maxtree;
  MaxUpdateQuery<int,int> mintree;
  SumUpdateQuery<int,int> sumtree;
  maxtree.set_by_vector(vector<int>(n+5,0));
  mintree.set_by_vector(vector<int>(n+5,0));
  sumtree.set_by_vector(vector<int>(n+5,0));
 
  for(int i=0;i<m;i++){
    string qer;
    int a,b;
    cin>>qer>>a>>b;
 
    if(qer=="update"){
      maxtree.update(a,a+1,b);
      mintree.update(a,a+1,b);
      sumtree.update(a,a+1,b);
    }
    else if(qer=="add"){
      maxtree.update(a,a+1,maxtree[a]+b);
      mintree.update(a,a+1,mintree[a]+b);
      sumtree.update(a,a+1,sumtree[a]+b);
    }
    else if(qer=="getMin"){
      cout<<maxtree.query(a,b)<<'\n';
    }
    else if(qer=="getMax"){
      cout<<mintree.query(a,b)<<'\n';
    }
    else if(qer=="getSum"){
      cout<<sumtree.query(a,b)<<'\n';
    }
  }
   
  return(0);
}

ステータス

項目	データ
問題	1072 - セグメントツリー技術基礎
ユーザー名	ei1918
投稿日時	2021-07-12 18:23:01
言語	C++17
状態	Accepted
得点	1
ソースコード長	13213 Byte
最大実行時間	383 ms
最大メモリ使用量	20336 KB

セット

	セット	得点	Cases
1	ALL	1 / 1	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
in01	AC	28 ms	604 KB	1
in02	AC	165 ms	1068 KB	1
in03	AC	263 ms	14372 KB	1
in04	AC	321 ms	14016 KB	1
in05	AC	155 ms	15340 KB	1
in06	AC	146 ms	8428 KB	1
in07	AC	178 ms	7304 KB	1
in08	AC	294 ms	5808 KB	1
in09	AC	316 ms	12688 KB	1
in10	AC	285 ms	7468 KB	1
in11	AC	78 ms	5948 KB	1
in12	AC	132 ms	2888 KB	1
in13	AC	341 ms	16696 KB	1
in14	AC	310 ms	6240 KB	1
in15	AC	248 ms	14512 KB	1
in16	AC	235 ms	5056 KB	1
in17	AC	298 ms	13804 KB	1
in18	AC	209 ms	17456 KB	1
in19	AC	281 ms	15016 KB	1
in20	AC	211 ms	14808 KB	1
in21	AC	208 ms	11812 KB	1
in22	AC	333 ms	12468 KB	1
in23	AC	278 ms	17516 KB	1
in24	AC	285 ms	13428 KB	1
in25	AC	221 ms	7844 KB	1
in26	AC	383 ms	19748 KB	1
in27	AC	363 ms	19092 KB	1
in28	AC	312 ms	11624 KB	1
in29	AC	165 ms	17400 KB	1
in30	AC	362 ms	20336 KB	1
in31	AC	182 ms	12816 KB	1
in32	AC	274 ms	12452 KB	1