题目:
代码:
#pragma GCC optimize(3)
#pragma GCC target("avx")
// #pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
// #pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
// #pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
// #pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
// #pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
// #define int long long
// #define cerr ((ostream) 0)
#define endl '\n'
#define debug(x) cerr << #x << " = " << x << endl
#define rep(i, a, b) for (register int i = (a); i <= (b); i++)
#define per(i, a, b) for (register int i = (a); i >= (b); i--)
#define gn(u, v) for (int v : G.G[u])
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define pii pair<int, int>
#define vi vector<int>
#define vpii vector<pii>
#define vvi vector<vi>
#define no cout << "NO" << endl
#define yes cout << "YES" << endl
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define tomin(x, y) ((x) = min((x), (y)))
#define tomax(x, y) ((x) = max((x), (y)))
#define ck(mask, i) (((mask) >> (i)) & 1)
#define pq priority_queue
#define FLG (cerr << "Alive!" << endl);
struct Vector {
double x, y;
Vector() {}
Vector(double _x, double _y) {
x = _x;
y = _y;
}
friend bool operator < (const Vector &x, const Vector &y) {
if (x.x == y.x) return x.y < y.y;
return x.x < y.x;
}
friend Vector operator + (const Vector &x, const Vector &y) {
return Vector(x.x + y.x, x.y + y.y);
}
friend Vector operator - (const Vector &x, const Vector &y) {
return Vector(x.x - y.x, x.y - y.y);
}
friend double operator * (const Vector &x, const Vector &y) {
return x.x * y.x + x.y * y.y;
}
friend double operator / (const Vector &x, const Vector &y) {
return x.x * y.y - x.y * y.x;
}
friend ostream& operator << (ostream& o, Vector v) {
return o << v.x << " " << v.y;
}
friend istream& operator >> (istream& i, Vector& v) {
return i >> v.x >> v.y;
}
double length() {
return sqrt(x * x + y * y);
}
Vector turn(double theta) {
double c = cos(theta);
double s = sin(theta);
// cerr << format("({}, {}) turns {} equals ({}, {});\n", x, y, theta, c * x - s * y, c * y + s * x) << endl;
return Vector(c * x - s * y, c * y + s * x);
}
};
const int MAXN = 1e6 + 5;
Vector a[MAXN];
struct SegTree {
struct Node {
int l, r;
Vector sum;
double lz;
} tr[MAXN * 4];
void pushup(int k) {
tr[k].sum = tr[k * 2].sum + tr[k * 2 + 1].sum;
}
void lazy(int k, double v) {
tr[k].lz += v;
tr[k].sum = tr[k].sum.turn(v);
}
void pushdown(int k) {
if (!tr[k].lz)
return;
lazy(k * 2, tr[k].lz);
lazy(k * 2 + 1, tr[k].lz);
tr[k].lz = 0;
}
void build(int k, int l, int r) {
tr[k] = { l, r, a[l], 0 };
if (l == r)
return;
int mid = (l + r) >> 1;
build(k * 2, l, mid);
build(k * 2 + 1, mid + 1, r);
pushup(k);
}
void update(int k, int l, int r, double v) {
if (tr[k].l >= l && tr[k].r <= r)
return lazy(k, v);
pushdown(k);
int mid = (tr[k].l + tr[k].r) >> 1;
int lc = k * 2, rc = k * 2 + 1;
if (r <= mid)
update(lc, l, r, v);
else if (l > mid)
update(rc, l, r, v);
else
update(lc, l, mid, v), update(rc, mid + 1, r, v);
pushup(k);
}
Vector query(int k, int l, int r) {
if (tr[k].l >= l && tr[k].r <= r)
return tr[k].sum;
pushdown(k);
int mid = (tr[k].l + tr[k].r) >> 1;
int lc = k * 2, rc = k * 2 + 1;
if (r <= mid)
return query(lc, l, r);
else if (l > mid)
return query(rc, l, r);
else
return query(lc, l, mid) + query(rc, mid + 1, r);
}
} seg;
int n, c;
int l[MAXN];
int angle[MAXN];
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
bool flag = false;
while (cin >> n >> c) {
if (flag) cout << endl;
flag = true;
rep(i, 1, n) {
int l;
cin >> l;
a[i] = { 0.0, (double)l };
angle[i] = 180;
}
seg.build(1, 1, n);
cout << fixed << setprecision(2);
// cerr << seg.query(1, 1, n) << endl;
rep(i, 1, c) {
int s;
double a;
cin >> s >> a;
s++;
a = a - angle[i];
angle[i] += a;
// cerr << format("turned angle {} rad", a / 180 * acos(-1)) << endl;
seg.update(1, s, n, a / 180 * acos(-1));
Vector ans = seg.query(1, 1, n);
cout << ans << endl;
}
}
return 0;
}
思路:线段树维护区间总向量,懒标记维护当前区间转了多少rad
