제출 #1229378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229378		dibamboo23	Addk (eJOI21_addk)	C++20	100 / 100	263 ms	14636 KiB

Main

#include <bits/stdc++.h>

#define ll long long
#define F first
#define S second
#define sz size()

using namespace std;

[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;

inline int rd(){
	int num;cin>>num;
	return num;
}

inline ll rdll(){
	ll num;cin>>num;
	return num;
}

[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e6+3;

struct trio{
	ll res,sum;
	int cnt;
};

trio t_l[N],t_r[N];

trio merge_r(trio A,trio B){
	trio C={0,0,0};
	C.res=A.res+B.res+(ll)A.cnt*B.sum;
	C.sum=A.sum+B.sum;
	C.cnt=A.cnt+B.cnt;
	return C;
}
trio merge_l(trio A,trio B){
	trio C={0,0,0};
	C.res=A.res+B.res+(ll)B.cnt*A.sum;
	C.sum=A.sum+B.sum;
	C.cnt=A.cnt+B.cnt;
	return C;
}

int n;

void upd(int pos,int x,int v=1,int tl=1,int tr=n){
	if(tl==tr){
		t_l[v]={x,x,1};
		t_r[v]={x,x,1};
		return;
	}
	int md=(tl+tr)>>1;
	if(pos<=md)upd(pos,x,v+v,tl,md);
	else upd(pos,x,v+v+1,md+1,tr);
	t_l[v]=merge_l(t_l[v+v],t_l[v+v+1]);
	t_r[v]=merge_r(t_r[v+v],t_r[v+v+1]);
}

trio get_r(int l,int r,int v=1,int tl=1,int tr=n){
	if(tl>=l&&tr<=r)return t_r[v];
	if(tl>r||l>tr)return {0,0,0};
	int md=(tl+tr)>>1;
	return merge_r(get_r(l,r,v+v,tl,md),get_r(l,r,v+v+1,md+1,tr));
}
trio get_l(int l,int r,int v=1,int tl=1,int tr=n){
	if(tl>=l&&tr<=r)return t_l[v];
	if(tl>r||l>tr)return {0,0,0};
	int md=(tl+tr)>>1;
	return merge_l(get_l(l,r,v+v,tl,md),get_l(l,r,v+v+1,md+1,tr));
}

// max(l,i-m+1)
// min(r-m+1,i) - max(l,i-m+1)

int get(int i,int l,int r,int m){
	return min(r-m+1,i)-max(l,i-m+1)+1;
}

int a[N],b[N];
int vals[N];

int find(int lq,int rq,int L,int R,int m,int x){
	int l=lq,r=rq,res=lq;
	while(r>=l){
		int md=(r+l)>>1;
		if(get(md,L,R,m)==x){
			res=md;
			l=md+1;
		}
		else r=md-1;
	}
	return res;
}

void code(){
	int k;cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>vals[i];
		upd(i,vals[i]);
	}
	int q;cin>>q;
	while(q--){
		int tp;cin>>tp;
		if(tp==1){
			for(int i=0;i<k;i++)cin>>a[i];
			for(int i=0;i<k;i++)b[i]=vals[a[(i+1)%k]];
			for(int i=0;i<k;i++){
				vals[a[i]]=b[i];
				upd(a[i],vals[a[i]]);
			}
			continue;
		}
		int l,r,m;cin>>l>>r>>m;
		int md=(l+r)>>1;
		int x=get(md,l,r,m);
		int R=find(md,r,l,r,m,x);
		int L=l+(r-R);
		ll res=get_r(L,R).sum*(ll)x;
		if(l!=L)res+=get_r(l,L-1).res;
		if(r!=R)res+=get_l(R+1,r).res;
		cout<<res<<"\n";
	}
}




signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int tt=1;
	// cin>>tt;
	while(tt--)code(),cout<<"\n";
}

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