結果

問題 No.3494 一点挿入区間和取得
コンテスト
ユーザー 👑 tails
提出日時 2026-04-04 03:19:06
言語 cLay
(20250308-1 + boost 1.89.0)
コンパイル:
clayc _filename_
実行:
./a.out
結果
AC  
実行時間 15 ms / 6,000 ms
コード長 449 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,844 ms
コンパイル使用メモリ 195,452 KB
実行使用メモリ 9,304 KB
最終ジャッジ日時 2026-04-04 03:19:19
合計ジャッジ時間 4,966 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

fenwick<ll>fi,fs;
ll kth(ll v){
	ll k=-1,d=1<<16;
	while(d){
		if(fi.data[k+d]<=v){
			v-=fi.data[k+d];
			k+=d;
		}else{
		}
		d>>=1;
	}
	return k+1;
}
{
	ll@n,@q,@a[n],@(i,x,l,r)[q];
	fi.malloc(1<<17,1);
	fs.malloc(n+q,1);
	rrep(j,n+q){
		fi.add(j,1);
	}
	rrep(j,q){
		r[j]=kth(r[j]-1);
		l[j]=kth(l[j]-1);
		i[j]=kth(i[j]);
		fi.add(i[j],-1);
	}
	rep(j,n){
		fs.add(kth(j),a[j]);
	}
	rep(j,q){
		fs.add(i[j],x[j]);
		wt(fs.range(l[j],r[j]));
	}
}
0