【专题网址】点击打开链接

【A HDU 1166】

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 500005;
struct node{
    int l,r,sum;
}Tree[maxn<<2];
int a[maxn];
void Push_Up(int rt){
    Tree[rt].sum = Tree[rt<<1].sum+Tree[rt<<1|1].sum;
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r;
    if(l==r){
        Tree[rt].sum=a[l];
        return ;
    }
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    Push_Up(rt);
}
void Update(int id,int val,int l,int r,int rt){
    if(Tree[rt].l==id&&Tree[rt].r==id){
        Tree[rt].sum+=val;
        return ;
    }
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(id<=mid) Update(id,val,l,mid,rt<<1);
    else Update(id,val,mid+1,r,rt<<1|1);
    Push_Up(rt);
}
int query_ans(int L,int R,int l,int r,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].sum;
    }
    int ret=0;
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) ret+=query_ans(L,R,l,mid,rt<<1);
    if(mid<R)  ret+=query_ans(L,R,mid+1,r,rt<<1|1);
    return ret;
}
int main(){
    int tt,n,l,r,ncase=1;
    scanf("%d",&tt);
    while(tt--){
        scanf("%d",&n);
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        memset(Tree,0,sizeof(Tree));
        Build(1,n,1);
        char op[10];
        printf("Case %d:\n",ncase++);
        while(scanf("%s",op)){
            if(strcmp(op,"End")==0) break;
            scanf("%d%d",&l,&r);
            if(op[0]=='Q') printf("%d\n",query_ans(l,r,1,n,1));
            if(op[0]=='A') Update(l,r,1,n,1);
            if(op[0]=='S') Update(l,-r,1,n,1);
        }
    }
    return 0;
}

【B HDU 1754 I Hate It】 


#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 200010;
struct node{
    int l,r,maxx;
}Tree[maxn<<2];
int a[maxn];
void Push_Up(int rt){
    Tree[rt].maxx = max(Tree[rt<<1].maxx,Tree[rt<<1|1].maxx);
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r;
    if(l==r){
        Tree[rt].maxx=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    Push_Up(rt);
}
void Update(int id,int val,int l,int r,int rt){
    if(Tree[rt].l==id&&Tree[rt].r==id){
        Tree[rt].maxx=val;
        return ;
    }
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(id<=mid) Update(id,val,l,mid,rt<<1);
    else        Update(id,val,mid+1,r,rt<<1|1);
    Push_Up(rt);
}
int query_ans(int L,int R,int l,int r,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].maxx;
    }
    int ret=0;
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) ret=max(ret,query_ans(L,R,l,mid,rt<<1));
    if(mid<R)  ret=max(ret,query_ans(L,R,mid+1,r,rt<<1|1));
    return ret;
}
int main(){
    int n,m,l,r;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        Build(1,n,1);
        char op[10];
        while(m--){
            scanf("%s%d%d",op,&l,&r);
            if(op[0]=='U') Update(l,r,1,n,1);
            else           printf("%d\n",query_ans(l,r,1,n,1));
        }
    }
    return 0;
}

【C POJ 3468 A Simple Problem with Integers】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 100010;
struct node{
    int l,r;
    ll sum,lazy;
}Tree[maxn<<2];
int a[maxn];
void Push_Up(int rt){
    Tree[rt].sum = Tree[rt<<1].sum+Tree[rt<<1|1].sum;
}
void Push_Down(int rt,int m){
    if(Tree[rt].lazy!=0){
        Tree[rt<<1].lazy+=Tree[rt].lazy;
        Tree[rt<<1|1].lazy+=Tree[rt].lazy;
        Tree[rt<<1].sum+=(m-(m>>1))*Tree[rt].lazy;
        Tree[rt<<1|1].sum+=(m>>1)*Tree[rt].lazy;
        Tree[rt].lazy=0;
    }
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].lazy=0;
    if(l==r){
        Tree[rt].sum=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    Push_Up(rt);
}
void Update(int L,int R,int c,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        Tree[rt].lazy+=c;
        Tree[rt].sum+=(ll)c*(Tree[rt].r-Tree[rt].l+1);
        return ;
    }
    Push_Down(rt,Tree[rt].r-Tree[rt].l+1);
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) Update(L,R,c,rt<<1);
    if(mid<R)  Update(L,R,c,rt<<1|1);
    Push_Up(rt);
}
ll query_ans(int L,int R,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].sum;
    }
    Push_Down(rt,Tree[rt].r-Tree[rt].l+1);
    ll ret=0;
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) ret+=query_ans(L,R,rt<<1);
    if(mid<R)  ret+=query_ans(L,R,rt<<1|1);
    return ret;
}
int main(){
    int n,m,l,r,c;
    while(~scanf("%d%d",&n,&m)){
        for(int i=1; i<=n; i++) scanf("%d",&a[i]);
        Build(1,n,1);
        char op[10];
        while(m--){
            scanf("%s",op);
            if(op[0]=='Q'){
                scanf("%d%d",&l,&r);
                printf("%I64d\n",query_ans(l,r,1));
            }else{
                scanf("%d%d%d",&l,&r,&c);
                Update(l,r,c,1);
            }
        }
    }
    return 0;
}

【D POJ 2528 Mayor's posters】 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10010;
struct node{
    int l,r,lazy;
}Tree[maxn<<4];
struct seg{
    int l,r;
    seg(){}
    seg(int l,int r):l(l),r(r){}
}query[maxn];
int X[maxn<<2],ans;
bool Hash[maxn<<4];
void Push_Down(int rt){
    if(Tree[rt].lazy!=-1){
        Tree[rt<<1].lazy=Tree[rt<<1|1].lazy=Tree[rt].lazy;
        Tree[rt].lazy=-1;
    }
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].lazy=-1;
    if(l==r) return ;
    int m=(l+r)>>1;
    Build(l,m,rt<<1);
    Build(m+1,r,rt<<1|1);
}
void Update(int L,int R,int c,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        Tree[rt].lazy=c;
        return ;
    }
    Push_Down(rt);
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) Update(L,R,c,rt<<1);
    if(mid<R)  Update(L,R,c,rt<<1|1);
}
void query_ans(int l,int r,int rt){
    if(Tree[rt].lazy!=-1){
        if(!Hash[Tree[rt].lazy]) ans++;
        Hash[Tree[rt].lazy]=true;
        return ;
    }
    if(l==r) return ;
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    query_ans(l,mid,rt<<1);
    query_ans(mid+1,r,rt<<1|1);
}
int main(){
    int tt,n,l,r;
    int cnt,m;
    scanf("%d",&tt);
    while(tt--){
        cnt=0;
        scanf("%d",&n);
        for(int i=0; i<n; i++){
            scanf("%d%d",&l,&r);
            query[i]=seg(l,r);
            X[cnt++]=l,X[cnt++]=r;
        }
        //离散化之后做成线段树
        sort(X,X+cnt);
        m=1;
        for(int i=1; i<cnt; i++)  if(X[i]!=X[i-1])   X[m++]=X[i];
        for(int i=m-1; i>=1; i--) if(X[i]!=X[i-1]+1) X[m++]=X[i-1]+1;
        sort(X,X+m);
        Build(0,m,1);
        for(int i=0; i<n; i++){
            int l=lower_bound(X,X+m,query[i].l)-X;
            int r=lower_bound(X,X+m,query[i].r)-X;
            Update(l,r,i,1);
        }
        memset(Hash,false,sizeof(Hash));
        ans=0;
        query_ans(0,m,1);
        printf("%d\n",ans);
    }
    return 0;
}

【E HDU 1698 Just a Hook 】 


#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 100010;
struct node{
    int l,r;
    ll sum,lazy;
}Tree[maxn<<2];
int a[maxn];
void Push_Up(int rt){
    Tree[rt].sum = Tree[rt<<1].sum+Tree[rt<<1|1].sum;
}
void Push_Down(int rt,int m){
    if(Tree[rt].lazy!=0){
        Tree[rt<<1].lazy=Tree[rt].lazy;
        Tree[rt<<1|1].lazy=Tree[rt].lazy;
        Tree[rt<<1].sum=(m-(m>>1))*Tree[rt].lazy;
        Tree[rt<<1|1].sum=(m>>1)*Tree[rt].lazy;
        Tree[rt].lazy=0;
    }
}
void Build(int l,int r,int rt){
    Tree[rt].l=l,Tree[rt].r=r,Tree[rt].lazy=0;
    if(l==r){
        Tree[rt].sum=1;
        return ;
    }
    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    Push_Up(rt);
}
void Update(int L,int R,int c,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        Tree[rt].lazy=c;
        Tree[rt].sum=(ll)c*(Tree[rt].r-Tree[rt].l+1);
        return ;
    }
    Push_Down(rt,Tree[rt].r-Tree[rt].l+1);
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) Update(L,R,c,rt<<1);
    if(mid<R)  Update(L,R,c,rt<<1|1);
    Push_Up(rt);
}
ll query_ans(int L,int R,int rt){
    if(L<=Tree[rt].l&&Tree[rt].r<=R){
        return Tree[rt].sum;
    }
    Push_Down(rt,Tree[rt].r-Tree[rt].l+1);
    ll ret=0;
    int mid=(Tree[rt].l+Tree[rt].r)>>1;
    if(L<=mid) ret+=query_ans(L,R,rt<<1);
    if(mid<R)  ret+=query_ans(L,R,rt<<1|1);
    return ret;
}
int main(){
    int tt,n,q;
    int l,r,c,ncase=1;
    scanf("%d",&tt);
    while(tt--){
        scanf("%d",&n);
        Build(1,n,1);
        scanf("%d",&q);
        while(q--){
            scanf("%d%d%d",&l,&r,&c);
            Update(l,r,c,1);
        }
        printf("Case %d: The total value of the hook is %I64d.\n",ncase++,Tree[1].sum);
    }
    return 0;
}

【PS】这几个题都是非常简单的，因此只上了我自己的代码，如果不懂可以看其他人的博客的解题思路。专题以后的题，持续更新。。。