why
查看原帖
why
655407
WisNourx_楼主2024/4/13 11:16

WA on #8 #9 #10,why?

#include<cmath>
#include<vector>
#include<complex>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

char buf[1<<20], *p1=buf, *p2=buf;
#define getchar() (p1==p2&&(p2=buf+fread(p1=buf, 1, 1<<20, stdin), p1==p2)?EOF:*p1++)
template <typename T>
void read(T &x)
{
	x=0;int f=1;char c=getchar();
	while (!isdigit(c)) f=(c=='-')?-1:1, c=getchar();
	while (isdigit(c)) x=(x<<1)+(x<<3)+c-'0', c=getchar();
	x*=f;
}

typedef double LD;
const int N=1e5+10;
int n, m;LD x[N], y[N];
struct node{LD mul, sx, vx, vy;};
struct trnode
{
	int l, r;
	LD tagx, tagy, cov, mul, vx, vy, sx;
	trnode() {tagx=tagy=cov=mul=vx=vy=sx=0;}
}tr[N<<3];

LD f(int x) {return x*(x+1)*(2*x+1)/6;}
LD get(int l, int r) {return f(r)-f(l-1);}

node operator +(const node &n1, const node &n2) 
{
	node res;
	res.mul=n1.mul+n2.mul;
	res.sx=n1.sx+n2.sx; 
	res.vx=n1.vx+n2.vx; 
	res.vy=n1.vy+n2.vy; 
	return res;
}

void add(int p, LD S, LD T)
{
	int l=tr[p].l, r=tr[p].r;
	tr[p].mul+=S*tr[p].vy+T*tr[p].vx+(r-l+1)*1.0*S*T;
	tr[p].sx+=2.0*S*tr[p].vx+(r-l+1)*1.0*S*S;
	tr[p].vx+=(r-l+1)*1.0*S;tr[p].vy+=(r-l+1)*1.0*T;
	tr[p].tagx+=S, tr[p].tagy+=T;
}

void cover(int p)
{
	int l=tr[p].l, r=tr[p].r;
	tr[p].mul=tr[p].sx=get(l, r);
	tr[p].vx=tr[p].vy=(l+r)*(r-l+1)/2.0;
	tr[p].tagx=tr[p].tagy=0;tr[p].cov=1;
}

void pushup(int p)
{
	tr[p].mul=tr[p<<1].mul+tr[p<<1|1].mul;
	tr[p].vx=tr[p<<1].vx+tr[p<<1|1].vx;
	tr[p].vy=tr[p<<1].vy+tr[p<<1|1].vy;
	tr[p].sx=tr[p<<1].sx+tr[p<<1|1].sx;
}

void build(int p, int l, int r)
{
	tr[p].l=l, tr[p].r=r;
	if (l==r) 
	{
		tr[p].vx=x[l], tr[p].vy=y[l];
		tr[p].sx=x[l]*x[l], tr[p].mul=x[l]*y[l];
	}
	else
	{
		int mid=(l+r)>>1;
		build(p<<1, l, mid), build(p<<1|1, mid+1, r);
		pushup(p);
	}
}
 
void pushdown(int p)
{
	if (tr[p].cov)
	{
		cover(p<<1), cover(p<<1|1);
		tr[p].cov=0;
	}
	if (tr[p].tagx||tr[p].tagy)
	{
		LD tagx=tr[p].tagx, tagy=tr[p].tagy;
		add(p<<1, tagx, tagy), add(p<<1|1, tagx, tagy);
		tr[p].tagx=tr[p].tagy=0;
	}
}
 
void change1(int p, int l, int r, LD S, LD T)
{
	if (l<=tr[p].l&&tr[p].r<=r)
	{
		add(p, S, T);
		return ;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if (l<=mid) change1(p<<1, l, r, S, T);
	if (r>mid) change1(p<<1|1, l, r, S, T);
	pushup(p);
}

void change2(int p, int l, int r, LD S, LD T)
{
	if (l<=tr[p].l&&tr[p].r<=r)
	{
		cover(p), add(p, S, T);
		return ;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;
	if (l<=mid) change2(p<<1, l, r, S, T);
	if (r>mid) change2(p<<1|1, l, r, S, T);
	pushup(p);
}

node query(int p, int l, int r)
{
	if (l<=tr[p].l&&tr[p].r<=r) return {tr[p].mul, tr[p].sx, tr[p].vx, tr[p].vy};
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)>>1;node res={0, 0, 0, 0};
	if (l<=mid) res=res+query(p<<1, l, r);
	if (r>mid) res=res+query(p<<1|1, l, r);
	pushup(p);return res;
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1;i<=n;i++) scanf("%lf", &x[i]);
	for (int i=1;i<=n;i++) scanf("%lf", &y[i]);
	build(1, 1, n);
	for (int i=1;i<=m;i++)
	{
		int op, l, r;LD S, T;
		scanf("%d%d%d", &op, &l, &r);
		if (op==1)
		{
			node res=query(1, l, r);
			LD avgx=res.vx/((r-l+1)*1.0), avgy=res.vy/((r-l+1)*1.0);
			LD ans1=res.mul-avgx*res.vy-avgy*res.vx+(r-l+1)*1.0*avgx*avgy;
			LD ans2=res.sx-2.0*avgx*res.vx+(r-l+1)*1.0*avgx*avgx;
			printf("%.10lf\n", ans1/ans2);
		}
		else if (op==2) scanf("%lf%lf", &S, &T), change1(1, l, r, S, T);
		else scanf("%lf%lf", &S, &T), change2(1, l, r, S, T);
	}
	return 0;
}

感觉像是区间覆盖的错,但是找不出来qaq

2024/4/13 11:16
加载中...