結果
| 問題 |
No.2809 Sort Query
|
| コンテスト | |
| ユーザー |
👑  b1agmpo1e
|
| 提出日時 | 2025-11-18 02:25:02 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,562 ms / 2,000 ms |
| コード長 | 9,991 bytes |
| コンパイル時間 | 14,573 ms |
| コンパイル使用メモリ | 171,100 KB |
| 実行使用メモリ | 190,440 KB |
| 最終ジャッジ日時 | 2025-11-18 02:26:29 |
| 合計ジャッジ時間 | 77,272 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 71 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (142 ミリ秒)。 /home/judge/data/code/Main.cs(115,23): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(295,20): warning CS8981: 型名 'input' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Reflection.Emit;
using System.Runtime.InteropServices.Marshalling;
using System.Security.Cryptography;
using System.Security.Cryptography.X509Certificates;
using System.Linq;
using Microsoft.VisualBasic;
namespace test
{
internal class Program
{
static void Main(string[] args)
{
cin = new input();
//mod = new mod(998244353);
//toolbox = new toolbox();
//Priority_Queue = new Priority_Queue(true);
var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
//toolbox.StartTimer();
var time=new Stopwatch();
time.Start();
int n = cin.intreed();
int q = cin.intreed();
var arr = new List<long>();
arr.Add(0);
for (int i = 1; i <= n; i++)
{
arr.Add(cin.longreed());
}
var tree=new AvlMultiset();
bool sorted = false;//1度でもソートされたか
var changed = Enumerable.Range(1, n).ToList();
var changedFlag = new bool[n + 1];
Array.Fill(changedFlag, true);
changedFlag[0] = false;
while (q-- > 0)
{
int mode = cin.intreed();
if (mode == 1)
{
int k = cin.intreed();//k番目の値が更新される
long x = cin.longreed();
arr[k]=x;
if(!changedFlag[k])
{
changedFlag[k]=true;
changed.Add(k);
}
}
else if (mode == 2)
{
if(changed.Count==0)
continue;
changed.Sort();
if(!sorted)
{
foreach(var k in changed)
{
tree.Insert(arr[k]);
changedFlag[k]=false;
}
changed.Clear();
sorted=true;
continue;
}
int removed=0;
foreach(var k in changed)
{
int target=k-removed;
long val=tree[target];
tree.Erase(val);
removed++;
}
foreach(var k in changed)
{
tree.Insert(arr[k]);
changedFlag[k]=false;
}
changed.Clear();
}
else
{
int k = cin.intreed();
if (changedFlag[k])
{
System.Console.WriteLine(arr[k]);
}
else
{
System.Console.WriteLine(tree[k]);
}
}
}
Console.Error.WriteLine(time.ElapsedMilliseconds);
//toolbox.PrintElapsedTime();
Console.Out.Flush();
}
static input cin;
//static mod mod;
//static toolbox toolbox;
//static Priority_Queue Priority_Queue;
}
public class AvlMultiset
{
//1-indexです!!!!!!
private class node
{
public long val;
public int cnt;//同じ値の個数
public int height;
public int size;//部分木内の要素数（cnt含む）
public node left;
public node right;
public node(long v)
{
val = v;
cnt = 1;
height = 1;
size = 1;
}
}
private node root;
private static int Height(node t) => t?.height ?? 0;
private static int Size(node t) => t?.size ?? 0;
private static void Update(node t)
{
if (t == null) return;
t.height = Math.Max(Height(t.left), Height(t.right)) + 1;
t.size = Size(t.left) + Size(t.right) + t.cnt;
}
private static int BalanceFactor(node t) => Height(t.left) - Height(t.right);
private static node RotateRight(node y)
{
var x = y.left;
var t2 = x.right;
x.right = y;
y.left = t2;
Update(y);
Update(x);
return x;
}
private static node RotateLeft(node x)
{
var y = x.right;
var t2 = y.left;
y.left = x;
x.right = t2;
Update(x);
Update(y);
return y;
}
private static node Balance(node t)
{
if (t == null) return null;
Update(t);
int bf = BalanceFactor(t);
if (bf > 1)
{
if (BalanceFactor(t.left) < 0)
{
t.left = RotateLeft(t.left);
}
return RotateRight(t);
}
if (bf < -1)
{
if (BalanceFactor(t.right) > 0)
{
t.right = RotateRight(t.right);
}
return RotateLeft(t);
}
return t;
}
private node Insert(node t, long val)
{
if (t == null) return new node(val);
if (val < t.val)
{
t.left = Insert(t.left, val);
}
else if (val > t.val)
{
t.right = Insert(t.right, val);
}
else
{
t.cnt++;
Update(t);
return t;
}
return Balance(t);
}
private node RemoveMin(node t, out node removed)
{
if (t.left == null)
{
removed = t;
var right = t.right;
t.left = null;
t.right = null;
return right;
}
t.left = RemoveMin(t.left, out removed);
return Balance(t);
}
private node Erase(node t, long val)
{
if (t == null) return null;
if (val < t.val)
{
t.left = Erase(t.left, val);
}
else if (val > t.val)
{
t.right = Erase(t.right, val);
}
else
{
if (t.cnt > 1)
{
t.cnt--;
return Balance(t);
}
if (t.left == null) return t.right;
if (t.right == null) return t.left;
t.right = RemoveMin(t.right, out var successor);
successor.left = t.left;
successor.right = t.right;
t = successor;
}
return Balance(t);
}
private bool Find(node t, long val)
{
while (t != null)
{
if (val < t.val) t = t.left;
else if (val > t.val) t = t.right;
else return true;
}
return false;
}
private long GetKth(node t, int k)
{
if (t == null || k < 1 || k > Size(t))
throw new ArgumentOutOfRangeException(nameof(k));
int leftCount = Size(t.left);
if (k <= leftCount)
{
return GetKth(t.left, k);
}
if (k <= leftCount + t.cnt)
{
return t.val;
}
return GetKth(t.right, k - leftCount - t.cnt);
}
//外部向け
public void Insert(long val) => root = Insert(root, val);
public void Erase(long val) => root = Erase(root, val);
public bool Find(long val) => Find(root, val);
public int Count() => Size(root);
public long this[int index] => GetKth(root, index);
}
internal class input
{
string[] soloinput;
int t;
public input()
{
soloinput = new string[0];
t = 0;
}
public string soloreed()
{
if (t < soloinput.Length)
{
return soloinput[t++];
}
string input = Console.ReadLine();
while (input == "")
{
input = Console.ReadLine();
}
soloinput = input.Split(" ");
t = 0;
return soloinput[t++];
}
public int intreed()
{
return int.Parse(soloreed());
}
public int[] arrayint(int N)
{
int[] A = new int[N];
for (int i = 0; i < N; i++)
{
A[i] = intreed();
}
return A;
}
public long longreed()
{
return long.Parse(soloreed());
}
public long[] arraylong(long N)
{
long[] A = new long[N];
for (long i = 0; i < N; i++)
{
A[i] = longreed();
}
return A;
}
public decimal decimalreed()
{
return decimal.Parse(soloreed());
}
public decimal[] arraydecimal(long N)
{
decimal[] A = new decimal[N];
for (decimal i = 0; i < N; i++)
{
A[(long)i] = decimalreed();
}
return A;
}
}
}