結果

問題 No.877 Range ReLU Query
コンテスト
ユーザー vjudge1
提出日時 2026-08-24 10:39:05
言語 C++14
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 84 ms / 2,000 ms
+ 326µs
コード長 1,501 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,063 ms
コンパイル使用メモリ 185,104 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2026-08-24 10:39:11
合計ジャッジ時間 5,389 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e5+5;
int n,q,n1,n2,a[N],ca[N<<1],ql[N],qr[N],qx[N],hp[N<<1],hq[N<<1],pn[N],pv[N],qn[N],qi[N],cnt;
ll c1[N],c2[N],ans[N];

void init(int n){
    n1=n;
    n2=n;
    memset(c1,0,sizeof(c1));
    memset(c2,0,sizeof(c2));
}

void add1(int p,ll x){
    for(int i=p;i<=n1;i+=i&-i){
    	c1[i]+=x;
	}
}

void add2(int p,ll x){
    for(int i=p;i<=n2;i+=i&-i){
    	c2[i]+=x;
	}
}

ll sum1(int p){
	ll v=0;
	for(int i=p;i;i-=i&-i) v+=c1[i];
	return v;
}

ll sum2(int p){
	ll v=0;
	for(int i=p;i;i-=i&-i) v+=c2[i];
	return v;
}

int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		ca[i]=a[i];
	}
	for(int i=1;i<=q;i++){
		int op;
		scanf("%d%d%d%d",&op,&ql[i],&qr[i],&qx[i]);
		ca[n+i]=qx[i];
	}
	sort(ca+1,ca+n+q+1);
    int m=unique(ca+1,ca+n+q+1)-ca-1;
    memset(hp,-1,sizeof(hp));
    memset(hq,-1,sizeof(hq));
    for(int i=1;i<=n;i++){
        int idx=lower_bound(ca+1,ca+m+1,a[i])-ca;
        pv[i]=i;
        pn[i]=hp[idx];
        hp[idx]=i;
    }
    for(int i=1;i<=q;i++){
    	int idx=lower_bound(ca+1,ca+m+1,qx[i])-ca;
    	qi[i]=i;
    	qn[i]=hq[idx];
    	hq[idx]=i;
	}
	init(n);
	for(int i=m;i>=1;i--){
		for(int p=hp[i];p!=-1;p=pn[p]){
			int pos=pv[p];
			add1(pos,a[pos]);
			add2(pos,1);
		}
		for(int p=hq[i];p!=-1;p=qn[p]){
			int x=qi[p];
			ans[x]=sum1(qr[x])-sum1(ql[x]-1)-(sum2(qr[x])-sum2(ql[x]-1))*qx[x];
		}
	}
	for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}
0