ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#211257 | #2398. 游戏 | shiruiheng | 100 | 1921ms | 50384kb | C++11 | 1.9kb | 2024-08-10 10:16:45 | 2024-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
*/
Details
小提示:点击横条可展开更详细的信息
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