慢慢变小的序列
https://ac.nowcoder.com/acm/contest/895/G
题目描述
给一个长度为 n 的序列A1,A2,…,AnA1,A2,…,An,你需要支持以下两种操作: 操作 1:L R X Y,对所有L≤i≤RL≤i≤R赋值 Ai=min(Ai,(i−L)×Y+X)Ai=min(Ai,(i−L)×Y+X),其中 L, R, X, Y 均为整数,且有 1≤L≤R≤n,|X|≤100000,|Y|≤51≤L≤R≤n,|X|≤100000,|Y|≤5操作 2:x,询问AxAx的值,这里 x 是整数,且有1≤x≤n1≤x≤n。
输入描述:
第一行包含两个整数n,q(1≤n,q≤100000)n,q(1≤n,q≤100000),分别表示序列长度为以及操作次数,
第二行是 n 个整数 Ai(−100000≤Ai≤100000)Ai(−100000≤Ai≤100000)接下来 q 行,每行第一个数字表示操作类型,接下来输入对应题面描述。
输出描述:
对于每个操作 2,输出对应查询的结果。示例1
输入
5 5 0 0 0 0 0 2 1 1 1 5 2 -1 2 5 1 1 2 -1 2 2 1
输出
0 -2 -1
我们可以把(i-L)*Y+X 看成 i*Y-L*Y+X,这样的话-L*Y+X就是一个常数。因为|Y|<=5,所以我们可以开11个线段树分别存Y的情况,这样查询的时候就很方便了
写push_down函数的时候要注意下,要保留最小值,不然可能会出现如下情况:
区间5-10更新最小值为5,然后区间1-10更新最小值为10,这样当区间1-10下推的时候就把区间5-10给覆盖了
1 #include<bits/stdc++.h> 2 #define lson l,mid,rt<<1 3 #define rson mid+1,r,rt<<1|1 4 typedef long long ll; 5 #define maxn 100005 6 using namespace std; 7 8 int Tree[15][maxn<<2]; 9 int Lazy[15][maxn<<2]; 10 int a[maxn]; 11 12 int n,q; 13 14 void push_down(int tree[],int lazy[],int rt){ 15 if(lazy[rt]!=0x3f3f3f3f){ 16 lazy[rt<<1]=min(lazy[rt<<1],lazy[rt]); 17 lazy[rt<<1|1]=min(lazy[rt<<1|1],lazy[rt]); 18 tree[rt<<1]=min(tree[rt<<1],lazy[rt]); 19 tree[rt<<1|1]=min(tree[rt<<1|1],lazy[rt]); 20 lazy[rt]=0x3f3f3f3f; 21 } 22 } 23 24 void add(int tree[],int lazy[],int L,int R,int v,int l,int r,int rt){ 25 if(L<=l&&R>=r){ 26 tree[rt]=min(tree[rt],v); 27 lazy[rt]=tree[rt]; 28 return; 29 } 30 push_down(tree,lazy,rt); 31 int mid=l+r>>1; 32 if(L<=mid) add(tree,lazy,L,R,v,lson); 33 if(R>mid) add(tree,lazy,L,R,v,rson); 34 } 35 36 int query(int tree[],int lazy[],int L,int l,int r,int rt){ 37 if(l==r){ 38 return tree[rt]; 39 } 40 push_down(tree,lazy,rt); 41 int mid=l+r>>1; 42 if(L<=mid) return query(tree,lazy,L,lson); 43 return query(tree,lazy,L,rson); 44 } 45 46 int main(){ 47 std::ios::sync_with_stdio(false); 48 cin>>n>>q; 49 for(int i=1;i<=n;i++){ 50 cin>>a[i]; 51 } 52 for(int i=0;i<15;i++){ 53 for(int j=0;j<(maxn<<2);j++){ 54 Tree[i][j]=0x3f3f3f3f; 55 Lazy[i][j]=0x3f3f3f3f; 56 } 57 } 58 int pos,L,R,x,y; 59 while(q--){ 60 cin>>pos; 61 if(pos==1){ 62 cin>>L>>R>>x>>y; 63 add(Tree[y+5],Lazy[y+5],L,R,-L*y+x,1,n,1); 64 } 65 else{ 66 cin>>x; 67 int ans=a[x]; 68 for(int i=0;i<=10;i++){ 69 ans=min(ans,(i-5)*x+query(Tree[i],Lazy[i],x,1,n,1)); 70 } 71 cout<<ans<<endl; 72 } 73 } 74 }View Code