tjkendev/LYDSY-4695-0-task.md

## LYDSY-4695-0-task.md

      
    Raw
  

              LYDSY-4695-0-task.md
            
          
    LYDSY Education Online Judge - 4695: 最假女选手

問題ページ:

https://www.lydsy.com/JudgeOnline/problem.php?id=4695
問題概要:

1からNの番号がついている、N個の要素列が与えられる。以下の操作を合計M回処理せよ。

操作1: 区間[L, R]について、xを加える
操作2: 区間[L, R]について、xより小さい値をxに更新
操作3: 区間[L, R]について、xより大きい値をxに更新
操作4: 区間[L, R]の総和を出力
操作5: 区間[L, R]の最大値を出力
操作6: 区間[L, R]の最小値を出力

入力形式:


1行目には N が与えられる
2行目には N 個の要素列の初期値 A_1, A_2, ..., A_N が与えられる
3行目には 操作の合計回数 M が与えられる
以下M行には、操作クエリの引数(3つもしくは4つ)が与えられる

(3+i)行目には、i番目の操作が与えられる
Tpが操作タイプ, LとRを問題文中の区間, xを問題文中のxとする
Tp = 1,2,3のときは4つの引数("Tp L R X")が与えられる
Tp = 4,5,6のときは3つの引数("Tp L R")が与えられる


出力形式:


各操作4,5,6ごとに、1行に1つの整数を出力せよ

制約:


1 ≤ Tp ≤ 6
N, M ≤ 5*10^5
|A_i| ≤ 10^8
操作1について、|x| ≤ 1000
操作2と3について、 |x| ≤ 10^8

入力例1:

2
1 2
2
2 1 2 2
4 1 2

出力例1:

4


## LYDSY-4695-1-source-code.cpp
// 提出コード(C++)
// Memory: 95560 kb, Time: 44004 ms
#include<algorithm>
#include<iostream>
#include<cassert>
#include<cstdio>
using namespace std;
typedef long long ll;

#define N (1 << 19)

// Segment Tree Beats
// - l<=i<r について、 A_i の値を min(A_i, x) に更新
// - l<=i<r について、 A_i の値を max(A_i, x) に更新
// - l<=i<r の中の A_i の最大値を求める
// - l<=i<r の中の A_i の最小値を求める
// - l<=i<r の A_i の和を求める
// - l<=i<r について、 A_i の値に x を加える
// - l<=i<r について、 A_i の値を x に更新

// 各ノードごとに構造体にまとめる形で実装 (このように実装しないとTLEした)
class SegmentTree {
  static const ll inf = 1e18;
  struct Node {
    Node *left, *right;
    ll max_v, smax_v, max_c;
    ll min_v, smin_v, min_c;
    ll sum;
    ll len, ladd, lval;

    Node() : left(0), right(0), ladd(0), lval(inf) {}

    void init(ll x) {
      max_v = min_v = sum = x;
      smax_v = -inf; smin_v = inf;
      max_c = min_c = 1;
    }

    void init_empty() {
      max_v = smax_v = -inf;
      min_v = smin_v = inf;
      max_c = min_c = 0;
    }

    void update_max(ll x) {
      sum += (x - max_v) * max_c;

      if(max_v == min_v) {
        max_v = min_v = x;
      } else if(max_v == smin_v) {
        max_v = smin_v = x;
      } else {
        max_v = x;
      }

      if(lval != inf && x < lval) {
        lval = x;
      }
    }

    void update_min(ll x) {
      sum += (x - min_v) * min_c;

      if(max_v == min_v) {
        max_v = min_v = x;
      } else if(max_v == smin_v) {
        min_v = smax_v = x;
      } else {
        min_v = x;
      }

      if(lval != inf && lval < x) {
        lval = x;
      }
    }

    void addall(ll x) {
      max_v += x;
      if(smax_v != -inf) smax_v += x;
      min_v += x;
      if(smin_v != inf) smin_v += x;

      sum += len * x;
      if(lval != inf) {
        lval += x;
      } else {
        ladd += x;
      }
    }

    void updateall(ll x) {
      max_v = min_v = x;
      smax_v = -inf; smin_v = inf;
      max_c = min_c = len;

      sum = len * x;
      lval = x; ladd = 0;
    }

    void push() {

      if(lval != inf) {
        left->updateall(lval);
        right->updateall(lval);
        lval = inf;
        return;
      }

      if(ladd != 0) {
        left->addall(ladd);
        right->addall(ladd);
        ladd = 0;
      }

      if(max_v < left->max_v) {
        left->update_max(max_v);
      }
      if(left->min_v < min_v) {
        left->update_min(min_v);
      }

      if(max_v < right->max_v) {
        right->update_max(max_v);
      }
      if(right->min_v < min_v) {
        right->update_min(min_v);
      }
    }

    void update() {
      sum = left->sum + right->sum;

      if(left->max_v < right->max_v) {
        max_v = right->max_v;
        max_c = right->max_c;
        smax_v = max(left->max_v, right->smax_v);
      } else if(left->max_v > right->max_v) {
        max_v = left->max_v;
        max_c = left->max_c;
        smax_v = max(left->smax_v, right->max_v);
      } else {
        max_v = left->max_v;
        max_c = left->max_c + right->max_c;
        smax_v = max(left->smax_v, right->smax_v);
      }

      if(left->min_v < right->min_v) {
        min_v = left->min_v;
        min_c = left->min_c;
        smin_v = min(left->smin_v, right->min_v);
      } else if(left->min_v > right->min_v) {
        min_v = right->min_v;
        min_c = right->min_c;
        smin_v = min(left->min_v, right->smin_v);
      } else {
        min_v = left->min_v;
        min_c = left->min_c + right->min_c;
        smin_v = min(left->smin_v, right->smin_v);
      }
    }
  };

  int n, n0;
  Node *root;

  void _update_min(ll x, int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a || nd->max_v <= x) {
      return;
    }
    if(a <= l && r <= b && nd->smax_v < x) {
      nd->update_max(x);
      return;
    }

    nd->push();
    _update_min(x, a, b, nd->left, l, (l+r)/2);
    _update_min(x, a, b, nd->right, (l+r)/2, r);
    nd->update();
  }

  void _update_max(ll x, int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a || x <= nd->min_v) {
      return;
    }
    if(a <= l && r <= b && x < nd->smin_v) {
      nd->update_min(x);
      return;
    }

    nd->push();
    _update_max(x, a, b, nd->left, l, (l+r)/2);
    _update_max(x, a, b, nd->right, (l+r)/2, r);
    nd->update();
  }

  void _add_val(ll x, int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      nd->addall(x);
      return;
    }

    nd->push();
    _add_val(x, a, b, nd->left, l, (l+r)/2);
    _add_val(x, a, b, nd->right, (l+r)/2, r);
    nd->update();
  }

  void _update_val(ll x, int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a) {
      return;
    }
    if(a <= l && r <= b) {
      nd->updateall(x);
      return;
    }

    nd->push();
    _update_val(x, a, b, nd->left, l, (l+r)/2);
    _update_val(x, a, b, nd->right, (l+r)/2, r);
    nd->update();
  }

  ll _query_max(int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a) {
      return -inf;
    }
    if(a <= l && r <= b) {
      return nd->max_v;
    }
    nd->push();
    ll lv = _query_max(a, b, nd->left, l, (l+r)/2);
    ll rv = _query_max(a, b, nd->right, (l+r)/2, r);
    return max(lv, rv);
  }

  ll _query_min(int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a) {
      return inf;
    }
    if(a <= l && r <= b) {
      return nd->min_v;
    }
    nd->push();
    ll lv = _query_min(a, b, nd->left, l, (l+r)/2);
    ll rv = _query_min(a, b, nd->right, (l+r)/2, r);
    return min(lv, rv);
  }

  ll _query_sum(int a, int b, Node *nd, int l, int r) {
    if(b <= l || r <= a) {
      return 0;
    }
    if(a <= l && r <= b) {
      return nd->sum;
    }
    nd->push();
    ll lv = _query_sum(a, b, nd->left, l, (l+r)/2);
    ll rv = _query_sum(a, b, nd->right, (l+r)/2, r);
    return lv + rv;
  }

public:
  SegmentTree(int n, ll *a) : n(n) {
    n0 = 1;
    while(n0 < n) n0 <<= 1;

    Node *nds = new Node[2*n0];
    root = nds;

    nds[0].len = n0;
    for(int i=0; i<n0-1; ++i) {
      nds[i].left = &nds[2*i+1];
      nds[i].right = &nds[2*i+2];
      nds[2*i+1].len = nds[2*i+2].len = (nds[i].len >> 1);
    }

    for(int i=0; i<n; ++i) nds[n0-1+i].init(a[i]);
    for(int i=n; i<n0; ++i) nds[n0-1+i].init_empty();
    for(int i=n0-2; i>=0; i--) nds[i].update();
  }

  void update_min(int a, int b, ll x) {
    _update_min(x, a, b, root, 0, n0);
  }

  void update_max(int a, int b, ll x) {
    _update_max(x, a, b, root, 0, n0);
  }

  void add_val(int a, int b, ll x) {
    _add_val(x, a, b, root, 0, n0);
  }

  void update_val(int a, int b, ll x) {
    _update_val(x, a, b, root, 0, n0);
  }

  ll query_max(int a, int b) {
    return _query_max(a, b, root, 0, n0);
  }

  ll query_min(int a, int b) {
    return _query_min(a, b, root, 0, n0);
  }

  ll query_sum(int a, int b) {
    return _query_sum(a, b, root, 0, n0);
  }
};

ll v[N];

int main() {
  int n, m;
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  for(int i=0; i<n; ++i) cin >> v[i];
  SegmentTree stb(n, v);

  cin >> m;
  while(m--) {
    int t; ll l, r, x;
    cin >> t >> l >> r;
    if(t < 4) cin >> x;
    switch(t) {
      case 1:
        stb.add_val(l-1, r, x);
        break;
      case 2:
        stb.update_max(l-1, r, x);
        break;
      case 3:
        stb.update_min(l-1, r, x);
        break;
      case 4:
        printf("%lld\n", stb.query_sum(l-1, r));
        break;
      case 5:
        printf("%lld\n", stb.query_max(l-1, r));
        break;
      case 6:
        printf("%lld\n", stb.query_min(l-1, r));
        break;
    }
  }
  return 0;
}
	// 提出コード(C++)
	// Memory: 95560 kb, Time: 44004 ms
	#include<algorithm>
	#include<iostream>
	#include<cassert>
	#include<cstdio>
	using namespace std;
	typedef long long ll;

	#define N (1 << 19)

	// Segment Tree Beats
	// - l<=i<r について、 A_i の値を min(A_i, x) に更新
	// - l<=i<r について、 A_i の値を max(A_i, x) に更新
	// - l<=i<r の中の A_i の最大値を求める
	// - l<=i<r の中の A_i の最小値を求める
	// - l<=i<r の A_i の和を求める
	// - l<=i<r について、 A_i の値に x を加える
	// - l<=i<r について、 A_i の値を x に更新

	// 各ノードごとに構造体にまとめる形で実装 (このように実装しないとTLEした)
	class SegmentTree {
	static const ll inf = 1e18;
	struct Node {
	Node left, right;
	ll max_v, smax_v, max_c;
	ll min_v, smin_v, min_c;
	ll sum;
	ll len, ladd, lval;

	Node() : left(0), right(0), ladd(0), lval(inf) {}

	void init(ll x) {
	max_v = min_v = sum = x;
	smax_v = -inf; smin_v = inf;
	max_c = min_c = 1;
	}

	void init_empty() {
	max_v = smax_v = -inf;
	min_v = smin_v = inf;
	max_c = min_c = 0;
	}

	void update_max(ll x) {
	sum += (x - max_v) * max_c;

	if(max_v == min_v) {
	max_v = min_v = x;
	} else if(max_v == smin_v) {
	max_v = smin_v = x;
	} else {
	max_v = x;
	}

	if(lval != inf && x < lval) {
	lval = x;
	}
	}

	void update_min(ll x) {
	sum += (x - min_v) * min_c;

	if(max_v == min_v) {
	max_v = min_v = x;
	} else if(max_v == smin_v) {
	min_v = smax_v = x;
	} else {
	min_v = x;
	}

	if(lval != inf && lval < x) {
	lval = x;
	}
	}

	void addall(ll x) {
	max_v += x;
	if(smax_v != -inf) smax_v += x;
	min_v += x;
	if(smin_v != inf) smin_v += x;

	sum += len * x;
	if(lval != inf) {
	lval += x;
	} else {
	ladd += x;
	}
	}

	void updateall(ll x) {
	max_v = min_v = x;
	smax_v = -inf; smin_v = inf;
	max_c = min_c = len;

	sum = len * x;
	lval = x; ladd = 0;
	}

	void push() {

	if(lval != inf) {
	left->updateall(lval);
	right->updateall(lval);
	lval = inf;
	return;
	}

	if(ladd != 0) {
	left->addall(ladd);
	right->addall(ladd);
	ladd = 0;
	}

	if(max_v < left->max_v) {
	left->update_max(max_v);
	}
	if(left->min_v < min_v) {
	left->update_min(min_v);
	}

	if(max_v < right->max_v) {
	right->update_max(max_v);
	}
	if(right->min_v < min_v) {
	right->update_min(min_v);
	}
	}

	void update() {
	sum = left->sum + right->sum;

	if(left->max_v < right->max_v) {
	max_v = right->max_v;
	max_c = right->max_c;
	smax_v = max(left->max_v, right->smax_v);
	} else if(left->max_v > right->max_v) {
	max_v = left->max_v;
	max_c = left->max_c;
	smax_v = max(left->smax_v, right->max_v);
	} else {
	max_v = left->max_v;
	max_c = left->max_c + right->max_c;
	smax_v = max(left->smax_v, right->smax_v);
	}

	if(left->min_v < right->min_v) {
	min_v = left->min_v;
	min_c = left->min_c;
	smin_v = min(left->smin_v, right->min_v);
	} else if(left->min_v > right->min_v) {
	min_v = right->min_v;
	min_c = right->min_c;
	smin_v = min(left->min_v, right->smin_v);
	} else {
	min_v = left->min_v;
	min_c = left->min_c + right->min_c;
	smin_v = min(left->smin_v, right->smin_v);
	}
	}
	};

	int n, n0;
	Node *root;

	void _update_min(ll x, int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a \|\| nd->max_v <= x) {
	return;
	}
	if(a <= l && r <= b && nd->smax_v < x) {
	nd->update_max(x);
	return;
	}

	nd->push();
	_update_min(x, a, b, nd->left, l, (l+r)/2);
	_update_min(x, a, b, nd->right, (l+r)/2, r);
	nd->update();
	}

	void _update_max(ll x, int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a \|\| x <= nd->min_v) {
	return;
	}
	if(a <= l && r <= b && x < nd->smin_v) {
	nd->update_min(x);
	return;
	}

	nd->push();
	_update_max(x, a, b, nd->left, l, (l+r)/2);
	_update_max(x, a, b, nd->right, (l+r)/2, r);
	nd->update();
	}

	void _add_val(ll x, int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a) {
	return;
	}
	if(a <= l && r <= b) {
	nd->addall(x);
	return;
	}

	nd->push();
	_add_val(x, a, b, nd->left, l, (l+r)/2);
	_add_val(x, a, b, nd->right, (l+r)/2, r);
	nd->update();
	}

	void _update_val(ll x, int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a) {
	return;
	}
	if(a <= l && r <= b) {
	nd->updateall(x);
	return;
	}

	nd->push();
	_update_val(x, a, b, nd->left, l, (l+r)/2);
	_update_val(x, a, b, nd->right, (l+r)/2, r);
	nd->update();
	}

	ll _query_max(int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a) {
	return -inf;
	}
	if(a <= l && r <= b) {
	return nd->max_v;
	}
	nd->push();
	ll lv = _query_max(a, b, nd->left, l, (l+r)/2);
	ll rv = _query_max(a, b, nd->right, (l+r)/2, r);
	return max(lv, rv);
	}

	ll _query_min(int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a) {
	return inf;
	}
	if(a <= l && r <= b) {
	return nd->min_v;
	}
	nd->push();
	ll lv = _query_min(a, b, nd->left, l, (l+r)/2);
	ll rv = _query_min(a, b, nd->right, (l+r)/2, r);
	return min(lv, rv);
	}

	ll _query_sum(int a, int b, Node *nd, int l, int r) {
	if(b <= l \|\| r <= a) {
	return 0;
	}
	if(a <= l && r <= b) {
	return nd->sum;
	}
	nd->push();
	ll lv = _query_sum(a, b, nd->left, l, (l+r)/2);
	ll rv = _query_sum(a, b, nd->right, (l+r)/2, r);
	return lv + rv;
	}

	public:
	SegmentTree(int n, ll *a) : n(n) {
	n0 = 1;
	while(n0 < n) n0 <<= 1;

	Node nds = new Node[2n0];
	root = nds;

	nds[0].len = n0;
	for(int i=0; i<n0-1; ++i) {
	nds[i].left = &nds[2*i+1];
	nds[i].right = &nds[2*i+2];
	nds[2i+1].len = nds[2i+2].len = (nds[i].len >> 1);
	}

	for(int i=0; i<n; ++i) nds[n0-1+i].init(a[i]);
	for(int i=n; i<n0; ++i) nds[n0-1+i].init_empty();
	for(int i=n0-2; i>=0; i--) nds[i].update();
	}

	void update_min(int a, int b, ll x) {
	_update_min(x, a, b, root, 0, n0);
	}

	void update_max(int a, int b, ll x) {
	_update_max(x, a, b, root, 0, n0);
	}

	void add_val(int a, int b, ll x) {
	_add_val(x, a, b, root, 0, n0);
	}

	void update_val(int a, int b, ll x) {
	_update_val(x, a, b, root, 0, n0);
	}

	ll query_max(int a, int b) {
	return _query_max(a, b, root, 0, n0);
	}

	ll query_min(int a, int b) {
	return _query_min(a, b, root, 0, n0);
	}

	ll query_sum(int a, int b) {
	return _query_sum(a, b, root, 0, n0);
	}
	};

	ll v[N];

	int main() {
	int n, m;
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i=0; i<n; ++i) cin >> v[i];
	SegmentTree stb(n, v);

	cin >> m;
	while(m--) {
	int t; ll l, r, x;
	cin >> t >> l >> r;
	if(t < 4) cin >> x;
	switch(t) {
	case 1:
	stb.add_val(l-1, r, x);
	break;
	case 2:
	stb.update_max(l-1, r, x);
	break;
	case 3:
	stb.update_min(l-1, r, x);
	break;
	case 4:
	printf("%lld\n", stb.query_sum(l-1, r));
	break;
	case 5:
	printf("%lld\n", stb.query_max(l-1, r));
	break;
	case 6:
	printf("%lld\n", stb.query_min(l-1, r));
	break;
	}
	}
	return 0;
	}