ProdSet<T> (Library Checker: Point Set Range Composite (Large Array)) (CpLibrary.Verify/Collections/ProdSet.cs)

• View this file on GitHub
• Last update: 2025-08-03 01:11:51+09:00
• Problem: https://judge.yosupo.jp/problem/point_set_range_composite_large_array

Depends on

• CpLibrary/Collections/ProdSet.cs
• CpLibrary/IO/Scanner.cs

Code

using CpLibrary.Collections;
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using ModInt = AtCoder.StaticModInt<AtCoder.Mod998244353>;

namespace CpLibrary.Verify.Collections
{
	// competitive-verifier: document_title ProdSet<T> (Library Checker: Point Set Range Composite (Large Array))
	internal class ProdSetTest : CompetitiveVerifier.ProblemSolver
	{
		public override string Url => "https://judge.yosupo.jp/problem/point_set_range_composite_large_array";
		public override void Solve()
		{
			var sr = new Scanner(new StreamReader(Console.OpenStandardInput()));

			var (n, q) = sr.ReadValue<long, int>();

			var ps = new ProdSet<(long index, (ModInt a, ModInt b) f), IOp>(new TupleComparer<long, (ModInt a, ModInt b)>());
			ps.Add((0, (1, 0)));

			for (int i = 0; i < q; i++)
			{
				var query = sr.ReadInt();
				if (query == 0)
				{
					var (p, c, d) = sr.ReadValue<long, int, int>();
					var idx = ps.LowerBound((p, (0, 0)));
					if (idx >= ps.Count || ps[idx].index != p)
					{
						ps.Add((p, (c, d)));
					}
					else
					{
						ps.RemoveAt(idx);
						ps.Add((p, (c, d)));
					}
				}
				else
				{
					var (l, r, x) = sr.ReadValue<int, int, long>();
					var l2 = ps.LowerBound((l, (0, 0)));
					var r2 = ps.LowerBound((r, (0, 0)));
					var prod = ps.Prod(l2, r2);
					var ans = prod.f.a * x + prod.f.b;
					Console.WriteLine(ans);
				}
			}
		}

		public readonly struct IOp : IProdSetOperator<(long index, (ModInt a, ModInt b) f)>
		{
			public (long index, (ModInt a, ModInt b) f) Identity => (-1, (1, 0));
			public (long index, (ModInt a, ModInt b) f) Operate((long index, (ModInt a, ModInt b) f) f, (long index, (ModInt a, ModInt b) f) g)
			{
				return (f.index, (g.f.a * f.f.a, g.f.a * f.f.b + g.f.b));
			}
		}

		public class TupleComparer<T1, T2> : IComparer<(T1, T2)>
			where T1 : IComparable<T1>
		{
			public int Compare((T1, T2) x, (T1, T2) y)
			{
				return x.Item1.CompareTo(y.Item1);
			}
		}
	}
}

Test cases

Env	Name	Status	Elapsed	Memory
	dense_00	AC	678 ms	47 MB
	dense_01	AC	1368 ms	48 MB
	dense_02	AC	1957 ms	64 MB
	example_00	AC	73 ms	29 MB
	many_query_0_00	AC	1497 ms	83 MB
	many_query_0_01	AC	1484 ms	82 MB
	many_query_1_00	AC	1706 ms	48 MB
	many_query_1_01	AC	1600 ms	48 MB
	max_random_00	AC	1993 ms	66 MB
	max_random_01	AC	2009 ms	65 MB
	max_random_02	AC	2012 ms	66 MB
	near_0_and_N_00	AC	1828 ms	55 MB
	near_0_and_N_01	AC	1826 ms	56 MB
	query_0_then_1_00	AC	2051 ms	72 MB
	query_0_then_1_01	AC	2055 ms	72 MB
	random_00	AC	1596 ms	68 MB
	random_01	AC	1627 ms	63 MB
	random_02	AC	1497 ms	63 MB
	random_03	AC	227 ms	41 MB
	random_04	AC	505 ms	50 MB
	small_N_00	AC	613 ms	47 MB
	small_N_01	AC	678 ms	48 MB
	small_N_02	AC	702 ms	47 MB
	small_N_03	AC	712 ms	47 MB
	small_N_04	AC	779 ms	47 MB

Back to top page