Submission #756244

#	Time	Username	Problem	Language	Result	Execution time	Memory
756244		dzdzx	Addk (eJOI21_addk)	C++17	0 / 100	237 ms	4752 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct node{
	int sumR,sum,sumL,size;
};
node t[400001];
node merge(node a,node b){
	node res;
	res.sum=a.sum+b.sum;
	res.sumL=a.sumL+b.sumL+b.sum*a.size;
	res.sumR=b.sumR+a.sumR+a.sum*b.size;
	res.size=a.size+b.size;
	return res;
}
node new_val(int a){
	node res;
	res.sum=res.sumR=res.sumL=a;
	res.size=1;
	if (a==-1){
		res.sum=res.sumR=res.sumL=0;
		res.size=0;		
	}
	return res;
}
void update(int v,int tl,int tr,int ind,int val){
	if (tl==tr)t[v]=new_val(val);else{
		int tm=(tl+tr)/2;
		if (ind<=tm)update(v*2,tl,tm,ind,val);else update(v*2+1,tm+1,tr,ind,val);
		t[v]=merge(t[v*2],t[v*2+1]);
	}
}
node query(int v,int tl,int tr,int l,int r){
	if (l>r)return new_val(-1);
	if (l==tl && r==tr)return t[v];
	int tm=(tl+tr)/2;
	return merge(query(v*2,tl,tm,l,min(r,tm)),query(v*2+1,tm+1,tr,max(l,tm+1),r));
}
int main(){
	int n,k;
	cin>>n>>k;
	int a[n+1];
	for (int i=1;i<=n;i++){
		cin>>a[i];
		update(1,1,n,i,a[i]);
	}
	int q;
	cin>>q;
	while (q--){
		int t;
		cin>>t;
		if (t==1){
			vector <int> v;
			v.push_back(0);
			int x[k+1];
			for (int i=1;i<=k;i++){
				cin>>x[i];
				if (i!=1)v.push_back(x[i]);
			}
			v.push_back(x[1]);
			for (int i=1;i<=k;i++){
				a[x[i]]=a[v[i]];
				update(1,1,n,x[i],a[x[i]]);
			}
		}else{
			int l,r,m;
			cin>>l>>r>>m;
			if (r-l+1>=2*m-2){
				cout<<query(1,1,n,l,l+m-2).sumL+query(1,1,n, r-m+2,r).sumR+query(1,1,n,l+m-1,r-m+1).sum*m<<"\n";
			}else{
				cout<<query(1,1,n,l,l+m-2).sumL+query(1,1,n, r-m+2,r).sumR-query(1,1,n,r-m+2,l+m-2).sum*(n-1)<<"\n";
			}
		}
	}


}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8