求助线段树经典题,过样例,全WA
查看原帖
求助线段树经典题,过样例,全WA
232838
huangkx楼主2023/1/2 18:49

RT,求调,感觉码风还是看得下去的。做法是根据欧拉公式维护复数。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
int n, m;
complex < long double > a[N + 5];
struct Segment_Tree{
	complex < long double > sum[4 * N + 5], mul[4 * N + 5];
	void Push_Up(int u)
	{
		sum[u] = sum[u << 1] + sum[u << 1 | 1];
	}
	void Push_Down(int u)
	{
		if(mul[u].real() == 0 && mul[u].imag() == 0) return;
		sum[u << 1] *= mul[u];
		sum[u << 1 | 1] *= mul[u];
		mul[u << 1] *= mul[u];
		mul[u << 1 | 1] *= mul[u];
		mul[u].real(0), mul[u].imag(0);
	}
	void Build(int u, int l, int r, complex < long double > arr[])
	{
		if(l > r) return;
		if(l == r){
			sum[u] = arr[l];
			mul[u].real(0), mul[u].imag(0);
			return;
		}
		int mid = (l + r) >> 1;
		Build(u << 1, l, mid, arr);
		Build(u << 1 | 1, mid + 1, r, arr);
		Push_Up(u);
	}
	void Change(int u, int l, int r, int L, int R, complex < long double > V)
	{
		if(l > r || l > R || r < L) return;
		if(l >= L && r <= R){
			sum[u] *= V;
			if(mul[u].real() == 0 && mul[u].imag() == 0) mul[u] = V;
			else mul[u] *= V;
			return;
		}
		int mid = (l + r) >> 1;
		Push_Down(u);
		Change(u << 1, l, mid, L, R, V);
		Change(u << 1 | 1, mid + 1, r, L, R, V);
		Push_Up(u);
	}
	complex < long double > Query(int u, int l, int r, int L, int R)
	{
		complex < long double > tmp; tmp.real(0), tmp.imag(0);
		if(l > r || l > R || r < L) return tmp;
		if(l >= L && r <= R) return sum[u];
		int mid = (l + r) >> 1;
		Push_Down(u);
		tmp = Query(u << 1, l, mid, L, R) + Query(u << 1 | 1, mid + 1, r, L, R);
		Push_Up(u);
		return tmp;
	}
};
Segment_Tree tr;
signed main()
{
	scanf("%d", & n);
	for(int i = 1; i <= n; i ++){
		int v; scanf("%d", & v);
		complex < long double > vv; vv.real(0), vv.imag(v);
		a[i] = exp(vv);
	}
	tr.Build(1, 1, n, a);
	scanf("%d", & m);
	while(m --){
		int op; scanf("%d", & op);
		if(op == 1){
			int l, r, v; scanf("%d%d%d", & l, & r, & v);
			complex < long double > vv; vv.real(0), vv.imag(v);
			tr.Change(1, 1, n, l, r, exp(vv));
		}
		if(op == 2){
			int l, r; scanf("%d%d", & l, & r);
			printf("%.1Lf\n", tr.Query(1, 1, n, l, r).imag());
		}
	}
	return 0;
}
2023/1/2 18:49
加载中...