100+100+100+100+60=460
坐标变换 (其一)题目大意给定\(n\)个操作，每个操作将坐标 \((x,y)\)变为 \((x + dx, y + dy)\)。
给定 \(m\)个点，问这 \(m\)个点经过这 \(n\)次操作变换后的坐标。
解题思路注意到操作是可合并的，因此可以先将这\(n\)个操作合并成一个操作，然后对每个点都经过这个操作变换即可，时间复杂度为 \(O(n + m)\)。
本题 \(n,m\)只有 \(100\)，也可以 \(O(nm)\)依次对每个点进行操作变换。
神奇的代码#include using namespace std;int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n, m;cin >> n >> m;int dx = 0, dy = 0;for(int i = 0; i < n; ++ i){int x, y;cin >> x >> y;dx += x;dy += y;}for(int i = 0; i < m; ++ i){int x, y;cin >> x >> y;cout m;vector op(n);for(auto &i : op){int opp;double k;cin >> opp >> k;if (opp == 1)i[0] = k;else{i[0] = 1;i[1] = k;}}for(int i = 1; i < n; ++ i){op[i][0] *= op[i - 1][0];op[i][1] += op[i - 1][1];}for(int i = 0; i < m; ++ i){int l, r, x, y;cin >> l >> r >> x >> y;-- l, -- r;double R = sqrt(1ll * x * x + 1ll * y * y), theta = 0;if (x == 0){if (y > 0)theta = pi / 2;else theta = -pi / 2;}else{theta = atan2(y, x);}R *= op[r][0];theta += op[r][1];if (l){R /= op[l - 1][0];theta -= op[l - 1][1];}cout = mo) dsum -= mo;}else if (info[u] == '-'){sum = lans[0] - rans[0];dsum = lans[1] - rans[1];if (sum >= mo) sum -= mo;if (dsum >= mo) dsum -= mo;}else{sum = 1ll * lans[0] * rans[0] % mo;dsum = (1ll * lans[0] * rans[1] % mo + 1ll * lans[1] * rans[0] % mo);if (dsum >= mo) dsum -= mo;}if (sum < 0)sum += mo;if (dsum < 0)dsum += mo;return array{sum, dsum};}};for(int i = 0; i < m; ++ i){int x;cin >> x;-- x;for(auto &i : a)cin >> i;cout n >> m >> p >> q;vector pos(p);unordered_map row, col, ld, rd;auto insert = [&](int id){int x = pos[id][0], y = pos[id][1];row[x].insert({y, id});col[y].insert({x, id});ld[x + y].insert({y, id});rd[x - y].insert({y, id});};auto remove = [&](int id){int x = pos[id][0], y = pos[id][1];row[x].erase({y, id});col[y].erase({x, id});ld[x + y].erase({y, id});rd[x - y].erase({y, id});};for(int i = 0; i < p; ++ i){cin >> pos[i][0] >> pos[i][1];insert(i);}for(int i = 0; i < q; ++ i){int u, v, t;cin >> u >> v >> t;vector candidate;auto search = [&](const set& people, int d, int dirr, int dirl){auto pos = people.lower_bound(array{d, p});if (pos != people.end()){candidate.push_back({(*pos)[0] - d, (*pos)[1], dirr});}if (pos != people.begin()){pos = prev(pos);if ((*pos)[0] == d && pos != people.begin())pos = prev(pos);if ((*pos)[0] != d){candidate.push_back({d - (*pos)[0], (*pos)[1], dirl});}}};search(row[u], v, 2, 6);search(col[v], u, 0, 4);search(ld[u + v], v, 3, 7);search(rd[u - v], v, 1, 5);if (candidate.empty())continue;sort(candidate.begin(), candidate.end(), [&](const array& a, const array& b){return a[0] < b[0];});int mindis = min({u - 1, n - u, v - 1, m - v});if (candidate[0][0] > mindis)continue;mindis = candidate[0][0];for(int i = 0; i < candidate.size(); ++ i){if (candidate[i][0] != mindis)break;int dis = candidate[i][0];int id = candidate[i][1];remove(id);int dir = (candidate[i][2] + t) % 8;pos[id][0] = u + dis * dx[dir];pos[id][1] = v + dis * dy[dir];insert(id);}}LL ans = 0;for(int i = 0; i < p; ++ i){ans ^= (1ll * (i + 1) * pos[i][0] + pos[i][1]);}cout = 0 ? val : 0);sum[root] = val;return;}int mid = (l + r) >> 1;if (pos > n >> m;vector G(n);vector edge;for(int i = 1; i < n; ++ i){int u, v, w, b;cin >> u >> v >> w >> b;-- u, -- v;G[u].push_back(edge.size());G[v].push_back(edge.size());edge.push_back({u, v, w, b});}vector maxd(n, 0);LL ans = 0;function dfs = [&](int u, int fa){for(auto &i : G[u]){int v = edge[i][0] ^ edge[i][1] ^ u;if (v == fa)continue;int d = edge[i][3] - edge[i][2];dfs(v, u);ans = max(ans, maxd[u] + maxd[v] + d);maxd[u] = max(maxd[u], maxd[v] + d);}};dfs(1, 1);cout > y;-- x;edge[x][2] = y;ans = 0;fill(maxd.begin(), maxd.end(), 0);dfs(1, 1);cout > y;-- x;edge[x][2] = y;seg.update(1, 1, n - 1, x + 1, edge[x][3] - edge[x][2]);cout > x >> y;-- x;edge[x][2] = y;int d = edge[x][3] - edge[x][2];ans = 0;int cur = (deep[edge[x][0]] < deep[edge[x][1]] ? edge[x][0] : edge[x][1]);int son = cur ^ edge[x][0] ^ edge[x][1];while(cur != -1){maxs[cur].erase({maxs_id[cur][son], son});maxs_id[cur][son] = (*maxs[son].rbegin())[0] + d;maxs[cur].insert({maxs_id[cur][son], son});anss[cur].erase({anss_id[cur][son], son});anss_id[cur][son] = (*anss[son].rbegin())[0];anss[cur].insert({anss_id[cur][son], son});anss[cur].erase({anss_id[cur][-2], -2});if (maxs[cur].size() > 1){auto c1 = maxs[cur].rbegin();auto c2 = next(c1);anss_id[cur][-2] = (*c1)[0] + (*c2)[0];anss[cur].insert({anss_id[cur][-2], -2});}son = cur;cur = f[cur];}ans = max(0ll, (*anss[0].rbegin())[0]);cout