| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 580837 |
2022-06-22T01:09:32 Z |
penguin133 |
Addk (eJOI21_addk) |
C++14 |
|
139 ms |
8976 KB |
#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;
}
}
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
Main.cpp:84:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
84 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
3768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
139 ms |
8976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
