线段树WA70pt求助s
查看原帖
线段树WA70pt求助s
302394
dingshengyang楼主2022/2/2 17:21

RT

#include <bits/stdc++.h>
#define R register
#define inl inline
#define fastios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define Debug(file) freopen(file".in","r",stdin);freopen(file".out","w",stdout);
using namespace std;
typedef unsigned long long LL;
LL f(LL x) {
	return x * x;
}
typedef pair<LL, LL> PII;

LL gcd(LL a, LL b) {
	return (!b) ? (a) : (gcd(b, a % b));
}

struct fra {
	LL x, y;
	void judge() {
		LL gg = gcd(x, y);
		x /= gg;
		y /= gg;
	}
	fra operator =(pair<LL, LL> p) {
		x = p.first;
		y = p.second;
		judge();
		return *this;
	}
	fra operator +(fra p) {
		LL ny = y * p.y;
		LL nx = (p.y * x) + (y * p.x);
		fra tmp = {nx, ny};
		tmp.judge();
		return tmp;
	}
	fra operator -(fra p) {
		LL ny = y * p.y;
		LL nx = (p.y * x) - (y * p.x);
		fra tmp = {nx, ny};
		tmp.judge();
		return tmp;
	}
	fra operator *(fra p) {
		LL nx = x * p.x;
		LL ny = y * p.y;
		fra tmp = {nx, ny};
		tmp.judge();
		return tmp;
	}
	fra operator /(fra p) {
		fra tmp = {p.y, p.x};
		return (*this) * tmp;
	}
	fra rec() {
		return {y, x};
	}
};

istream &operator >>(istream &i, fra &f) {
	scanf("%llu/%llu", &f.x, &f.y);
	return i;
}

ostream &operator <<(ostream &o, fra f) {
	printf("%llu/%llu", f.x, f.y);
	return o;
}
/*----------FRACTION-----------PART------------*/
const int N = 1e5 + 5;

struct node {
	int l, r;
	LL ps, sum;
	LL add;
} tr[N * 4];
LL n, m, a[N];

void pushup(int u) {
	tr[u].ps = tr[u << 1].ps + tr[u << 1 | 1].ps;
	tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void pushdown(int u) {
	node &l = tr[u << 1];
	node &r = tr[u << 1 | 1];
	node &now = tr[u];
	l.add += now.add;
	r.add += now.add;
	l.ps += (f(now.add) * (l.r - l.l + 1)) + (2 * l.sum * now.add);
	r.ps += (f(now.add) * (r.r - r.l + 1)) + (2 * r.sum * now.add);
	l.sum += (l.r - l.l + 1) * now.add;
	r.sum += (r.r - r.l + 1) * now.add;
	now.add = 0;
}

void build(int u, int l, int r) {
	if (l == r)
		tr[u] = {l, r, f(a[l]), a[l],0};
	else {
		int mid = l + r >> 1;
		tr[u] = {l, r, 0, 0, 0};
		build(u << 1, l, mid);
		build(u << 1|1, mid + 1, r);
		pushup(u);
	}
}

void modify(int u, int l, int r, LL v) {
	if (l <= tr[u].l && tr[u].r <= r) {
		tr[u].add += v;
		tr[u].ps += (f(v) * (tr[u].r - tr[u].l + 1)) + (2 * tr[u].sum * v);
		tr[u].sum += (tr[u].r - tr[u].l + 1) * v;
	} else {
		int mid = tr[u].l + tr[u].r >> 1;
		pushdown(u);
		if (l <= mid) {
			modify(u << 1, l, r, v);
		}
		if (r > mid) {
			modify(u << 1 | 1, l, r, v);
		}
		pushup(u);
	}
}

LL query_sum(int u, int l, int r) {
	if (l <= tr[u].l && tr[u].r <= r) {
		return tr[u].sum;
	} else {
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		LL ans = 0;
		if (l <= mid)
			ans = query_sum(u << 1, l, r);
		if (r > mid)
			ans += query_sum(u << 1 | 1, l, r);
		return ans;
	}
}

LL query_fs(int u, int l, int r) {
	if (l <= tr[u].l && tr[u].r <= r) {
		return tr[u].ps;
	} else {
		pushdown(u);
		int mid = tr[u].l + tr[u].r >> 1;
		LL ans = 0;
		if (l <= mid)
			ans += query_fs(u << 1, l, r);
		if (r > mid)
			ans += query_fs(u << 1 | 1, l, r);
		return ans;
	}
}

/*----------SEGMENT----TREE----PART------------*/
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++)
		scanf("%llu", &a[i]);
	build(1,1,n);
	for (int i = 0; i < m; i ++) {
		int op, l, r;LL d;
		scanf("%d%d%d", &op, &l, &r);
		if (op == 1) {
			scanf("%llu", &d);
			modify(1, l, r, d);
		}
		if (op == 2) {
			fra tmp = {query_sum(1, l, r), (r - l + 1)};
			tmp.judge();
			cout << tmp << endl;
		}
		if (op == 3) {
			LL sum = query_sum(1,l,r);
			LL pfs = query_fs(1,l,r);
			fra av = {sum,r-l+1};
			fra ans = {pfs,1};
			ans = (av*av)*fra{(r-l+1),1}+ans;
			ans = ans - fra{2,1}*av*fra{sum,1};
			ans = ans/fra{r-l+1,1};
			cout << ans << endl;
		}
	}
	return 0;
}
2022/2/2 17:21
加载中...