分块囚调
查看原帖
分块囚调
542265
Russia_Pengpengpeng楼主2024/11/28 09:12

暴力打块全T???

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> Pair;
const int MAXN = 2e5 + 10;
ll N, M, a[MAXN], X, Y, K, OP, t, L[1000], R[1000], g[MAXN], add[1000], p, q;
double si[1000], co[1000], Sin, Cos, ans; 
void solute( int x, int y ) {
	p = g[x]; q = g[y];
	if( p == q ) {
		for( int i = x; i <= y; i ++ ) {
			si[p] -= sin( a[i] );
			co[p] -= cos( a[i] );
			Sin = sin( a[i] + K );
			Cos = cos( a[i] + K );
			a[i] += K;
			si[p] += Sin;
			co[p] += Cos;
		}
		return;
	} else {
		for( int i = p + 1; i <= q - 1; i ++ ) { 
			add[i] += K;
			Sin = si[i] * cos( K ) + co[i] * sin( K );
			Cos = co[i] * cos( K ) - si[i] * sin( K );
			si[i] = Sin;
			co[i] = Cos;
		}
		for( int i = x; i <= R[p]; i ++ ) {
			si[p] -= sin( a[i] );
			co[p] -= cos( a[i] );
			Sin = sin( a[i] + K );
			Cos = cos( a[i] + K );
			a[i] += K;
			si[p] += Sin;
			co[p] += Cos;
		}
		for( int i = L[q]; i <= y; i ++ ) {
			si[q] -= sin( a[i] );
			co[q] -= cos( a[i] );
			Sin = sin( a[i] + K );
			Cos = cos( a[i] + K );
			a[i] += K;
			si[q] += Sin;
			co[q] += Cos;
		}
		return;
	}
}
double ask( int x, int y ) {
	p = g[x]; q = g[y];
	ans = 0;
	if( p == q ) {
		for( int i = x; i <= y; i ++ ) ans += sin( a[i] + add[p] );
	} else {
		for( int i = p + 1; i <= q - 1; i ++ ) ans += si[i];
		for( int i = x; i <= R[p]; i ++ ) ans += sin( a[i] + add[p] );
		for( int i = L[q]; i <= y; i ++ ) ans += sin( a[i] + add[q] );
	}
	return ans;
}
template<typename tpn>
tpn read(  ) {
	tpn w = 1, rd = 0; char ch = getchar(  );
	while( !isdigit( ch ) ) { if( ch == '-' ) w = -1; ch = getchar(  ); }
	while( isdigit( ch ) ) { rd = rd * 10 + ch - '0'; ch = getchar(  ); }
	return w * rd;
}
int main(  ) {
	N = read<ll>(  );
	for( int i = 1; i <= N; i ++ ) a[i] = read<ll>(  );
	t = sqrt( N );
	for( int i = 1; i <= t; i ++ ) {
		L[i] = ( i - 1 ) * t + 1;
		R[i] = i * t;
	}
	if( R[t] <= N ) { L[t + 1] = R[t] + 1; R[t + 1] = N; t ++; }
	for( int i = 1; i <= t; i ++ ) {
		for( int j = L[i]; j <= R[i]; j ++ ) g[j] = i, si[i] += sin( a[j] ), co[i] += cos( a[i] );
	}
	M = read<ll>(  );
	for( int i = 1; i <= M; i ++ ) {
		OP = read<ll>(  );
		if( OP == 1 ) {
			X = read<ll>(  ); Y = read<ll>(  ); K = read<ll>(  );
			solute( X, Y );
		} else {
			X = read<ll>(  ); Y = read<ll>(  );
			printf( "%.1f\n", ask( X, Y ) );
		}
	} 
	return 0;
}
2024/11/28 09:12
加载中...