UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211237#2398. 游戏drdilyor1001709ms50320kbC++112.7kb2024-08-10 08:43:262024-08-10 12:33:20

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
void ts(){cout<<"IAKIOI\n";}
inline int read(){
	int n=0,f=1,ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		n=n*10+ch-'0';
		ch=getchar();
	}
	return n*f;
}
const int mod=998244353;
struct mint{
    int x;mint(int o=0){x=o;}mint&operator+=(mint a){return(x+=a.x)%=mod,*this;}mint&operator-=(mint a){return(x+=mod-a.x)%=mod,*this;}
    mint&operator*=(mint a){return(x=1ll*x*a.x%mod),*this;}mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
    mint&operator/=(mint a){return*this*=(a^=mod-2);}friend mint operator+(mint a,mint b){return a+=b;}friend mint operator-(mint a,mint b){return a-=b;}
    friend mint operator*(mint a,mint b){return a*=b;}friend mint operator/(mint a,mint b){return a/=b;}friend mint operator^(mint a,int b){return a^=b;}
    mint operator-(){return 0-*this;}bool operator==(const mint b)const{return x==b.x;}
};
int n,m;
int seg[1000005*4],seg2[1000005*4];
int tag[1000005*4];
void pushdown(int id,int l,int r){
	if(!tag[id])return;
	int mid=(l+r)/2;
	tag[id*2]+=tag[id],tag[id*2+1]+=tag[id];
	seg[id*2]+=(mid-l+1)*tag[id],seg[id*2+1]+=tag[id]*(r-mid);
	seg2[id*2]+=((l+mid)*(mid-l+1)/2)*tag[id];
	seg2[id*2+1]+=((r+mid+1)*(r-mid)/2)*tag[id];
	tag[id]=0;
}
void mdf(int id,int l,int r,int ql,int qr,int d){
	if(l==ql&&r==qr){
		seg[id]+=(r-l+1)*d;
		seg2[id]+=d*((l+r)*(r-l+1)/2);
		tag[id]+=d;
		return;
	}
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(qr<=mid)mdf(id*2,l,mid,ql,qr,d);
	else if(ql>mid)mdf(id*2+1,mid+1,r,ql,qr,d);
	else mdf(id*2,l,mid,ql,mid,d),mdf(id*2+1,mid+1,r,mid+1,qr,d);
	seg[id]=seg[id*2]+seg[id*2+1];
	seg2[id]=seg2[id*2]+seg2[id*2+1];
}
int qry(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr)return seg[id];
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(qr<=mid)return qry(id*2,l,mid,ql,qr);
	if(ql>mid)return qry(id*2+1,mid+1,r,ql,qr);
	return qry(id*2,l,mid,ql,mid)+qry(id*2+1,mid+1,r,mid+1,qr);
}
int qry2(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr)return seg2[id];
	pushdown(id,l,r);
	int mid=(l+r)/2;
	if(qr<=mid)return qry2(id*2,l,mid,ql,qr);
	if(ql>mid)return qry2(id*2+1,mid+1,r,ql,qr);
	return qry2(id*2,l,mid,ql,mid)+qry2(id*2+1,mid+1,r,mid+1,qr);
}
signed main(){
	n=read(),m=read();
	while(m--){
		int ty=read();
		if(ty==2){
			int l=read(),r=read();
			int res=0;
			if(l>1)res+=qry(1,1,n,1,l-1)*(r-l+1);
			if(l<=r)res+=qry(1,1,n,l,r)*(r+1);
			res-=qry2(1,1,n,l,r);
			printf("%lld\n",res);
		}
		else{
			int s=read(),l=read(),r=read();
			mdf(1,1,n,l,r,s);
			if(r<n)mdf(1,1,n,r+1,r+1,-(r-l+1)*s);
		}
	}
	return 0;
}

详细

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

Test #1:

score: 10
Accepted
time: 5ms
memory: 1932kb

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: 6ms
memory: 1936kb

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: 43ms
memory: 48996kb

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: 160ms
memory: 50320kb

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: 309ms
memory: 50316kb

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: 299ms
memory: 50316kb

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: 192ms
memory: 50316kb

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: 238ms
memory: 50316kb

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: 230ms
memory: 50316kb

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: 227ms
memory: 50320kb

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