Untitled
unknown
plain_text
a year ago
3.5 kB
2
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define MAX 100000 #define MAX_STOCK_LEN 10 struct stock { int id; int price; string name; }stocks[MAX]; struct node { int id; int diff; }; int lazy[4 * MAX]; node seg[4 * MAX]; unordered_map<string, int> umap; node check(node a, node b) { if (a.diff != b.diff) return (a.diff > b.diff) ? a : b; return (a.id < b.id) ? a : b; } int n; void makeSegment(int index, int left, int right) { if (left == right) { seg[index].id = stocks[left].id; return; } if (left > right) return; int mid = (left + right) / 2; makeSegment(index * 2 + 1, left, mid); makeSegment(index * 2 + 2, mid + 1, right); seg[index] = check(seg[index * 2 + 1] , seg[index * 2 + 2]); } void rangeUpdateByLazy(int index, int left, int right, int x, int y, int val) { if (lazy[index] != 0) { seg[index].diff += lazy[index]; if (left != right) { lazy[index * 2 + 1] += lazy[index]; lazy[index * 2 + 2] += lazy[index]; } lazy[index] = 0; } if (left >= x && right <= y) { seg[index].diff += val; if (left != right) { lazy[index * 2 + 1] += val; lazy[index * 2 + 2] += val; } return; } if (left > y || right < x || left > right) return; int mid = (left + right) / 2; rangeUpdateByLazy(index * 2 + 1, left, mid, x, y, val); rangeUpdateByLazy(index * 2 + 2, mid + 1, right, x, y, val); seg[index] = check(seg[index * 2 + 1], seg[index * 2 + 2]); } node getRangeQueryLazy(int index, int left, int right, int x, int y) { if (lazy[index] != 0) { seg[index].diff += lazy[index]; if (left != right) { lazy[index * 2 + 1] += lazy[index]; lazy[index * 2 + 2] += lazy[index]; } lazy[index] = 0; } if (left >= x && right <= y) return seg[index]; if (left > y || right < x || left > right) return { -1,INT_MIN };; int mid = (left + right) / 2; return check(getRangeQueryLazy(index * 2 + 1, left, mid, x, y) , getRangeQueryLazy(index * 2 + 2, mid + 1, right, x, y)); } bool compare(stock& a, stock& b) { return a.name < b.name; } void init(int N, char mStocks[][MAX_STOCK_LEN + 1], int mPrices[]) { n = N; umap.clear(); for (int i = 0; i < 4 * MAX; i++) { seg[i].diff = 0; seg[i].id = -1; lazy[i] = 0; } for (int i = 0; i < n; i++) { stocks[i].id = i; stocks[i].name = mStocks[i]; stocks[i].price = mPrices[i]; } sort(stocks, stocks + n, compare); for (int i = 0; i < n; i++) { umap[stocks[i].name] = i; } makeSegment(0, 0, n - 1); } void changePrices(char mFromStock[], char mToStock[], int mPriceDiff) { int l = umap[mFromStock]; int r = umap[mToStock]; rangeUpdateByLazy(0, 0, n - 1, l, r, mPriceDiff); } int getPrice(char mStock[]) { int it = umap[mStock]; node n1 = getRangeQueryLazy(0, 0, n - 1, it, it); return stocks[it].price + n1.diff; } int getMostIncreasedStock(char mFromStock[], char mToStock[]) { int l = umap[mFromStock]; int r = umap[mToStock]; node res = getRangeQueryLazy(0, 0, n - 1, l, r); return res.id; }