題意是給你n長度的鉤子，每單位的初始值為1，然後m個操作，將(l,r)之間的值變為v，求最後n長度的值的和。
#include #include #include #include #include #include #include #include #include #include #define LL __int64 using namespace std; const int maxn=100005; int sum[maxn*4]; //區間和 int setv[maxn*4]; //區間的值 void build(int o,int L,int R) //建樹過程 { if(L==R) { sum[o]=1; //初始都為1 return; } int M=(L+R)>>1; build(o*2,L,M); //左子樹 build(o*2+1,M+1,R); //右子樹 sum[o]=sum[o*2+1]+sum[o*2]; //當前區間的和為左右子樹的和 } void pushdown(int o,int l) { if(setv[o]>0) //若此區間已經被覆蓋 { setv[o*2]=setv[o*2+1]=setv[o]; //沿著左右子樹傳遞下去 sum[o*2]=(l-(l>>1))*setv[o]; //左子樹的和為這個區間的值乘以長度 sum[o*2+1]=(l>>1)*setv[o]; //同理求右子樹的和 setv[o]=0; //清除這個區間的標記 } } void update(int o,int v,int L,int R,int l,int r) { if(l<=L && r>=R) { setv[o]=v; //若完全覆蓋，則標記為v，代表這個區間的值 sum[o]=setv[o]*(R-L+1); //這個區間的和為區間值乘以長度 } else { pushdown(o,R-L+1); int M=(L+R)>>1; if(l<=M) update(o*2,v,L,M,l,r); //往左子樹傳遞更新 if(r>M) update(o*2+1,v,M+1,R,l,r); //往右子樹傳遞更新 sum[o]=sum[o*2]+sum[o*2+1]; } } int main() { int t,n,m,cont=1; scanf("%d",&t); while(t--) { memset(setv,0,sizeof(setv)); scanf("%d",&n); build(1,1,n); scanf("%d",&m); while(m--) { int l,r,v; scanf("%d%d%d",&l,&r,&v); update(1,v,1,n,l,r); } printf("Case %d: The total value of the hook is ",cont++); printf("%d.\n",sum[1]); } return 0; }
【poj4011】Automated Telephone E
nyoj 1176 免費餡餅（DP） 免費
學習C++與.net不同的是，一定要搞清楚Windo
初學C++ 之 auto關鍵字（IDE：VS2013），au
hdu 2604 Queuing£¨¾ØÕóÓÅ»¯µÝÍÆ
