結果
| 問題 |
No.259 セグメントフィッシング＋
|
| コンテスト | |
| ユーザー |
 eitaho
|
| 提出日時 | 2016-07-26 15:44:40 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,140 ms / 2,000 ms |
| コード長 | 12,077 bytes |
| コンパイル時間 | 1,153 ms |
| コンパイル使用メモリ | 120,060 KB |
| 実行使用メモリ | 75,092 KB |
| 最終ジャッジ日時 | 2024-11-06 17:00:07 |
| 合計ジャッジ時間 | 20,258 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 23 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using Enu = System.Linq.Enumerable;
public class Program
{
public void Solve()
{
int N = Reader.Int(), Q = Reader.Int();
int last = 0;
var L = new Treap();
var R = new Treap();
L.Build(new long[N]);
R.Build(new long[N]);
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
foreach (var q in Reader.StringTable(Q))
{
int t = int.Parse(q[1]), x = int.Parse(q[2]), y = int.Parse(q[3]);
int diff = t - last;
last = t;
Treap.Node La, Lb, Ra, Rb;
int mid = diff % N;
Treap.Split(L.Root, mid, out La, out Lb);
Treap.Split(R.Root, N - mid, out Ra, out Rb);
if (diff / N % 2 == 0)
{
L.Root = Treap.Merge(Lb, Treap.Reverse(Rb));
R.Root = Treap.Merge(Treap.Reverse(La), Ra);
}
else
{
L.Root = Treap.Merge(Treap.Reverse(Ra), La);
R.Root = Treap.Merge(Rb, Treap.Reverse(Lb));
}
if (q[0] == "L")
L[x] += y;
else if (q[0] == "R")
R[x] += y;
else
Console.WriteLine(L.Sum(x, y) + R.Sum(x, y));
}
Console.Out.Flush();
}
public class Treap
{
public Node Root;
public class Node
{
static readonly Random random = new Random(0);
public Node _L, _R;
public int Count;
public long Val;
//public long RangeAdded;
//public long Min;
//public long Max;
public long Sum;
public bool Reversed;
public readonly int Priority;
public Node(long val)
{
Val = val; Count = 1; Priority = random.Next();
//Min = val;
//Max = val;
Sum = val;
}
public Node L
{
get { if (Reversed) PushDown(); return _L; }
set { if (Reversed)PushDown(); _L = value; }
}
public Node R
{
get { if (Reversed) PushDown(); return _R; }
set { if (Reversed) PushDown(); _R = value; }
}
public void PushDown()
{
//if (!Reversed && RangeAdded == 0) return;
if (_L != null)
{
//_L.RangeAdded += RangeAdded;
//_L.Min += RangeAdded;
//_L.Max += RangeAdded;
//_L.Sum += RangeAdded * _L.Count;
_L.Reversed ^= Reversed;
}
if (_R != null)
{
//_R.RangeAdded += RangeAdded;
//_R.Min += RangeAdded;
//_R.Max += RangeAdded;
//_R.Sum += RangeAdded * _R.Count;
_R.Reversed ^= Reversed;
}
//if (Reversed)
//{
var t = _L; _L = _R; _R = t;
Reversed = false;
//}
//Val += RangeAdded;
//RangeAdded = 0;
Update(this);
}
public override string ToString()
{
return Val + (_L == null ? "" : " L:" + _L.Val) + (_R == null ? "" : " R:" + _R.Val);
}
}
public void Build(long[] A, int L = 0, int R = -1)
{
Root = BuildRec(A, L, R == -1 ? A.Length : R);
}
Node BuildRec(long[] A, int L, int R)
{
if (R == -1) R = A.Length;
if (R - L <= 0) return null;
int mid = L + R >> 1;
var node = new Node(A[mid]);
node.L = BuildRec(A, L, mid);
node.R = BuildRec(A, mid + 1, R);
Update(node);
return node;
}
public int Count { get { return Size(Root); } }
static int Size(Node n) { return n == null ? 0 : n.Count; }
static Node Update(Node n)
{
n.Count = 1 + (n._L == null ? 0 : n._L.Count) + (n._R == null ? 0 : n._R.Count);
//n.Min = n.Val;
//n.Max = n.Val;
//if (n._L != null)
//{
// n.Min = Math.Min(n.Min, n._L.Min);
// n.Max = Math.Max(n.Max, n._L.Max);
//}
//if (n._R != null)
//{
// n.Min = Math.Min(n.Min, n._R.Min);
// n.Max = Math.Max(n.Max, n._R.Max);
//}
//n.Min += n.RangeAdded;
//n.Max += n.RangeAdded;
n.Sum = n.Val + /*n.RangeAdded * n.Count + */ (n._L == null ? 0 : n._L.Sum) + (n._R == null ? 0 : n._R.Sum);
return n;
}
long RangeQuery(Node node, int L, int R, long init, Func<Node, long> nF, Func<long, long, long> F)
{
if (node == null || L >= R) return init;
if (L == 0 && R == Size(node)) return nF(node);
long res = init;
int Lsize = Size(node.L);
if (Lsize >= L && Lsize < R)
res = node.Val;
if (L < Lsize)
res = F(res, RangeQuery(node.L, L, Math.Min(R, Lsize), init, nF, F));
if (R - Lsize - 1 > 0)
res = F(res, RangeQuery(node.R, Math.Max(0, L - Lsize - 1), R - Lsize - 1, init, nF, F));
return res;
}
//public long Min(int L, int R) { return RangeQuery(Root, L, R, long.MaxValue, n => n.Min, Math.Min); }
//public long Max(int L, int R) { return RangeQuery(Root, L, R, long.MinValue, n => n.Max, Math.Max); }
public long Sum(int L, int R) { return RangeQuery(Root, L, R, 0, n => n.Sum, (a, b) => a + b); }
//public void RangeAdd(int L, int R, long val) { RangeAdd(Root, L, R, val); }
//void RangeAdd(Node node, int L, int R, long val)
//{
// if (node == null || L >= R) return;
// if (L == 0 && R == node.Count)
// {
// node.RangeAdded += val;
// Update(node);
// return;
// }
// int Lsize = Size(node.L);
// if (Lsize >= L && Lsize < R) node.Val += val;
// if (L < Lsize) RangeAdd(node.L, L, Math.Min(R, Lsize), val);
// if (R - Lsize - 1 > 0) RangeAdd(node.R, Math.Max(0, L - Lsize - 1), R - Lsize - 1, val);
// Update(node);
//}
public long this[int index]
{
get
{
Debug.Assert(index >= 0 && index < Size(Root));
var node = Root;
while (index != Size(node.L))
if (index < Size(node.L)) node = node.L;
else { index -= Size(node.L) + 1; node = node.R; }
return node.Val;
}
set
{
if (index < Size(Root)) RemoveAt(index);
Insert(index, value);
}
}
public static Node Merge(Node L, Node R)
{
if (L == null) return R;
if (R == null) return L;
if (L.Priority > R.Priority)
{
L.R = Merge(L.R, R);
return Update(L);
}
R.L = Merge(L, R.L);
return Update(R);
}
public static void Split(Node n, int index, out Node L, out Node R)
{
if (n == null) { L = R = null; return; }
Node a, b;
if (index <= Size(n.L))
{
Split(n.L, index, out a, out b);
n.L = b;
L = a;
R = Update(n);
}
else
{
Split(n.R, index - Size(n.L) - 1, out a, out b);
n.R = a;
L = Update(n);
R = b;
}
}
public static void Split(Node n, int L, int R, out Node a, out Node b, out Node c)
{
Node t;
Split(n, R, out t, out c);
Split(t, L, out a, out b);
}
public void Insert(int index, long val) { Root = Insert(Root, new Node(val), index); }
public Node Insert(Node node, Node newNode, int index)
{
if (node == null || index == Size(node.L) || newNode.Priority > node.Priority)
{
Node L, R;
Split(node, index, out L, out R);
node = Merge(L, newNode);
node = Merge(node, R);
}
else
{
if (index < Size(node.L))
node.L = Insert(node.L, newNode, index);
else
node.R = Insert(node.R, newNode, index - Size(node.L) - 1);
Update(node);
}
return node;
}
public void RemoveAt(int index) { Root = RemoveAt(Root, index); }
Node RemoveAt(Node node, int index)
{
if (node == null || index == Size(node.L))
{
Node L1, R1, L2, R2;
Split(node, index, out L1, out R1);
Split(R1, 1, out L2, out R2);
node = Merge(L1, R2);
}
else
{
if (index < Size(node.L))
node.L = RemoveAt(node.L, index);
else
node.R = RemoveAt(node.R, index - Size(node.L) - 1);
Update(node);
}
return node;
}
public void Reverse(int L, int R) { Root = Reverse(Root, L, R); }
public static Node Reverse(Node node, int L = 0, int R = -1)
{
if (node == null) return null;
if (R == -1) R = Size(node);
Node a, b, c;
Split(node, L, R, out a, out b, out c);
b.Reversed ^= true;
return Merge(a, Merge(b, c));
}
}
}
class Entry { static void Main() { new Program().Solve(); } }
class Reader
{
static TextReader reader = Console.In;
static readonly char[] separator = { ' ' };
static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;
static string[] A = new string[0];
static int i;
static void Init() { A = new string[0]; }
public static void Set(TextReader r) { reader = r; Init(); }
public static void Set(string file) { reader = new StreamReader(file); Init(); }
public static bool HasNext() { return CheckNext(); }
public static string String() { return Next(); }
public static int Int() { return int.Parse(Next()); }
public static long Long() { return long.Parse(Next()); }
public static double Double() { return double.Parse(Next()); }
public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }
public static int[] IntArray(int N) { return Range(N, Int); }
public static int[][] IntTable(int H) { return Range(H, IntLine); }
public static string[] StringArray(int N) { return Range(N, Next); }
public static string[][] StringTable(int N) { return Range(N, () => Split(Line())); }
public static string Line() { return reader.ReadLine().Trim(); }
static string[] Split(string s) { return s.Split(separator, op); }
static T[] Range<T>(int N, Func<T> f) { var r = new T[N]; for (int i = 0; i < N; r[i++] = f()) ; return r; }
static string Next() { CheckNext(); return A[i++]; }
static bool CheckNext()
{
if (i < A.Length) return true;
string line = reader.ReadLine();
if (line == null) return false;
if (line == "") return CheckNext();
A = Split(line);
i = 0;
return true;
}
}