第五届山东省ACM

D

类型: 线段树 区间更新

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=100000*4;
typedef long long LL;
int N,Q,T;

LL lazy[maxn];
LL sum[maxn];
bool flag[maxn];

void init(){
    memset(lazy,0,sizeof(lazy));
    memset(sum,0,sizeof(sum));
    memset(flag,false,sizeof(flag));
}

void PushDown(int p,int m){
    if(flag[p]){
        lazy[p<<1]=lazy[p<<1|1]=0;
        sum[p<<1]=sum[p<<1|1]=sum[p]=0;
        flag[p<<1]=flag[p<<1|1]=true;
        flag[p]=false;
    }
    if(lazy[p]){
        lazy[p<<1]+=lazy[p];
        lazy[p<<1|1]+=lazy[p];
        sum[p<<1]+=(m-(m>>1))*lazy[p];
        sum[p<<1|1]+=(m>>1)*lazy[p];
        lazy[p]=0;
    }
}

void update(int p,int l,int r,int c,int L,int R){
    if(L<=l && r<=R){
        lazy[p]+=c;
        sum[p]+=(LL)(r-l+1)*c;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) update(p<<1,l,mid,c,L,R);
    if(R>mid) update(p<<1|1,mid+1,r,c,L,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

LL Query(int p,int l,int r,int L,int R){
    if(L<=l && r<=R)
        return sum[p];
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    LL ret=0;
    if(L<=mid) ret+=Query(p<<1,l,mid,L,R);
    if(R>mid) ret+=Query(p<<1|1,mid+1,r,L,R);
    return ret;
}

void setf(int p,int l,int r,int L,int R,int c){

    if(L<=l && r<=R){
        lazy[p]=0;
        sum[p]=0;
        flag[p]=true;
        return;
    }
    PushDown(p,r-l+1);
    int mid=(l+r)>>1;
    if(L<=mid) setf(p<<1,l,mid,L,R,c);
    if(R>mid) setf(p<<1|1,mid+1,r,L,R,c);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}

int main(){
    cin>>T;
    while(T--){
        init();
        scanf("%d%d",&N,&Q);
        int t,l,r,last=0;
        LL ans=0;
        for(int i=1;i<=Q;++i){
            scanf("%d%d%d",&t,&l,&r);
            ///先更新全部区间的值
            update(1,1,N,t-last,1,N);
            ///然后查询所需区间内的和
            ans+=Query(1,1,N,l,r);
            ///最后将所需区间内的值置为0
            setf(1,1,N,l,r,0);
            last=t;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

POJ 3468

类型: 线段树区间更新.

题目连接: POJ炸了,用virtual judge的链接
:earth_africa:POJ-3468

题意: 给你N个数,Q个操作,操作有两种,‘Q a b ’是询问a~b这段数的和,‘C a b c’是把a~b这段数都加上c。

题解: 区间问题,首先想到线段树,这里我们建两个线段树.data,datb.
data用来维护区间所更新的值.
datb则用来维护区间的和.
计算的时候只需要 每部分的区间和 + 每部分更新的值 即为最终答案.(百度说这叫Lazy思想.)

github:
:earth_africa:POJ-3468.cpp

Code:

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
///区间更新
typedef long long ll;

const int DAT_SIZE=(1<<18)-1;
const int MAX_N=100000+10;
const int MAX_Q=100000+10;

int N,Q;
int A[MAX_N];
char T[MAX_Q];
int L[MAX_Q],R[MAX_Q],X[MAX_Q];

///线段树,a维护区间应加值,b维护区间和
ll data[DAT_SIZE],datb[DAT_SIZE];

///对区间[a,b]同时加x
///k是节点编号,对应的区间是[l,r)
void add(int a,int b,int x,int k,int l,int r){
    if(a<=l&&r<=b){
        data[k]+=x;
    }else if(l<b && a<r){
        datb[k]+=(min(b,r)-max(a,l))*x;
        add(a,b,x,(k<<1)+1,l,(l+r)>>1);
        add(a,b,x,(k<<1)+2,(l+r)>>1,r);
    }
}

///计算[a,b)的和
ll sum(int a,int b,int k,int l,int r){
    if(b<=l || a>=r){
        return 0;
    }else if(a<=l && r<=b){
        return data[k]*(r-l)+datb[k];
    }else{
        ll res=(min(b,r)-max(a,l))*data[k];
        res+=sum(a,b,(k<<1)+1,l,(l+r)>>1);
        res+=sum(a,b,(k<<1)+2,(l+r)>>1,r);
        return res;
    }
}

///下标0开头的线段树初始化
///开区间[a,b)
void solve(){
    for(int i=0;i<N;++i){
        add(i,i+1,A[i],0,0,N);
//        printf("\nadd: %d -> %d\n",i,A[i]);
    }
    for(int i=0;i<Q;++i){
        if(T[i]=='C'){
            add(L[i],R[i]+1,X[i],0,0,N);
        }else{
            printf("%lld\n",sum(L[i],R[i]+1,0,0,N));
        }
    }
}

int main(){
    while(scanf("%d%d",&N,&Q)==2){
        memset(data,0,sizeof(data));
        memset(datb,0,sizeof(datb));
        for(int i=0;i<N;++i){
            scanf("%d",&A[i]);
        }
        ///区间是[0...N)所以要减一
        for(int i=0;i<Q;++i){
            scanf("%*c%c",&T[i]);
            if(T[i]=='C'){
                scanf("%d%d%d",&L[i],&R[i],&X[i]);
                L[i]-=1;R[i]-=1;
            }else{
                scanf("%d%d",&L[i],&R[i]);
                L[i]-=1;R[i]-=1;
            }
        }
        solve();
    }
    return 0;
}

POJ 2991

类型: 线段树

题目连接: :earth_asia:POJ-Crane

题意: 有一个为N节的机械手,每次可以让某个关节点旋转到某一角度,问旋转操作结束之后最末端节点的坐标。

题解: 线段树区间更新。
结点值保存该区间的向量及旋转角(注意他给出的不是旋转角)一个区间的向量值=左子区间的向量+右子区间的向量。
求一个向量(x0,y0)逆时针旋转B度后的向量有一个公式:
x1= x0 * cosB – y0 * sinB
y1 = x0 * sinB + y0 * cosB
顺时针就把-B代入:
x1= x0 * cosB + y0 * sinB
y1 = -x0 * sinB + y0 * cosB

github: :earth_africa:POJ 2991.cpp

Code:

#define _USE_MATH_DEFINES///使用math库中的定义
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<math.h>
using namespace std;

const int ST_SIZE=(1<<15)-1;
const int MAX_N=10010;
const int MAX_C=10010;

int N,C;
int L[MAX_N];
int S[MAX_C],A[MAX_N];

double vx[ST_SIZE],vy[ST_SIZE]; ///各节点的向量
double ang[ST_SIZE]; ///各节点的角度

double prv[MAX_N];

///初始化线段树
void init(int k,int l,int r){
    ang[k]=vx[k]=0.0;
    if(r-l==1){
        ///叶子结点
        vy[k]=L[l];
    }else{
        int chl=(k<<1)+1,chr=(k<<1)+2;
        init(chl,l,(l+r)>>1);
        init(chr,(l+r)>>1,r);
        vy[k]=vy[chl]+vy[chr];
    }
}

///把s和s+1的角度变为a
///v是节点编号,l,r表示当前结点对应的是[l,r]区间
void update(int s,double a,int k,int l,int r){
    if(s<=l) return;
    else if(s<r){
        int chl=(k<<1)+1,chr=(k<<1)+2;
        int m=(l+r)>>1;
        update(s,a,chl,l,m);
        update(s,a,chr,m,r);
        if(s<=m) ang[k]+=a;

        double s=sin(ang[k]),c=cos(ang[k]);
        vx[k]=vx[chl]+(c*vx[chr]-s*vy[chr]);
        vy[k]=vy[chl]+(s*vx[chr]+c*vy[chr]);
    }
}

void solve(){
    init(0,0,N);
    for(int i=0;i<C;++i){
        int s=S[i];
        double a=A[i]/360.0*2*M_PI;///把角度换算成弧度
        update(s,a-prv[s],0,0,N);
        prv[s]=a;

        printf("%.2f %.2f\n",vx[0],vy[0]);
    }
}

int main(){
    while(scanf("%d%d",&N,&C)==2){
        for(int i=0;i<N;++i){
            scanf("%d",&L[i]);
            prv[i]=M_PI;///180°的弧度值
        }
        for(int i=0;i<C;++i)
            scanf("%d%d",&S[i],&A[i]);
        solve();
    }
    return 0;
}

2017多校训练2 HDU 6047 Maximum Sequence

原题连接: :point_right:Maximum Sequence
题意: 给定一个长度为n的a数组和b数组,要求a[n+1]…a[2*n]的最大总和。 限制条件为ai≤max{aj-j│bk≤j<i}。
题解: 两种方法,一种是线段树,另一种是第一次记录maxv数组,记录每个i到maxindex(A)的最大值,然后动态更新.
github:
1.线段树法: :point_right:1003_Range_Tree.cpp
2.暴力动态更新法: :point_right:1003.cpp

///线段树法
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
const int maxnode=2000050;

int b[maxnode],N;
int maxv[maxnode];

void build(int o,int l,int r){
    if(l==r){
        if(l>N) return;///预先分配2*N个结点
        scanf("%d",&maxv[o]);maxv[o]-=l;
        return;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int query(int o,int l,int r,int ll,int rr){
    if(l>=ll&&r<=rr) return maxv[o];
    int ma=-1,mid=(l+r)>>1;
    if(mid>=ll) ma=max(ma,query(o<<1,l,mid,ll,rr));
    if(rr>mid) ma=max(ma,query(o<<1|1,mid+1,r,ll,rr));
    return ma;
}

void update(int o,int l,int r,int p,int val){
    if(l==r){
        maxv[o]=val;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(o<<1,l,mid,p,val);
    else update(o<<1|1,mid+1,r,p,val);
    maxv[o]=max(maxv[o<<1],maxv[o<<1|1]);
}

int main(){
    while(~scanf("%d",&N)&&N){
        build(1,1,2*N);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        LL ans=0;
        for(int i=N+1;i<=2*N;++i){
            int k=query(1,1,2*N,b[i-N],i-1);
            update(1,1,2*N,i,k-i);
            ans=(ans+k)%mod;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

///HDU 6047 暴力动态更新法
#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+50;
const int mod=1e9+7;
int N;
int a[maxn],b[maxn],maxa[maxn];

int main(){
    while(~scanf("%d",&N)&&N){
        for(int i=1;i<=N;++i){
            int aa;
            scanf("%d",&aa);
            a[i]=aa-i;
        }
        maxa[N]=a[N];
        for(int i=N-1;i>=1;--i) maxa[i]=max(maxa[i+1],a[i]);
        for(int i=1;i<=N;++i) scanf("%d",&b[i]);
        sort(b+1,b+1+N);
        long long ans=0;
        ans=(ans+maxa[b[1]])%mod;
        int t=maxa[b[1]]-N-1;
        for(int i=2;i<=N;++i){
            maxa[b[i]]=max(maxa[b[i]],t);
            ans=(ans+maxa[b[i]])%mod;
            t=max(t,maxa[b[i]]-N-1);
        }
        printf("%lld\n",ans%mod);
    }
    return 0;
}