UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211257#2398. 游戏shiruiheng1001921ms50384kbC++111.9kb2024-08-10 10:16:452024-08-10 12:36:28

answer

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pi pair<ll, ll>
#define N 4444444
#define ls(x) ((x) << 1)
#define rs(x) (((x) << 1) | 1)
ll n, m, s, l, r, op;
struct sgt{
	ll sum[N], tl[N], tr[N];
	//ll lv[N], rv[N];
	void pushup(int t){
		sum[t] = sum[ls(t)] + sum[rs(t)];
	}
	void add(int rt, ll l, ll r, ll x, ll s){
		sum[rt] += (r - l + 1) * (l + r - 2 * x + 2) / 2 * s;
		tl[rt] += s * (l - x + 1);
		tr[rt] += s * (r - x + 1);
	}
	void add2(int rt, ll l, ll r, ll s, ll t){
		sum[rt] += (r - l + 1) * (s + t) / 2;
		tl[rt] += s;
		tr[rt] += t;
	}
	void pushdown(int rt, ll l, ll r){
		if(!tl[rt] && !tl[rt])
			return;
		int mid = (l + r) >> 1;
		ll d = (tr[rt] - tl[rt]) / (r - l);
		add2(ls(rt), l, mid, tl[rt], tl[rt] + (mid - l) * d);
		add2(rs(rt), mid + 1, r, tl[rt] + (mid - l + 1) * d, tr[rt]);
		tl[rt] = tr[rt] = 0;
	}
	void update(int rt, ll l, ll r, ll x, int y, ll s){
		if(x <= l && r <= y){
			add(rt, l, r, x, s);
			return;
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		if(x <= mid)
			update(ls(rt), l, mid, x, y, s);
		if(y > mid)
			update(rs(rt), mid + 1, r, x, y, s);
		pushup(rt);
	}
	ll query(int rt, int l, int r, int x, int y){
		if(x <= l && r <= y){
			return sum[rt];
		}
		pushdown(rt, l, r);
		int mid = (l + r) >> 1;
		ll ans = 0;
		if(x <= mid)
			ans += query(ls(rt), l, mid, x, y);
		if(y > mid)
			ans += query(rs(rt), mid + 1, r, x, y);
		pushup(rt);
		return ans;
	}
}st;
int main(){
	scanf("%lld%lld", &n, &m);
	for(int i = 1 ; i <= m ; i++){
		scanf("%lld", &op);
		if(op == 1){
			scanf("%lld%lld%lld", &s, &l, &r);
			st.update(1, 1, n, l, r, s);
			//cerr << st.query(1, 1, n, l, r) << "\n";
		}
		else{
			scanf("%lld%lld", &l, &r);
			printf("%lld\n", st.query(1, 1, n, l, r));
		}
	}
	return 0;
}
/*
10 7
1 2 6 9
2 4 6
1 -4 2 8
2 2 6
1 -3 1 9
2 6 8
2 4 8
2
-58
-123
-178
*/

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 10ms
memory: 1996kb

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: 9ms
memory: 1996kb

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: 10
Accepted
time: 23ms
memory: 47436kb

input:

666666 10000
1 92 555251 586462
1 393 28541 523118
1 448 17256 369367
1 -28 89257 596132
1 -338 3136...

output:

-414130189712976
77743328869266
-733317938115289
-16114105741314
-728855592871891
-618655286944621
-...

result:

ok 1111 lines

Test #4:

score: 10
Accepted
time: 110ms
memory: 50380kb

input:

666666 50000
1 -249 309981 333889
1 477 309512 463171
1 0 71655 592642
1 45 191249 527454
1 55 38872...

output:

120968444808072
-37038538159888
-1101768280866595
-1522590947086835
12009109183517
-363676922444525
...

result:

ok 5555 lines

Test #5:

score: 10
Accepted
time: 223ms
memory: 50384kb

input:

666666 100000
1 -183 598736 630118
1 -337 605875 639236
1 -62 265069 340682
1 -96 370300 571646
1 -1...

output:

-250805903081209
-53573550596528
-209778044605386
707244607925095
687363641118024
-353194926792326
1...

result:

ok 11111 lines

Test #6:

score: 10
Accepted
time: 226ms
memory: 50384kb

input:

666666 100000
2 121929 379928
2 34550 66844
1 96 338911 637923
2 161666 370147
1 -282 313713 463127
...

output:

0
0
46837507488
-2144565871356
12891851830
8888329560532
3600670974792
5838384797676
5198143259786
3...

result:

ok 49753 lines

Test #7:

score: 10
Accepted
time: 383ms
memory: 50380kb

input:

750000 100000
1 -318 454211 721481
2 239247 294171
2 52513 339575
2 424462 638364
2 683282 740790
1 ...

output:

0
0
-5392147899330
-3014688113400
-1060371486324
-3974117952270
273653038350
-222431173482
371388923...

result:

ok 49624 lines

Test #8:

score: 10
Accepted
time: 441ms
memory: 50380kb

input:

1000000 100000
1 -108 318728 708230
1 -242 8738 411540
1 -119 458000 972357
2 368015 850304
1 -182 1...

output:

-21232196185685
-20910538239000
-3733012342070
-66375750961180
-16926598739637
-12520509636427
-5091...

result:

ok 49764 lines

Test #9:

score: 10
Accepted
time: 265ms
memory: 50384kb

input:

1000000 100000
2 347033 984386
2 277881 323793
1 431 735974 973576
2 782909 863840
1 -22 379088 6406...

output:

0
0
3048712203338
-275350879342
2861261347158
10963743541855
980271778300
5329951205134
712899593630...

result:

ok 49769 lines

Test #10:

score: 10
Accepted
time: 231ms
memory: 50384kb

input:

1000000 100000
1 -238 406279 814973
1 -425 637451 721356
1 237 340114 658854
2 279214 591961
2 17862...

output:

3413253435344
4249749642085
3270374154195
-7408047958251
0
23029818546288
18074770628646
28102134374...

result:

ok 49741 lines

Extra Test:

score: 0
Extra Test Passed