結果
| 問題 | No.879 Range Mod 2 Query |
| ユーザー |
 keymoon
|
| 提出日時 | 2019-09-07 15:08:40 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,278 bytes |
| コンパイル時間 | 3,937 ms |
| コンパイル使用メモリ | 118,812 KB |
| 実行使用メモリ | 59,864 KB |
| 最終ジャッジ日時 | 2024-06-26 11:08:07 |
| 合計ジャッジ時間 | 17,508 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 38 ms
19,712 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
コンパイルメッセージ
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.Net;
using System.Net.Sockets;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.Threading.Tasks;
using System.Text.RegularExpressions;
using static System.Math;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
public static class P
{
public static void Main()
{
var nq = Console.ReadLine().Split().Select(int.Parse).ToArray();
var n = nq[0];
var q = nq[1];
var a = Console.ReadLine().Split().Select(int.Parse).ToArray();
//区間代入/区間加算/区間和ができれば嬉しいが
SegmentTree<Section, long> rsq =
new SegmentTree<Section, long>
(
a.Select(x => new Section() { Elem = x, Length = 1 }).ToArray(),
new Section() { Length = 0, Elem = 0 },
0,
(x, y) => new Section() { Length = x.Length + y.Length, Elem = (x.Elem & (long.MaxValue - 1)) + (y.Elem & (long.MaxValue - 1)) },
(x, y) =>
{
//x加算にy埋めはy埋め
//x埋めにy埋めはy埋め
if (y < 0) return y;
//x埋めに区間y加算が降ってきたら、x+y埋め
if (x < 0) return ~((~x) + y);
//区間x加算に区間y加算はx+y加算
return x + y;
},
(x, y) =>
{
if (y < 0) return new Section() { Elem = x.Length * (~y), Length = x.Length };
return new Section() { Elem = x.Elem + x.Length * y, Length = x.Length };
}
);
SegmentTree<Section, bool> rsqBit =
new SegmentTree<Section, bool>
(
a.Select(x => new Section() { Elem = x & 1, Length = 1 }).ToArray(),
new Section() { Length = 0, Elem = 0 },
false,
Section.Merge,
(x, y) => x ^ y,
(x, y) => y ? new Section() { Length = x.Length, Elem = x.Length - x.Elem } : x
);
for (int i = 0; i < q; i++)
{
var query = Console.ReadLine().Split().Select(int.Parse).ToArray();
var l = query[1] - 1;
var r = query[2] - 1;
if (query[0] == 1)
{
rsq.Update(l, r, -1);
}
else if (query[0] == 2)
{
rsq.Update(l, r, query[3]);
rsqBit.Update(l, r, (query[3] & 1) == 1);
}
else
{
Console.WriteLine(rsq.Query(l, r).Elem + rsqBit.Query(l, r).Elem);
}
}
}
}
struct Section
{
public int Length;
public long Elem;
public static Section Merge(Section a, Section b) => new Section() { Length = a.Length + b.Length, Elem = a.Elem + b.Elem };
public override string ToString() => $"length : {Length} elem : {Elem}";
}
class SegmentTree<DataT, OperatorT>
{
public readonly int Size;
DataT DataIdentity;
OperatorT OperatorIdentity;
Func<DataT, DataT, DataT> MergeData;
Func<OperatorT, OperatorT, OperatorT> MergeOperator;
Func<DataT, OperatorT, DataT> Operate;
int LeafCount;
int Height;
DataT[] Data;
OperatorT[] Operators;
#region Construct
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public SegmentTree(int size, DataT dataIdentity, OperatorT operatorIdentity, Func<DataT, DataT, DataT> mergeData, Func<OperatorT, OperatorT, OperatorT> mergeOpeator, Func<DataT, OperatorT, DataT> operate)
: this(dataIdentity, operatorIdentity, mergeData, mergeOpeator, operate)
{
Size = size;
Build();
for (int i = 0; i < Data.Length; i++) Data[i] = DataIdentity;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public SegmentTree(DataT[] data, DataT dataIdentity, OperatorT operatorIdentity, Func<DataT, DataT, DataT> mergeData, Func<OperatorT, OperatorT, OperatorT> mergeOpeator, Func<DataT, OperatorT, DataT> operate)
: this(dataIdentity, operatorIdentity, mergeData, mergeOpeator, operate)
{
Size = data.Length;
Build();
for (int i = 0; i < data.Length; i++) Data[i + LeafCount] = data[i];
for (int i = data.Length + LeafCount; i < Data.Length; i++) Data[i] = dataIdentity;
for (int i = LeafCount - 1; i >= 0; i--) Data[i] = MergeData(Data[i << 1], Data[(i << 1) + 1]);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private SegmentTree(DataT dataIdentity, OperatorT operatorIdentity, Func<DataT, DataT, DataT> mergeData, Func<OperatorT, OperatorT, OperatorT> mergeOpeator, Func<DataT, OperatorT, DataT> operate)
{
DataIdentity = dataIdentity;
OperatorIdentity = operatorIdentity;
MergeData = mergeData;
MergeOperator = mergeOpeator;
Operate = operate;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Build()
{
Height = 1;
LeafCount = 1;
while (LeafCount < Size) { Height++; LeafCount <<= 1; }
Operators = new OperatorT[LeafCount << 1];
for (int i = 0; i < Operators.Length; i++) Operators[i] = OperatorIdentity;
Data = new DataT[LeafCount << 1];
}
#endregion
public DataT this[int index]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get { Propagate(index + LeafCount); return Reflect(index); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set { Propagate(index += LeafCount); Data[index] = value; Operators[index] = OperatorIdentity; Calculate(index, index); }
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Update(int l, int r, OperatorT x)
{
l += LeafCount;
r += LeafCount;
int origL = l, origR = r;
Propagate(l, r);
while (l <= r)
{
if ((l & 1) == 1) Operators[l] = MergeOperator(Operators[l], x);
if ((r & 1) == 0) Operators[r] = MergeOperator(Operators[r], x);
l = (l + 1) >> 1; r = (r - 1) >> 1;
}
Calculate(origL, origR);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public DataT Query(int l, int r)
{
l += LeafCount;
r += LeafCount;
DataT lRes = DataIdentity, rRes = DataIdentity;
Propagate(l, r);
while (l <= r)
{
if ((l & 1) == 1) lRes = MergeData(lRes, Reflect(l));
if ((r & 1) == 0) rRes = MergeData(Reflect(r), rRes);
l = (l + 1) >> 1; r = (r - 1) >> 1;
}
return MergeData(lRes, rRes);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Propagate(int ind) { for (int i = Height - 1; i >= 1; i--) { Eval(ind >> i); } return; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Propagate(int l, int r)
{
if (l == r) { Propagate(l); return; }
int xor = l ^ r, i = Height - 1;
for (; (xor >> i) == 0; i--) { Eval(l >> i); }
for (; i >= 1; i--) { Eval(l >> i); Eval(r >> i); }
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private DataT Reflect(int ind) { return Operate(Data[ind], Operators[ind]); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Eval(int ind)
{
int l = ind << 1, r = ind << 1 | 1;
Operators[l] = MergeOperator(Operators[l], Operators[ind]);
Operators[r] = MergeOperator(Operators[r], Operators[ind]);
Data[ind] = Reflect(ind);
Operators[ind] = OperatorIdentity;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private void Calculate(int l, int r)
{
var xor = l ^ r;
while (xor > 1) { xor >>= 1; l >>= 1; r >>= 1; Data[l] = MergeData(Reflect(l << 1), Reflect((l << 1) | 1)); Data[r] = MergeData(Reflect(r << 1), Reflect((r << 1) | 1)); }
while (l > 1) { l >>= 1; Data[l] = MergeData(Reflect(l << 1), Reflect((l << 1) | 1)); }
}
}