結果
| 問題 |
No.1234 典型RMQ
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2020-09-18 22:45:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 524 ms / 2,000 ms |
| コード長 | 15,499 bytes |
| コンパイル時間 | 2,350 ms |
| コンパイル使用メモリ | 117,120 KB |
| 実行使用メモリ | 39,936 KB |
| 最終ジャッジ日時 | 2024-11-09 02:01:18 |
| 合計ジャッジ時間 | 13,854 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 27 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using YukicoderContest266.Extensions;
using YukicoderContest266.Questions;
namespace YukicoderContest266.Questions
{
public class QuestionF : AtCoderQuestionBase
{
public override IEnumerable<object> Solve(TextReader inputStream)
{
_ = inputStream.ReadInt();
var a = inputStream.ReadLongArray();
var segTree = new LazySegmentTree<MinLong, Adder>(a.Select(ai => new MinLong(ai)).ToArray());
var queries = inputStream.ReadInt();
for (int q = 0; q < queries; q++)
{
var (k, l, r, c) = inputStream.ReadValue<int, int, int, int>();
l--;
if (k == 1)
{
segTree.Update(l, r, new Adder(c));
}
else
{
yield return segTree.Query(l, r).Value;
}
}
}
readonly struct MinLong : IMonoid<MinLong>
{
public long Value { get; }
public MinLong Identity => new MinLong(1L << 60);
public MinLong(long value)
{
Value = value;
}
public MinLong Multiply(MinLong other) => Value < other.Value ? this : other;
}
[StructLayout(LayoutKind.Auto)]
readonly struct Adder : IMonoidWithAct<MinLong, Adder>, IEquatable<Adder>
{
public long Value { get; }
public Adder Identity => new Adder();
public Adder(long value)
{
Value = value;
}
public override string ToString() => Value.ToString();
public MinLong Act(MinLong monoid) => new MinLong(monoid.Value + Value);
public Adder Multiply(Adder other) => new Adder(Value + other.Value);
public override bool Equals(object obj)
{
return obj is Adder adder && Equals(adder);
}
public bool Equals(Adder other)
{
return Value == other.Value;
}
public override int GetHashCode()
{
return HashCode.Combine(Value);
}
}
public interface ISemigroup<TSet> where TSet : ISemigroup<TSet>
{
public TSet Multiply(TSet other);
public static TSet operator *(ISemigroup<TSet> a, TSet b) => a.Multiply(b);
}
public interface IMonoid<TSet> : ISemigroup<TSet> where TSet : IMonoid<TSet>, new()
{
public TSet Identity { get; }
}
public interface IMonoidWithAct<TMonoid, TOperator> : IMonoid<TOperator>
where TMonoid : IMonoid<TMonoid>, new()
where TOperator : IMonoid<TOperator>, new()
{
public TMonoid Act(TMonoid monoid);
}
public class LazySegmentTree<TMonoid, TOperator>
where TMonoid : IMonoid<TMonoid>, new()
where TOperator : IMonoidWithAct<TMonoid, TOperator>, IEquatable<TOperator>, new()
{
private readonly TMonoid[] _data;
private readonly TOperator[] _lazy;
private readonly TMonoid _monoidIdenty;
private readonly TOperator _operatorIdentity;
private readonly int _leafOffset; // n - 1
private readonly int _leafLength; // n (= 2^k)
public int Length { get; }
public LazySegmentTree(ICollection<TMonoid> data)
{
Length = data.Count;
_leafLength = GetMinimumPow2(data.Count);
_leafOffset = _leafLength - 1;
_data = new TMonoid[_leafOffset + _leafLength];
_monoidIdenty = new TMonoid().Identity;
_operatorIdentity = new TOperator().Identity;
data.CopyTo(_data, _leafOffset);
BuildTree();
_lazy = Enumerable.Repeat(_operatorIdentity, _data.Length).ToArray();
}
private void LazyEvaluate(int index)
{
if (_lazy[index].Equals(_operatorIdentity))
{
return;
}
else if (index < _leafOffset) // 葉でない場合は子に伝播
{
var left = (index << 1) + 1;
var right = left + 1;
_lazy[left] = _lazy[index].Multiply(_lazy[left]);
_lazy[right] = _lazy[index].Multiply(_lazy[right]);
}
// 自身を更新
_data[index] = _lazy[index].Act(_data[index]);
_lazy[index] = _operatorIdentity;
}
public void Update(int begin, int end, TOperator op)
{
if (begin < 0)
{
throw new ArgumentOutOfRangeException(nameof(begin));
}
if (end > Length)
{
throw new ArgumentOutOfRangeException(nameof(end));
}
if (begin >= end)
{
throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
}
Update(begin, end, op, 0, 0, _leafLength);
}
private void Update(int begin, int end, TOperator op, int index, int left, int right)
{
LazyEvaluate(index);
if (begin <= left && right <= end) // 全部含まれる
{
_lazy[index] = _lazy[index].Multiply(op);
LazyEvaluate(index);
}
else if (begin < right && left < end) // 一部だけ含まれる
{
var l = (index << 1) + 1;
var r = l + 1;
Update(begin, end, op, l, left, (left + right) / 2);
Update(begin, end, op, r, (left + right) / 2, right);
_data[index] = _data[l].Multiply(_data[r]);
}
}
public TMonoid Query(int begin, int end)
{
if (begin < 0)
{
throw new ArgumentOutOfRangeException(nameof(begin));
}
if (end > Length)
{
throw new ArgumentOutOfRangeException(nameof(end));
}
if (begin >= end)
{
throw new ArgumentException($"{nameof(end)} must be grater than {nameof(begin)}");
}
return Query(begin, end, 0, 0, _leafLength);
}
private TMonoid Query(int begin, int end, int index, int left, int right)
{
LazyEvaluate(index);
if (right <= begin || end <= left) // 範囲外
{
return _monoidIdenty;
}
else if (begin <= left && right <= end) // 全部含まれる
{
return _data[index];
}
else // 一部だけ含まれる
{
var l = (index << 1) + 1;
var r = l + 1;
var leftValue = Query(begin, end, l, left, (left + right) / 2); // 左の子
var rightValue = Query(begin, end, r, (left + right) / 2, right); // 右の子
return leftValue.Multiply(rightValue);
}
}
private void BuildTree()
{
foreach (ref var unusedLeaf in _data.AsSpan()[(_leafOffset + Length)..])
{
unusedLeaf = _monoidIdenty; // 単位元埋め
}
for (int i = _leafLength - 2; i >= 0; i--) // 葉の親から順番に一つずつ上がっていく
{
var left = (i << 1) + 1;
var right = left + 1;
_data[i] = _data[left].Multiply(_data[right]); // f(left, right)
}
}
private int GetMinimumPow2(int n)
{
var p = 1;
while (p < n)
{
p <<= 1;
}
return p;
}
}
}
}
namespace YukicoderContest266
{
class Program
{
static void Main(string[] args)
{
IAtCoderQuestion question = new QuestionF();
var answers = question.Solve(Console.In);
var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(writer);
foreach (var answer in answers)
{
Console.WriteLine(answer);
}
Console.Out.Flush();
}
}
}
#region Base Class
namespace YukicoderContest266.Questions
{
public interface IAtCoderQuestion
{
IEnumerable<object> Solve(string input);
IEnumerable<object> Solve(TextReader inputStream);
}
public abstract class AtCoderQuestionBase : IAtCoderQuestion
{
public IEnumerable<object> Solve(string input)
{
var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
var reader = new StreamReader(stream, Encoding.Unicode);
return Solve(reader);
}
public abstract IEnumerable<object> Solve(TextReader inputStream);
}
}
#endregion
#region Extensions
namespace YukicoderContest266.Extensions
{
public static class StringExtensions
{
public static string Join<T>(this IEnumerable<T> source) => string.Concat(source);
public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source);
public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
}
public static class TextReaderExtensions
{
public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
public static string ReadString(this TextReader reader) => reader.ReadLine();
public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
// Supports primitive type only.
public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));
public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
return (v1, v2);
}
public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
return (v1, v2, v3);
}
public static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
return (v1, v2, v3, v4);
}
public static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
return (v1, v2, v3, v4, v5);
}
public static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
return (v1, v2, v3, v4, v5, v6);
}
public static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
return (v1, v2, v3, v4, v5, v6, v7);
}
public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));
return (v1, v2, v3, v4, v5, v6, v7, v8);
}
}
}
#endregion