UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211269#2398. 游戏YuanWeize2042ms2484kbC++1.9kb2024-08-10 11:14:032024-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...

output:


result: