#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
#define USING_ORDERED_SET 0
#if USING_ORDERED_SET
#include<bits/extc++.h>
using namespace __gnu_pbds;
template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
#endif
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
struct SegmentTree{
vector<ll>tree;
void build(int n){
tree.assign(n<<2|3,0);
}
ll get(int v,int l,int r,int ql,int qr){
if(qr<l||r<ql)return 0ll;
if(ql<=l&&r<=qr)return tree[v];
int mid=(l+r)>>1;
return get(v<<1,l,mid,ql,qr)+get(v<<1|1,mid+1,r,ql,qr);
}
void update(int v,int l,int r,int pos,ll val){
if(l==r){
tree[v]=val;
return;
}
int mid=(l+r)>>1;
if(pos>mid)update(v<<1|1,mid+1,r,pos,val);
else update(v<<1,l,mid,pos,val);
tree[v]=tree[v<<1]+tree[v<<1|1];
}
}tree[3];
ll a[100005];
int b[100005];
int main(){
int n,k,q;
scanf("%d%d",&n,&k);
tree[0].build(n);
tree[1].build(n);
tree[2].build(n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i]=x;
tree[0].update(1,1,n,i,a[i]);
tree[1].update(1,1,n,i,a[i]*i);
tree[2].update(1,1,n,i,a[i]*(n-i+1));
}
scanf("%d",&q);
while(q--){
int type;
scanf("%d",&type);
if(type&1){
for(int i=0;i<k;i++)scanf("%d",&b[i]);
ll temp=a[b[0]];
for(int i=1;i<k;i++){
tree[0].update(1,1,n,b[i-1],a[b[i]]);
tree[1].update(1,1,n,b[i-1],a[b[i]]*b[i-1]);
tree[2].update(1,1,n,b[i-1],a[b[i]]*(n-b[i-1]+1));
a[b[i-1]]=a[b[i]];
}
tree[0].update(1,1,n,b[k-1],temp);
tree[1].update(1,1,n,b[k-1],temp*b[k-1]);
tree[2].update(1,1,n,b[k-1],temp*(n-b[k-1]+1));
a[b[k-1]]=a[b[0]];
}else{
int l,r,m;
ll ans=0;
scanf("%d%d%d",&l,&r,&m);
if(2*m>r-l+1)m=r-l+2-m;
ans+=tree[1].get(1,1,n,l,l+m-1)-tree[0].get(1,1,n,l,l+m-1)*1ll*(l-1);
ans+=tree[2].get(1,1,n,r-m+1,r)-tree[0].get(1,1,n,r-m+1,r)*1ll*(n-r);
if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
else ans+=tree[0].get(1,1,n,l+m,r-m)*(1ll*m);
printl("________________");
printf("%lld\n",ans);
}
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:82:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | if(2*m-1==r-l+1)ans-=m*a[l+r>>1];
| ~^~
Main.cpp:18:29: warning: statement has no effect [-Wunused-value]
18 | #define printl(args...) 0
| ^
Main.cpp:84:4: note: in expansion of macro 'printl'
84 | printl("________________");
| ^~~~~~
Main.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d%d",&n,&k);
| ~~~~~^~~~~~~~~~~~~~
Main.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | scanf("%d",&x);
| ~~~~~^~~~~~~~~
Main.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
58 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
Main.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%d",&type);
| ~~~~~^~~~~~~~~~~~
Main.cpp:63:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | for(int i=0;i<k;i++)scanf("%d",&b[i]);
| ~~~~~^~~~~~~~~~~~
Main.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
78 | scanf("%d%d%d",&l,&r,&m);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
5 ms |
596 KB |
Output is correct |
| 5 |
Correct |
7 ms |
724 KB |
Output is correct |
| 6 |
Correct |
10 ms |
852 KB |
Output is correct |
| 7 |
Correct |
13 ms |
980 KB |
Output is correct |
| 8 |
Correct |
16 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
20 ms |
1388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2508 KB |
Output is correct |
| 2 |
Correct |
68 ms |
3720 KB |
Output is correct |
| 3 |
Correct |
97 ms |
4840 KB |
Output is correct |
| 4 |
Correct |
181 ms |
8476 KB |
Output is correct |
| 5 |
Correct |
236 ms |
11984 KB |
Output is correct |
| 6 |
Correct |
247 ms |
11740 KB |
Output is correct |
| 7 |
Correct |
203 ms |
11716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
196 ms |
5816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
