过阳历全tle可爱线段树求条玄关
查看原帖
过阳历全tle可爱线段树求条玄关
762199
fulichang楼主2024/10/6 09:16
//from.luogu P6327 by.flic 24-10-6
//https://www.luogu.com.cn/problem/P6327

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, m;
int a[N], tag[N << 2];
double sina[N << 2], cosa[N << 2], si[200], cs[200];

void pushup (int rt) {
	sina[rt] = sina[rt << 1] + sina[rt << 1 | 1];
	cosa[rt] = cosa[rt << 1] + cosa[rt << 1 | 1];
}

void build (int l, int r, int rt) {
	if (l == r) {
		sina[rt] = si[a[l] % 180];
		cosa[rt] = cs[a[l] % 180];
		return;
	}
	int mid = l + r >> 1;
	build(l, mid, rt << 1);
	build(mid + 1, r, rt << 1 | 1);
	pushup(rt);
}

void pushdown (int l, int r, int rt) {
	if (tag[rt]) {
		int mid = l + r >> 1;
		double ts = sina[rt << 1], tc = cosa[rt << 1], ct = cs[tag[rt] % 180], st = si[tag[rt] % 180];
		sina[rt << 1] = ts * (mid - l + 1) * ct + tc * (mid - l + 1) * st;
		cosa[rt << 1] = tc * (mid - l + 1) * ct - ts * (mid - l + 1) * st;
		tag[rt << 1] += tag[rt];
		ts = sina[rt << 1 | 1], tc = cosa[rt << 1 | 1];
		sina[rt << 1 | 1] = ts * (r - mid) * ct + tc * (r - mid) * st;
		cosa[rt << 1 | 1] = tc * (r - mid) * ct - ts * (r - mid) * st;
		tag[rt << 1 | 1] += tag[rt];
		tag[rt] = 0;
	}
}

void update (int l, int r, int rt, int L, int R, double cc, double sc, int c) {
	if (L <= l && r <= R) {
		tag[rt] += c;
		double ts = sina[rt], tc = cosa[rt];
		sina[rt] = ts * (r - l + 1) * cc + tc * (r - l + 1) * sc;
		cosa[rt] = tc * (r - l + 1) * cc - ts * (r - l + 1) * sc;
		return;
	}
	pushdown(l, r, rt);
	int mid = l + r >> 1;
	if (L <= mid)
		update(l, mid, rt << 1, L, R, cc, sc, c);
	if (R > mid)
		update(mid + 1, r, rt << 1 | 1, L, R, cc, sc, c);
	pushup(rt);
}

double query (int l, int r, int rt, int L, int R) {
	if (L <= l && r <= R)
		return sina[rt];
	pushdown(l, r, rt);
	int mid = l + r >> 1;
	double res = 0;
	if (L <= mid)
		res += query(l, mid, rt << 1, L, R);
	if (R > mid)
		res += query(mid + 1, r, rt << 1 | 1, L, R);
	return res;
}

int main (void) {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 0; i < 180; i++)
		si[i] = sin(i), cs[i] = cos(i);
	build(1, n, 1);
	cin >> m;
	cout << fixed << setprecision(1);
	while (m--) {
		int opt, x, y, z;
		cin >> opt >> x >> y;
		if (opt == 1)
			cin >> z, update(1, n, 1, x, y, cs[z % 180], si[z % 180], z);
		else
			cout << query(1, n, 1, x, y) << '\n';
	}
	return 0;
}
2024/10/6 09:16
加载中...