wustoj 1260 RMQ with Shifts
线段树单点更新,注意cin会超时,记得每次update后还要更新相应数组a的值。#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; #define MAXN 100010 struct node { int l,r,mid; int sum; }tree[MAXN*4]; int ans; int top; int a[MAXN]; int num[MAXN]; void build(int l,int r,int id) { tree[id].l=l; tree[id].r=r; tree[id].mid=(l+r)>>1; if(l==r) { scanf("%d",&tree[id].sum); a[top++]=tree[id].sum; return; } build(l,tree[id].mid,id<<1); build(tree[id].mid+1,r,id<<1|1); tree[id].sum=min(tree[id<<1].sum,tree[id<<1|1].sum); } void query(int l,int r,int id) { if(tree[id].l==l&&tree[id].r==r) { ans=min(ans,tree[id].sum); return; } if(r<=tree[id].mid) query(l,r,id<<1); else if(l>tree[id].mid) query(l,r,id<<1|1); else { query(l,tree[id].mid,id<<1); query(tree[id].mid+1,r,id<<1|1); } } void up(int id,int num,int val) { if(tree[id].l==num&&tree[id].r==num) { tree[id].sum=val; a[num]=val; return; } if(num<=tree[id].mid) up(id<<1,num,val); else up(id<<1|1,num,val); tree[id].sum=min(tree[id<<1].sum,tree[id<<1|1].sum); } int main() { char str[100]; int n,m; while(scanf("%d%d",&n,&m)!=EOF) { top=1; build(1,n,1); while(m--) { int len=0; scanf("%s",str); int s=0; for(int i=6;str[i];i++) { if(str[i]==','||str[i]==')') { num[len++]=s; s=0; } else { s=s*10+str[i]-'0'; } } if(str[0]=='q') { ans=0x7fffffff; int l=num[0]; int r=num[1]; query(l,r,1); printf("%d\n",ans); } else if(str[0]=='s') { int tmp=a[num[0]]; for(int i=0;i<len;i++) { if(i==len-1) up(1,num[i],tmp); else up(1,num[i],a[num[i+1]]); } } } } return 0; }
补充:软件开发 , C++ ,