【题目描述】
一个长为n的序列，每个元素有一个a[i],b[i]，a[i]为0||1，每个点和他相邻的两个点分别有两条边，权值为cost1[i],cost2[i]，对于每个区间l,r，我们可以给每一个数一个c[i]值，c[i]=0||1，使得Σ(b[j]*(a[j]^c[j]))+cost1[j]*(c[j]^c[j+1])+cost2[j]*(c[j]^c[j+2])，j,j+1,j+2在[l,r]内时累加，现在有m次操作：
M x：将x位置的a[i]^=1；
Q l r：询问区间l,r的答案。
首先假设询问的只是一个区间，那么我们可以比较容易的用dp来求解w[i][s]表示到第i位的时候，后两位选的s的最小值，那么我们可以转移到w[i+1][ss]。这样就可以得到答案了。
但是现在我们支持区间询问和修改，所以我们用线段树来维护，每个节点记录w[s]，s为这个区间左面两个点c[i]的选取方法和右面两个点的选取方法，那么只要我们可以维护线段树每个节点的w[i]，我们就可以解决这个问题了。
对于合并操作比较简单，只需要枚举两个节点的s，然后更新的ss就可以了。
反思：一个节点的情况需要特殊处理，开始没注意到这个，后来改了半天，合并的时候还分了三种情况讨论= =。
还需要开LL，设inf的时候设的是#define inf (1<<60) 结果改了半天= =
评测数据的5号评测点少了一个操作，然后我的输出就多了一行= =。
//By BLADEVIL #include <cstdio> #include <cstring> #define min(x,y) (x>y)?y:x; #define inf (1ll<<60) #define maxn 30010 #define LL long long using namespace std; struct rec { int left,right; LL key; LL w[20]; rec() { left=right=0; key=inf; for (LL i=0;i<20;i++) w[i]=inf; } }t[maxn<<2]; LL n,m; LL a[maxn],b[maxn],cost1[maxn],cost2[maxn]; char s[10]; void init(int x) { t[x].w[0]=b[t[x].left]*a[t[x].left]; t[x].w[1]=b[t[x].left]*(a[t[x].left]^1); t[x].key=min(t[x].w[0],t[x].w[1]); } rec update(rec a,rec b) { rec ans; ans.left=a.left; ans.right=b.right; if ((a.left==a.right)&&(b.left==b.right)) for (LL s=0;s<4;s++) { LL ss=s|(s<<2); LL c1=((s&2)==2)?1:0,c2=((s&1)==1)?1:0; //if ((ss==3)&&(a.left==1)) printf("%d %d\n",c1,c2); if ((a.w[c1]==inf)||(b.w[c2]==inf)) continue; ans.w[ss]=min(ans.w[ss],a.w[c1]+b.w[c2]+(c1^c2)*cost1[a.right]); //if ((ss==3)&&(a.left==1)&&(a.right==1)) printf("%d\n",ans.w[ss]); ans.key=min(ans.key,ans.w[ss]); //if ((a.left==1)&&(a.right==1)) printf("%d %d\n",ans.key,ss); } else if (a.left==a.right) for (LL s1=0;s1<2;s1++) for (LL s2=0;s2<16;s2++) { if ((a.w[s1]==inf)||(b.w[s2]==inf)) continue; LL s=0; s|=s1<<3; s|=(s2&8)>>1; s|=s2&3; LL c2=((s2&8)==8)?1:0,c3=((s2&4)==4)?1:0; ans.w[s]=min(ans.w[s],a.w[s1]+b.w[s2]+(s1^c2)*cost1[a.left]+(s1^c3)*cost2[a.left]); ans.key=min(ans.key,ans.w[s]); } else if (b.left==b.right) for (LL s1=0;s1<16;s1++) for (LL s2=0;s2<2;s2++) { if ((a.w[s1]==inf)||(b.w[s2]==inf)) continue; LL s=0; s|=s2; s|=(s1&1)<<1; s|=s1&12; LL c1=((s1&2)==2)?1:0,c2=((s1&1)==1)?1:0; ans.w[s]=min(ans.w[s],a.w[s1]+b.w[s2]+(c1^s2)*cost2[a.right-1]+(c2^s2)*cost1[a.right]); ans.key=min(ans.key,ans.w[s]); } else if ((a.left!=a.right)&&(b.left!=b.right)) for (LL s1=0;s1<16;s1++) for (LL s2=0;s2<16;s2++) { if ((a.w[s1]==inf)||(b.w[s2])==inf) continue; LL s=(s1>>2)<<2; s|=s2&3; LL c1=((s1&2)==2)?1:0,c2=((s1&1)==1)?1:0; LL c3=((s2&8)==8)?1:0,c4=((s2&4)==4)?1:0; LL Ans=a.w[s1]+b.w[s2]; Ans+=cost1[a.right]*(c2^c3)+cost2[a.right]*(c2^c4)+cost2[a.right-1]*(c1^c3); ans.w[s]=min(ans.w[s],Ans); ans.key=min(ans.key,ans.w[s]); } return ans; } void build(int x,int l,int r) { t[x].left=l; t[x].right=r; if (t[x].left==t[x].right) { init(x); return ; } int mid=l+r>>1; build(x<<1,l,mid); build((x<<1)+1,mid+1,r); t[x]=update(t[x<<1],t[(x<<1)+1]); } rec query(int x,int l,int r) { if ((t[x].left==l)&&(t[x].right==r)) return t[x]; int mid=t[x].left+t[x].right>>1; if (mid>=r) return query(x<<1,l,r); else if (mid<l) return query((x<<1)+1,l,r); else return update(query(x<<1,l,mid),query((x<<1)+1,mid+1,r)); } void change(int x,int y) { if (t[x].left==t[x].right) { init(x); return ; } LL mid=t[x].left+t[x].right>>1; if (y>mid) change((x<<1)+1,y); else change(x<<1,y); t[x]=update(t[x<<1],t[(x<<1)+1]); } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); scanf("%lld%lld",&n,&m); for (LL i=1;i<=n;i++) scanf("%lld",&a[i]); for (LL i=1;i<=n;i++) scanf("%lld",&b[i]); for (LL i=1;i<n;i++) scanf("%lld",&cost1[i]); for (LL i=1;i<n-1;i++) scanf("%lld",&cost2[i]); build(1,1,n); /* for (LL s=0;s<16;s++) printf("%d %d\n",s,query(1,1,3).w[s]); return 0; */ //printf("%d\n",query(1,2,4).key); return 0; while (m--) { scanf("%s",s); LL x,y; if (s[0]==‘Q‘) { scanf("%lld%lld",&x,&y); printf("%lld\n",query(1,x,y).key); } else { scanf("%lld",&x); a[x]^=1; change(1,x); } } //for (LL s=0;s<16;s++) printf("%d %d\n",s,query(1,1,4).w[s]); fclose(stdin); fclose(stdout); return 0; }
【HMOI】小C的填数游戏 DP+线段树维护,布布扣,bubuko.com
原文：http://www.cnblogs.com/BLADEVIL/p/3632245.html