传送门:https://ac.nowcoder.com/acm/contest/895/G
题意:
题解:
如果我们区间更新最小值的话,这个min值将变的十分难以维护,所以我们考虑将公式拆分出来
我们发现,每次更新时,实际上我们查询到的答案只与原先的ai以及修改后的min [y] [pos]有关,所以我们维护一个关于y的线段树,考虑到y的数据范围只有-5~5,我们开十一颗线段树,维护每一个y值时的当前区间的最小值即可,Min[y][rt]代表Y值为y时,当前区间的最小值是多少;
由于yi可以在后面枚举y的时候消掉,所以我们每次就只需要区间维护min(Min[y][rt],X-L\y)这个值,后面查询的时候加上单点位置pos*y即可
代码:
/** * ┏┓ ┏┓ * ┏┛┗━━━━━━━┛┗━━━┓ * ┃ ┃ * ┃ ━ ┃ * ┃ > < ┃ * ┃ ┃ * ┃... ⌒ ... ┃ * ┃ ┃ * ┗━┓ ┏━┛ * ┃ ┃ Code is far away from bug with the animal protecting * ┃ ┃ 神兽保佑,代码无bug * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┃ * ┃ ┗━━━┓ * ┃ ┣┓ * ┃ ┏┛ * ┗┓┓┏━┳┓┏┛ * ┃┫┫ ┃┫┫ * ┗┻┛ ┗┻┛ */ // warm heart, wagging tail,and a smile just for you! // // _ooOoo_ // o8888888o // 88" . "88 // (| -_- |) // O\ = /O // ____/`---'\____ // .' \| |// `. // / \||| : |||// \ // / _||||| -:- |||||- \ // | | \\ - /// | | // | \_| ''\---/'' | | // \ .-\__ `-` ___/-. / // ___`. .' /--.--\ `. . __ // ."" '< `.___\_<|>_/___.' >'"". // | | : `- \`.;`\ _ /`;.`/ - ` : | | // \ \ `-. \_ __\ /__ _/ .-` / / // ======`-.____`-.___\_____/___.-`____.-'====== // `=---=' // ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ // 佛祖保佑 永无BUG #include <set> #include <map> #include <deque> #include <queue> #include <stack> #include <cmath> #include <ctime> #include <bitset> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; typedef pair<LL, LL> pLL; typedef pair<LL, int> pLi; typedef pair<int, LL> pil;; typedef pair<int, int> pii; typedef unsigned long long uLL; #define ls rt<<1 #define rs rt<<1|1 #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define bug printf("*********\n") #define FIN freopen("input.txt","r",stdin); #define FON freopen("output.txt","w+",stdout); #define IO ios::sync_with_stdio(false),cin.tie(0) #define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]\n" #define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]\n" #define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]\n" const double eps = 1e-8; const int mod = 1e9 + 7; const int maxn = 1e5 + 5; const int INF = 0x3f3f3f3f; const LL INFLL = 0x3f3f3f3f3f3f3f3f; void build(int num[], int l, int r, int rt) { num[rt] = INF; if(l == r) return; int mid = (l + r) >> 1; build(num,lson); build(num,rson); } void update(int L, int R, int val, int num[], int l, int r, int rt) { if(L <= l && r <= R) { num[rt] = min(num[rt], val); return; } int mid = (l + r) >> 1; if(L <= mid) update(L, R, val, num, lson); if(R > mid) update(L, R, val, num, rson); } int query(int pos, int num[], int l, int r, int rt) { if(l == r) { return num[rt]; } int mid = (l + r) >> 1; if(pos <= mid) return min(num[rt], query(pos, num, lson)); else return min(num[rt], query(pos, num, rson)); } int num[12][maxn << 2]; int a[maxn]; int main() { #ifndef ONLINE_JUDGE FIN #endif int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for(int i = 0; i <= 10; i++) { build(num[i], 1, n, 1); } while(m--) { int op; scanf("%d", &op); if(op == 1) { int L, R, X, Y; scanf("%d%d%d%d", &L, &R, &X, &Y); int val = (-L * Y + X); update(L, R, val, num[Y + 5], 1, n, 1); } else { int pos; scanf("%d", &pos); int ans = a[pos]; for(int y = 0; y <= 10; y++) { ans = min(ans, (y - 5) * pos + query(pos, num[y], 1, n, 1)); } printf("%d\n", ans); } } return 0; }