結果
| 問題 |
No.1054 Union add query
|
| コンテスト | |
| ユーザー |
 Lily89164763
|
| 提出日時 | 2020-11-21 09:48:31 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,263 ms / 2,000 ms |
| コード長 | 13,965 bytes |
| コンパイル時間 | 3,317 ms |
| コンパイル使用メモリ | 119,068 KB |
| 実行使用メモリ | 118,856 KB |
| 最終ジャッジ日時 | 2024-07-23 15:26:45 |
| 合計ジャッジ時間 | 11,646 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 8 |
コンパイルメッセージ
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 CompLib.Util;
using System.Threading;
using CompLib.Collections.Generic;
using CompLib.DataStructure;
public class Program
{
private int N, Q;
private int[] T, A, B;
void Scan()
{
var sc = new Scanner();
N = sc.NextInt();
Q = sc.NextInt();
T = new int[Q];
A = new int[Q];
B = new int[Q];
for (int i = 0; i < Q; i++)
{
T[i] = sc.NextInt();
switch (T[i])
{
case 1:
A[i] = sc.NextInt() - 1;
B[i] = sc.NextInt() - 1;
break;
case 2:
A[i] = sc.NextInt() - 1;
B[i] = sc.NextInt();
break;
case 3:
A[i] = sc.NextInt() - 1;
B[i] = sc.NextInt();
break;
}
}
}
public void Solve()
{
Scan();
#region 同じグループが連続するように並べる
var ls = new List<int>[N];
var grp = new int[N];
for (int i = 0; i < N; i++)
{
ls[i] = new List<int>();
ls[i].Add(i);
grp[i] = i;
}
for (int i = 0; i < Q; i++)
{
if (T[i] != 1) continue;
int ga = grp[A[i]];
int gb = grp[B[i]];
if (ga == gb) continue;
if (ls[ga].Count >= ls[gb].Count)
{
foreach (var j in ls[gb])
{
ls[ga].Add(j);
grp[j] = ga;
}
}
else
{
foreach (var j in ls[ga])
{
ls[gb].Add(j);
grp[j] = gb;
}
}
}
var hs = new HashSet<int>();
for (int i = 0; i < N; i++)
{
hs.Add(grp[i]);
}
int[] idx = new int[N];
int ptr = 0;
foreach (var g in hs)
{
foreach (int i in ls[g])
{
idx[i] = ptr++;
}
}
#endregion
var st = new SegmentTree<int>(N + 1, (l, r) => l + r, 0);
var uf = new UnionFind(N);
int[] left = new int[N];
int[] right = new int[N];
for (int i = 0; i < N; i++)
{
left[i] = i;
right[i] = i + 1;
}
Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) {AutoFlush = false});
for (int i = 0; i < Q; i++)
{
switch (T[i])
{
case 1:
int rA = uf.Find(idx[A[i]]);
int rB = uf.Find(idx[B[i]]);
if (uf.Connect(rA, rB))
{
int rC = uf.Find(rA);
left[rC] = Math.Min(left[rA], left[rB]);
right[rC] = Math.Max(right[rA], right[rB]);
}
break;
case 2:
int r = uf.Find(idx[A[i]]);
st[left[r]] += B[i];
st[right[r]] -= B[i];
break;
case 3:
Console.WriteLine(st.Query(0, idx[A[i]] + 1));
break;
}
}
Console.Out.Flush();
}
public static void Main(string[] args) => new Program().Solve();
// public static void Main(string[] args) => new Thread(new Program().Solve, 1 << 27).Start();
}
namespace CompLib.DataStructure
{
using System.Collections.Generic;
using System.Linq;
class UnionFind
{
private readonly int _n;
private readonly int[] _parent, _size;
/// <summary>
/// n頂点の無向グラフに 1.辺を追加, 2.2頂点が同じ連結成分に属するか判定 ができるデータ構造
/// </summary>
/// <param name="n">頂点の個数</param>
public UnionFind(int n)
{
_n = n;
_parent = new int[_n];
_size = new int[_n];
for (int i = 0; i < _n; i++)
{
_parent[i] = i;
_size[i] = 1;
}
}
/// <summary>
/// iがいる連結成分の代表値
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public int Find(int i) => _parent[i] == i ? i : Find(_parent[i]);
/// <summary>
/// x,yが同じ連結成分にいるか?
/// </summary>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns></returns>
public bool Same(int x, int y) => Find(x) == Find(y);
/// <summary>
/// (x, y)に辺を追加する
/// </summary>
/// <remarks>
/// ACLでは連結された代表値を返しますが、ここでは連結できたか?を返します
/// </remarks>
/// <param name="x"></param>
/// <param name="y"></param>
/// <returns>x,yが違う連結成分だったならtrueを返す</returns>
public bool Connect(int x, int y)
{
x = Find(x);
y = Find(y);
if (x == y) return false;
// データ構造をマージする一般的なテク
if (_size[x] > _size[y])
{
_parent[y] = x;
_size[x] += _size[y];
}
else
{
_parent[x] = y;
_size[y] += _size[x];
}
return true;
}
/// <summary>
/// iが含まれる成分のサイズ
/// </summary>
/// <param name="i"></param>
/// <returns></returns>
public int GetSize(int i) => _size[Find(i)];
/// <summary>
/// 連結成分のリスト
/// </summary>
/// <returns></returns>
public List<int>[] Groups()
{
var leaderBuf = new int[_n];
var groupSize = new int[_n];
for (int i = 0; i < _n; i++)
{
leaderBuf[i] = Find(i);
groupSize[leaderBuf[i]]++;
}
var result = new List<int>[_n];
for (int i = 0; i < _n; i++)
{
result[i] = new List<int>(groupSize[i]);
}
for (int i = 0; i < _n; i++)
{
result[leaderBuf[i]].Add(i);
}
return result.Where(ls => ls.Count > 0).ToArray();
}
}
}
namespace CompLib.Collections.Generic
{
using System;
using System.Diagnostics;
public class SegmentTree<T>
{
// 見かけ上の大きさ、実際の大きさ
private readonly int _n, _size;
private T[] _array;
private T _identity;
private Func<T, T, T> _operation;
public SegmentTree(int n, Func<T, T, T> operation, T identity)
{
_n = n;
_size = 1;
while (_size < _n)
{
_size *= 2;
}
_identity = identity;
_operation = operation;
_array = new T[_size * 2];
for (int i = 1; i < _size * 2; i++)
{
_array[i] = _identity;
}
}
public SegmentTree(T[] a, Func<T, T, T> operation, T identity)
{
_n = a.Length;
_size = 1;
while (_size < _n)
{
_size *= 2;
}
_identity = identity;
_operation = operation;
_array = new T[_size * 2];
for (int i = 0; i < a.Length; i++)
{
_array[i + _size] = a[i];
}
for (int i = a.Length; i < _size; i++)
{
_array[i + _size] = identity;
}
for (int i = _size - 1; i >= 1; i--)
{
_array[i] = operation(_array[i * 2], _array[i * 2 + 1]);
}
}
/// <summary>
/// A[i]をnに更新 O(log N)
/// </summary>
/// <param name="i"></param>
/// <param name="n"></param>
public void Update(int i, T n)
{
Debug.Assert(0 <= i && i < _n);
i += _size;
_array[i] = n;
while (i > 1)
{
i /= 2;
_array[i] = _operation(_array[i * 2], _array[i * 2 + 1]);
}
}
/// <summary>
/// A[left] op A[left+1] ... op A[right-1]を求める
/// </summary>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
public T Query(int left, int right)
{
Debug.Assert(0 <= left && left <= right && right <= _n);
T sml = _identity;
T smr = _identity;
left += _size;
right += _size;
while (left < right)
{
if ((left & 1) != 0) sml = _operation(sml, _array[left++]);
if ((right & 1) != 0) smr = _operation(_array[--right], smr);
left >>= 1;
right >>= 1;
}
return _operation(sml, smr);
}
/// <summary>
/// op(a[0],a[1],...,a[n-1])を返します
/// </summary>
/// <returns></returns>
public T All()
{
return _array[1];
}
/// <summary>
/// f(op(a[l],a[l+1],...a[r-1])) = trueとなる最大のrを返します
/// </summary>
/// <param name="l"></param>
/// <param name="f"></param>
/// <returns></returns>
public int MaxRight(int l, Func<T, bool> f)
{
Debug.Assert(0 <= l && l <= _n);
#if DEBUG
Debug.Assert(f(_identity));
#endif
if (l == _n) return _n;
l += _size;
T sm = _identity;
do
{
while (l % 2 == 0) l >>= 1;
if (!f(_operation(sm, _array[l])))
{
while (l < _size)
{
l <<= 1;
if (f(_operation(sm, _array[l])))
{
sm = _operation(sm, _array[l]);
l++;
}
}
return l - _size;
}
sm = _operation(sm, _array[l]);
l++;
} while ((l & -l) != l);
return _n;
}
/// <summary>
/// f(op(a[l],a[l+1],...a[r-1])) = trueとなる最小のlを返します
/// </summary>
/// <param name="r"></param>
/// <param name="f"></param>
/// <returns></returns>
public int MinLeft(int r, Func<T, bool> f)
{
Debug.Assert(0 <= r && r <= _n);
#if DEBUG
Debug.Assert(f(_identity));
#endif
if (r == 0) return 0;
r += _size;
T sm = _identity;
do
{
r--;
while (r > 1 && (r % 2 != 0)) r >>= 1;
if (!f(_operation(_array[r], sm)))
{
while (r < _size)
{
r = (2 * r + 1);
if (f(_operation(_array[r], sm)))
{
sm = _operation(_array[r], sm);
r--;
}
}
return r + 1 - _size;
}
sm = _operation(_array[r], sm);
} while ((r & -r) != r);
return 0;
}
public T this[int i]
{
set { Update(i, value); }
get
{
Debug.Assert(0 <= i && i < _n);
return _array[i + _size];
}
}
}
}
namespace CompLib.Util
{
using System;
using System.Linq;
class Scanner
{
private string[] _line;
private int _index;
private const char Separator = ' ';
public Scanner()
{
_line = new string[0];
_index = 0;
}
public string Next()
{
if (_index >= _line.Length)
{
string s;
do
{
s = Console.ReadLine();
} while (s.Length == 0);
_line = s.Split(Separator);
_index = 0;
}
return _line[_index++];
}
public string ReadLine()
{
_index = _line.Length;
return Console.ReadLine();
}
public int NextInt() => int.Parse(Next());
public long NextLong() => long.Parse(Next());
public double NextDouble() => double.Parse(Next());
public decimal NextDecimal() => decimal.Parse(Next());
public char NextChar() => Next()[0];
public char[] NextCharArray() => Next().ToCharArray();
public string[] Array()
{
string s = Console.ReadLine();
_line = s.Length == 0 ? new string[0] : s.Split(Separator);
_index = _line.Length;
return _line;
}
public int[] IntArray() => Array().Select(int.Parse).ToArray();
public long[] LongArray() => Array().Select(long.Parse).ToArray();
public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
}
}