ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#211269 | #2398. 游戏 | YuanWeize | 20 | 42ms | 2484kb | C++ | 1.9kb | 2024-08-10 11:14:03 | 2024-08-10 12:38:13 |
answer
#include<bits/stdc++.h>
#define N 200005
#define M 2000005
#define inf 0x3f3f3f3f
#define ls k<<1
#define rs k<<1|1
#define pa pair<int,int>
#define int long long
using namespace std;
int n,m;
int a[N];
struct Node{
int l,r,d,x,sum;
}tr[N*4];
int solve(int k,int x,int d){
int cnt=tr[k].r-tr[k].l+1;
int ret=x+x+(cnt-1)*d;
ret=(ret*cnt)>>1;
return ret;
}
void pp(int k){
tr[k].sum=tr[ls].sum+tr[rs].sum;
}
void pd(int k){
if(tr[k].d||tr[k].x){
tr[ls].sum+=solve(ls,tr[k].x,tr[k].d);
tr[ls].d+=tr[k].d;
tr[ls].x+=tr[k].x;
tr[k].x+=(tr[ls].r-tr[ls].l+1)*tr[k].d;
tr[rs].sum+=solve(rs,tr[k].x,tr[k].d);
tr[rs].d+=tr[k].d;
tr[rs].x+=tr[k].x;
}
tr[k].d=tr[k].x=0;
}
void build(int l,int r,int k){
tr[k].l=l;
tr[k].r=r;
if(l==r){
tr[k].sum=a[l];
return;
}
int d=(l+r)>>1;
build(l,d,ls);
build(d+1,r,rs);
pp(k);
}
void update(int l,int r,int x,int d,int k){
if(tr[k].l>=l&&tr[k].r<=r){
tr[k].sum+=solve(k,x,d);
tr[k].d+=d;
tr[k].x+=x;
return;
}
pd(k);
int md=(tr[k].l+tr[k].r)>>1;
if(r<=md) update(l,r,x,d,ls);
else if(l>md) update(l,r,x,d,rs);
else{
update(l,md,x,d,ls);
x+=(md-l+1)*d;
update(md+1,r,x,d,rs);
}
pp(k);
}
int query(int l,int r,int k){
if(tr[k].l>=l&&tr[k].r<=r){
return tr[k].sum;
}
pd(k);
int md=(tr[k].l+tr[k].r)>>1;
int sum=0;
if(l<=md)sum+=query(l,r,ls);
if(r>md)sum+=query(l,r,rs);
return sum;
}
signed main(){
cin>>n>>m;
build(1,n,1);
while(m--){
int op;
cin>>op;
if(op==1){
int l,r;
int s;
cin>>s>>l>>r;
update(l,r,s,s,1);
}else{
int l,r;
cin>>l>>r;
cout<<query(l,r,1)<<endl;
}
}
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 23ms
memory: 2484kb
input:
10000 10000 2 7160 9968 1 -473 6964 8476 1 -153 5216 7023 2 6352 6868 1 -323 2338 2855 1 415 8414 88...
output:
0 -110345895 -118168581 -43417983 -4860827434 -604843653 -2613457133 -534205626 -89290630 484290874 ...
result:
ok 5015 lines
Test #2:
score: 10
Accepted
time: 19ms
memory: 2480kb
input:
10000 10000 1 326 2291 8264 2 2344 3512 1 146 4506 4804 1 342 1373 4495 1 -267 929 3525 1 444 3384 8...
output:
243137972 7529843014 0 11315350608 10741570136 -23729193 8497340876 11134190564 4752384896 166579811...
result:
ok 5048 lines
Test #3:
score: 0
Runtime Error
input:
666666 10000 1 92 555251 586462 1 393 28541 523118 1 448 17256 369367 1 -28 89257 596132 1 -338 3136...
output:
result:
Test #4:
score: 0
Runtime Error
input:
666666 50000 1 -249 309981 333889 1 477 309512 463171 1 0 71655 592642 1 45 191249 527454 1 55 38872...
output:
result:
Test #5:
score: 0
Runtime Error
input:
666666 100000 1 -183 598736 630118 1 -337 605875 639236 1 -62 265069 340682 1 -96 370300 571646 1 -1...
output:
result:
Test #6:
score: 0
Runtime Error
input:
666666 100000 2 121929 379928 2 34550 66844 1 96 338911 637923 2 161666 370147 1 -282 313713 463127 ...
output:
result:
Test #7:
score: 0
Runtime Error
input:
750000 100000 1 -318 454211 721481 2 239247 294171 2 52513 339575 2 424462 638364 2 683282 740790 1 ...
output:
result:
Test #8:
score: 0
Runtime Error
input:
1000000 100000 1 -108 318728 708230 1 -242 8738 411540 1 -119 458000 972357 2 368015 850304 1 -182 1...
output:
result:
Test #9:
score: 0
Runtime Error
input:
1000000 100000 2 347033 984386 2 277881 323793 1 431 735974 973576 2 782909 863840 1 -22 379088 6406...
output:
result:
Test #10:
score: 0
Runtime Error
input:
1000000 100000 1 -238 406279 814973 1 -425 637451 721356 1 237 340114 658854 2 279214 591961 2 17862...