NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #211261 | #2398. 游戏 | sean1381 | 0 | 0ms | 0kb | C++11 | 1.6kb | 2024-08-10 10:22:42 | 2024-08-10 12:36:51 |
answer
#include<bits/stdc++.h>
#define MAXN 1000005
using namespace std;
long long n,m,a[MAXN];
struct segtree{
long long sum[4*MAXN],len[4*MAXN],lazy[4*MAXN];
void pushup(int k){
sum[k]=sum[k*2]+sum[k*2+1];
}
void add(int k,int v){
sum[k]+=(len[k]*v);
lazy[k]+=v;
}
void pushdown(int k){
for(int i=k*2;i<=k*2+1;i++) add(i,lazy[k]);
lazy[k]=0;
}
void build(int k,int l,int r){
len[k]=r-l+1;
if(l==r){sum[k]=a[l]; return;}
int mid=(l+r)/2;
build(k*2,l,mid); build(k*2+1,mid+1,r);
pushup(k);
}
long long query(int k,int l,int r,int x,int y){
if(l>=x&&r<=y) return sum[k];
if(l>y||x>r) return 0;
pushdown(k);
int mid=(l+r)/2;
return query(k*2,l,mid,x,y)+query(k*2+1,mid+1,r,x,y);
}
void update_add(int k,int l,int r,int x,int y,int v)
{
if(l>=x&&r<=y) {add(k,v); return;}
if(l>y||x>r) return;
pushdown(k);
int mid=(l+r)/2;
update_add(k*2,l,mid,x,y,v); update_add(k*2+1,mid+1,r,x,y,v);
pushup(k);
}
}seg;
int main(){
ios :: sync_with_stdio ( false );
//cin.tie ( 0 ), cout.tie ( 0 );
cin>>n>>m;
//for(int i=1;i<=n;i++) {cin>>a[i];}
seg.build(1,1,n);
for(int i=0;i<m;i++)
{
int type,x,y,k;
cin>>type;
if(type==1)
{
cin>>k;cin>>x>>y;
for(int i=x;i<=y;i++){
seg.update_add(1,1,n,i,y,k);
}
}
else if(type==2)
{
cin>>x>>y;
cout<<seg.query(1,1,n,x,y)<<endl;
}
}
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:
0 -110345895 -118168581 -43417983 -4860827434 -604843653 -2613457133 -534205626 -89290630 484290874 ...
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:
243137972 7529843014 0 11315350608 10741570136 -23729193 8497340876 11134190564 4752384896 166579811...
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:
0 0 46837507488 -2144565871356 12891851830 8888329560532
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:
0 0 -5392147899330 -3014688113400 -1060371486324 -3974117952270 273653038350 -222431173482 371388923...
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:
-21232196185685
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:
0 0 3048712203338 -275350879342 2861261347158 10963743541855 980271778300 5329951205134 712899593630...
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:
3413253435344 4249749642085 3270374154195 -7408047958251
