Submission #580839

#	Time	Username	Problem	Language	Result	Execution time	Memory
580839		penguin133	Addk (eJOI21_addk)	C++14	100 / 100	429 ms	22164 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pi pair<int, int> 
#define pii pair<int, pair<int, int> >
int P[200005], P2[200005], A[200005], S[200005];
int n,k;
struct node{
	int s,e,m,val,val2,val3;
	node *l, *r;
	node(int _s, int _e){
		val = val2 = val3 = 0;
		s = _s, e = _e, m = (s + e)/2;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void update(int p, int v){
		if(s == e)val = v, val2 = s*v, val3 = (n-s+1)*v;
		else{
			if(p <= m)l->update(p,v);
			else r->update(p,v);
			val = l->val + r->val;
			val2 = l->val2 + r->val2;
			val3 = l->val3 + r->val3;
		}
	}
	int query(int a, int b){
		if(s == a && e == b)return val;
		else if(b <= m)return l->query(a,b);
		else if(a > m)return r->query(a,b);
		else return l->query(a,m) + r->query(m+1,b);
	}
	int query2(int a, int b){
		if(s == a && e == b)return val2;
		else if(b <= m)return l->query2(a,b);
		else if(a > m)return r->query2(a,b);
		else return l->query2(a,m) + r->query2(m+1,b);
	}
	int query3(int a, int b){
		if(s == a && e == b)return val3;
		else if(b <= m)return l->query3(a,b);
		else if(a > m)return r->query3(a,b);
		else return l->query3(a,m) + r->query3(m+1,b);
	}
}*root;
 
void solve(){
	cin >> n >> k;
	root = new node(1, n);
	for(int i=1;i<=n;i++){
		cin >> A[i];
		root->update(i, A[i]);
	}
	int q;cin >> q;
	while(q--){
		int x;cin >> x;
		if(x == 1){
			int p;cin >> p;int prev = p;p = A[p];
			for(int i=2;i<=k;i++){
				int x;cin >> x;
				A[prev] = A[x];
				root->update(prev, A[x]);
				prev = x;
			}
			root->update(prev, p);
			A[prev] = p;
		}
		else{
			int l,r,m;
			cin >> l >> r >> m;
			int tmp = (r-l+1);
			m = min(m, tmp+1-m);
			int ans = 0;
			if(m > 1)ans += root->query2(l, l+m-2) - (l-1)*(root->query(l, l+m-2));
			if(m > 1)ans += root->query3(r-m+2, r) - (n-r)*(root->query(r-m+2, r));
			if(r-m+1 >= l+m-1)ans += m*(root->query(l+m-1, r-m+1));
			cout << ans << '\n';
		}
	}
}
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

Main.cpp:85:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   85 | main(){
      | ^~~~

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