結果
| 問題 |
No.2809 Sort Query
|
| コンテスト | |
| ユーザー |
👑  b1agmpo1e
|
| 提出日時 | 2025-11-18 02:32:46 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
AC
|
| 実行時間 | 1,605 ms / 2,000 ms |
| コード長 | 10,065 bytes |
| コンパイル時間 | 10,696 ms |
| コンパイル使用メモリ | 170,876 KB |
| 実行使用メモリ | 189,988 KB |
| 最終ジャッジ日時 | 2025-11-18 02:34:06 |
| 合計ジャッジ時間 | 79,153 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 71 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (109 ミリ秒)。 /home/judge/data/code/Main.cs(115,22): warning CS8981: 型名 'node' には、小文字の ASCII 文字のみが含まれています。このような名前は、プログラミング言語用に予約されている可能性があります。 [/home/judge/data/code/main.csproj] /home/judge/data/code/Main.cs(268,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());
}
Treap.node root = null;
var treapRand = new Random(998244353);
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)
{
Treap.Insert(ref root,arr[k],treapRand);
changedFlag[k]=false;
}
changed.Clear();
sorted=true;
continue;
}
int removed=0;
foreach(var k in changed)
{
int target=k-removed;
long val=Treap.GetKth(root,target);
Treap.Erase(ref root,val);
removed++;
}
foreach(var k in changed)
{
Treap.Insert(ref root,arr[k],treapRand);
changedFlag[k]=false;
}
changed.Clear();
}
else
{
int k = cin.intreed();
if (changedFlag[k])
{
System.Console.WriteLine(arr[k]);
}
else
{
System.Console.WriteLine(Treap.GetKth(root,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 static class Treap
{
//1-indexです!!!!!!
public class node
{
public long val;
public node left;//小さい
public node right;//大きい
public int cnt;//部分木の大きさ（freq含む）
public int freq;//このノードに格納されている同値の個数
public int priority;//優先度
public node(long val, int priority, node left = null, node right = null)
{
this.val = val;
this.priority = priority;
this.left = left;
this.right = right;
this.freq = 1;
}
public long update()
{
cnt = freq;
if (left != null) cnt += left.cnt;
if (right != null) cnt += right.cnt;
return cnt;
}
}
//key未満のノードとkey以上のノードに分割する
private static void Split(node t, long key, out node left, out node right)
{
if (t == null)
{
left = null;
right = null;
return;
}
else if (key <= t.val)
{
//key以上なので、今回のノードと右側部分木は右に行く
Split(t.left, key, out left, out t.left);
right = t;
}
else
{
//key未満なので、今回のノードと右側部分木は右に行く
Split(t.right, key, out t.right, out right);
left = t;
}
t.update();
}
//左と右を合体した新たな木(t)を作る
private static void Marge(ref node t, node left, node right)
{
if (left == null || right == null)
{
t = left ?? right;
}
else if (left.priority > right.priority)
{
//leftの方が優先度高い
Marge(ref left.right, left.right, right);
t = left;
}
else
{
//rightの方が優先度高い
Marge(ref right.left, left, right.left);
t = right;
}
if (t != null) t.update();
}
public static void Insert(ref node root, long key, Random rand)
{
var item = new node(key, rand.Next());
Insert(ref root, item);
}
private static void Insert(ref node t, node item)
{
if (t == null)
{
t = item;
}
else if (item.val == t.val)
{
t.freq++;
}
else if (item.priority > t.priority)
{
//itemの方が優先度高い このノードをitemに置き換える 今のノードtはledtかrightに入る
Split(t, item.val, out item.left, out item.right);
t = item;
}
else
{
//こいつは優先度がヒープになることに反するので、下に潜る
Insert(ref item.val < t.val ? ref t.left : ref t.right, item);
}
t.update();
}
public static void Erase(ref node root, long key)
{
EraseNode(ref root, key);
}
private static void EraseNode(ref node t, long key)
{
if (t == null) return;
if (t.val == key)
{
if (t.freq > 1)
{
t.freq--;
}
else
{
//今いるノードを消す このノードを子供をマージしてできた木に置き換える
Marge(ref t, t.left, t.right);
}
}
else
{
//このノードは消したいノードじゃない
EraseNode(ref key < t.val ? ref t.left : ref t.right, key);
}
if (t != null) t.update();
}
public static long GetKth(node t, int k)
{
if (t == null || k < 1 || k > t.cnt)
throw new ArgumentOutOfRangeException(nameof(k));
int leftCount = t.left != null ? t.left.cnt : 0;
if (k <= leftCount)
{
return GetKth(t.left, k);
}
else if (k <= leftCount + t.freq)
{
return t.val;
}
else
{
return GetKth(t.right, k - leftCount - t.freq);
}
}
}
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;
}
}
}