QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403243 | #2861. 相关分析 | rzh123 | 100 ✓ | 171ms | 30784kb | C++17 | 3.2kb | 2024-05-01 23:02:16 | 2024-05-01 23:02:17 |
Judging History
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