UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211266#2398. 游戏czh12345600ms0kbC++112.5kb2024-08-10 10:39:382024-08-10 12:37:53

answer

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
const int N = 1e6;
long long t[N << 2], d[N << 2], d2[N << 2];
int n;
void add(int x, long long v, int L, int R){
	t[x] += v * (R - L + 1);
	d[x] += v;
	return;
}
void add2(int x, long long v, int L, int R){
	if (L == R){
		t[x] += v;
	} else {
		d2[x] += v;
	}
	return;
}
void pushup(int x){
	t[x] = t[x << 1] + t[x << 1 | 1];
	return;
}
void pushdown(int x, int L, int R){
	int mid = (L + R) >> 1;
	if (d[x]){
		add(x << 1, d[x], L, mid);
		add(x << 1 | 1, d[x], mid + 1, R);
		d[x] = 0;
	}
	if (d2[x]){
		add2(x << 1, d2[x], L, mid);
		t[x << 1 | 1] += d2[x] * (mid - L + 1) * (R - mid);
		d[x << 1 | 1] += d2[x] * (mid - L + 1);
//		change(x << 1 | 1, d2[x] * (mid - L + 1), mid + 1, R, mid + 1, R);
		add2(x << 1 | 1, d2[x], mid + 1, R);
		d2[x] = 0;
	}
	pushup(x);
	return;
}
void change(int x, long long v, int l, int r, int L, int R){
	if (l == L && r == R){
		add(x, v, L, R);
		return;
	}
	pushdown(x, L, R);
	int mid = (L + R) >> 1;
	if (r <= mid){
		change(x << 1, v, l, r, L, mid);
	} else if (l > mid){
		change(x << 1 | 1, v, l, r, mid + 1, R);
	} else {
		change(x << 1, v, l, mid, L, mid);
		change(x << 1 | 1, v, mid + 1, r, mid + 1, R);
	}
	pushup(x);
	return;
}
void change2(int x, long long v, int l, int r, int L, int R){
	if (l == L && r == R){
		add2(x, v, L, R);
		return;
	}
	pushdown(x, L, R);
	int mid = (L + R) >> 1;
	if (r <= mid){
		change2(x << 1, v, l, r, L, mid);
	} else if (l > mid){
		change2(x << 1 | 1, v, l, r, mid + 1, R);
	} else {
		change(1, v * (mid - l + 1), mid + 1, r, 1, n);
		change2(x << 1, v, l, mid, L, mid);
		change2(x << 1 | 1, v, mid + 1, r, mid + 1, R);
	}
	pushup(x);
	return;
}
long long query(int x, int l, int r, int L, int R){
	if (l == L && r == R){
		return t[x];
	}
	pushdown(x, L, R);
	int mid = (L + R) >> 1;
	if (r <= mid){
		return query(x << 1, l, r, L, mid);
	} else if (l > mid){
		return query(x << 1 | 1, l, r, mid + 1, R);
	} else {
		return query(x << 1, l, mid, L, mid) + query(x << 1 | 1, mid + 1, r, mid + 1, R);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m, op, l, r, x;
	cin >> n >> m;
	while (m--){
		cin >> op;
		if (op == 1){
			cin >> x >> l >> r;
			change2(1, x, l, r, 1, n);
		} else {
			cin >> l >> r;
			cout << query(1, l, r, 1, n) << "\n";
		}
		for (int i = 1; i <= n; i++){
			int t = query(1, i, i, 1, n);
		}
	}
	return 0;
}

详细

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

Test #1:

score: 0
Time Limit Exceeded

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:


result:


Test #2:

score: 0
Time Limit Exceeded

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:


result:


Test #3:

score: 0
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

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
Time Limit Exceeded

input:

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

output:


result: