using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using YukicoderContest265.Extensions; using YukicoderContest265.Questions; using System.Numerics; namespace YukicoderContest265.Questions { public class QuestionD : AtCoderQuestionBase { public override IEnumerable Solve(TextReader inputStream) { var (n, queries) = inputStream.ReadValue(); var segTree = new LazySegmentTree(Enumerable.Repeat(new Arm(Complex.One), n).ToArray()); var angles = new double[n]; for (int q = 0; q < queries; q++) { var input = inputStream.ReadIntArray(); var kind = input[0]; var index = input[1]; // 双対セグ木を持っていない if (kind == 0) { index--; var currentAngle = angles[index]; var targetAngle = input[2] * Math.PI * 2 / 360; segTree.Update(index, n, new Operation(Complex.FromPolarCoordinates(1, targetAngle - currentAngle))); angles[index] = targetAngle; } else if (kind == 1) { index--; var currentLength = segTree.Query(index, index + 1).Value.Magnitude; var targetLength = input[2]; segTree.Update(index, index + 1, new Operation(new Complex(targetLength / currentLength, 0))); } else { var coordinate = segTree.Query(0, index).Value; yield return $"{coordinate.Real} {coordinate.Imaginary}"; } } } readonly struct Arm : IMonoid { public Complex Value { get; } public Arm Identity => new Arm(Complex.Zero); public Arm(Complex value) { Value = value; } public Arm Multiply(Arm other) => new Arm(Value + other.Value); public override string ToString() => Value.ToString(); } readonly struct Operation : IMonoidWithAct, IEquatable { public Complex Value { get; } public Operation Identity => new Operation(Complex.One); public Operation(Complex value) { Value = value; } public Arm Act(Arm monoid) => new Arm(Value * monoid.Value); public Operation Multiply(Operation other) => new Operation(Value * other.Value); public override bool Equals(object obj) { return obj is Operation rotator && Equals(rotator); } public bool Equals(Operation other) { return Value.Equals(other.Value); } public override int GetHashCode() { return HashCode.Combine(Value); } public static bool operator ==(Operation left, Operation right) { return left.Equals(right); } public static bool operator !=(Operation left, Operation right) { return !(left == right); } public override string ToString() => Value.ToString(); } public interface ISemigroup where TSet : ISemigroup { public TSet Multiply(TSet other); } public interface IMonoid : ISemigroup where TSet : IMonoid, new() { public TSet Identity { get; } } public interface IMonoidWithAct : IMonoid where TMonoid : IMonoid, new() where TOperator : IMonoid, new() { public TMonoid Act(TMonoid monoid); } public class LazySegmentTree where TMonoid : IMonoid, new() where TOperator : IMonoidWithAct, IEquatable, 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 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 YukicoderContest265 { class Program { static void Main(string[] args) { IAtCoderQuestion question = new QuestionD(); 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 YukicoderContest265.Questions { public interface IAtCoderQuestion { IEnumerable Solve(string input); IEnumerable Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable Solve(TextReader inputStream); } } #endregion #region Extensions namespace YukicoderContest265.Extensions { public static class StringExtensions { public static string Join(this IEnumerable source) => string.Concat(source); public static string Join(this IEnumerable source, char separator) => string.Join(separator, source); public static string Join(this IEnumerable 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(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue(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(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(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(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(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(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(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