QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403243#2861. 相关分析rzh123100 ✓171ms30784kbC++173.2kb2024-05-01 23:02:162024-05-01 23:02:17

Judging History

你现在查看的是最新测评结果

  • [2024-05-01 23:02:17]
  • 评测
  • 测评结果:100
  • 用时:171ms
  • 内存:30784kb
  • [2024-05-01 23:02:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
constexpr int N=1e5+7;
using lf=double;
int n,m,x[N],y[N];
inline lf ss(lf l,lf r){
	return (l+r)*(r-l+1)/2;
}
inline lf sqs(lf l,lf r){
	--l;
	return r*(r+1)*(2*r+1)/6.0-l*(l+1)*(2*l+1)/6.0;
}
struct Res{
	lf x,y,x2,xy;
};
Res operator+(const Res &a,const Res &b){
	return Res{a.x+b.x,a.y+b.y,a.x2+b.x2,a.xy+b.xy};
}
struct Seg{
	struct Tag{
		bool e;
		lf x,y;
	};
	struct{
		int l,r;
		lf xs,ys,x2s,xys;
		Tag lz3,lz2;
		inline int len()const{return r-l+1;}
		void init(int x,int y){
			xs=x,ys=y,
			x2s=1ll*x*x,
			xys=1ll*x*y;
			lz2=lz3={false,0.0,0.0};
		}
	}tr[N<<2];
	void doasn(int k,Tag tg){
		if(!tg.e) return ;
		tr[k].lz2.e=false;
		tr[k].lz2.x=tr[k].lz2.y=0;
		tr[k].lz3=tg;
		tr[k].xs=ss(tr[k].l+tg.x,tr[k].r+tg.x);
		tr[k].ys=ss(tr[k].l+tg.y,tr[k].r+tg.y);
		tr[k].x2s=sqs(tr[k].l+tg.x,tr[k].r+tg.x);
		tr[k].xys=tr[k].len()*tg.x*tg.y+ss(tr[k].l,tr[k].r)*(tg.x+tg.y)+sqs(tr[k].l,tr[k].r);
	}
	void doadd(int k,Tag d){
		if(!d.e) return ;
		tr[k].lz2.e = true;
		tr[k].lz2.x += d.x,
		tr[k].lz2.y += d.y;
		tr[k].x2s += 2*d.x*tr[k].xs+tr[k].len()*d.x*d.x;
		tr[k].xys += d.x*tr[k].ys+d.y*tr[k].xs+d.x*d.y*tr[k].len();
		tr[k].xs += tr[k].len()*d.x;
		tr[k].ys += tr[k].len()*d.y;
	}
	void pup(int k){
		tr[k].xs = tr[k<<1].xs+tr[k<<1|1].xs;
		tr[k].ys = tr[k<<1].ys+tr[k<<1|1].ys;
		tr[k].x2s = tr[k<<1].x2s+tr[k<<1|1].x2s;
		tr[k].xys = tr[k<<1].xys+tr[k<<1|1].xys;
	}
	void pdn(int k){
		if(tr[k].lz3.e){
			doasn(k<<1,tr[k].lz3);
			doasn(k<<1|1,tr[k].lz3);
			tr[k].lz3={false,0.0,0.0};
		}
		if(tr[k].lz2.e){
			doadd(k<<1,tr[k].lz2);
			doadd(k<<1|1,tr[k].lz2);
			tr[k].lz2={false,0.0,0.0};
		}
	}
	void build(int k,int l,int r){
		tr[k].l=l,tr[k].r=r;
		tr[k].lz2=tr[k].lz3={false,0.0,0.0};
		if(l==r){
			tr[k].init(x[l],y[l]);
			return ;
		}
		int mi((l+r)>>1);
		build(k<<1,l,mi),build(k<<1|1,mi+1,r),
		pup(k);
	}
	void modify(int k,int l,int r,int ty,int s,int t){
		if(tr[k].l>=l&&tr[k].r<=r){
			if(ty==2) doadd(k,Tag{true,1.0*s,1.0*t});
			else doasn(k,Tag{true,1.0*s,1.0*t});
			return ;
		}
		pdn(k); int mi((tr[k].l+tr[k].r)>>1);
		if(l<=mi) modify(k<<1,l,r,ty,s,t);
		if(r>mi) modify(k<<1|1,l,r,ty,s,t);
		pup(k);
	}
	Res query(int k,int l,int r){
		if(tr[k].l>=l&&tr[k].r<=r){
			return Res{tr[k].xs,tr[k].ys,tr[k].x2s,tr[k].xys};
		}
		pdn(k); int mi((tr[k].l+tr[k].r)>>1);
		if(r<=mi) return query(k<<1,l,r);
		else if(l>mi) return query(k<<1|1,l,r);
		else return query(k<<1,l,r)+query(k<<1|1,l,r);
	}
}seg;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cout<<fixed<<setprecision(10);
	cin>>n>>m;
	for(int i{1};i<=n;++i){
		cin>>x[i];
	}
	for(int i{1};i<=n;++i){
		cin>>y[i];
	}
	seg.build(1,1,n);
	while(m--){
		int t,l,r,x{0},y{0};
		cin>>t>>l>>r;
		if(t==1){
			auto res=seg.query(1,l,r);
			int len{r-l+1};
			lf x0=res.x/len,y0=res.y/len;
			cout<< (res.xy-res.y*x0-res.x*y0+x0*y0*len) / (res.x2-2*res.x*x0+x0*x0*len) <<'\n';
		}
		else{
			cin>>x>>y;
			seg.modify(1,l,r,t,x,y);
		}
	}
	return 0;
}

/*
 (x-x0)(y-y0)
= xy-x0y-y0x+x0y0
 (x-x0)^2
= x^2 -2x*x0+x0^2

sum xy, sum x, sum y, sum x^2
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 0ms
memory: 4092kb

input:

711 662
31796 -21280 -56141 35697 96071 -32846 62715 64190 239 -18734 -94438 12690 -14439 43314 -50312 48336 86732 81739 56325 89371 76217 -50269 -87300 76237 -75459 37201 63523 -36833 -37871 40717 -57452 7594 -29459 52543 58716 71577 -8000 -76624 -14934 -51870 -7394 -6313 -14813 12035 53428 82733 -...

output:

1.0000000000
-0.7135448694
-0.0358702475
-0.0084668464
-0.7209893083
-0.2433334085
-1.4354994869
1.0000000000
0.0528636036
0.0064688195
1.0000000000
1.0000000000
0.4113679401
-0.4045617209
-0.8980526148
-0.3890742108
-0.3826716035
-0.5484293128
-0.3894396475
-0.0284321029
0.5120695257
-0.0351093792
...

result:

ok 221 numbers

Test #2:

score: 10
Accepted
time: 1ms
memory: 4060kb

input:

874 937
73039 -92536 43357 -42615 -24203 -37301 62968 44708 46826 84709 -8514 73155 -96493 -55082 -42698 -58738 51746 88504 -2417 9963 -6527 92008 -29551 -12257 -32286 52829 -76472 9700 74305 22599 23735 -35000 -35079 -49673 16232 -13124 -16872 -70693 -58247 -86677 -20135 -63553 6377 -76912 47001 -9...

output:

0.7784389470
0.3028843880
0.6768427575
-1.1045147134
-1.6626890654
3.3032685001
1.0000000000
5.5842142247
0.5461527691
10.9925066520
1.0000000000
-1.0576649897
4.8560385788
0.6005357087
-261.6812863462
-7.9607927915
1.0000000000
1.0000000000
0.4139904307
-1.1673423716
-1.2684101454
-0.8671847935
0.0...

result:

ok 288 numbers

Test #3:

score: 10
Accepted
time: 107ms
memory: 28288kb

input:

93429 92875
-12219 -26665 -35246 77236 18962 -71528 98069 -28204 -58620 23515 -43503 -9260 10575 -63979 67928 13555 -95969 -88513 -36015 -33215 40409 -69236 -2680 8165 -89906 -97057 43130 47404 53481 -76003 60322 -29369 21061 -62634 71506 -94220 97703 31511 -24765 98117 -95539 88037 69192 5158 -1489...

output:

-0.0113577518
-0.0048130346
0.0077661175
-0.0050521011
-0.0014928547
-0.0013284590
-0.0011968640
-0.0038461598
0.0010355747
-0.0111280578
-0.0026277050
-0.0080463891
-0.0087986003
0.0002327855
-0.0179487435
-0.0170082815
-0.0008403004
-0.0047770970
-0.0154304769
0.0051760735
-0.0097801940
-0.0034257...

result:

ok 46343 numbers

Test #4:

score: 10
Accepted
time: 113ms
memory: 28344kb

input:

99274 98422
86203 76389 65679 59740 30004 -58488 68870 56713 32815 -43124 81071 -38709 -68938 25388 -22591 35841 -68283 96284 6814 18108 -74982 39961 -67878 45185 -89777 -99220 46568 -59756 -56149 60315 -55170 19543 2479 -599 54741 99034 -38063 32774 37884 32743 -96313 -19055 80048 -87227 -46224 -30...

output:

0.0002004347
-0.0028388642
-0.0026616389
0.0086110546
0.0032923976
-0.0067316387
0.0089976426
0.0044519906
0.0040975020
0.0040964731
0.0032315204
-0.0000298447
-0.0026868230
0.0063847104
0.0163368425
-0.0034285405
-0.0089210228
0.0026724608
-0.0014428138
0.0008067393
0.0176346503
0.0075630739
0.0049...

result:

ok 49318 numbers

Test #5:

score: 10
Accepted
time: 107ms
memory: 28488kb

input:

92091 96718
36995 35006 -48687 76508 -76342 -5913 26247 -91678 3097 52095 73727 -4316 66336 -10038 -19702 -33106 67651 56189 83186 27991 -70569 -16687 -54123 70721 -24671 74098 -83757 11840 16159 83123 -38241 86508 -91091 52942 19834 73437 -11943 -67697 -89908 -59755 16676 16466 -26869 -51650 81471 ...

output:

0.0102520954
0.1337158676
0.0176854750
-0.2180147653
-0.1930549994
-0.0639753504
-0.0847013917
-0.2118457492
0.1548715446
0.2946794256
-0.1576556324
0.0363543577
-0.3506219437
-0.0814877273
-0.1443391509
-0.3067014376
-0.1528242130
-0.1484966702
0.0894687076
0.1401267429
-0.0399639307
0.1008691329
0...

result:

ok 48148 numbers

Test #6:

score: 10
Accepted
time: 97ms
memory: 27800kb

input:

94227 90816
-17848 -46929 -65113 90067 -50515 -6970 67543 -30367 -1011 99975 36766 61590 5788 -62862 -26730 -11412 39590 -75061 -18151 88165 21554 48356 -66497 7117 58946 -79427 -54808 -36505 -65645 -42925 87892 46831 31059 -98988 22987 -48778 60563 -27335 48943 -94181 20898 67895 12185 -12637 71569...

output:

0.0027671878
-0.1001601279
0.0603947135
0.0037390696
-0.1180038200
0.1718598584
0.1235936242
0.0794964126
0.2043252268
0.1124040088
0.0958835067
0.2812376466
0.1483478755
0.2852448032
0.0522165111
0.0690848557
0.2430276209
-0.1328527343
0.1752577508
0.0971967693
0.0413559861
0.2110177189
-0.00499528...

result:

ok 45576 numbers

Test #7:

score: 10
Accepted
time: 103ms
memory: 27688kb

input:

93395 91004
64189 44808 -61456 5290 66550 66941 81146 -57192 99828 -59317 -1294 81032 -39054 -90240 -89868 89099 -80110 -10974 -70695 -3643 -52087 -64642 -76055 21866 25295 -3495 -78821 32650 -81190 -91050 18767 52262 38880 6099 30294 -92142 -2215 5544 46765 -209 3445 -89823 -4386 -79934 57951 -7131...

output:

-0.0034179455
0.1102603957
0.1214667375
0.0833984856
0.3115855667
-0.1010205105
0.2573679298
-0.0141792113
-0.0558498309
-0.2154756030
0.0664502580
0.1274820353
0.1771546610
-0.0665434444
0.1519093196
-0.0721997440
0.0237273590
0.0530738959
-0.2203342830
0.0198576958
0.3227990148
0.1704932701
0.1400...

result:

ok 45586 numbers

Test #8:

score: 10
Accepted
time: 163ms
memory: 28520kb

input:

95954 95942
56386 -99781 64719 48356 58384 5844 56237 -85671 -28062 17509 -28614 -53896 14442 65833 -57625 7073 16706 62135 -6139 2199 -27475 88754 57344 67284 69107 75597 59971 -42986 19381 -51604 95567 11586 33847 -29621 75462 13858 -89891 -59800 71031 47783 -67299 36074 54218 -49645 29734 -57046 ...

output:

0.0000454425
-0.5423401275
-0.6834349736
-0.8566378679
1.0000000000
0.5640094770
0.0579318147
1.0000000000
-0.0573356970
0.0042098451
1.8678375779
-0.1832734895
0.0717775033
0.1478760131
1.3082319518
-0.9308992965
-1.0340844665
-0.4978353570
1.0000000000
-0.1408547550
-0.2914607220
0.7547689499
0.05...

result:

ok 32019 numbers

Test #9:

score: 10
Accepted
time: 149ms
memory: 28804kb

input:

97778 91848
35160 -51303 13651 45759 24915 39505 77351 85431 -73616 77028 -30910 21284 -70483 -13638 -2324 -49855 53010 -34603 -22139 77101 -63331 30641 -50099 89152 -773 -66849 -46611 -99142 -84859 -68088 73386 15532 -75628 99886 -4310 -24668 -85252 66195 -55211 -10440 53612 17257 29247 7649 94474 ...

output:

-0.0001946126
-0.0564296528
4.7460498177
0.0099363108
-0.5244289895
1.0000000000
-0.4214691811
-1.9941679699
-0.0017041781
1.0000000000
-1.4908923106
0.2085836882
0.6405954135
0.2623376735
0.4949727039
-0.6699902591
0.3412473687
0.2064307453
0.3242980284
1.0000000000
0.0923988242
-0.3848811920
-0.93...

result:

ok 30419 numbers

Test #10:

score: 10
Accepted
time: 171ms
memory: 30784kb

input:

98343 95328
57697 56771 88988 -1614 -40500 -92443 -345 -83247 26894 24637 6449 32486 35799 -45479 -65583 47246 56365 88294 -70235 25519 -5699 82083 24595 54288 -45095 -34132 -13429 -45842 -7461 2281 91898 -57409 28705 68489 -85683 -607 78585 -84245 89483 89278 -60767 96738 -54329 -90488 -38607 33176...

output:

-0.0064152616
-0.4213648173
0.2559817535
-1.2555209888
-1.5361459519
1.0000000000
1.8620000970
0.2147940882
0.1042947681
-0.3207631315
-0.3072218387
-0.5418670727
-0.2887393538
-0.5665214771
1.0000000000
-0.4959159388
0.8388909490
-0.1623746615
0.5002153302
1.0243389962
-0.4051371510
-0.2094708764
1...

result:

ok 31766 numbers